Vagrearg - Lights Out, Turing Style

Lights Out, Turing Style

Introduction and principle

The game Lights Out is an interesting game. The simplicity combined with the sense of achievement (when getting the lights out) is amazing. Human minds can sometimes be entertained by the simplest of interactions.
So, as one of those entertained minds, I wanted to build such a game. But, why do it the easy way if you can do it the hard way? The easy way is to make some 5x5 matrix of LEDs and buttons and put a micro-controller in there. Then write some code and you're done. Well, that is not a satisfying strategy. Besides, anyone can do it that way. The theory of the Lights Out puzzle can be found at Jaap's Puzzle Page, including mathematical descriptions and proofs.

You may skip the ideas and principle behind the design and go straight to the circuit design or, for the impatient, to the build log. A video is available too.

This is what the finished game looks like. Read on through all the pages to see all the big and small details. The features include:

Lights Out game play
Adjustable random initialization
Solvability test
Manual mode
Game replay
7400/4000 logic design

Principle

The game play is easily calculated in matrix form, where the next light pattern is the sum modulo 2 of the current state and a mask consisting of (x,y-1), (x-1,y), (x,y), (x+1,y) and (x,y+1). The "sum modulo 2" is the binary XOR function. An example pushing button (3,3):

⊕

Pushing buttons on the edges does not wrap. This observation can be used to extend the board from a 5x5 matrix to a 7x7 matrix. This change causes the XOR mask to remain constant. Pushing button (4,5) gives:

⊕

The next observation is that all game play moves are symmetrical and can be calculated at any position if the sum of transformations is zero. Mathematically, the following holds for any geometrical transformation function

T

T (A \oplus M) = T (A) \oplus T (M)

As an example this can be illustrated with button (3,1) in a torus view of the matrix:

⊕

Trans(-3,-1)

Trans(3,1)

⊕

⇒

In the binary world, all that is a power of two is easier to work with. So, extending the board to 8x8 would make sense (this makes the designing part a lot easier). The board coordinates are defined with (0,0) at position top left and (7,7) at position bottom right. However, the active coordinates have the range ({1..5},{1..5}), which is the viewing window. The above board then looks like:

The last step is not to see a matrix, but 64 bits in a line (a tape, hence the Turing reference), where (7,7) is connected to (0,0). The board is now a shift-register of length 64 and the end is connected to the start. This transformation is no problem because the calculations are independent of geometrical transformations, as long as they are applied to both the source and the mask:

It is an easy task in a shift register to move bits in either direction. With a circular shift-register, such as this case, it is assured that the state of the shift-register is restored for any modulo 64 shifts in the same direction. It can also be determined that any position in the matrix can be shifted into the first register position by shifting

64 - (8 y + x)

times.
If the mask is defined as a register, initialized with a constant of 64 bits, then changing coordinate (x,y) would require a minimum of 64 shifts. The first

64 - (8 y + x)

are required to move the pattern to a known position. Then the mask is applied and the pattern is shifted

8 y + x

positions to restore the original position.
This procedure would require a parallel function to be applied on the shift-registers, which is not very efficient. More efficient would be to calculate the result while shifting and applying the XOR function on the bits moving from (7,7) to (0,0). A stream processor, as you will.
A mask which can be applied in the (7,7) to (0,0) feedback loop looks like:

It should be noted that a mask length of 17 bits would be sufficient to store the entire mask. Following bits of the mask are always constant at zero and

A \oplus 0 = A

.
To change any position on the board, while using the stream processor procedure, we must align the pattern in such way that (x,y+1) is positioned at (7,7) for a change of (x,y). Coordinate (x,y+1) is the first field that will be changed by the mask, so this is the one that must be "first-in-line". A constant offset of -9 shifts is introduced to position (x,y+1) to (7,7), with respect to the above equations. Minus eight to get to row y+1 and minus one to get from (0,0) to (7,7). In other words, relocating the view window by -9 shifts makes it possible to use stream calculations. Please note that this static offset does not change the button coordinates, which still are in the range ({1..5},{1..5}).

and constant mask

The procedure is now as follows:

for button (x,y) shift the data register $64 - (8 y + x)$ times using $A_{0, 0} (n + 1) \Leftarrow A_{7, 7} (n)$
shift both data and mask register 17 times while calculating $A_{0, 0} (n + 1) \Leftarrow A_{7, 7} (n) \oplus M_{7, 7} (n)$
shift the data register up to the next modulo 64 position using $A_{0, 0} (n + 1) \Leftarrow A_{7, 7} (n)$ to restore the pattern

The minimal number of shifts performed for button (1,1) is: 64-(8*1+1)+17=72; and for button (5,5): 64-(8*5+5)+17=36. That means that the next valid pattern will always be restored at modulo position 2*64 shifts. An alternative formulation where a 17-bit mask register is stuffed with zeros fill:

for(count = 0; count < 2*64; count++) {
	if(count < 64-(8*y+x)) {
		A₀(n+1) = A₆₃(n);
		shift(A);
	} else {
		A₀(n+1) = A₆₃(n) ⊕ M₁₆(n);
		M₀(n+1) = 0;
		shift(A);
		shift(M);
	}
}

Quiet Patterns

There are known combinations of lights that cannot be solved. From all 2²⁵ possible combinations, only 2²³ result in the ability to turn off all lights. That means that initializing the board randomly has a 1 in 4 chance of resulting in a playable game. Those odds are not good.
There are test-patterns, known as quiet patterns, which can be used to test for a solvable combination. The Mathematics of Lights Out at Jaap's Puzzle Page describes in detail how the quiet patterns are calculated. The two patterns of interest are (the highlighted fields are the fields part of the pattern):

and

A game is solvable if the number of turned on lights is even for both quiet patterns. That means that a parity test on a game's initial setup should return even parity for both patterns for it to be solvable.
When initializing the game with random data (simply shift in random bits in the shift register), then it is possible to determine whether or not the result will be solvable by calculating the parity of both quiet patterns on the fly. Initialization of the game must assure that at least 40 random bits are shifted in (to assure complete reset) and then continue shifting in random bits until a solvable pattern emerges.

Simulated test

A small program was written (in C) to see if the theory would work out properly, including testing the quiet patterns. It consists of an interactive game play system and a simulation of many random boards. The simulation should confirm that 25% of all boards are solvable and properly detected by the quiet patterns.
After a few runs and some bug fixing, it was determined that it works out just as the theory said it would. Now to make this in hardware.
Moore's law at work: Modern computers are actually fast enough to test all 33554432 combinations sequentially. My 8 year old 1.8GHz pentium mobile machine takes a couple of minutes to randomly test 1000000 patterns. With the currently available multi-core and much faster CPUs it would take few minutes to test all combinations (and less if the code were to be optimized).

Next part: Designing a circuit

Posted: 2011-09-24
Updated: 2011-10-13



Overengineering @ request	Prutsen & Pielen since 1982