LightsOut
This program shows a puzzle with coloured lights. By clicking on the lights, you can make them change colour or go out. The aim is to make all the lights go out. The program also incorporates an expert solver for the puzzle that uses linear algebra to find the quickest solution.
Instructions
A pattern of coloured squares will appear. The goal is to turn all the squares white by clicking on selected squares. Each click affects the square you click and also up to four adjacent squares. From the initial configuration, it is possible to solve the puzzle in at most five clicks. Click on "Random 5" to get a new puzzle, or on "Random 10" if 5 clicks is too easy.
What has it to do with algebra?
Pressing the "Solve" button displays a solution to the problem, which you can then carry out by clicking on the squares indicated. Solving a problem that the program has invented itself is easy, because the program knows where it clicked to generate the problem; but you can also pose any problem you like by changing to "Setup" mode and clicking on squares. The majority of problems created in this way cannot be solved, but the program will always find a solution when one exists.
The program solves the puzzle by converting it to a set of simultaneous equations, which it then solves by Gaussian Elimination, an algorithm taught informally in first year Mathematics courses and studied in depth in second year courses on Numerical Analysis. In order (for example) to change the top left square from red to white, the total number of clicks in that square or in the two adjacent squares must be equal to 2, or to a number that differs from 2 by a multiple of 3. This gives one of a set of 25 linear equations – one for each square – that must be satisfied by any solution. Instead of using the real numbers as usual, these equations must be solved in the field Z3 of integers modulo 3, but the same algorithms can be used as for ordinary simultaneous equations. The "modulo 3" part comes about because clicking three times in any square returns the puzzle to its original state.
In fact, the matrix of coefficients is singular, so some problems have multiple solutions and others have none. If solutions exist, the program examines all of them to find the one that requires least clicks. Solving 25 linear equations by hand is an onerous task, but a computer is able to do it in an instant.