CS61C Homework 2 - Lights Out!

Your job is to write code to solve and analyze a variant of the popular hand-held toy Lights Out. You are given a 3 x 3 grid of lights. In the initial state, some may be on, some may be off. If you push on a light, it toggles the state of itself and its immediate neighbors (if any) to the north, south, east and west. The goal is to turn all the lights out. Here's a great puzzle page to help you understand the basics. Note that the order of the button presses doesn't matter in any solution.

Our version is slightly different; we "sew" the top and bottom of the board (but NOT the left and right), so that if you push a light on the bottom, it'll affect its neighbors on the top row and vice-versa. E.g., If our board had all its lights on (1=on, 0-off):

1 1 1 
1 1 1 
1 1 1 

and you push the bottom-right button, the resulting state would be

1 1 0
1 1 0
1 0 0

Note that the bottom-left light didn't toggle because there's no "connectivity" left-to-right. As another example, given the following almost-solved state:

 1 1 1 
 1 0 1 
1 1 1

the solution is simple -- push buttons highlighted in bold 1s below:

1 0 0 
0 0 0 
0 0 1 

OR

0 0 1 
0 0 0 
1 0 0 

You are to write two programs (one to play the game and one to perform analysis):

1. Write SolveLightsOut which takes a single argument, InitialState (written as a row-major binary bit-string. E.g., the second position shown above would be written 110110100) and prints to stdout the most optimal solution (fewest button presses) also as a bit string (if several optimal ones exist, print them all, each separated on a different line, sorted by smallest-to-largest [if you considered each answer to be an unsigned number]). If no solution exists, print "No Solution Exists". E.g.,
   SolveLightsOut 111101111 would print out 001000100 and 100000001 as in the second example above. If the user provides no argument or an argument that is not a valid bit string, print a useful Usage message.
2. Write AnalyzeLightsOut which will compute the answer to two questions:
   1. Of the 2⁹ initial states, how many have no solution? I.e., no combinations of input button presses can turn the lights out.
   2. Which of the initial states is the most interesting? (interesting = requires the most button pushes to solve) If there are several, choose the one that is first (again, sorting the InitialStates from smallest-to-largest as unsigned numbers). When run, AnalyzeLightsOut will compute and print out the following:
      % AnalyzeLightsOut
      States with no solution:
      Most interesting state :
      

You should use bit manipulation to toggle your initial board states. (You may want to read up on macros to do this quickly for you) Also, you should encode the board position as an unsigned number (which type is appropriate here?), not an array of bits. Your code design and style will be part of your grade. Hint -- we shouldn't see duplicate code in AnalyzeLightsOut and SolveLightsOut -- you should think about how to modularize your code into different files.

You should also include a makefile with your submission.  The only requirment is that running the command "gmake" should produce two executable files SolveLightsOut and AnalyzeLightsOut.  For those of you unfamiliar with gmake, a reference for it may be found at http://www.gnu.org/software/make/manual/make.html.   You shouldn't need to read the entire document to be able to meet the requirements.