The Quaternary Gray Code and Ziggu Puzzles

Those who have held a Ziggu puzzle may have stumbled upon this approach to exploring its configurations: modify the leftmost piece that does not undo the most recent modification. Pleasantly, this approach will eventually solve the puzzle. Moreover, it does so in as few moves as possible. However, it isn’t immediately clear how many moves are made during the solution. We prove that exactly $6\cdot 2^n-3n-5$ states are on the shortest solution, and we refer to these states as Ziggu states or strings. Furthermore, if one replaces “leftmost” with “rightmost” then the exploratory approach again solves the puzzle, and it does so in as many moves as possible. In fact, this longest solution visits every one of the $(3^{n+1}-1)/2$ states, and it is the only solution to do so. Both of these formulae assume that state is encoded as one of the $4^n$ quaternary (i.e., base $4$) strings with $n$ digits, as explained later on. These three formulae are summarized in Table 4 and they explain why Ziggu puzzles can be considered to be $4$-ary, $3$-ary, or $2$-ary exponential puzzles.

These results imply that Gray code puzzles are simpler than Ziggu puzzles. This is because Gray code puzzles can typically be solved using a similar exploratory approach: modify the only piece that does not undo the most recent modification. In fact, in most Gray code puzzles there is never a choice of which piece to modify (so long as the previous modification is known) and this approach gives the only solution.

We show that the connection between Ziggu puzzles and Gray code puzzles runs even deeper. In Gray code puzzles each state can be represented by an $n$-bit binary string, and the next state is obtained by flipping the bit according to the binary reflected Gray code. Similarly, the longest and shortest solutions to Ziggu puzzles can be understood using the quaternary (i.e., base $4$) reflected Gray code. More specifically, the longest solution is obtained by skipping over invalid encodings in the quaternary reflected Gray code, and the shortest solution is obtained by additionally skipping over non-Ziggu states in the longest solution. This is illustrated in Figure 4 and the gaps in Table 1.

The aforementioned results show how to solve Ziggu puzzles from the start configuration to the target configuration in one sitting. However, a solver may wish to leave the puzzle in a state that is part way through the longest or shortest solution. To help with these situations we provide $O(n)$-time comparison and successor algorithms, which give the relative order of two states and the next state, respectively.

A preliminary version of this paper has additional material [7] including ranking and unranking (see Section 11). Its longer title also pays homage to an article by Martin Gardner [5] (see also [6]) which discusses the Gray code and several of the aforementioned puzzles.

Section 2 provides background on Gray code and Ziggu puzzles. Section 3 gives a non-technical description of how to solve Gray code and Ziggu puzzles. Section 4 explains our Ziggu maze abstraction and how the mazes are formed in Zigguflat and Zigguhooked. Section 5 derives recursive formulae for shortest and longest solution lengths. Section 6 cover the binary and quaternary reflected Gray codes. Section 7 provides recursive descriptions of Gray code and Ziggu puzzle solutions. Sections 8 and 9 present the successor rules and comparison formulae for the solutions to these puzzles. Section 10 presents loopless algorithms for generating the shortest solution to Ziggu puzzles. We end with final remarks in Section 11. Omitted proofs follow from first principles or appear in [7].

The most famous family of exponential puzzles is the Gray code puzzle family, which are related to the well-known pattern of binary numbers or words known as the binary reflected Gray code (BRGC) or simply “the” Gray code [13]. A sampling appears in Figure 5.

The family contains vintage puzzles including Spin-Out (see [16] and [3]) and The Brain. In these puzzles the underlying state space or state graph is simply a path labeled by the Gray code. The ends of the path are $0^n$ and ${10}^{n-1}$ and correspond to the first and last words in the Gray code. The state $1^n$ also features prominently as it is the start or target state in many of the puzzles. For example, the state space of The Brain with $n=4$ pieces appears in Figure 2(b) and the state space for Spin-Out with $n=3$ dials appears in Figure 11(a).

Most famously, the family contains two historical puzzles. In the Towers of Hanoi the Gray code provides the shortest solution of length $2^n$ among its $3^n$ states, and in Baguenaudier (or “Chinese Rings”) [17] the state space is the Gray code except that some pairs of moves can be made simultaneously.

