3-Colors Tower of Hanoi

3-Colors Tower of Hanoi (Algorithm)

By Stuart Anderson
6 February, 2006

Assumptions:

3 pegs, 3N disks of N different sizes, 3 colors of each size. Size N is the largest disk, size 1 the smallest.

Rules: A larger disk must never sit on top of a smaller disk. Equal size disks are OK to stack. The only allowed move is to transfer a single disk from one peg to another.

Starting Position: Each peg holds all N disks of a single color, ordered by size from largest (bottom) to smallest (top).

Ending Position: Same as starting position, but the colors of the stacks are rotated among the pegs, so that no peg holds the same color stack as it did in the starting position. In other words, a derangement of the stacks in the starting position.

Definitions:

A BASE of depth k is an arrangement of the k largest disks of each color (3k disks altogether) across all 3 pegs, so that no two disks of the same size are on the same peg.

A STACK of depth m is an arrangement of the m smallest disks of each color (3m disks altogether) into a single stack on one of the pegs, so that all three disks of each size (1 through m) are together on that one peg.

The idea:

Since there are very many positions possible, I will choose a subset of particularly simple positions that is broad enough to include all the absolutely necessary positions that must be used in a solution. By confining my moves to this subset, I will get a particularly simple algorithm, although it will not be possible to prove that it solves the puzzle in the minimum number of moves.

Since in order to effect a derangement of the largest disks, all the smaller ones must be gathered into a single stack, a stack of depth N-1 is necessary at some point. Since the starting and ending positions are bases of depth N, these are necessary positions as well. The simplest definition of a subset of all positions that would include these is this: A stack of depth k on top of a base of depth N-k. I will choose these to be the allowed positions. The starting and ending positions fit into this scheme with k = 0, and the intermediate stack fits with k = N-1.

I will only consider sequences of moves that start and end with allowed positions. There are four basic operations needed:

MOVE(a, b) moves the top disk of peg a to peg b. MOVE is invertible, and the inverse of MOVE(a, b) is MOVE(b, a).
SHIFT(a, b, c, k) moves a stack of depth k from peg a to peg b and ignores peg c. SHIFT is invertible, and the inverse of SHIFT(a, b, c, k) is SHIFT(b, a, c, k). It can be defined recursively just like the algorithm for the ordinary one-color Tower of Hanoi:
```
SHIFT(a, b, c, k)
{     
  if k > 0          
  {          
    SHIFT(a, c, b, k-1)
    MOVE(a, b)          
    MOVE(a, b)          
    MOVE(a, b)          
    SHIFT(c, b, a, k-1)         
  }    
}
```
GATHER collects the top layer of disks from a base onto the bottom of a stack of depth k-1 located at peg a, leaving the resulting larger stack on peg c, and using peg b as a temporary location. It can be defined non-recursively by calling SHIFT:
```
GATHER(a, b, c, k)
{
  MOVE(b, c)
  SHIFT(a, b, c, k-1)
  MOVE(a, c)
  SHIFT(b, c, a, k-1)
}
```
SPREAD is the inverse of GATHER, and distributes the bottom 3 disks from a stack of depth k on peg a to form a new layer on top of a base, and leaves the reduced stack on peg c, using peg b as a temporary location. It is defined much as GATHER:
```
SPREAD(a, b, c, k)
{
  SHIFT(a, b, c, k-1)
  MOVE(a, c)
  SHIFT(b, c, a, k-1)
  MOVE(a, b)
}
```

Some observations:

SHIFT reverses the color order in the bottom 3 disks of the stack. However, because SHIFT calls itself twice in each recursion, all disks above the bottom 3 have had their color order reversed an even number of times (in fact a power of 2). Hence all the color order in the stack is preserved, except for its very bottom layer of 3 disks. GATHER and SPREAD each call SHIFT twice, so that in practice, even the bottom layer of the stack has its color order preserved.

GATHER and SPREAD preserve a record of the color order of the base and the stack. If the colors are numbered 1, 2 and 3, then the color order of the top layer of the base can be thought of as a permutation of those numbers, call it B. Similarly, the color order in the bottom 3 disks of a stack is some permutation of [1, 2, 3] (ordered from the top down), call it S. The calling arguments of GATHER are some permutation of [1, 2, 3] as well, [a, b, c] = p([1, 2, 3]), where p is a permutation operation. As is easy to check (there are only a few cases) S = p(B). For instance, if the colors in the base are in the order 3, 2, 1, and if GATHER is called with parameters [a, b, c] = [1, 3, 2], its permutation is (2, 3). The permutation of the bottom 3 colors of the stack will then be (2, 3)[3, 2, 1] = [3, 1, 2].

