shatters-puzzle
How to Use
To use this solver, click on a tower to turn that tower green. Match the current layout with what you see in-game and then click Solve. The towers that you must shoot in-game will be the towers with full opacity. To reset the puzzle, click the Reset button.You can simulate the puzzle by clicking on the Simulate button. This will allow adjacent towers to be flipped just like the real puzzle. To go back to manually toggling a tower, you can click on Stop Simulation. To randomly generate a new puzzle, you can click the New Puzzle button.
Lights Out Puzzle
Within Realm of the Mad God and its dungeon The Shatters, there is a room that may spawn known as The Puzzle Room, which takes a similar form of the Lights Out puzzle. Within this room, there are nine towers and the goal is to make every tower green in order to continue. The rule of this puzzle is that by shooting a tower to flip its state, all horizontal and vertical adjacent towers have their states flipped as well.
When expressing the puzzle mathematically, each state of the tower can be represented in modulo 2. So, if a tower is green (which can be stated as on) then its value is 1. If the tower is red (which can be stated as off), its value is 0. Furthermore, each tower will be given its own index. The first row, from left to right, contains indices 0, 1, and 2. The second row contains indices 3, 4 and 5. Finally, the last row contains indices 6, 7, and 8.
The Lights Out Puzzle can be written as the matrix below, where each column contains the impact on every other tower when shooting that specific tower (from 0 to 8):
$$\begin{bmatrix}
1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0\\
0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0\\
1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0\\
0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0\\
0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1\\
0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0\\
0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1\\
\end{bmatrix}
\begin{bmatrix}
x_0\\
x_1\\
x_2\\
x_3\\
x_4\\
x_5\\
x_6\\
x_7\\
x_8\\
\end{bmatrix}
=
\begin{bmatrix}
b_0\\
b_1\\
b_2\\
b_3\\
b_4\\
b_5\\
b_6\\
b_7\\
b_8\\
\end{bmatrix}$$
The vertical matrix x represents the solution to the puzzle. In addition, the matrix b represents the current structure of the puzzle. We can then create the augmented matrix using the formula: \(A^{-1}b=x\)
$$\begin{bmatrix}
1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & b_0\\
1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & b_1\\
0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & b_2\\
1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & b_3\\
0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & b_4\\
0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & b_5\\
0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & b_6\\
0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & b_7\\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & b_8\\
\end{bmatrix}
=
\begin{bmatrix}
x_0\\
x_1\\
x_2\\
x_3\\
x_4\\
x_5\\
x_6\\
x_7\\
x_8\\
\end{bmatrix}$$
Then, we can perform a series of row reductions to get this resulting matrix:
\begin{bmatrix}
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & b_4+b_6+b_7+b_8\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & b_0+b_1+b_2+b_4\\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & b_0+b_2+b_3+b_7+b_8\\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & b_0+b_2+b_5+b_6+b_7\\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & b_0+b_3+b_4+b_6\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & b_0+b_1+b_5+b_6+b_8\\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & b_2+b_4+b_5+b_8\\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & b_1+b_3+b_4+b_5+b_7\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & b_1+b_2+b_3+b_6+b_8\\
\end{bmatrix}
As a result, we can write the following solution matrix:
$$\begin{bmatrix}
x_0\\
x_1\\
x_2\\
x_3\\
x_4\\
x_5\\
x_6\\
x_7\\
x_8\\
\end{bmatrix}
=
\begin{bmatrix}
b_0+b_2+b_5+b_6+b_7\\
b_4+b_6+b_7+b_8\\
b_0+b_2+b_3+b_7+b_8\\
b_2+b_4+b_5+b_8\\
b_1+b_3+b_4+b_5+b_7\\
b_0+b_3+b_4+b_6\\
b_0+b_1+b_5+b_6+b_8\\
b_0+b_1+b_2+b_4\\
b_1+b_2+b_3+b_6+b_8\\
\end{bmatrix}
$$
We can make use of these expressions by solving for each x. The value of each b is the value of the current puzzle arrangement at that specified index (so \(b_0\) is the bit value of the tower at index 0). To solve for each index of x, we must first XOR the value at each index of b with 1. This is due to the fact that we want all towers to be on rather than turning all towers off, which is the opposite of Lights Out. Then, we solve the expression using XOR for binary addition to get the final value for x at that index. If the result of that operation is equal to 1, then you must shoot that tower. If the result is 0, then the tower can be left how it is.
This solver's foundation, including the matrices shown on this page, come from a video created by mathapptician on YouTube. The video is embedded below, please do check out their channel. Furthermore, credit for the tower sprites used in this solver goes to DECA Games.
"Week 4 - Solving 3 x3 Lights Out completely" by mathapptician.