Perhaps the most direct implementation of a Gray code puzzle is B-Bar by Felix Davis. As in The Brain, its state space is the path formed by $\mathrm{𝖡𝖱𝖦𝖢}(n)$, however, in this case the puzzle begins and ends at the two extreme nodes. More broadly, Hamilton paths have been used as the basis for other sequential puzzles, including Hamilton’s Icosian game [15, 14].

The Gray code puzzle family also includes puzzles in which solutions are variations of the Gray code. For example, Rudenko’s Disc can be seen as a variation of the Towers of Hanoi. More specifically, the rule that larger discs cannot be placed on top of smaller discs is replaced by a physical limitation that disc $i$ can only be pushed down $i$ positions from the top of each channel. In other words, disc $i$ can have at most $i-1$ discs on top of it, but the discs on top can have any number. As a result, the binary reflected Gray code provides a solution, but not the shortest. Panex Jr and Stacker by CoreMods further refine this idea by limiting the height of one of the channels (i.e., pegs) thereby lengthening the solutions.

The Towers of Bucharest restricts the Towers of Hanoi by not allowing discs to move directly between the left and right pegs. The puzzle is also known as Linear Towers of Hanoi. Regardless of its name, the unique solution visits all $3^n$ states in ternary Gray code order [20, 10, 11], and so it is also the longest possible solution to the Towers of Hanoi (see Figure 2). Another puzzle that follows the ternary Gray code is Crazy Elephant Dance [2].

The Ziggurat puzzle was created by Eitan Cher and Bram Cohen and submitted to the 2021 Puzzle Design Competition [1]. The puzzle is notable for several reasons. It is an exponential puzzle since it consists of some number of (nearly) identical pieces and the number of steps required to solve the puzzle grows exponentially in some base. Unlike previous puzzles of this type it is a burr meaning that the goal is to fully disassemble (or reassemble) it. It is also frameless meaning that the puzzle consists only of its pieces without any other structure holding it together.¹¹1Note that the black base in Figure 6(a) is simply a stand and is not part of the puzzle. The name of the puzzle is based on how the pieces are initially stacked into a 3-dimensional pyramidal configuration resembling a ziggurat temple. The underlying maze mechanic underpinning the puzzle is discussed in Section 4.

Oskar van Deventer implemented the same underlying maze structure in a variety of creative ways in subsequent puzzles including Zigguflat, Ziggutwist, Ziggutwist Too, Zigguchain, Zigguhooked, Ziggutrees, and Ziggustretch. All of these puzzles are seen in Figure 6 with $p=6$ pieces. In some of these puzzles the mazes can be clearly seen (e.g., Zigguflat) while in others they are partially obscured (e.g., Ziggutwist) or fully obscured (e.g., Ziggustretch). Ziggu puzzles are typically color-coded so that the red piece is the only one that can be modified in the starting configuration. Right-handed solvers often hold the puzzle with this piece on the right. We’ll assume this orientation in our discussions, and we’ll also refer to the red piece as the first piece, the orange piece as the second piece, and so on. (In Ziggurat the bottom piece is the first piece.)

While each Ziggu puzzle is unique, they fall into two primary categories, summarized in Table 3. Ziggurat, Zigguflat, Ziggutrees, and Ziggustretch (Figures 6(a)-6(d)) are all 4-neighbor puzzles, meaning that each piece touches at most four other pieces. In particular, Figure 6(b) shows that the yellow piece touches the orange and red pieces in one direction, as well as the blue and green pieces in the other direction. On the other hand, Zigguchain, Zigguhooked, Ziggutwist, and Ziggutwist Too are all 2-neighbor puzzles, as each piece touches up to two other pieces. This is easily seen in Figures 6(e)-6(h), where the pieces are arranged linearly and each piece touches its left and right neighbor.

In the remainder of this paper, we consider Zigguflat and Zigguhooked as examples of 4- and 2-neighbor puzzles. These have the advantage of using distinctly different implementations of the Ziggu maze while still being planar, which makes the mechanics visible. As noted in Table 3, while both Zigguflat and Zigguhooked consist of $p=6$ pieces, Zigguhooked will take longer to solve since it has $5$ mazes, while Zigguflat has only $4$ mazes.

Despite these seemingly large differences, all of the Ziggu puzzles are identical in an abstract sense. More specifically, all Ziggu puzzles with $m$ mazes have identical state spaces and solutions.