SPREAD similarly gives B = q(S), where [c, b, a] = q^-1([1, 2, 3]). Note the order reversal here. In order for SPREAD to be a true inverse of GATHER, the stack has to start where GATHER left it, and end where GATHER found it. Also, of course, q is inverted because SPREAD takes S to B instead of B to S. In short, q is the inverse of the reverse of the parameter permutation of SPREAD. Examining the definitions of GATHER and SPREAD line by line shows that each operation in SPREAD(c, b, a, k) is the exact inverse an operation in GATHER(a, b, c, k), and that the operations are carried out in the reverse order.

Recursive GATHER and SPREAD:

I defined GATHER and SPREAD nonrecursively to make it clearer how they preserve color permutation information. For any given base + stack position, there are two possible ways to apply GATHER or SPREAD: if the stack of depth k is on peg 1, for instance, GATHER(1, 2, 3, k) and GATHER(1, 3, 2, k) could be applied. These would leave the stack in different positions and also leave the bottom three disks in the new larger stack in a different color order. Therefore, the only way to make GATHER and SPREAD recursive and still inverse of each other, is to define a standard choice if permutation at each depth in such a way that SPREAD is inverse to GATHER at each depth.

Such a choice would have to be made in any case, merely to make GATHER and SPREAD recursive; the point here is that the choices must be compatible. For both GATHER and SPREAD, the previous call to them must leave the stack in the starting position for the next call. I will chose to make GATHER always rotate the parameters backwards in the subroutine call, and SPREAD always rotate them forwards, as follows (new definitions replace the old definitions):

GATHER(a, b, c, k)
{
  if k > 1
  {
    GATHER(b, c, a, k-1)
  }

  MOVE(b, c)
  SHIFT(a, b, c, k-1)
  MOVE(a, c)
  SHIFT(b, c, a, k-1)
}

SPREAD(a, b, c, k)
{
  SHIFT(a, b, c, k-1)
  MOVE(a, c)
  SHIFT(b, c, a, k-1)
  MOVE(a, b)

  if k > 1
  {
    SPREAD(c, a, b, k-1)
  }
}

With these definitions, it is easy to check that SPREAD(c, b, a, k) is the inverse of GATHER(a, b, c, k) at the k^th depth, and that the recursive calls are to SPREAD(a, c, b, k-1) and GATHER(b, c, a, k-1), which are inverses at the k-1 depth. Therefore, the recursive SPREAD and GATHER are inverses at all levels.

Now the solution to the 3-color Tower of Hanoi with 3N disks is:

GATHER(1, 2, 3, N)
SHIFT(3, 2, 1, N)
SHIFT(2, 1, 3, N)
SPREAD(1, 3, 2, N)

The first line gathers all the disks into a stack on peg 3, and the next two lines move the stack to peg 1 (using 2 SHIFT calls, because doing it with just one would leave the bottom 3 disks on the stack in the wrong order). Since GATHER has put all the disks onto 1 peg, the SHIFT operations are equivalent to permuting the pegs with the permutation (1, 2, 3). Normally the inverse of GATHER(1, 2, 3, N) would be SPREAD(3, 2, 1, N), but because of the permutation of peg positions, the correct inverse has parameter order (1, 2, 3)[3, 2, 1] = [1, 3, 2]. Because the parameters have been rotated, SPREAD is "fooled" into distributing the colors onto different pegs than the ones they started on. In fact, the colors of the final position are permuted by the same permutation mentioned just above, (1, 2, 3).

In general you could solve the puzzle for whatever cyclic permutation of the colors you wanted by defining:

PERMUTE(a, b, c, N)
{
  GATHER(a, b, c, N)
  SHIFT(c, b, a, N)
  SHIFT(b, a, c, N)
  SPREAD(a, c, b, N)
}

This will not work, I think, for non-cyclic permutations [a, b, c].

Well, that's it. It is more complicated than the solution to the 1 color Tower of Hanoi, and it may not be optimal, but it clearly works. Perhaps some use could be made of the fact that GATHER and SPREAD keep the color permutation information in a recoverable form to make a true "next step" algorithm.

(The algorithm has been implemented in a Java simulation.)

Tower of Hanoi
Tower of Hanoi, the Hard Way
Bicolor Towers of Hanoi
- Bicolor Towers of Hanoi, Solution
3-Colors Tower of Hanoi
3-Colors Tower of Hanoi (Algorithm)
Hanoing
Sierpinski Gasket and Tower of Hanoi

72103945