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 four diagonal neighbors (if any) to the northwest, northeast, southwest, and southeast. The goal is to turn all the lights out. Here's a great puzzle page to help you understand the basics of the classic version of the puzzle. 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, and the left and right of the board, so that if you push a light on the bottom, it'll affect its diagonal neighbors on the top row and vice-versa, and if you push a light at the right, it'll affect its diagonal neighbors on the left. 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: (make sure you understand this before continuing)
0 0 1
0 0 1
1 1 0
As another example, given the following almost-solved state:
0 0 0
1 1 1
1 1 1
the solution is simple -- push buttons highlighted in bold 1s below:
0 0 0
0 0 1
0 0 1
OR
0 0 0
0 1 0
0 1 0
OR
0 0 0
1 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 requirement 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. Type submit hw2 to begin the submission process. Make sure you submit all of your files, including your makefile.