Gray code puzzles and Ziggu puzzles can be solved using the same basic principle: don’t look back! This means that you should never reverse your progress by undoing your most recent move. This advice is enough to solve many Gray code puzzles due to the following: Gray code puzzles have at most one non-reversing move. In other words, when you move to a new state there is at most one move that doesn’t take you back to your previous state. In some puzzles (e.g., Spin-Out) the only complication is that there are two different moves that can be made from the start state; the wrong first move leads toward a dead-end from which you need to undo your final move and then never look back. That is, the state space is a path and only one direction takes you to the solution. For example, the neighbors in Spin-Out²²2A design flaw in the initial run of Spin-Out puzzles introduces more states and shorter solutions by allowing dials on the right to be rotated to the right. This can be fixed by extending the right end of the frame. Our discussion of Spin-Out ignores the flaw. are illustrated in Figure 7. In Towers of Hanoi there can be two non-reversing moves, but this reduces to one when putting additional restrictions on how and when to move the smallest disc.³³3On every odd numbered turn, move disc $1$ one peg to the left (right) for even (odd) $n$.

Ziggu puzzles are more challenging than Gray code puzzles due to the following: Ziggu puzzles can have more than one non-reversing move; hence Ziggu puzzles have solutions of different lengths. A puzzle with $m$ mazes and $n=m+1$ digits can have up to $\lceil \frac{n}{2}\rceil +1$ non-reversing moves⁴⁴4For example, the state $2020\mathrm{\cdots }202$ (see Section 4) allows changes to each $2$ and the last $0$.^,555The shortest solution only visits states with up to two non-reversing moves. In this sense, Ziggu puzzles remain relatively simple until you go off course.. Figure 8 gives an example of such a state in Zigguhooked. While Ziggu puzzles have more complicated states, the unique shortest and longest solutions are generated by simple extremal versions of the basic don’t look back principle: For the shortest/longest solution, always make the leftmost/rightmost non-reversing move. Since there is only one available move from the start state, you always begin by moving in the correct direction. Besides the start state, the only other “dead end” is the solution state. As a result, you’ll never need to backtrack over previous moves. However, you can return to a previous state by going around in a circle (i.e., through a cycle of states) if you don’t follow either of the extremal versions of the basic principle.

By design exponential puzzles take a long time to solve, and solvers may wish to take a break. Trouble will ensue if a solver resumes by undoing the last move they made before taking a break. This can be avoided by recording the last move made. In fact, less information is needed: we only one bit of information. One literal bit.

Gray code puzzles have a “metronome” property wherein every second change involves the first piece. The change sequence follows the binary ruler sequence: $1,2,1,3,1,2,1,4,1,\mathrm{\dots }$ (Oeis A001511). So you only need to remember if your most recent move involved the first piece or not. The metronome property holds for puzzles that start in an intermediate state (e.g., Spin-Out) although the change sequence is a (reversed) subsequence of Oeis A001511.

The shortest solution to Ziggu puzzles instead have a “stair-climbing” property wherein successive changes differ by at most one: $1,1,1,2,1,1,1,2,1,1,1,2,3,2,1,\mathrm{\dots }$. Suppose that you always make the $1$ moves in succession (i.e., when changing the first piece you do it three times in a row). Treating each $1,1,1$ as a single $1$ is natural in most of the Ziggu puzzles (e.g., the first dial in Zigguhooked moves freely between its two extreme states $0$ and $3$). With this assumption you just remember if your most recent move went up (e.g., $2$ then $3$) or down (e.g., $3$ then $2$). In the first case you will attempt to move up again (e.g., $2$ then $3$ then $4$); if the puzzle does not allow this, then you will move down (e.g., $2$ then $3$ then $2$). In the second case you move down again (e.g., $3$ then $2$ then $1$) or repeatedly move the first piece.

Here is a general tip to avoid undoing your work in a Gray code or Ziggu puzzle: Never pause after changing the first piece or going down.

For example, the $3$-Ziggu maze with state $(0,1),(2,0),(3,2)$ has the maze representation . While there are $6$ digits in the state description, since $r_1=c_2$ and $r_2=c_3$, we can describe the state of this $3$-Ziggu maze with $4$ digits with the base $4$ string $1023$.

Definition 1 immediately gives a bijection between the set of $m$-Ziggu mazes and the set of length $m+1$ base $4$ strings in which $3$ is the only digit appearing to the right of a $3$.

