Trial Run

At first glance, the Gray code in Figure 4 seems to be a workable solution to the ring problem. When the bits in a particular state are all  , all rings are off the rail; if they are all 1, they're all on top, so the generated sequence shows a solution to get from the "all off" state back to the puzzle's initial state when it arrived in the mail. To go from the initial "all on top" state to "all off," the puzzle master has proceed backward in the generated sequence.

Is the procedure correct in detail, though? I'll whip up a test script to run through all the codes and check the two conditions of the game for each one: Is only one ring really moved at a time, either from top to bottom (1=>0) or from bottom to top (0=>1)? And does the auto-player only move the first ring, or, if it is another ring's turn, is its right neighbor on top as required, and are all the other rings down? Time to dissect the Gray code with Python's bit operations.

The utility function bits_set() starting in line 10 of Listing 2 searches through the bits of a number and returns an array with the index numbers of the bits set to 1. Among other things, it serves as a controller to verify that I've arrived at the end of the sequence when all nine rings are on top, that is, when the first nine-element array with index numbers comes back from bits_set().

01 #!/usr/bin/env python3
02 import operator
03 import math
04 from graycode import grayme
05
06 def rings_changed(pos1,pos2):
07     xor = operator.xor(pos1,pos2)
08     return bits_set(xor)
09
10 def bits_set(num):
11     bits = []
12     while True:
13         if num == 0:
14             break
15         bit = int(math.log(num,2))
16         mask = 1 << bit
17         num  &= ~mask
18         bits.append(bit)
19     return(bits)
20
21 def move_valid(pos1,pos2):
22     changed=rings_changed(pos1, pos2)
23
24     if len(changed) != 1:
25         # only one ring can change per move
26         raise Exception(
27           "More than one change: " +
28           str(changed))
29
30     if changed[0] != 0:
31         # next ring up?
32         mask = 1 << changed[0]-1
33         if not (pos2 & mask):
34             raise Exception(
35               "Next ring not up: " +
36               str(changed))
37
38         if changed[0] > 1:
39             # right-most rings down?
40             mask = ~(~0 << changed[0]-1)
41             rest = pos2 & mask
42             if len(bits_set(rest)) != 0:
43                 raise Exception(
44                   "Rings not down: " +
45                   str(changed))
46 def main():
47     i=0
48     rings=9
49     last_gray=None
50     while True:
51         gray=grayme(i)
52         print(format(gray,"08b"))
53
54         if last_gray is not None:
55             move_valid(last_gray, gray)
56
57         last_gray=gray
58
59         if len(bits_set(gray)) == rings:
60             break
61
62         i += 1
63
64 if __name__ == "__main__":
65     main()

The test script also checks how many and which bits have changed from one Gray code to the next and ensures that only one bit (i.e., one ring) has moved each time. To do this, the rings_changed() function processes two Gray codes from line 6 with the XOR operator, which sets bits to 1 at the positions that differ.

Then the loop counts the 1 bits in the endless while loop in line 12 and appends their indices to the array returned by the function, using append() (Figure 5). For this to happen, the loop determines the index of the highest set bit in the current state with the formula

Figure 5: Using XOR, the test script checks which rings the user moves according to the Gray code.

int(math.log(num,2))

which calculates the logarithm of the number to be examined to base 2 and rounds it down to the next integer value. To clear the highest bit found this way, it then generates a mask with a bit set at the critical position and combines the number and the mask with a bit-wise AND operator:

mask = 1 << bit
num  &= ~mask

The next round of the loop may find more bits in the lower ranks, register them, and clear them, until the value finally turns to   and the loop is aborted.

Whether a move proposed by the Gray code is valid is checked by the move_valid() function starting in line 21. First, it throws an exception if more than one bit (ring) has changed (line 26), so the main program does not have to check its return value at all and simply relies on the fact that it will blow up if something is off. For rings 2 and above, the if construct as of line 30 uses one mask to check whether all right-hand side rings are on top and otherwise terminates with an error in line 34.

For rings 3 and above, Lines 38 and following use a mask of 1 bits to check whether all rings further on the right are at the bottom.

Right-Aligned 1s

A mask with n right-aligned 1s is generated by the following somewhat strange construct

~(~0 << n)

in line 40. The ~0 first creates the bit complement of the number   (i.e., an integer in which all bits are set to 1). It then shifts the bits by n digits to the left, which fills the first n bits on the right with  s, while the rest of the number keeps 1 bit values.

Another complement ~ outside the parenthesis flips all bits again, so that the mask has set the first n bits on the right to 1 as desired. Figure 6 finally shows the output of the test script and verifies that the Gray code complies with all rules of the ring game.

Figure 6: The test script checks 341 Gray code transitions for their validity in the puzzle.

The bit-wise method is not suitable for a larger numbers of rings, but works up to the integer limit of 32 or 64 bits, depending on the platform. Ring games with more than 10 rings are not practical anyway, because the number of combinations would skyrocket. The game is a nice way to pass the time (Figure 7) but can result in a nervous breakdown. It is important to plan the moves to the next ring to be removed. It is incredibly frustrating if you remove a ring that needs to stay on top in order to remove another ring in the heat of the moment. This means retracing all your steps and wasting even more time.

Figure 7: After about 250 moves, just before I solved the puzzle.

The Author

Mike Schilli works as a software engineer in the San Francisco Bay area, California. Each month in his column, which has been running since 1997, he researches practical applications of various programming languages. If you email him at mailto:mschilli@perlmeister.com he will gladly answer any questions.