## 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

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) isMOVE(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 ofSHIFT(a, b, c, k) isSHIFT(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

SPREAD similarly gives ^{-1}([1, 2, 3]).

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,

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 ^{th} depth, and that the recursive calls are to

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

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

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
- 3-Colors Tower of Hanoi
- 3-Colors Tower of Hanoi (Algorithm)
- Hanoing
- Sierpinski Gasket and Tower of Hanoi

|Contact| |Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny63802992 |