Nine squares, each one either black or white, are arranged in a 3 X 3 grid. Figure 2.24 shows one possible

Figure 2.24
The nine squares puzzle
Arrangement. When touched, each square changes its own state and the states of some of its neighbors (black ( white and white ( black). Figure 2.25 shows

Figure 2.25
State changes for the nine squares puzzle
How the state changes work. (Touching the square whose number is circled causes the states of the squares marked * to change.) The object of the game is to turn all nine squares black. [Exercises 35 and 36 are adapted from puzzles that can be found in the interactive CD-ROM game The Seventh Guest (Trilobyte Software/Virgin Games, 1992).]
(a) If the initial configuration is the one shown in Figure 2.24, show that the game can be won and describe a winning sequence of moves.
(b) Prove that the game can always be won, no matter what the initial configuration.

Transcribed Image Text:

3-6 9 5 4-7 23 7 8 9 7 8 9 123 4 56 4 56