# An algorithm for solving this puzzle

The puzzle goes like this:

There is a $n\times n$ - board with each cell containing a whole number. Let's call this the matrix $A$ and denote its elements by $a_{ij} \in \mathbb Z$. The cells can be clicked. When a cell is clicked its value is incresed by $4$ and its neighbour's values decreased by $1$. By neigbours we mean the four cells that are next to it (if cell is on the boundary, we go around as in torus).

We start from the configuration that all the cells are zero. After clicking any cell we can bring the board back to $A=0$ by clicking all the other cells once (every cell gets +4-1-1-1-1 = 0). So every configuration that is achieved by clicking the board can be brought back to the initial $A=0$ by clicking the board.

Hence this forms a group where the elements are the configurations of the board that are achieved by clicking and product of two configurations $A_1$ and $A_2$ is doing the clickings that are needed to make $A_1$ and then the clickings for $A_2$ (there are many possibilities for the clickings, but it doesn't matter which ones we pick) and the identity element is $A=0$. The product is also commutative since we only increase or decrease the value of a cell and it doesn't matter in which order we do them.

The puzzle is to bring the board to $A=0$ by clicking.

My question is: Is there an algorithm for solving for a random (achievable) configuration what clickings must be done?

• This group of the configurations, is it actually $\{a\in \mathbb{Z}^{n^2} : a_1 + a_2 + \dots a_{n^2} = 0\}$? I think this is equivalent to the claim that the 'effect-matrix' $S$ has rank $n^2-1$. – ploosu2 Feb 28 '14 at 20:26
• This is a generalization of the classic puzzle known as Lights Out (which is generally played over $\mathbb{Z}/2\mathbb{Z}$), and that's been extensively studied; you can find a good deal more information under that name online. – Steven Stadnicki Feb 28 '14 at 20:39

I figured out a solution while I wrote the question but I decided to post this anyhow since it's a nice puzzle (in my opinion). If you have other solutions, I'd really like to hear them. BTW, don't know if this puzzle has already 'been invented' or not, couldn't find anything by googling... :D

For a configuration $b = (b_{\alpha})_{\alpha = 1}^{n^2}$ we denote by $x_{\alpha}$ the number of times the $\alpha$th cell (counting by moving one row at a time) was clicked to get to that configuration. Now the puzzle can be solved with a linear equation

$$Sx = b,$$

where $S$ is a matrix encoding the information how the clickings affect the values of the cells. For example for a $3\times 3$ case

$$S= \left( \begin{array}{ccc} 4 & -1 & -1 & -1 & 0 & 0 & -1 & 0 & 0\\ -1 & 4 & -1 & 0 & -1 & 0 & 0 & -1 & 0\\ -1 & -1 & 4 & 0 & 0 & -1 & 0 & 0 & -1\\ -1 & 0 & 0 & 4 & -1 & -1 & -1 & 0 & 0\\ 0 & -1 & 0 & -1 & 4 & -1 & 0 & -1 & 0\\ 0 & 0 & -1 & -1 & -1 & 4 & 0 & 0 & -1\\ -1 & 0 & 0 & -1 & 0 & 0 & 4 & -1 & -1\\ 0 & -1 & 0 & 0 & -1 & 0 & -1 & 4 & -1\\ 0 & 0 & -1 & 0 & 0 & -1 & -1 & -1 & 4\\ \end{array} \right)$$

The rank of this matrix is $8$ so every configuration where the cells sum to zero is achievable (the image is $8$-dimenional and is contained in the 8-dimensional subspace where elements sum to zero). The problem with just solving this linear equation is that the solution vector might not be all natural numbers. But we can multiply it by a suitable natral number to make it all whole numbers and add big enought $(k,k,\dots ,k,k)$ to make all non-negative. This gives the clickings that were made to have this configuration. Now all we have to do is click the cells enough many times to make every entry in $x$ the same as the biggest one in it.

• This is the standard solution technique for such puzzles. – hmakholm left over Monica Feb 28 '14 at 19:23
• Other than manually checking, how do you tell that it has rank 8? For an even by even, it has rank at most $n^2 - 2$, where you can split the cells according to their parity. – Calvin Lin Feb 28 '14 at 19:38
• I checked manually, or with: bluebit.gr/matrix-calculator – ploosu2 Feb 28 '14 at 19:54

Since the moves are commutative and since the only way to increment a cell is to click on it, clicking on any negative value at each time will solve the puzzle if there is a solution. More: it will solve it with the lowest number of moves.

It explains why the pyzzle is not very popular on google.

I guess the greedy algorithm works also here. How come I didn't think that right away... :D

Just start clicking the cells that have the lowest (most negative, that is) value. Is there some sort of clear way to see that this always works?