# Puzzle group of $4\times 4$ “flip” game

I have been goofing around with the game "flip," which can be played at the following link. The puzzle consists of an $$n\times n$$ grid of squares that are either black or white, and when one clicks on one of the squares, its color and the colors of each of its four neighbors are toggled.

It is easy to show that any board configuration is solvable for the $$2\times 2$$ and $$3\times 3$$ versions of the puzzle. Thus, since game moves commute, the groups corresponding to these puzzles are $$\mathbb Z_2^4$$ and $$\mathbb Z_2^9$$ respectively.

However, I have discovered that the $$4\times 4$$ game is not so simple; there exist some board configurations that are not solvable. This can be demonstrated as follows.

Suppose we color the board like this:

One may easily verify that any move toggles an even number of the red-colored squares; thus, in any solvable puzzles, the number of black squares in the red region is even. This narrows down the group of solvable puzzles to $$\mathbb Z_2^{15}$$; however, since reflections/rotations of this coloring produce further restrictions, the group must be even smaller than this. In fact, using this strategy, I have narrowed it down to a subgroup of $$\mathbb Z_2^{14}$$, and I suspect it can be narrowed down even further to $$\mathbb Z_2^{13}$$.

My question is: what is the puzzle group of the $$4\times 4$$ puzzle? I know this problem can be reduced to finding the rank of a $$16\times 16$$ matrix, but... surely there's a better way.

• Perhaps a definition of "puzzle group" is in order, if we are to justify an answer here. It seems connected with the possible "states" of a game of size $n\times n$. You may be thinking that the "moves" form a group that acts on the states. It is then of interest to determine any "unsolvable" states by working out the orbits of the states under the group action. – hardmath Dec 27 '18 at 0:08
• This game is called "Lights out". I will write a program to find out the groups of $n\times m$ lightsout for some values for you, give me a minute. – SmileyCraft Dec 27 '18 at 0:46

As I mentioned in the comment, this game is called Lights Out. The moves form a finite abelian boolean group ($$g^2=0$$ for all $$g$$), which means it will always be isomorphic to $$\mathbb{Z}_2^k$$ for some $$k$$. Also notice that any solution can be encoded as a set of cells that you have to click.

Without ever clicking the top row, you can always click the squares until only the bottom row has lit up squares. Simply go from top to bottom and keep clicking below lit up squares. It is also easy to see that there is a unique way to achieve this. Let us call this "fixing the board".

To speedrun this game, as I used to do some times, fixing the board was step one. For step two, you must memorize for every cell in the top row which cells in the bottom row will flip when you click the top cell and then fix the board. Let us call these the bottom vectors. You should then quickly recognize what linear combination of bottom vectors equals the current bottom row. Then click all corresponding cells in the top row and once again fix the board.

Notice that, in $$1\times1$$, $$2\times2$$ and $$3\times3$$ Lights Out, the bottom vectors are linearly independent. This exactly means that every possible board can be solved. The $$4\times4$$ Lights Out is also quite special, since every bottom vector is all $$0$$. This means that for every solvable Lights Out, there are $$2^4$$ ways of solving it. This is because we can click any cells in the top row and then fix the board. Hence $$4\times4$$ Lights Out is isomorphic to $$\mathbb{Z}_2^{12}$$.

In general, for $$n\times m$$ Lights Out ($$n$$ wide $$m$$ high), we can consider the span of all bottom vectors (these are of length $$n$$). Let $$c$$ denote the codimension of this span inside $$\mathbb{Z}_2^n$$. Then $$n\times m$$ Lights Out is isomorphic to $$\mathbb{Z}_2^{n\times m-c}$$. Also, any solvable Lights Out board has $$2^c$$ solutions.

Here is a table of some codimensions: $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \times&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\\\hline 1&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\\\hline 2&&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0\\\hline 3&&&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2\\\hline 4&&&&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0\\\hline 5&&&&&2&0&4&1&1&0&4&0&1&1&4&0&2&0&3&1\\\hline 6&&&&&&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0\\\hline 7&&&&&&&0&2&0&0&7&0&0&2&0&0&4&0&0&2\\\hline 8&&&&&&&&0&1&0&2&0&7&0&2&0&1&0&2&6\\\hline 9&&&&&&&&&8&0&1&0&0&5&0&0&1&0&8&1\\\hline 10&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0\\\hline 11&&&&&&&&&&&6&0&1&2&8&0&4&0&3&2\\\hline 12&&&&&&&&&&&&0&0&0&0&0&0&0&0&0\\\hline 13&&&&&&&&&&&&&0&1&0&0&13&0&0&1\\\hline 14&&&&&&&&&&&&&&4&2&8&1&0&6&0\\\hline 15&&&&&&&&&&&&&&&0&0&4&0&0&2\\\hline 16&&&&&&&&&&&&&&&&8&0&0&0&0\\\hline 17&&&&&&&&&&&&&&&&&2&0&3&7\\\hline 18&&&&&&&&&&&&&&&&&&0&0&0\\\hline 19&&&&&&&&&&&&&&&&&&&16&2\\\hline 20&&&&&&&&&&&&&&&&&&&&0\\\hline \end{array}$$ Here is a much bigger table, which you will have to compile yourself, since it does not fit on the page:

