8
$\begingroup$

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:

enter image description here

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – hardmath
    Dec 27, 2018 at 0:08
  • $\begingroup$ 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. $\endgroup$
    – SmileyCraft
    Dec 27, 2018 at 0:46

1 Answer 1

Reset to default
10
$\begingroup$

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}
$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – Franklin Pezzuti Dyer
    Dec 27, 2018 at 15:00
  • $\begingroup$ 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$. $\endgroup$
    – SmileyCraft
    Dec 27, 2018 at 18:33
  • $\begingroup$ 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? $\endgroup$
    – Franklin Pezzuti Dyer
    Dec 27, 2018 at 21:49
  • $\begingroup$ 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. $\endgroup$
    – SmileyCraft
    Dec 28, 2018 at 16:05
  • $\begingroup$ Okay the pattern does not even hold up to $24$ :P $\endgroup$
    – SmileyCraft
    Dec 28, 2018 at 16:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .