A Python script calculates the solution to the Chinese Rings puzzle
Time Waster – Solve the Chinese Ring Puzzle
Mike Schilli takes on the almost 2,000-year-old Chinese Rings puzzle. Instead of just jingling rings, he tries to find a solution with logical operators.
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.
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).
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.
Listing 1
graycode.py
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.
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.
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters
Support Our Work
Linux Magazine content is made possible with support from readers like you. Please consider contributing when you’ve found an article to be beneficial.
News
-
New Steam Client Ups the Ante for Linux
The latest release from Steam has some pretty cool tricks up its sleeve.
-
Gnome OS Transitioning Toward a General-Purpose Distro
If you're looking for the perfectly vanilla take on the Gnome desktop, Gnome OS might be for you.
-
Fedora 41 Released with New Features
If you're a Fedora fan or just looking for a Linux distribution to help you migrate from Windows, Fedora 41 might be just the ticket.
-
AlmaLinux OS Kitten 10 Gives Power Users a Sneak Preview
If you're looking to kick the tires of AlmaLinux's upstream version, the developers have a purrfect solution.
-
Gnome 47.1 Released with a Few Fixes
The latest release of the Gnome desktop is all about fixing a few nagging issues and not about bringing new features into the mix.
-
System76 Unveils an Ampere-Powered Thelio Desktop
If you're looking for a new desktop system for developing autonomous driving and software-defined vehicle solutions. System76 has you covered.
-
VirtualBox 7.1.4 Includes Initial Support for Linux kernel 6.12
The latest version of VirtualBox has arrived and it not only adds initial support for kernel 6.12 but another feature that will make using the virtual machine tool much easier.
-
New Slimbook EVO with Raw AMD Ryzen Power
If you're looking for serious power in a 14" ultrabook that is powered by Linux, Slimbook has just the thing for you.
-
The Gnome Foundation Struggling to Stay Afloat
The foundation behind the Gnome desktop environment is having to go through some serious belt-tightening due to continued financial problems.
-
Thousands of Linux Servers Infected with Stealth Malware Since 2021
Perfctl is capable of remaining undetected, which makes it dangerous and hard to mitigate.