IBM Ponder This #300 · April 2023

A game is played on an $n\times n$ grid of lightbulbs. We are given an initial state where some of the bulbs are off and some are on. Then, at every step:

1. A bulb in the off state is chosen.

2. The bulb is turned on, and every other bulb in the row and in the column of the bulb is toggled: If it was on, it turns off, and vice versa.

The goal of the game is to reach a grid where all the light bulbs are on. We use a coordinate system where the grid cell at column $x$ and row $y$, with $1\le x,y\le n$ is denoted by $(x,y)$ , where $(1,1)$ is the bottom-left grid cell. A solution is denoted by a list of coordinates of the corresponding bulbs.

For example, given the initial grid state

0011
1101
0110
0001

Cell $(1,3)$ is 1 while $(3,1)$ is 0, and a solution is given by:
$[(1,1),(2,4),(2,3),(4,4)]$
As can be seen by following the changes:

0011       1011       0100       0000       1111
1101 (1,1) 0101 (2,4) 0001 (2,3) 1110 (4,4) 1111
0110  -->  1110  -->  1010  -->  1110  -->  1111
0001       1110       1010       1110       1111

Your goal: Find a solution for the initial state of this $24\times 24$ grid:

000001000000000001110011
110100010110101000010011
011101110000001101001110
000110111000110101101100
101101011010010011101010
111000100101110100101000
110001011100000000000101
100000010001100000000010
000110010010110110101001
011101101011111011100000
011000101010111011111100
100011110010000100100111
000111010010100010001110
011001010001001111110101
110001000010111000100000
000000101100101000101001
111001010010010011110110
100000110001111111011010
110100000011100100110010
101000110111001110010000
110000000010011100100101
111111011011111100010101
000000000110101011100000
110001111100000011001111

A bonus "*" will be given for finding a solution with less than 430 steps for this $30\times 30$ grid:

110001000000100101110011001000
010100001100011101010111100110
000110011010011111100010100010
111101110110011101110100110001
000110001000100011001101100010
101111001110110010111101001111
001110000101101001101000001101
111001110000101011111111110100
110000000000110111111001100100
111001110100111110001110111011
111010100010010100000001101100
010111110011001111110100001001
010100111011000001100000011010
010001010110111100100111001101
111111010001011100101100110110
101000110110010111111011001001
111011000100101111101001100010
101001100011010100010000100001
111111100111111110010111110010
010000010000011001001010010011
111010110011011111101100110110
011100110001101001100000000110
111110100101010000100011011010
111100011111000011110001001111
111000111111101011111011100100
101011000011001110101011000011
001101011101000001100101101001
010010100000011011100101010001
010111101001110100010110010010
110000011010111110100110000010

Solution

Best opened after a real attempt

To be added.