Programming Puzzle: Lights Out
I encountered this puzzle as a mini-challenge in a game my sister was playing years ago, and it turned out to be from a handheld game called Lights Out. It consists of twenty-five lights in a 5-by-5 grid. Clicking on any light toggles that light and those in the 4-neighborhood around it (excluding wraparound). The challenge was to click enough lights to make all twenty-five lights active at the same time:
Now, this problem was a kid’s game that was supposed to be solved by hand, but we were honestly having a bit of a hard time. That’s when I realized I could give up and solve it by writing a simple program. At the time my inspiration was that there were only twenty-five lights that could each only be in one of two states, and 2²⁵ is only about 32 million, so it could be solved by exhaustively trying all combinations of light pushes and seeing which one succeeded. Also the order you push the lights in doesn’t matter, so it can indeed by tried exhaustively.
Brute Force Part I
We stored the grid of lights as a matrix of zeros and ones, and used a single helper function to do the toggling:
def toggle(board, r, c):
board[r][c] ^= 1 if r:
board[r - 1][c] ^= 1 if r < len(board) - 1:
board[r + 1][c] ^= 1 if c:
board[r][c - 1] ^= 1 if c < len(board[r]) - 1:
board[r][c + 1] ^= 1
Next we program the exhaustive search using the Cantor diagonal approach where we number every solution consecutively and loop through all 2²⁵ of them using an integer i. Then we use the bits of each value of i to determine which lights to push, i.e., if the j'th bit of i is set then we toggle the light at position j for that solution. The only math is converting from the linear j index into the row and column indices r and c:
for i in range(2 ** (N ** 2)):
board = [[0] * N for _ in range(N)]
for j in range(N ** 2):
if i & (1 << j):
toggle(board, j // N, j % N) if all(all(_) for _ in board):
print('Solved {}'.format(i))
break
Now, this works, but it takes a while. In fact, the repl.it I just wrote for it is still running while I’ve been able to write an entire draft of this Medium post. Granted repl.it runs things at only a quarter power, but we can do better.
Brute Force Part II
The next solution I tried was backtracking search. This kind of code is some of my favorite since it lends to very elegant recursive functions. We use a recursive solving function whose job is only to try all possible values for a single position in the problem, here toggling a light at position(r, c). The function has to explore both branches: first toggle the light and recurse (to see if the rest of the problem is solvable); and then don’t toggle the light and recurse (to see if the rest of the problem is solvable):
def do_search(board, toggles, r, c):
if all(all(_) for _ in board):
# We've toggled all lights on the board; solution found.
return True
elif r >= N or c >= N:
# We've reached the end without finding a solution.
return False # Iterate through the grid in row-major order.
r_next = r
c_next = c + 1
if c_next >= N:
r_next += 1
c_next = 0 # Try toggling.
toggle(board, r, c)
toggles[r][c] = '*'
if do_search(board, toggles, r_next, c_next):
return True
toggles[r][c] = '.'
toggle(board, r, c) # Try not toggling.
return do_search(board, toggles, r_next, c_next)
The first part is just standard recursive boundary checking to see if we’ve either solved the problem or reached the end of the search space. The second part is the one that explores both branches and recurses, terminating early if either of the branches finds a solution. This is a good example of a solution by reduction, since this function only tries to solve a single position in the puzzle, then passes the rest of the problem off to a future version of itself recursively.
Another elegant thing to note is that the # Try toggling part is “mirror-symmetric”:
1. toggle(board, r, c)
2. toggles[r][c] = '*'
3. if do_search(board, toggles, r_next, c_next): return True
4. toggles[r][c] = '.'
5. toggle(board, r, c)Line 1 toggles the board, line 2 records the click in toggles, and then line 3 recurses and returns if we succeeded. Otherwise, we have to backtrack by undoing the state changes we did, so line 4 unsets the click in toggles and line 5 untoggles the board (toggle is its own inverse function, so we just call it again). Hence the outer lines 1 and 5 are inverses of each other, the inner lines 2 and 4 are inverses of each other, and the central line 3 is the recursive call.
This is a useful skeleton for backtracking search: the mirror symmetry reminds you that any action you take needs to be undone before you backtrack. No matter if you need n lines of code for the full state change, the next line will always be the recursive call, and the following n lines will undo the changes of the first n.
(N.B. This only applies if you’re passing the same data structures between all the recursive functions. If you copy the data structures each time you recurse, no functions are sharing the same objects so there’s no need to undo your local state changes. But that approach is not memory-efficient.)
Beyond Brute Force
One catch is that this code will also take a while to run. It’s also not even as efficient as the exhaustive search since this uses recursion, which means it’s popping millions of frames on and off the stack whereas the old approach was just iterating through a for loop. But the flaw of the first exhaustive search was, if we just found out that value i is not a solution, that tells us nothing about whether value i + 1is a solution. With backtracking search, we can do constraint checking to determine when to stop searching unsolvable branches early.
The reason this code is taking so long is, it may have left some lights off in row 1, but it still continues exploring how it should be toggling rows 3, 4, and 5. This is wrong because lights in row 1 can only be affected by toggles on rows 1 and 2. By the time you start exploring row 3, row 1 must be solved, otherwise you need to backtrack. This reasoning is similar to the N queens solution where we solve the problem by files (columns): if we’ve messed up somewhere in the first three files, it won’t be fixed by continuing the search to the next five files, so we have to backtrack early.
The check we add here is illustrated below (it depends on the fact that we’re processing the lights in row-major order, but the same principles could be applied to a column-major search). If we’re exploring an interior point like A (c > 1), that means light B (one row and one column back) must be on; otherwise, no other lights we will toggle for the rest of the search will affect B and we have to backtrack. If we’re exploring a left edge point like C (c = 0), that means light D (two rows back on the opposite edge) must be on as no other lights we will toggle for the rest of the search will affect it:
The code for this is four lines:
if r and c and not board[r - 1][c - 1]:
return False
elif c == 0 and r > 1 and not board[r - 2][N - 1]:
return FalseThese constraints only cover a portion of the grid, with the A⇒B constraint covering the green squares and the C⇒D constraint covering the blue. You could add a third constraint when checking the last row, that states that the light two columns away from where you are must be on. But by the time you’re searching the last row there are only 2⁵—or 32—more possible states. Adding an extra constraint that only gets checked on the last row might actually cost you more computation overall than the branches you save.
Results
With added constraint checking, the finished search is now so fast that we can put it in a loop and try for the biggest grid (largest N) that we can solve. Interestingly, even-sized puzzles tend to find radially symmetric solutions that can be solved instantly, while odd-sized puzzles tend to find asymmetric solutions that take progressively longer. I excerpt the solutions up to N = 14 below, where asterisks ('*') mean to toggle that light and periods ('.') mean to skip it:
N: 4
****
*..*
****
....N: 5
**...
**.**
..***
.***.
.**.*N: 6
*.**.*
.****.
******
******
.****.
*.**.*N: 7
**.*.**
***.***
.**.**.
*..*..*
.**.**.
***.***
**.*.**N: 8
**....**
**.**.**
..****..
.******.
.******.
..****..
**.**.**
**....**N: 9
********.
*......*.
**....**.
.*.**.*..
*********
**.**.*.*
......*.*
..*...***
*...*....N: 10
*.*....*.*
.*..**..*.
*.*.**.*.*
...*..*...
.**.**.**.
.**.**.**.
...*..*...
*.*.**.*.*
.*..**..*.
*.*....*.*N: 11
********.**
*......****
**....*..*.
.*.**..****
*****.**.**
**.*.**....
...*.*.**..
...***.**.*
**....*..*.
**...*.**.*
...*...**..N: 12
*.*......*.*
.*..****..*.
*.*.*..*.*.*
...******...
.****..****.
.*.*.**.*.*.
.*.*.**.*.*.
.****..****.
...******...
*.*.*..*.*.*
.*..****..*.
*.*......*.*N: 13
**.*.***.*.**
***.**.**.***
.**.*...*.**.
*..*******..*
.****...****.
**.*.*.*.*.**
*..*..*..*..*
**.*.*.*.*.**
.****...****.
*..*******..*
.**.*...*.**.
***.**.**.***
**.*.***.*.**N: 14
****..***..**.
*..*..*.*..**.
****..*.*.....
......***.*..*
....*....*....
***.....*.***.
*.*..**...*.*.
*.*..**...*.*.
***.....*.***.
....*....*....
......***.*..*
****..*.*.....
*..*..*.*..**.
****..***..**.
All the Solutions
Note that any solution that isn’t already radially symmetric can be rotated to generate another valid solution. Here are actually four valid solutions for the 5-by-5 puzzle that are all rotations of the one we found above:
So an obvious followup question to ask is, now that we’ve found one solution for each N, how do we find all the solutions for each N?
We can accomplish this with some simple modifications to the recursive function. First, we drop the boolean return; since the return True was just used to signal that we had found a solution and could stop searching, that is no longer needed. And second, we add an extra argument to store all the solutions in, and instead of returning early when we find a solution, we save a snapshot of it to this array and continue searching:
import copydef do_search(board, toggles, r, c, solutions):
if all(all(_) for _ in board):
solutions.append(copy.deepcopy(toggles))
return
......
solutions = []
do_search(board, toggles, 0, 0, solutions)
However, this code will still collect all of the rotated solutions. We could post-process the list of solutions in order to remove those, but here I chose to build a hash set of solutions as we went along to keep from ever saving duplicates. This requires adding another argument to save hashes of all the solutions and their rotations, and checking any prospective solution’s hash and its rotated forms’ hashes against it. This code got a little involved so I won’t excerpt it here, but see the full Python code if interested.
In the end we find that N=5 indeed only has that one unique solution, just rotated four times. The other solution counts I found were:
N=4: 6N=5: 1N=6: 1N=7: 1N=8: 1N=9: 70N=10: 1N=11: 16N=12: 1N=13: 1N=14: 6N=15: 1
These numbers were pretty surprising. I can understand many puzzles only having one solution, but N=9 having a whopping 70 solutions? I did not see that coming. Here’s a look at the first four solutions for that size:
********.
*......*.
**....**.
.*.**.*..
*********
**.**.*.*
......*.*
..*...***
*...*....*******..
*.....*.*
**...***.
.*.*.****
***.*.***
***....*.
.*...****
****.*.**
**.***...******.**
*....****
**..*..*.
.*...****
**.***.**
*.**.....
*.*.*.*..
***..*..*
....*.*..******..*
*....*...
**..**.*.
.*..*.*..
**..*..**
*...*.***
***.****.
..**..*.*
.*.****..
If you look at the first row of each, you can see a binary counting effect (which is a direct result of how the backtracking search iterates through positions). If we treat the toggled spaces as zeros and the ignored spaces as ones, from the first 10 solutions we have the top row spelling out the numbers 1, 3, 4, 6, 9, 11, 12, 14, 16, and 18. Beyond that, the downstream structure of each solution is roughly the same. It seems that N=9 is simply a lucky configuration that you can pick almost any opening you want on the top row and suss it out with the right toggling afterwards.