$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \times&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20&21&22&23&24&25&26&27&28&29&30&31&32&33&34&35&36&37&38&39&40&41&42&43&44&45&46&47&48&49&50&51&52&53&54&55&56&57&58&59&60&61&62\\\hline 1&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\\\hline 2&&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0\\\hline 3&&&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&0&2\\\hline 4&&&&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0\\\hline 5&&&&&2&0&4&1&1&0&4&0&1&1&4&0&2&0&3&1&1&0&5&0&1&1&3&0&2&0&4&1&1&0&4&0&1&1&4&0&2&0&3&1&1&0&5&0&1&1&3&0&2&0&4&1&1&0&4&0&1&1\\\hline 6&&&&&&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6\\\hline 7&&&&&&&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2&0&0&4&0&0&2&0&0&7&0&0&2\\\hline 8&&&&&&&&0&1&0&2&0&7&0&2&0&1&0&2&6&1&0&2&0&1&0&8&0&1&0&2&0&1&6&2&0&1&0&2&0&7&0&2&0&1&0&2&6&1&0&2&0&1&0&8&0&1&0&2&0&1&6\\\hline 9&&&&&&&&&8&0&1&0&0&5&0&0&1&0&8&1&0&0&1&4&0&1&0&0&9&0&0&1&0&4&1&0&0&1&8&0&1&0&0&5&0&0&1&0&8&1&0&0&1&4&0&1&0&0&9&0&0&1\\\hline 10&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&10&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&10&0\\\hline 11&&&&&&&&&&&6&0&1&2&8&0&4&0&3&2&1&0&10&0&1&2&3&0&4&0&8&2&1&0&6&0&1&2&7&0&4&0&3&2&1&0&11&0&1&2&3&0&4&0&7&2&1&0&6&0&1&2\\\hline 12&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&12\\\hline 13&&&&&&&&&&&&&0&1&0&0&13&0&0&1&0&0&1&0&0&7&0&0&1&0&0&1&0&0&13&0&0&1&0&0&1&0&0&7&0&0&1&0&0&1&0&0&13&0&0&1&0&0&1&0&0&7\\\hline 14&&&&&&&&&&&&&&4&2&8&1&0&6&0&1&0&2&4&1&0&2&0&5&0&2&0&9&4&2&0&1&0&6&0&1&0&2&4&1&0&2&0&5&8&2&0&1&4&2&0&1&0&6&0&1&0\\\hline 15&&&&&&&&&&&&&&&0&0&4&0&0&2&0&0&15&0&0&2&0&0&4&0&0&2&0&0&8&0&0&2&0&0&4&0&0&2&0&0&15&0&0&2&0&0&4&0&0&2&0&0&8&0&0&2\\\hline 16&&&&&&&&&&&&&&&&8&0&0&0&0&0&0&0&0&0&0&0&0&8&0&0&0&8&0&0&0&0&0&0&0&0&0&0&8&0&0&0&0&0&8&0&0&0&0&0&0&0&0&8&0&0&0\\\hline 17&&&&&&&&&&&&&&&&&2&0&3&7&1&0&5&0&1&1&15&0&2&0&4&1&1&6&4&0&1&1&4&0&14&0&3&1&1&0&5&6&1&1&3&0&2&0&16&1&1&0&4&0&1&7\\\hline 18&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\hline 19&&&&&&&&&&&&&&&&&&&16&2&0&0&3&4&0&2&0&0&11&0&0&2&0&4&3&0&0&2&16&0&3&0&0&6&0&0&3&0&8&2&0&0&3&4&0&2&0&0&19&0&0&2\\\hline 20&&&&&&&&&&&&&&&&&&&&0&1&0&2&0&1&6&2&0&1&0&2&0&1&0&8&0&1&0&2&0&1&0&2&6&1&0&2&0&1&0&2&0&7&0&2&0&1&0&2&0&1&6\\\hline 21&&&&&&&&&&&&&&&&&&&&&0&0&1&0&0&1&0&0&1&10&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&20&1\\\hline 22&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\hline 23&&&&&&&&&&&&&&&&&&&&&&&14&0&1&2&3&0&5&0&16&2&1&0&10&0&1&2&7&0&5&0&3&2&1&0&22&0&1&2&3&0&5&0&7&2&1&0&10&0&1&2\\\hline 24&&&&&&&&&&&&&&&&&&&&&&&&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0&0&4&0&0&0\\\hline 25&&&&&&&&&&&&&&&&&&&&&&&&&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&13\\\hline 26&&&&&&&&&&&&&&&&&&&&&&&&&&0&8&0&1&0&2&0&1&6&2&0&1&0&2&0&7&0&2&0&1&0&2&6&1&0&2&0&1&0&8&0&1&0&2&0&1&6\\\hline 27&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&3&0&0&2&0&0&27&0&0&2&0&0&3&0&0&8&0&0&3&0&0&2&0&0&15&0&0&2&0&0&3&0&0&8\\\hline 28&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\hline 29&&&&&&&&&&&&&&&&&&&&&&&&&&&&&10&0&4&1&17&4&4&0&1&1&12&0&2&0&3&5&1&0&5&0&9&9&3&0&2&4&4&1&1&0&12&0&1&1\\\hline 30&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&20&0&10&0&0&0&0&0&0&0&0&0&0&10&0&0&0&0&0&0&0&0&0&0&10&0&0&0&0&0&0&20&0\\\hline 31&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&0&8&0&0&2&0&0&4&0&0&2&0&0&31&0&0&2&0&0&4&0&0&2&0&0&8&0&0&2\\\hline 32&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&20&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&11&0\\\hline 33&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&16&0&1&0&0&1&0&0&1&0&0&9&0&0&1&0&0&9&0&0&1&0&0&1&0&0&17&0&0&1\\\hline 34&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4&6&0&0&0&4&0&0&0&0&10&0&0&0&0&4&0&0&0&6&4&0&0&0&0&4&0&0&6\\\hline 35&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&6&0&1&2&7&0&16&0&3&2&1&0&11&6&1&2&3&0&4&0&31&2&1&0&6&0&1&8\\\hline 36&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\hline 37&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\\\hline 38&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&0&2&0&1&12\\\hline 39&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&32&0&4&0&0&6&0&0&7&0&8&2&0&0&4&4&0&2&0&0&23&0&0&2\\\hline 40&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\hline 41&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&2&0&3&7&1&0&5&0&1&1&3&0&14&0&4&1&1&0&4&0&1&7\\\hline 42&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\hline 43&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&0&3&0&0&2&0&0&3&0&0&2&0&0&3&0&20&2\\\hline 44&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4&1&0&2&6&5&8&2&0&1&4&8&0&1&0&6&0&1&6\\\hline 45&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\\\hline 46&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\hline 47&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&30&0&1&2&3&0&5&0&7&2&1&0&11&0&1&2\\\hline 48&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&6&0&0&0&0&0&0&0&0&6\\\hline 49&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&8&1&0&0&1&4&0&1&0&0&9&0&0&1\\\hline 50&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&8&2&0&1&0&2&0&1&0&10&0&1&0\\\hline 51&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&3&0&0&2&0&0&3&0&0&14\\\hline 52&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0&0&0&0&0&0&0\\\hline 53&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&2&0&16&1&1&0&4&0&1&7\\\hline 54&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4&0&0&0&0&4&0&10&0\\\hline 55&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&2&0&0&7&0&0&8\\\hline 56&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&1&0&2&0&1&0\\\hline 57&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&1&0&0&1\\\hline 58&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0&0&0\\\hline 59&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&22&0&1&2\\\hline 60&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0&0&0\\\hline 61&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&40&1\\\hline 62&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&24\\\hline \end{array}$$

• Amazing, thank you so much! I wonder if there are any notable patterns in this table. Most numbers seem to be zero... I wonder if we can find a nice sequence of integers (not necessarily exhaustive) that guarantee the $n\times n$ game to have deficiency zero. Perhaps this is always true if $n$ is a triangular number? – Frpzzd Dec 27 '18 at 15:00
• One interesting pattern is that every row is repetative. I think you can show that the period of row $n$ is at most $4^{n^2}$. Also interesting is that every column corresponding to a multiple of $6$ (and column $10$ for some reason) appears to be all $0$. – SmileyCraft Dec 27 '18 at 18:33
• Any idea about why this is true for rows that are multiples of $6$? Have you verified this for higher multiples of $6$ like $24,30,36,$ etc, or just the multiples of $6$ in the table? – Frpzzd Dec 27 '18 at 21:49
• I have no idea why this happens, no. In order to verify for higher multiples of $6$, I'll have to get a faster algorithm, the one I currently have is exponential in width. With Gaussian elimination I should be able to make it polynomial, though. – SmileyCraft Dec 28 '18 at 16:05
• Okay the pattern does not even hold up to $24$ :P – SmileyCraft Dec 28 '18 at 16:08