Wieb Bosma, Radboud Universiteit Nijmegen
|
Reporting on joint work with Master student Daan Wanrooy,
I will discuss various problems and solutions related to a simple toy game.
This game, called "Lights Out", consists of a 5 by 5 array of buttons
that can light up. Pushing a button will alter its state (on/off) as well
as that of the (at most four) buttons that are its horizontal and vertical
neighbours. Goal of the game is to turn off all lights in a given pattern
by pushing buttons. Solving puzzles of this kind becomes easy with some linear algebra. Starting from there I will answer some related questions on the solution space for this game and for variants, obtained by changing the playing board, the number of states, and the rules of the game. This will also lead to some interesting complexity results. |