Ponder This - April 2023

[tgan]

https://research.ibm.com/haifa/ponde...April2023.html

[henryzz]

Unless I am being clueless the basic puzzle is solvable easily in excel.
Edit: maybe not

[EdH]

I think a visual aid for a manual version would be easy to code in Excel, but it's been a lot of years since I did any Visual Basic programming.

My initial thought was to skip this one, but now I'm wondering what a brute force effort would look like.

[EdH]

Darn! My 5000 line C program burned out all the bulbs. Back to the programming board. . .

[Max0526]

If anybody wants to try solving 24x24 manually, the QB64 (https://qb64.com/) code and Windows executables for manual solving and replaying (checking) are attached. Consider downgrading the screen resolution to 800x600.
My first try produced a solution in 576 steps (will be saved in save.txt). It definitely could be less steps.
Now I wonder whether it is possible to build a quick optimizer to shorten a saved solution. If so, I could click-solve the 30x30 and then shorten it to less than 430 steps, if possible.

[Max0526]

24x24 is solvable in 280 steps and 30x30 in 429 steps.
The longest run for a Windows executable written in QB64 (~250 lines of code) took ~40 seconds to find 429 steps.

[EdH]

I've tried a random approach in C and so far the most bulbs I have had lit are 371 after several days of running.

[Max0526]

Originally Posted by EdH

I've tried a random approach in C and so far the most bulbs I have had lit are 371 after several days of running.

The idea here is too basic -- parity. Although to develop it, it took me a couple of days playing 8x8 on a randomly set board.
Each bulb is put on the intersection of a row and a column. Count parity for each row and each column (how many bulbs are on/1 in each row and each column). Then each bulb can be assigned one of the three priority levels:
1) both row and column have odd parity;
2) both row and column have even parity;
3) one has odd and one has even parity.
Your goal is to turn all bulbs on making everything even parity.
a) Which level (1, 2, or 3) do you think has the highest priority and dictates one of the next moves?
b) Which level goes next?
c) Which one has the lowest priority?
Make a random move in the highest priority level. The whole board will immediately change. Recalculate the priority levels for each bulb. Repeat.
Assigning the correct order for a), b), c) guarantees solving any board, but not necessarily in the least number of steps.
Good luck!