I am not a fan of puzzles due to my lack of patience. However, when I recently read in an excerpt from Martin Gardner's venerable 1972 Scientific American column [1] in an online antiquarian bookstore that the Chinese Rings puzzle could be solved with Gray codes [2] from the field of information theory, I was gripped by game fever. I ordered the ring set online for little money.

A second-century Chinese general named Zhuge Liang is said to have invented the game, which was nicknamed "Baguenaudier" [3] (time waster) many centuries later. Allegedly, his intention was to keep his wife busy during his absence. The metal contraption arrived in a cardboard box with printed Chinese characters. Exhibiting great foresight, I immediately clamped the rail with the silver rings in my vise for electronic crafts to prepare for some time-consuming tinkering.

The nine inconspicuous rings initially all sit on two metal rails connected in the front, and they are also tied to one another through small metal rods (Figure 1). This restrictive suspension initially gives the impression that nothing can be changed at all in the entire construction, but the enclosed operating instructions indicate that there are indeed a limited number of possible moves.

Figure 1: At the start, all nine rings sit on the metal frame.

Ticket to Ride

The player moves one ring per turn by guiding it through the middle gap of the rail, either to lift it onto the rail or to remove it from there and move it down through the rail opening. The game is subject to precisely two restrictions: The first (outer right) ring can be moved freely at any time. Any other ring can only be moved if (a) its direct right-hand neighbor is up on the rail and (b) all other rings to its right are down.

In the initial constellation in Figure 1, two moves are possible: The player can pull off the first ring to the right, lift it up, skew it, and then let it drop down through the central opening in the rail. If the player leaves the first ring alone, the second ring on the rail can be considered as an alternative. Since the second ring from the right has only one ring to the right (ring number 1), which is also at the top of the rail, the former can be moved downward.

In the second case, the player pushes the right ring a little further to the right to the end of the rail (without dropping it) and at the same time pulls the second ring to the right, guiding it to the right out of the rail, then skewing it, and pushing it down through the rail gap.

The same is true for moving a ring from bottom to top; in Figure 2 ring 4 is down, while ring 3 is up, and rings 2 and 1 are down. According to the rules, the player can lift ring 4 up through the gap in the rail, guide it to the right past ring 3 at the edge of the rail, thread it from the right onto the rail, and then deposit it (Figure 3).

Figure 2: Ring 3 is at the top; rings 1 and 2 are at the bottom, so ring 4 …

Figure 3: … can be pulled up and placed at the top through ring 3.

As you can read on Wikipedia [3], all nine rings of the puzzle can be removed in a total of 341 moves, so that in the end – surprisingly – only the empty rail remains. The absolutely annoying thing about the procedure is that the player has to backtrack dozens of times, because to remove ring 9, for example, ring 8 must be at the top, but rings 1 to 7 must be at the bottom.

How does ring 7, which is initially on top like all other rings, reach the bottom? With ring 6 at the top, while rings 1 to 5 are at the bottom. How does ring 5 reach the bottom? With ring 4 at the top, while rings 1 to 3 are at the bottom.

And so it goes, back and forth, until finally ring 9 is at the bottom and then ring 8 – until finally ring 1 drops off after the 341st move. In general, the formula for the minimum number of moves for odd numbers is

increasing exponentially with the number of rings.

The player has to think carefully about which ring to turn next; a move in the wrong direction means you have to turn around later on and retrace your steps, because otherwise you will end up going round in circles instead of making progress.

Let's Automate!

At first glance, the repetitive moves with the rings might remind a mathematically inclined person of binary numbers, but those tend to change by more than one bit at a time. Just think of the sequence going from 0111 (5) to 1000 (6), where four bits (or rings) change at the same time. Gray codes [2] behave differently and change only by one bit at each step. Instead of 00, 01, 10, 11, Gray code, which is named after the physicist Frank Gray, counts 00, 01, 11, 10, and luckily, there's a simple formula to convert binary numbers to Gray code [3]:

num XOR (num >> 1)

According to the formula, the number 2 (binary 10), for example, becomes 11 thanks to the one-bit shift to the right, and the XOR operator (^) connects 10 and 01 to create 11, as it always returns a true bit if the bits of both operators differ at one point. Listing 1 [4] implements it in a simple Python script with the grayme() function. It gets the XOR operator from the operator package as the xor() function.

01 #!/usr/bin/env python3
02 import operator
03
04 def grayme(num):
05     shifted=num>>1
06     return(operator.xor(num,shifted))
07
08 def main():
09     for i in range(15):
10         print(i, format(i,"08b"),
11               format(grayme(i),"08b"))
12
13 if __name__ == "__main__":
14     main()

As a practical test, the for loop in the main() function iterates from line 8 on, over the numbers from 1 to 14, and outputs the number in each round in decimal, binary, and Gray code (Figure 4). Contrary to its philosophy ("There's one way to do it"), Python offers three different methods for string formatting à la printf(). Listing 1 uses the core function format(), which outputs integers with the format string 08b in 8-bit width as binary numbers with leading zeros. The print statement also outputs the decimal number i itself, as well as the Gray code generated with grayme() as binary bits.

Figure 4: Gray codes of the numbers 1 to 14 only differ by one bit from their predecessors.

Command or Library

The typical Python code snippet

if __name__ == "__main__"

checks if the script was called at the command line and, in this case, jumps to the main() function as of line 8. However, if the script was pulled into another script as a package using import graycode, it does not execute the main() code, but integrates the grayme() function into the script, which can then invoke it by calling graycode.grayme().

Alternatively, a Python script can import the function directly into its namespace using

from graycode import grayme

so that grayme() simply works there.