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?
Best Answer
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.