kern f

quinto

Goal of this puzzle is to turn the color of every cell of a 5 x 5 matrix from the initial green into blue. The cells are buttons, if you press a button you toggle the color of the cell and of it's neighbors (every cell has 4 neighbors, i.e. the cells that share an edge with the cell). Initially all the cells are colored green. Solving the puzzle means finding a sequence of pressing buttons such that the resulting matrix has all cells colored blue.






A number of approaches in solving the problem are given in this webpage [1].

I want to make an observation here that cuts down the number of searches by being more targeted than the brute-force search (even the one exploiting locality as described in the last section of [1]).

Consider a solution n x n matrix that has ones where the corresponding cell button got pressed and zeros where it didn't get pressed. There are n row-vectors v_1, v_2, ..., v_n in this solution matrix. Let M_i be the resulting matrix after pushing the buttons from row-vectors v_1,..,v_i.

Lemma: A necessary condition for a solution is that v_i has ones exactly in the positions in which M_(i-1) has zeros.

Proof: If v_i doesn't have a one in position k where M_(i-1)((i - 1, k)) = 0 then the final result M will also have M((i - 1, k)) = 0 because none of the row-vectors j with j > i influence the cell value ((i - 1, k)) anymore. But that is a contradiction with our assumption that the row-vectors are a solution. One argues similarly for M_(i-1)((i - 1, k)) = 1 that v_i((k)) = 0. This proves the lemma.

Using this lemma we see that the first row-vector of a solution determines the whole solution. We don't have to search the whole space anymore, only try all the possible values for the first row-vector. We cut the solution space from 2^(n x n) to 2^n.

There might be other necessary properties that would shrink the solution space even more. One conjecture is that for odd n one of the diagonals of the solution matrix is made of ones and the solution matrix is symmetric with that diagonal as symmetry axis. Maybe I'll get back to this some time.

Posted by Uwe Hoffmann at September 1, 2003 06:04 PM