The first puzzle in the Ziggu family was Ziggurat. Each Ziggurat piece contains a Ziggu maze, and successive pieces have alternating chirality. For example, the blue pieces in Figure 6(a) have an $𝖲$ -shaped maze and the orange pieces have an $𝖲$ -shaped maze. The bottom of each piece contains a nub that navigates the maze two pieces below it. For example, the nub of the top blue piece passes through the top orange piece and stays within the maze of next blue piece. The puzzle is solved when every maze is solved (i.e., every nub reaches the end of its respective maze) which allows it to be disassembled. The challenge comes from the fact that consecutive pieces move in lockstep in one of the two directions of the maze. This is accomplished by the railing at the bottom of each piece slotting into the channel of the piece below it, as shown on the right side of 6(a). As a result, making progress in one maze can involve moving to the opposite end of the previous maze, and this cascade of back-and-forth movements gives the puzzle its exponential nature. The Ziggurat puzzle inspired Oskar van Deventer to create the vast family of Ziggu puzzles shown in Figure 6. These puzzles all use the Ziggu maze, but they feel distinct and provide differing enjoyable puzzling experiences.

The Zigguflat puzzle consists of $p=6$ interlocking pieces as shown in Figure 6(b). The mazes are cut into the green, yellow, orange, and red pieces, and those mazes are navigated by $𝖳$-shaped nubs of the purple, blue, green, and yellow pieces, respectively. Therefore Zigguflat has $m=p-2=4$ mazes. Notice that the orange and red pieces only do not have $𝖳$ -shaped nubs and the purple and blue pieces do not have mazes so that the fully assembled puzzle is a rectangle. As the commercial version of Zigguflat has $m=4$ mazes, it requires $n=m+1=5$ digits to describe its state. See Figure 10(a) for an example. To read off the digits describing the state of the commercial Zigguflat puzzle with 6 pieces, the first four digits describe the vertical positions of the purple, blue, green, and yellow nubs within the mazes they navigate, respectively. The final fifth digit describes the horizontal position of the yellow nub within the red maze.

The Zigguhooked puzzle consists of $p$ interlocking dials with $p=6$ in the commercially available version (see Figure 6(f).) Each maze is formed at the interface of two consecutive dials, so there are $m=p-1$ mazes in total. The rotation of the dials are described by $n=p$ digits. Given a pair of adjacent dials, rotating the left dial changes the vertical position within the maze, while rotating the right dial changes the horizontal position within the maze. One can also read the digits off of the dials without examining the mazes. The radial positions are numbered increasing in a counterclockwise direction, where the states $0$, $1$, $2$, and $3$ correspond to the arrow pointing in the approximately 3:45, 3:15, 2:45, and 2:15 directions of the hour hand on a clock face, respectively. So a Zigguhooked puzzle in the state $0213$ would have its dials in position $\to$ $\to$ $\to$ $\to$ . See Figure 10(b) for an example.

As was shown in Table 2, most Gray code puzzles run between states that are encoded as $0^n$ and ${10}^{n-1}$, or between $0^n$ and $1^n$ (or vice versa).

We previously saw the recurrences for the number of moves $f(n)$ and the number of states $g(n)$ required to solve the Towers of Hanoi in Section 1. These holds for B-Bar as well. The two recurrences are provided in the top of Table 5. Theorem 2 substitutes in closed forms of these recurrences.

Recurrences for the number of moves $f(n)$ and the number of states $g(n)$ required to solve Spin-Out appear in Figure 11(b). These hold for Baguenaudier and The Brain as well. The two recurrences are provided in the bottom of Table 5. Theorem 3 substitutes in closed forms of these recurrences.

Ziggu puzzles always have the same start state and target state, so these factors do not result in different recurrences. However, these puzzles have different shortest and longest solutions, so we will still develop two different pairs of recurrences. The principle behind our recurrences can be found in Figure 12. More specifically, this figure shows how the shortest and longest solutions in a Ziggu maze puzzle can be expressed in terms of the solutions to smaller Ziggu maze puzzles. Figure 13 and 13 then illustrates the recurrences for the shortest and longest solutions in Zigguhooked, respectively. All four recurrences and summarized in Table 6. Theorem 4 substitutes in closed forms of the respective formulae.