UPDATED 9/10/2004
Mini Lights Out, sold by Tiger Electronics
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):
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.