An Algorithm(n) for Solving Lights Out

Version 1.0

Perhaps many of you agree that Lights Out is not very easy to solve...

But it is easy to solve if you have a solution algorithm. (An algorithm is a precise sequence of instructions designed to solve a problem.)

// An algorithm for solving the game Lights Out
// Written by R.W. Smyth 7/17/01 (12:30am)
// Version 1.0
//
// For convenience, let's agree to number the rows in the game board
// one through five starting at the top.  Similarly, let's number the 
// columns one to five, starting at the left.  We'll use the notation 
// S(i,j) to refer to the square in row i, column j (e.g. S(1,5) refers 
// to the square in the upper righthand corner of the game board). 
//
// Note:  This is definitely NOT the most efficient algorithm for
// solving the game.

(1) Click (once) on each square in row 2 which is directly
    below a white square in row 1.
(2) Click on each square in row 3 which is directly below
    a white square in row 2.
(3) Click on each square in row 4 which is directly below
    a white square in row 3.
(4) Click on each square in row 5 which is directly below
    a white square in row 4.
(5) IF ( S(5,1) and S(5,5) have the same color as each other )
       AND ( S(5,2) and S(5,4) have the same color as each other ) 
    THEN
           skip directly to step (6),
    OTHERWISE 
           click (once each) on the following squares:
           S(1,1), S(2,2), S(2,3), S(2,4), S(3,3), S(3,5)
           S(4,4), S(4,5) and S(5,5),
           // Note:  These nine squares may be clicked on in any order.
           and repeat steps (1) - (4).
(6) IF there are any white squares in row 5
    THEN
           click on the square immediately to the right of the leftmost
           white square in row 5,
    OTHERWISE
           proceed immediately to the next step.
(7) IF there are any white squares in row 5
    THEN
           click on the square immediately to the right of the leftmost
           white square in row 5,
    OTHERWISE
           proceed immediately to the next step.
(8) IF there are any white squares in row 5
    THEN
           click on the square immediately to the right of the leftmost
           white square in row 5,
    OTHERWISE
           proceed immediately to the next step.
(9) Click on each square in row 3 which is directly above a white square
    in row 4.
(10) Click on each square in row 2 which is directly above a white square
     in row 3.
(11) Click on each square in row 1 which is directly above a white square
     in row 2.

Discussion Questions

Can anyone suggest any improvements in the algorithm above?

What makes one algorithm better than another?

Project Suggestion #2

Warning: This suggestion is "on the edge." Some of the questions I'm asking are perhaps unreasonably difficult. Strong talent in mathematics is more or less required for success here. (That said, I hope someone takes up the challenge.)

Answer as many as possible of the following questions:
• How many distinct combinations of black and white squares are possible on a 5x5 grid?
• Does every possible configuration of black and white squares on a 5x5 grid constitute a solvable Lights Out gameboard? (If you discover the answer, you should prove that your answer is correct. If you can not discover the answer, perhaps you can still contrive an algorithm, which if followed patiently to its conclusion would produce the answer.)
• (Without prejudious to the previous question) what is the maximum number of clicks which may be required to solve a "solvable" Lights Out gameboard? (Again, if you discover the answer, you should prove that your answer is correct. If you can not discover the answer, perhaps you can still contrive an algorithm, which if followed patiently to its conclusion would produce the answer.)
• Can you think of any ways to "tweak" the game to make it more interesting?
• Feel free to add any clever observations you have about the game.