Lights Out
Hard · Sequential · SystemVerilog · VHDL
Lights Out is an electronic puzzle released by Tiger Electronics in 1995, played on a 5×5 board of lit buttons. Pressing a button toggles its own light and the lights directly above, below, left and right of it; the board does not wrap around, so a corner press changes only three lights. The goal is to turn every light off.
Design a circuit that solves Lights Out: given a board, it decides whether some set of presses turns every light off and, if one does, says which buttons to press.
Example
On the board below, pressing the center button clears all five lights at once.
'''Starting board Press here Finished board . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . O O O . . . X . . . . . . . . . O . . . . . . . . . . . . . . . . . . . . . . . . . . . '''
Board
The board arrives on board_row one row at a time through a valid/ready handshake, starting from the top row (row 0); rows may come with gaps between them. Each row is 5 bits, with the leftmost light in the most significant bit, so a lone light in the leftmost column is 5'b10000. After the fifth row, ready stays low until the circuit has given its answer.
Answer
As it turns out, the order of the presses doesn't matter (can you see why?), and pressing a button twice just undoes the first press. So a solution comes down to one choice per button, press it or not, and fits in a 25-bit key. Some boards may have multiple solutions, in which case any key that clears the board is accepted, and some boards may have no solution, such as a lone light in a corner, and the circuit must report it as unsolvable.
The circuit has up to 25 cycles after the last row is received to produce an answer. When it has an answer, it pulses done for one cycle, with solvable high in that cycle if the board has a solution. If it is solvable, the key follows in the next five cycles with key_valid high and key_row carrying rows 0 to 4 in order, a 1 meaning press that button.
ready is high again in the cycle after the last key row, or, for an unsolvable board, in the cycle after done. It stays high until the next board starts.
solvable matters only while done is high, and key_row only while key_valid is high.
Reset
resetn is a synchronous, active-low reset that abandons any board or answer in progress and makes the circuit ready for a new board.