I solved this puzzle properly, by hand! It only took like four hours.
You know there's a simple algorithm for this puzzle: you just have to construct and solve a 54x54 linear system in β€β! Each cell influences some subset of the other cells (and sets them to 1), so you make a column out of each cell to form a matrix π, as well as a vector for the solution π, and then solve ππ± + π = 0 in β€β.
More in-depth details below the cut, I'll explain all of that at least briefly for folks who don't know what those terms mean. And you won't see the solution unless you want to, if you want to try this method for yourself.
The first part: we want to model toggling things on and off so we can handle the lights here. Luckily, mathematicians have our back, the set of numbers β€β represents that well. In it, there are only two numbers, 0 and 1, and addition works the same as usual except that 1 + 1 = 0 β so adding 1 to a number toggles it on and off. Multiplying is completely normal.
Next, we need a bunch of equations to figure out whether each square is toggled. We give each square a name so we can write about their relations: Let's say:
- square π₯β is toggled by squares π₯β, π₯β, π₯β , and π₯β
- it's initially on in the puzzle
- we want to turn it off (because it's "Lights Out")
We can write that equation as: π₯β + π₯β + π₯β + π₯β + 1 = 0. Conveniently, we can add 1 to both sides of this equation, and get π₯β + π₯β + π₯β + π₯β = 1, which is slightly nicer to work with later. We can make one equation like this for each cell in the grid, and then solve them all simultaneously.
Let's find an actual one of these equations, looking at the very first cell:
100000
010000
000000
000000
000000
000000
000000
000000
000000
We can unwrap this into a straight line that represents all of the cells it impacts:
100000010000000000000000000000000000000000000000000000
This isn't quite what we want for making our equations, instead of telling us what cells impact the first cell, this tells us which cells the first cell impacts. However, we can find this information pretty easily!
If we do this process for each cell on the board, we get 54 (6x9) of these 54-entry vectors. If we use these as columns of a matrix, we end up with columns that represent all of the cells that a given cell impacts, and the rows representing all of the cells that impacts that cell. We do the same unwrapping for the initial state of the board, and set that column next to our matrix, to give us an "augmented matrix" for solving the system.
If we look at the first row of our matrix, we've got:
110000100000000000000000000000000000000000000000000000|1
Just to make it clear on last time, this tells us all the cells that toggle the first cell π₯β. Turning this back into an equation, we get: π₯β + π₯β + π₯β = 1.
But we're going to want to work directly with the matrix, since it's much easier to solve as a matrix than as a bunch of separate equations.
The full linear system for this puzzle
110000100000000000000000000000000000000000000000000000|1
011000011000000000000000000000000000000000000000000000|1
011000000100000000000000000000000000000000000000000000|1
000100000100000000000000000000000000000000000000000000|0
000010000010000000000000000000000000000000000000000000|0
000011000000000000000000000000000000000000000000000000|1
010000100000000000000000000000000000000000000000000000|1
100000110000110000000000000000000000000000000000000000|1
001000011000000100000000000000000000000000000000000000|1
000110000110001010000000000000000000000000000000000000|0
000111000010000110000000000000000000000000000000000000|0
000001000001000000000000000000000000000000000000000000|1
000000000000100000110000000000000000000000000000000000|0
000000001000111000011000000000000000000000000000000000|1
000000011000011000001100000000000000000000000000000000|1
000000000110000100001110000000000000000000000000000000|0
000000000110000111000110000000000000000000000000000000|1
000000000000000011000011000000000000000000000000000000|1
000000000000010000110000100000000000000000000000000000|0
000000000000111000010000101000000000000000000000000000|0
000000000000010000011100010100000000000000000000000000|0
000000000000000100001100001110000000000000000000000000|0
000000000000000101000111000011000000000000000000000000|0
000000000000000001000011000011000000000000000000000000|1
000000000000000000000000110000100000000000000000000000|0
000000000000000000110000110000001000000000000000000000|0
000000000000000000010000001100011100000000000000000000|0
000000000000000000001100000110001110000000000000000000|0
000000000000000000000001000011000001000000000000000000|0
000000000000000000000010000001000011000000000000000000|0
000000000000000000000000100000100000110000000000000000|1
000000000000000000000000110000110000110000000000000000|1
000000000000000000000000000100011100010000000000000000|1
000000000000000000000000001000000100000100000000000000|0
000000000000000000000000000010000011000011000000000000|1
000000000000000000000000000000000011000011000000000000|1
000000000000000000000000000000010000100000000000000000|0
000000000000000000000000000000001000011000011000000000|0
000000000000000000000000000000000100011000011100000000|1
000000000000000000000000000000001100000100001100000000|1
000000000000000000000000000000000110000010000011000000|1
000000000000000000000000000000000001000001000001000000|1
000000000000000000000000000000000000010000100000010000|0
000000000000000000000000000000000000101000010000001000|0
000000000000000000000000000000000000011000001000011100|1
000000000000000000000000000000000000001110000100001100|0
000000000000000000000000000000000000000010000011000010|1
000000000000000000000000000000000000000011000001000010|1
000000000000000000000000000000000000000000010000100000|0
000000000000000000000000000000000000000000011000011000|0
000000000000000000000000000000000000000000000000001000|0
000000000000000000000000000000000000000000000100001100|0
000000000000000000000000000000000000000000000010000111|0
000000000000000000000000000000000000000000000011000001|1
This big matrix represents the vector equation πβπ₯β + πβπ₯β + β¦ + πβ βπ₯β β = π, which you can think of as either a bunch of equations, one for each cell, or one equation acting on the whole board. It says "π₯β decides if you toggle cells πβ, π₯β decides if you toggle the cells πβ, and so on, and after all the toggling, we want to toggle exactly the cells in the initial board π."
You can solve this with Gaussian elimination, which is luckily much easier in β€β since you only have to toggle between 0 and 1 instead of doing full addition.
- First, try to get it into row-echelon form, which means you need to try to make the lower left triangle of the matrix all zeroes. (If you manage it, it will automatically be in reduced form since there are no numbers besides 0 and 1).
- In broad terms, you want to add the rows with a leading number along the diagonal to any rows below them that have a 1 in that column, and slowly get rid of all of the 1s in the lower triangle.
- You need to swap some rows to make sure you keep having entries along the diagonal.
- You can find more detailed explanations of this elsewhere. (This is hopefully a little reminder for people who might have learned this in school and half-remember it?)
I did this mostly by hand, but I kept making little typos so I wrote a program that would execute the row operations for me. I still made all the decisions, but it prevented me from making any typosβif this were smaller (maybe a standard 5x5 board β 25x25 matrix) I would've stuck to fully doing it by hand, for fun.
The row operations helper script I used
linear_system.pyMATRIX_INPUT = """ (put your linear system in this string) """.strip().splitlines() def apply(a: str, b: str) -> str: """ Does xor on two augmented lines >>> apply("11010|0", "10110|1") '01100|1' """ return "".join( "|" if x == "|" else str(int(x) ^ int(y)) for x, y in zip(a, b) ) def show(lines: list[str]) -> None: pad = len(str(len(lines))) for i, line in enumerate(lines): print(f"{i:>{pad}} {line}") def show_help() -> None: print("help - show this output") print("add a b [b ...] - add row a to all rows indexed b") print("move a b - move row a before row b") def main(matrix_input) -> None: matrix = [line for line in matrix_input] first_time = True while True: show(matrix) if first_time: show_help() first_time = False try: cmd = input("> ") except KeyboardInterrupt: break try: cmd, *args = cmd.split() if cmd == "help": show_help() elif cmd == "add": a = int(args[0]) # Use a list comprehension to force it to fail early bs = [int(b) for b in args[1:]] for b in bs: matrix[b] = apply(matrix[a], matrix[b]) elif cmd == "move": a, b = args a, b = int(a), int(b) row = matrix.pop(a) matrix.insert(b, row) except: print("Error in command") if __name__ == "__main__": main(MATRIX_INPUT)
In this case, I had to arbitrarily assign two of the variables, because this puzzles seems slightly under-constrained (I believe this means there are 4βvery similarβvalid solutions). Once you get a fully solved matrix out:
The fully solved matrix
100000000000000000000000000000000000000000000000000000|0
010000000000000000000000000000000000000000000000000000|0
001000000000000000000000000000000000000000000000000000|0
000100000000000000000000000000000000000000000000000000|1
000010000000000000000000000000000000000000000000000000|0
000001000000000000000000000000000000000000000000000000|1
000000100000000000000000000000000000000000000000000000|1
000000010000000000000000000000000000000000000000000000|1
000000001000000000000000000000000000000000000000000000|0
000000000100000000000000000000000000000000000000000000|1
000000000010000000000000000000000000000000000000000000|0
000000000001000000000000000000000000000000000000000000|0
000000000000100000000000000000000000000000000000000000|0
000000000000010000000000000000000000000000000000000000|1
000000000000001000000000000000000000000000000000000000|0
000000000000000100000000000000000000000000000000000000|0
000000000000000010000000000000000000000000000000000000|0
000000000000000001000000000000000000000000000000000000|1
000000000000000000100000000000000000000000000000000000|0
000000000000000000010000000000000000000000000000000000|0
000000000000000000001000000000000000000000000000000000|0
000000000000000000000100000000000000000000000000000000|1
000000000000000000000010000000000000000000000000000000|0
000000000000000000000001000000000000000000000000000000|0
000000000000000000000000100000000000000000000000000000|1
000000000000000000000000010000000000000000000000000000|1
000000000000000000000000001000000000000000000000000000|0
000000000000000000000000000100000000000000000000000000|1
000000000000000000000000000010000000000000000000000000|0
000000000000000000000000000001000000000000000000000000|0
000000000000000000000000000000100000000000000000000000|0
000000000000000000000000000000010000000000000000000000|1
000000000000000000000000000000001000000000000000000000|0
000000000000000000000000000000000100000000000000000000|0
000000000000000000000000000000000010000000000000000000|0
000000000000000000000000000000000001000000000000000000|0
000000000000000000000000000000000000100000000000000000|1
000000000000000000000000000000000000010000000000000000|1
000000000000000000000000000000000000001000000000000000|0
000000000000000000000000000000000000000100000000000000|0
000000000000000000000000000000000000000010000000000000|0
000000000000000000000000000000000000000001000000000000|1
000000000000000000000000000000000000000000100000000000|0
000000000000000000000000000000000000000000010000000000|1
000000000000000000000000000000000000000000001000000000|0
000000000000000000000000000000000000000000000100000000|1
000000000000000000000000000000000000000000000010000000|1
000000000000000000000000000000000000000000000001000000|0
000000000000000000000000000000000000000000000000100000|1
000000000000000000000000000000000000000000000000010000|1
000000000000000000000000000000000000000000000000001000|0
000000000000000000000000000000000000000000000000000100|1
000000000000000000000000000000000000000000000000000010|0
000000000000000000000000000000000000000000000000000001|0
We can pull the solution back out of this grid, taking the column on the right and wrapping it back up into a grid.
(Spoilers) The solution vector, as a board
000101
110100
010001
000100
110100
010000
110001
010110
110100
And that works perfectly :D
One final note: This suggests a hell method for producing these puzzles. Any solvable linear system here generates a puzzle. For this one, since everything only affected its neighborhood, the matrix was very sparse. But if you made an extremely non-sparse matrix, you'd get any cell potentially toggling any other cell. Enjoy :)
