Lights Out is an eletronic game release by Tiger Eletronics in 1995. The game consists of a 5 by 5 grid of lights. When the game starts, a random number or a stored pattern of these lights is switched on. Pressing any of the lights will toggle it and the adjacent lights. The goal of the puzzle is to switch all the lights off, preferably in as few button presses as possible.
The game of Lights Out in the picture above can be represented like so, with the following initial start:
X . . . .
. . . . .
. . . . .
. . . . .
. . . . .
and the following moves:
4 4
3 3
In the final state of this game, there are 5 lights on at the end.
Given the following initial state of the game:
. X . X .
. X X X X
X X . X X
X X X X X
X X X X X
and the following moves:
3 2
2 4
3 3
0 3
1 2
3 1
1 4
4 0
1 4
0 1
0 1
0 2
0 2
3 1
0 4
2 2
1 3
3 1
2 2
1 1
0 0
4 3
4 4
2 3
4 3
How many lights are on at the end?
- Solve the kata using a recursive function if you haven't done so
- Can you do it using a fold/reduce, or equivalent in your language?
Lights Out has some interesting mathematical properties! Let's play with them :-)
- Is the initial configuration above solvable? Prove it!
- Write an algorithm to solve the game using the light chasing technique.