The Tower of Hanoi and Variations

Classic Hanoi

According to Rouse Ball, the original puzzle was invented by the French mathematician Lucas, in a paper published in 1883. Equipped since with an entirely bogus "ancient oriental" provenance, it has sporadically been sold as a children's puzzle under the name Tower of Bramah. It comprises a base plate on which is mounted a row of m vertical pins, and a stack of n perforated discs of graduated diameters. Initially the stack is placed on the left-most pin in decreasing order of size, and the Classic problem is to transfer all n discs in the minimum time (number of moves) using m = 3 pins :---

For an illustration, run the HanoiVar demonstration program and select the (default) option Classic. There is a considerable quantity of other programs on the Web which implement this version of the puzzle: some of the better ones are listed in M. Kolar's directory.

The standard approach to solving the Classic puzzle is via recursion from the largest disc down.

[See the Java method <I>tranC(Disc disc, Pin X, Pin Y, Pin Z)</I> in class <I>ClassicDefn</I>.] This algorithm is easily seen to be optimal by induction - for the largest disc to move, it is plainly necessary that all smaller discs are on the third pin. Similarly, it is unique: there is no choice about which disc may be moved at a given time. Also by induction we find the optimal time T(n) to transfer n discs: since T(n) = T(n-1) + 1 + T(n-1) for n > 0 and T(0) = 0, and the unique solution to these equations is T(n) = 2n - 1.

Though very directly implementable on computer via any modern programming language, recursion by largest disc is far from being a man-friendly technique. However, watching the motion of individual discs suggests a completely different algorithm: approaching the problem from the small end as it were, it may be shown that

The smallest disc motion is "clockwise" X to Y to Z to X ... for n even, "anticlockwise" X to Z to Y to X ... for n odd; in general, discs cycle in alternate directions, from the largest (anticlockwise) upwards.

This property leads to a slightly more involved algorithm [method <I>tranC(Pin X, Pin Y, Pin Z)</I> in class <I>ClassicDefn</I>] with period 3 moves, which is entirely iterative; the elimination of the recursion renders it sufficiently man-friendly to execute manually, to the amazement of your friends [the more nerdy, maybe]:

[The smallest disc moves when t mod 2 = 0.] Alternatively, select HanoiVar option Classic_P --- inevitably, this is indistinguishable from Classic by the uniqueness of the solution path, although inspection of the program reveals that the algorithms are quite distinct.

We may think of the discs in the Classic puzzle as coloured alternately green and red from the top of the stack downwards; indeed, we may even continue the colour scheme to include the bases of the pins, so that if (say) n is even then the largest disc will be coloured red, the left-hand base green, the middle red and the right-hand green. This colour-scheme emphasises the rather surprising fact that, throughout the solution :---

It can be shown that this property characterises the configurations along the optimal solution, from which we can deduce another man-friendly "bichromatic" algorithm:

[There is only one such colour-consistent move; initially, there is only one possible move; finally, there is no possible move other than reversing.] In addition, it is now easy to tell whether a given configuration lies on the optimal solution path: when the colours don't alternate, you've gone wrong! Classic leaves the bases uncoloured, but Classic_P colours them in order to emphasise this behaviour.

These two nontrivial characterisations of the Classic solution --- via cyclic direction, or via disc colour --- inspire a number of intriguing variations on the original puzzle, in the form of extra restrictions on the moves permitted. These vary from the trivial (Adjacent), through the elegant (Cyclic) and vicious (Domino), to unproven (Reves) and unconjectured (Reversi).

Cyclic Hanoi

We mentioned that in the classical solution, discs shift cyclically in alternate directions (left for largest colour, right for the other); Knuth suggested introducing the additional constraint that [say clockwise, from left to middle to right]; as before, the problem is to transfer the stack from left pin to right, or cyclically "leftwards", in the minimum possible time [which will now surely increase]. Quite obviously, we could have posed a distinct problem by demanding instead that all discs move anticlockwise; a little reflection reveals that this new problem is equivalent to transferring the pile from left pin to middle, or cyclically "rightwards", using clockwise moves.

Illustrations of the solutions to both problems are provided by selecting the Cyclic and Cyclic_R options in HanoiVar. Atkinson published a short analysis of the solution, which essentially as follows. Using recursion by largest disc as before, we find that now discover that the the two problems are mutually interdependent: transferring rightwards is much the same as before, except that it involves transferring the smaller stack leftwards; but transferring leftwards is slightly more complicated :---

As before, the solutions are unique and optimal.

Let A(n) and C(n) denote the times for leftwards and rightwards Hanoi with n discs. Then immediately from the above algorithm,

A(n) = A(n-1) + 1 + C(n-1) + 1 + A(n-1),
C(n) = A(n-1) + 1 + A(n-1),
A(0) = C(0) = 0.

It is an easy exercise in elementary algebra to verify the following recurrence in A(n) alone

A(n+3) = 3A(n+2) - 2A(n),
A(0) = 0, A(1) = 2, A(2) = 7;
the explicit formula for A(n)
A(n) = (xn+2 - yn+2)/4(31/2) - 1,
where x = 1+31/2 = 2.7320...
and y = 1-31/2 = -0.7320...
and 31/2 denotes the square root of 3;
with similar formulae for C(n) = 2A(n-1) + 1.

For Cyclic_L and Cyclic_R puzzles, the bases and discs are shaded in a curious fashion: initially the entire stack is orange, but as a discs move it may change to blue, or back again --- think of them as flat, flipping over to show their reverse side. Adjacent colours need not alternate. To complete our definitions, we also assign a colour to the bases, considered just larger than the largest disc: orange for leftward transfer, blue for rightward.

In detail, the colour-changing rule is that :---

It can be shown that, throughout the solution :--- and that this property characterises configurations along the optimal solution. The resulting man-friendly "coloured" algorithm is :---

Finally an attactive exercise in elementary Markov chains is to show that, throughout the configurations of a cyclic solution for large n, on average approximately

Rainbow Hanoi

We mentioned that in the Classic solution, discs coloured alternately with two colours remain coloured alternately. R. Neale suggested instead colouring the discs cyclically with three colours --- Hanoivar employs green, blue, red, ... from the smallest down -- then obeying the analogous additional restriction, in the form

The bases in the given problem are uncoloured, but immediately we attempt to construct a solution via recursion, we have to consider a number of subsidiary problems in which some or all of the bases are also coloured. This new complication prompts us to develop a systematic notation for such problems and the time taken to solve them. The colours of the larger discs depend of course on the remainder of n modulo 3 ; we denote these lower colours simply A, B, C, ..., from the largest disc A upwards, with D denoting uncoloured.

Then PQR(n) denotes the (optimal) time taken to transfer all n discs from the left pin via the middle to the right, under the Rainbow rule, with the bases coloured P, Q, R respectively [where P, Q, R denote any of A, B, C, D]. For example, DDD(n) denotes the problem with all bases uncoloured; BAC(n) the problem where the left, middle, right bases are coloured B, A, C. Both solutions are illustrated by HanoiVar, under Rainbow, Rainbow_C.

We shall just sketch the argument from this point on: detailed proofs have been prepared in particular by Lunnon and by Minsker. Potentially, we have 64 separate functions to consider, but these can be reduced by discarding reflections such as CAB(n) = BAC(n) [the moves of one being the moves of the other reversed, and in the reverse order], insoluble problems such as BBC(n) [not immediately obvious!], and those such as BAD(n) which in practice fail to occur in the course of the recursion [as it descends from all bases uncoloured to all coloured.] Each of the distinct 11 remaining problems has to be broken down recursively into two or three problems involving only n-1 discs, as for transfer_right and transfer_left in Cyclic. In this form the solution can be programmed as 17 mutually recursive procedures.

To evaluate the time functions, it's advisable to recast the recursions formally as a Markov chain (Feller chap.15), that is as simultaneous first-order linear recurrences in one variable with constant coefficients. These may be expressed concisely by the vector equation

s(1) = (1,1,1,1,1,1,1,1,1,1,1,1),
s(n+1) = M s(n).
where the vector s and matrix M are defined by
s = (DDD,CDD,CBD,CAD,BCD,BDC,CDC,CBC,BAC,CAC,BCB, 1),
M = 
            | 0,2,0,0,0,0,0,0,0,0,0,1 |
            | 0,1,1,0,0,0,0,0,0,0,0,1 |
            | 0,0,0,1,1,0,0,0,1,0,0,2 |
            | 0,0,0,0,0,0,1,1,0,0,0,1 |
            | 0,0,0,0,0,1,0,0,1,0,0,1 |
            | 0,0,1,1,0,0,0,0,0,0,0,1 |.
            | 0,0,2,0,0,0,0,0,0,0,0,1 |
            | 0,0,0,0,0,0,0,0,2,0,1,2 |
            | 0,0,0,0,0,0,0,1,0,1,0,1 |
            | 0,0,0,0,0,0,0,2,0,0,0,1 |
            | 0,0,0,0,0,0,0,0,2,0,0,1 |
            | 0,0,0,0,0,0,0,0,0,0,0,1 |

To solve such equations, compute the characteristic polynomial of the matrix, which comes out as (discarding an irrelevant factor -E) :---

E10 - E9 - 2E8 - 7E7 + 5E6 + 8E5 + 14E4 - 2E3 - 4E2 - 4E - 8
= (E - 1)(E5 - 3E2 - 2) (E4 - 2E2 - 6E - 4).
Interpreting E as the shift operator taking n -> n+1, the coefficients of this polynomial give an order 10 linear recurrence satisfied by DDD(n) (as well as by the other 10 functions); and its maximal (quartic) root x = 2.3117... gives the asymptotic complexity of the time :---
DDD(n) ~ 0.6576 (2.3117...)n.

We're still not quite out of the wood, because we have been concealing an embarrassing fact: 3 of the above problems (DDD, CDD, CDC) could in principle be broken down recursively into either two or three sub-problems. It's a pretty reasonable bet that using two rather than three is going to be faster, but that doesn't constitute a proof; indeed in one instance, the alternatives are equally fast:

CDC(3) = 11 = 2 CBD(2) + 2 = 3 BDC(2) + 3 .
To dispose of this apparently minor formality turns out to require careful analysis of the relevant recurrences. To begin with, notice that a sequence generated by a recurrence such as
E - 1, or E5 - 3E2 - 2, or E4 - 2E2 - 6E - 4,
where each term is a positive combination of those preceding, must have only terms which are non-negative, provided sufficiently many (here 5 or 4) of its initial terms are. The order 10 recurrence above is not of this form; however all its factors are, which permits any sequence it generates to be decomposed into a series of auxiliary sequences, each of which does possess the property. By inspecting the initial terms of each of these, we in turn show that each is non-negative. Carrying out this program for the sequence of differences between three- and two- subproblem solution times, it may be shown that that the former is never shorter. [A similar argument is needed to show that any combination of the two solutions must produce a time intermediate between them.] Finally, there are some irritatingly trivial possibilities to be eliminated for n<4, where a subproblem impossible for larger n happens to offer a feasible alternative: CDC(3) is a case in point.

Towers of Antwerp

This variation is credited by Minsker to Derick Wood. Initially there are not one but three stacks of n discs, one on each of the m = 3 pins, coloured all red, all white, all blue respectively. The problem is to simultaneously transfer all three stacks cyclically, so that finally they will be all blue, white, red. [For this purpose, a disc may be placed on top of a larger or equally large one, of any colour.] As usual, we are interested in (if possible) an optimal solution.

Largest-disc induction suggests something along the following lines:

With all the subsidiary operations defined (recursively) as simply as possible, this algorithm would certainly be optimal, and (modulo a few permutations) unique, if it solved the problem; in particular for n = 1 it costs just 5 moves to permute the 3 lone discs, which is easily seen to be optimal.

Unhappily, it then turns sullen: for n = 2, no amount of juggling with the order of collection and redistribution can persuade it to do other than either transpose only two or leave all unchanged at smaller levels. At this point Minsker's solution performs an mysterious detour: for n > 1, he deliberately moves two largest discs consecutively between the same two pins, thereby "wasting" a move, which unexpectedly contrives to induce all subsequent discs to assume their correct positions at no further cost. Since a single extra move is plainly incapable of further improvement, the algorithm must be optimal.

The modified, optimal algorithm now reads

Individual subsidiary operations required above are as follows:

[Notice that in the Java program, the corresponding transfer methods tran33() etc take Disc rather than Pin arguments, which may cause confusion in human readers!]

Expressing the recursions for n > 1 as a matrix recurrence equation,

s(1) = (6,2,2,3,1),
s(n+1) = M s(n).
where --- introducing the extra constant function 1 to account for individual disc moves ---
s = (T33, T31, T13, T11, 1),
M = 
            | 0,2,0,4,6 |
            | 0,1,0,2,2 |
            | 0,0,1,2,2 |.
            | 0,0,0,2,3 |
            | 0,0,0,0,1 |
By solving the resulting recurrence explicitly, the time can be shown to be
12 (2n) - 8 n - 10 moves for n > 1;
0, 5 moves for n = 0, 1.

In the demonstration Antwerp, the Discs field contains the number n of discs per stack. It would plainly also be feasible to consider the generalised problem involving m > 2 stacks, but as far as we are aware this remains unexplored.

Reves Puzzle & Many-Pin Hanoi

The generalisation of the Classic puzzle to m = 4 pins is discussed in a number of existing places: Stockmeyer's survey is a good starting point. Here we just summarise the facts, without any attempt at proof. Strictly speaking, the problem of finding the optimal solution remains unsolved, since the standard development relies on assuming that some optimal solution exists which satisfies the Frame hypothesis :--- This reasonable and apparently innocuous assumption is not infrequently completely overlooked by intending solvers, despite which Knuth has observed that it is in reality very hard; a little light on the reason for this will later be cast on examining another variation, Reversi.

Selecting Reves illustrates this standard solution, which proceeds by induction on both n and m, for m = 4. Given n discs initially on pin W to be transferred via X and Y to Z, having carefully chosen some small k between 1 and n, split the stack into the bottom (largest) k discs and the top n-k. Now transfer the top recursively to an intermediate pin, say X, for which task all 4 pins are available. X is now unavailable to the bottom, so transfer these from W via Y to Z using 3 pins only. Finally, transfer the top from X to Z using all 4 pins again.

To understand the optimal choice of k, it's helpful to watch what happens in the special case when n is the k-th "triangular" number, n = 1 + 2 + ... + (k-1) + k = k(k+1)/2: first the bottom k are split off, then the next k-1, and so on down to 1. For such n this is the only possible choice for k in the Frame algorithm; but for k(k+1)/2 < n < (k+1)(k+2)/2, k+1 may be used instead. As a result, Frame-type solutions are not unique.

The time to transfer n discs by this method is :---

Since k is close to the square root of 2n, this grows very roughly as (221/2 = 2.6651) raised to the power n1/2, which is sub-exponential; so no nice linear recurrence may be expected for this function.

[It is noteworthy that when n is triangular, the smallest disc moves only at times divisible by 4. This phenomenon has been analysed by Stockmeyer (private communication), via decomposition of the solution into transfers of "superdiscs" or substacks of size k.]

Once this solution is understood for m = 4 pins, it may be generalised straightforwardly to arbitrary m. Instead of triangular numbers we use binomial coefficents nCm = n!/m!(n-m)! ; now assuming m > 2, n > 0,

giving the size k = k(m,n) of the bottom sub-stack [method k_mn(m,n) in class ClassicDefn of HanoiLib.java].

If n = 0 the transfer is nugatory; otherwise, if m = 2 we should find n = 1, and the transfer just moves the disc; otherwise, we have the following solution algorithm, recursive in both m,n. The set P initially comprises all pins except the first and last; the function k(m,n) is defined in terms of the current m,n as above.

An expression for the time in the special case where n = n0 = s+m-3Cm-2, and the only possibility is k = s+m-4Cm-3, follows from noticing that in any Frame-type solution the largest disc makes 1 move, the next (m-2) make 2, the next m-1C2 make 4, etc, down to the smallest k making 2s-1. For general n there are a further n-n0 small discs making 2s, giving total time

The first expression has s terms; binomial series summation gives the second expression with m terms, more illuminating when m << n (many discs, few pins). To evaluate s numerically, notice that it is roughly the (m-2)-th root of n(m-2)!, from which the exact value can be located by trial-and-error adjustment.

An illustrative snapshot of the solution in operation is provided by the special case n = s+m-3Cm-2 above at exactly half-time, when pin 1 is empty and for 0 <= i <= m-2 the sub-stack on pin m-i comprises the next s-2+iCs-2 discs in descending order of size. For instance, taking m = 6 pins, s = 4, n = 7C4 = 35 discs, the time equals 20 3C3 + 21 4C3 + 22 5C3 + 23 6C3 = 1+8+40+160 = 209; after move 105 there are

The Many_Pin option will illustrate this algorithm perfectly happily for say n = 1000, m = 100 --- though it must be admitted that for this selection of parameters, the display might be considered a trifle enigmatic.

Turtle & Multi-Stack Hanoi

The multiple coloured stacks of the Antwerp problem are further constrained by forbidding any disc to move onto another of equal diameter. This in turn demands the introduction of extra pins, which are also coloured so that only discs of matching colour are permitted to utilise them. This variation is credited to Victor Mascolo.

The simplest version is illustrated by demonstration Turtle. There are 2 stacks of n discs, coloured respectively green and orange; initially, the green stack occupies pin 0, the orange stack pin 2; finally, the positions of the stacks will be reversed; there are 4 pins, pin 1 reserved for green discs and pin 3 for orange, emphasised by shading these pins appropriately.

The problem may be generalised to l stacks on m = 2l pins: initially stacks occupy alternate (even) pins, finally they transfer to the next even pin in cyclic order; (odd) pins in between accept only the colour initially to their left, whilst even pins accept both initial and final colours. Although Turtle is a special case of this Multi_Stack problem, the away pin of each stack turns out to collide inconveniently with the home pin of the other, causing the solution to cost an anomalously long time: we therefore implicitly assume l > 2.

Rephrasing the constraints, stack i has access to three adjacent pins:

its Home pin 2i, which it occupies initially, and is shared with discs from stack i-1;
its Ride pin 2i+1, initially empty, and exclusive to discs from stack i;
its Away pin 2i+2, which it will occupy finally, and is shared with discs from stack i+1;
here i = 0,...,l-1, and i+1, i-1 implicitly signify remainders modulo l.

The demonstration Multi_Stack colours the discs and ride pins of each stack individually, at any rate for small l. The Pins field must be loaded with twice the number of stacks 2l, and the Discs field with the number n of discs per stack.

The recursive solution involves a quartet of subsidiary problems, each of which transfers k (consecutive) discs of stack 0 between a specified pair of pins, while in parallel transferring k discs of every other stack between another (distinct but fixed) pair of pins. Each initial-final pair is denoted by two letters from the set {H,R,A}: for example, HAHR(n) denotes the transfer of stack 0 from its home to away pin, while simultaneously the remaining stacks transfer from their home to their ride pins. With this notation, the functions required are

HAHR(k), HRHA(k), HARA(k), RAHA(k).

The solution also involves the classical 3-pin problem, transferring the k discs of the singleton i-th stack between specified pins: in a similar fashion, these are denoted

HR(k,i), RH(k,i), AH(k,i), HA(k,i), RA(k,i), AR(k,i);
if k = 1, a single disc moves; if k = 0, nothing moves. [The iterative solution to the classical problem is suitable for implemention in this context, since it simply ignores discs of diameter exceeding k.]

The subsidiary solutions may now be expressed recursively as follows: for n = 0, nugatory; for n > 0,

HAHR(n) = {
     HRHA(n-1);
     { HR(1, i); AR(n-1, i) } for i = 1, ..., l-1;
     HA(1, 0); RA(n-1, 0) };
HRHA(n) = {
     HAHR(n-1);
     HR(1, 0); AR(n-1, 0);
     { HA(1, i); RA(n-1, i) } for i = l-1, ..., 1 };
HARA(n) = {
     HR(n-1, 0); HA(1, 0);
     { RH(n-1, i); RA(1, i) } for i = 1, ..., l-1;
     RAHA(n-1) };
RAHA(n) = {
     { HR(n-1, i); HA(1, i) } for i = l-1, ..., 1;
     RH(n-1, 0); RA(1, 0);
     HARA(n-1) };

In terms of these, the original problem HAHA(n) breaks down into nugatory cases l < 2; the special case l = 2; and the general case l > 2:

HAHA(n) = {
     HAHR(n-1); HR(1, 0);
     AR(n-1, 0); HA(1, 1);
     RH(n-1, 0); RA(1, 0);
     HARA(n-1) } if l = 2;
HAHA(n) = {
     HAHR(n-1); HR(1, 0);
     HA(1, i) for i = l-1, ..., 2;
     AH(n-1, 0); HA(1, 1); RA(1, 0);
     HARA(n-1) } if l > 2;

To evaluate the timing function, we proceed as before to derive the matrix recurrence for the vector <B>s</B>(<I>n</I>+1) from the recursion above: <DL> <DD> <B>s</B>(1) = (<I>l</I>,<I>l</I>,<I>l</I>,<I>l</I>,1,1), <DD> <B>s</B>(<I>n</I>+1) = <B>M s</B>(<I>n</I>). </DL> where vector <B>s</B> and matrix <B>M</B> are defined by <DL> <DD> <B>s</B> = (<I>HAHR</I>, <I>HRHA</I>, <I>HARA</I>, <I>RAHA</I>, 2<SUP><I>n</I></SUP>-1, 1), <DD> <B>M</B> = <PRE> | 0,1,0,0,<I>l</I>,<I>l</I> | | 1,0,0,0,<I>l</I>,<I>l</I> | | 0,0,0,1,<I>l</I>,<I>l</I> | | 0,0,1,0,<I>l</I>,<I>l</I> | | 0,0,0,0,2,1 | | 0,0,0,0,0,1 | </PRE> </DL> giving the as characteristic polynomial the recurrence <DL> <LI> (<B>E</B> - 1)<SUP>3</SUP>(<B>E</B> + 1)<SUP>2</SUP>(<B>E</B> - 2). </DL> <P> Solving and substituting into the top-level recursions gives finally the timings <DL> <DD> <I>HAHA</I>(<I>n</I>, 2) = 3 (2<SUP><I>n</I></SUP> - 1); </I> <DD> <I>HAHA</I>(<I>n</I>, <I>l</I>) = <I>l</I> (2<SUP><I>n</I></SUP> - 1) + (1/2) 2<SUP><I>n</I>. </I> </DL>

The timing function may be derived as in earlier problems via the Markov process method; but a more direct argument is as follows. Define

I(n) = 1 = timing for a single move;
T(n) = 2n - 1 = timing for the classical problem;
R(n) = timing for the subsidiary problems HAHR(n) etc;
P(n) = timing for the top-level problem HAHA(n).
By inspection of the pseudocode above it may be seen that R(n) is independent of which sub-problem is chosen; also
R(1) = l;    and for n > 1,
R(n) = R(n-1) + l T(n-1) + l I(n-1);
P(n) = 2 R(n-1) + T(n-1) + (l + 1) I(n-1) if l > 2;
        = 2 R(n-1) + 2 T(n-1) + 3 I(n-1) if l = 2.
Solving the recurrence and substituting,
R(n) = l T(n) = l (2n - 1);
P(n) = 0    if n = 0 or l < 2;
        = l T(n) + T(n-1) + 1 = l (2n - 1) + (1/2) 2n    if l > 2;
        = 3 T(n) = 3 (2n - 1)    if l = 2.

Closer examination of the algorithmic strategy suggests that, apart from the arbitrary choice of which pin shall be labelled 0, similar variations in the move order of the smallest discs, and obviously time-wasting discursions, there is virtually no choice about which move must be made next. So as in the classic case, the solution appears to be essentially unique; and the times given above therefore presumably optimal. <P> An approach to formally proving this is suggested by viewing <I>Multi_Stack</I> for larger parameters, say <I>l</I> = <I>n</I> = 10 (i.e. 100 discs on 20 pins) with delay set to 125 msec. It becomes obvious that the solution mostly comprises identical classic problems proceeding in parallel on different stacks, complicated only by the manner in which stack 0 fails to conform, and loosely synchronised in order that a sufficiently large disc of one colour is available to accept smaller discs of the adjacent colour. It is however less obvious how to convert this observation into a precisely specified algorithm. <P> Is this algorithm optimal? Since l stacks each with n discs are to be transferred, a lower bound on the time is evidently l T(n); a bound actually attained by the quartet of sub-problems. The main problem takes longer because one largest disc (say on home pin 0) must move to its ride pin before the other largest discs can move to their away pins; furthermore before it can do so, the stack of smaller discs above must transfer (to their away pin). This costs T(n-1) + 1 extra moves, giving a total at least equal to P(n); this is attained by the algorithm above for l > 2, which is therefore optimal in general. According to Stockmeyer, the twin-stack case requires more delicate analysis, assisted to some extent however by the fact that when l = 2 the move sequence is essentially unique.

See if you can shoot down this proof of optimality for m = 2 stacks :--- (1) Initially, both smallest discs must move before any larger disc begins moving; easily by inspection. (2) There must be (at least) one move of a smallest disc between each pair of moves of larger discs; this follows in the same way as for classical Hanoi. (3) Finally, both smallest discs must move after every larger disc has finished moving; by reversing the reasoning of (1). Now let f(n) denote the optimum time for n discs. By (1), (2), (3) f(n) >= f(n-1) + f(n-1) -1 + 4 = 2 f(n-1) + 3; also f(1) = 3. Hence f(n) >= 3 (2^n - 1); and since we have a solution for which the time equals this value, it must be optimal. [But does this reasoning involve an assumption that removing the smallest disc moves from an optimal sequence must result in an optimal sequence, which fails for Antwerp?!] Now then, if we could only tell which of the two smallest discs is to move, using just local information (e.g. which disc moved last, which discs are at the tops of the pins, etc) then we'd have a beautiful man-friendly smallest-disc recursion ... Each classic phase [during which just one stack moves] terminates when (a) the stack comprises (at most) two substacks; (b) some top disc diameter exceeds that of the third available pin. The next phase involves the stack occupying that third pin. ?? Or maybe the transfer phase terminates when the next move is impossible, and the subsequent phase involves the stack on the pin which would have been moved to, had the existing top been sufficiently large. ?? 2 stacks n discs: discs from same stack move in phase j, where 0 <= j <= 2 n; stack g(j) moves h(j) times consecutively, where for n > 0, h(0) = 1; h(n) = 1; h(j) = 3.2^(j-1) for 0 < j < n; h(j) = h(2n-j); g(j) = (j+n+1)mod 2; l stacks n discs: p = p(l,n) = number of phases = 2(l-1)(n-1) + 2 for l > 2; h(0) = 1; h((l-1)k) = 3.2^(k-1) for 0 < k < n-1; h((l-1)k + i) = 2^k for 0 < i < l-1; h((l-1)(n-1)) = 2^(n-2) + 1; h((l-1)(n-1) + i) = 1; h((l-1)n) = 1; h(j) = h(p-j) for j > (l-1)n. g(j) = (j+1)mod l for j mod 2(l-1) = 0, 1, ..., l-1 when n even; = -(j+1)mod l for j mod 2(l-1) = l-1, l, ..., 0 when n even, j < (l-1)n; g(j) = (-j)mod l for j mod 2(l-1) = 0, 1, ..., l-1 when n odd; = (j+2)mod l for j mod 2(l-1) = l-1, l, ..., 0 when n odd, j < (l-1)n; g((l-1)n) = 0; g(j) = -g(p-j)mod l, for j > (l-1)n. <P> The constraints could plainly be relaxed by permitting any disc access to any pin: Stockmeyer considers this variation. A further variation --- which we have not so far investigated --- introduces a single extra star pin, accepting discs from every stack.

Domino & Adjacent Hanoi

An alternative variation based on the Classic colouring scheme is to retain just two disc colours (pink and cyan in HanoiVar), but to introduce colour flipping (seen earlier under Cyclic) :--- It follows that initially the whole stack must be coloured the same (pink).

In many respects this puzzle is a somewhat gnarlier companion to Rainbow, involving as before a raft of subsidiary problems with coloured bases. To notate these we need A, B for the colour of the initial stack and the other colour, and also D, E, F for various uncoloured bases. Formerly we could assume that the destination pin was fixed on the right, but we now have to consider the possibilities that the final stack may be

Optimal solutions to all three puzzles are illustrated by HanoiVar under Domino_E, Domino_F, Domino respectively.

At this point as for Rainbow, we survey the subsidiary functions encountered as we follow the recursion down to all bases coloured. This is not an appealing prospect: in the first place, at a rough count there are potentially up to 81 functions involved; in the second, a recursion may in principle break down into 2,3 or even 4 (in the case of EDD(n)) smaller problems; and finally, beyond that variation lies the further possibility of varying the colours of the intermediate stacks, giving in the worst case 14 possible recursions for a single function.

To simplify things, we just assume the optimal recursion breaks the function into as few sub-functions as possible; and further more that a (sub)function that breaks down into 3 will always be greater than one that breaks down into 2, etc. In this way, and by discarding symmetries etc as previously, we arrive at a manageable set of 10 functions and recursions, programmable as 20 mutually recursive methods :---

DDE(n) = ADE(n-1) + 1 + DDA(n-1)
DDF(n) = ADE(n-1) + 1 + DAE(n-1) + 1 + DDA(n-1)
EDD(n) = ADE(n-1) + 1 + DAE(n-1) + 1 + DAE(n-1) + 1 + DDA(n-1)
ADE(n) = ADE(n-1) + 1 + DBA(n-1), DDB(n) = ADE(n)
ADF(n) = ADE(n-1) + 1 + DAB(n-1) + 1 + ADA(n-1), DDA(n) = ADF(n)
DBE(n) = ABE(n), DAE(n) = DBE(n)
ADB(n) = ABE(n-1) + 1 + DBA(n-1)
ABE(n) = ADB(n-1) + 1 + ABA(n-1), DAB(n) = ABE(n)
ABF(n) = ABE(n-1) + 1 + DAB(n-1) + 1 + ABA(n-1), DBA(n) = ABF(n)
ADA(n) = ABA(n)
DBB(n) = ABB(n), AAE(n) = DBB(n)
ABB(n) = ABB(n-1) + 1 + ABA(n-1), AAB(n) = ABB(n)
ABA(n) = ABA(n-1) + 1 + ABA(n-1) + 1 + ABA(n-1)
Fortunately, by this stage only one instance remains outstanding where it is unclear which of two possible break-downs to use: ADE(n) = ADE(n-1) + 1 + DBA(n-1) appears in practice to be preferable to the alternative ADE(n) = ADF(n-1) + 1 + DAB(n-1), although we have not currently taken the trouble to prove it. [Note that not all possible functions appear in the above list: for instance DBF(n), DAF(n) are viable problems --- the latter remarkable for its time --- which are unused by our solution.] It has been verified by exhaustive search that this algorithm gives optimum solutions for n <= 12.

Analysing the Markov chain as before, we find the vector equation

s(1) = (1,2,3,1,2,1,2,1,1,2,1,2,1),
s(n+1) = M s(n),
where
s = (DDE,DDF,EDD,ADE,ADF,ADB,ABE,ABF,AAB,ABA, 1),
M = 
            | 0,0,0,1,1,0,0,0,0,0,1 |
            | 0,0,0,1,1,0,1,0,0,0,2 |
            | 0,0,0,1,1,0,2,0,0,0,3 |
            | 0,0,0,1,0,0,0,1,0,0,1 |
            | 0,0,0,1,0,0,1,0,0,1,2 |
            | 0,0,0,0,0,0,1,1,0,0,1 |;
            | 0,0,0,0,0,1,0,0,0,1,1 |
            | 0,0,0,0,0,0,2,0,0,1,2 |
            | 0,0,0,0,0,0,0,0,1,1,1 |
            | 0,0,0,0,0,0,0,0,0,3,2 |
            | 0,0,0,0,0,0,0,0,0,0,1 |

the recurrence

E6 - 5E5 + 6E4 + 3E2 - 11E + 6
= (E - 3)(E3 - E - 2)(E - 1)2;
and the asymptotic orders of magnitude of the uncoloured functions
DDE(n), DDF(n), EDD(n) ~ 2, 3, 4 (5/33) 3n.

Two bottom-level problems are illustrated. Adjacent implements ABA(n), whose base colours always force a disc to move to an adjacent pin; and its time is exactly A(n) = 3n - 1. If for a moment we simply ignore the colours, the solution path passes through every possible configuration of n discs on 3 pins; so this is the slowest possible puzzle using 3 pins. This already rather tedious puzzle is worked to death under Adjacent_P, which implements (indistinguishably) the obvious period 6 algorithm. Finally Domino_B implements AAB(n), essentially the only other fully-coloured problem: its time is (3n - 1)/2 for n > 1.

Four-Star Hanoi

This variation due to Stockmeyer also generalises Adjacent Hanoi, but in a different direction: there are now four pins, the "star" of which is distinguished in that every move must involve that pin, either as origin or as destination. The illustration Four_Star colours the star pin white.

The analysis proceeds in a manner very similar to that of the Reve's, except that the subsidiary problem is now Adjacent Hanoi with a time of 3n - 1, rather than Classic with a time of 2n - 1. The algorithm is recursive, and --- subject as before to the Frame hypothesis --- is optimal. Given n discs initially on pin X to be transferred via Y and star S to Z: transfer the top n-k discs recursively to pin Y, using 4 pins; transfer the bottom k from X via S to Z, using 3 pins with the Adjacent algorithm; finally transfer the top recursively from Y to Z, using 4 pins.

To select the optimum value for k, first sort the integers 2i 3j into ascending order of magnitude, where i, j = 0,1,...; and define an to be the n-th number in this sequence for n > 0. Now choose k such that

3k-1   <=   an   <   3k;
that is,
k = 1 + [log(an)/log3]
   ~ [(2n log2/log3)1/2 + 0.1809] for large n;
remarkably, the approximation is exact for n < 1737. [Here and elsewhere, square brackets [...] in formulae denote integer part, or "floor" function.] The number of moves may then be shown optimal, with exact value
2(a1 + ... + an);
to which a reasonably good approximation appears to be
(2n log2/log3)1/2 exp((2n log2 log3)1/2).

Notice that Reversi_G also provides a solution to this problem, albeit a rather slow one taking twice as long as Classical. For more detailed discussion of the algorithm, and other related variations, see Stockmeyer's paper. The obvious further generalisation, to m pins with a starred subset of size l, does not appear to have been investigated.

Tower of Lundon

This confection was engineered by Lunnon in the course of a (deliberate but unsuccessful) attempt to humiliate a fellow enthusiast who had earlier incautiously described his HanoiVar implementation as "convoluted". A feature is the possibility of impasses arising: for example, should the two smaller top discs become coloured B, while the other remains A, further advance (or retreat) becomes impossible. The illustration Lundon colours the discs green, white, orange.

The algorithm is essentially a disguised and somewhat contorted variation of Cyclic: if the algorithm for Cyclic_L is applied to the initial stack, it is easily seen that all moves are legal, and the final stack will be coloured B (see Lundon_B); on the other hand, applying Cyclic_R with the direction reversed produces a final stack coloured C (see Lundon_C).

Maintaining the same colour A requires a little more ingenuity (the Tower of Lundon):

Alternatively, the subsidiary transfers can be interchanged (the Brandonbug variation):

The (optimal) time for either is easily computed from that for Cyclic: for n discs, A(n-1) + C(n-1) + 3 moves.

Checkers Hanoi

It's noticeable that in the Reves solution the two colours again tend to alternate, though careful observation will detect occasional lapses: these are easily seen to be unavoidable in a Frame-type optimal solution when n is a (not too small) triangular number. Somewhat diffidently then, we propose as a distinct variation for m = 4 pins (to be going on with) the rule :--- Optimal solutions, common to both Checkers and Reves, and of Frame type, exist for all n < 27 except n = 15,21. At n = 15 the optimal Checkers solution, though still Frame-type, costs time 137 moves against 129 for Reves. At n = 21, the fastest Frame-type solution costs 337 against 321 --- we do not know whether the former is optimal, though according to Korf the latter is.

An Frame-type algorithm may be developed for this problem by combining the solution given earlier for Reves with the coloured-base approach developed for Rainbow and Domino, and is illustrated under the option Checkers. There are 9 recursive procedures involved, corresponding to the 6 distinct functions (in notation analogous to Domino) DDDD(n), DDDB(n), BADD(n), DDBB(n), BDDB(n), BABB(n). All of these functions are slower than Reves by at worst a fraction 1/k or so, and at best equal it. Each of them is a slightly modified version of the Reves/Frame algorithm described earlier, which we recall chooses k so that n lies between the k-th and k+1-th triangular numbers, then temporarily stacks the n-k smaller discs on the third pin while Classical BAB(k) transfers the k largest. We recall also that it was permissible to substitute k+1 for k unless n happened to be triangular.

The first complication here is that once most pins are occupied by larger discs, inspection reveals that the algorithm must force k to have even parity, in order to respect the base colours. This restriction implies that our Checkers/Frame algorithm will be slower than Reves unless n is nearly midway between triangular numbers, when subsequent recursive levels can also avoid triangular numbers, at any rate until almost at bottom level.

To make this precise, we utilise along with

if Tk <= n < Tk+1, then Sk is the nearest semisquare to n. Now define the "persistance" p = p(n) to be the offset of n from the nearest semisquare, that is large n with small p are distant from triangular numbers. For example, centred on S4 = 12 midway between T4 = 10, T5 = 15 is the 5-tuple n = 10,11,12,13,14 for which p = -2,-1,0,+1,+2; by inspection, DDDD(n) = Reves(n) for all these.

We can show that our algorithm is as fast as Reves (and therefore almost certainly optimal) just when the persistance is small :---

For suppose we follow the execution of a Reves/Frame style algorithm for some argument n with small p, always employing whichever of k,k+1 happens to be even. Then at the next recursive level down --- where the new argument is n' = n-k, n-k-1 as k is even, odd --- a simple computation shows that the persistance does just that: p(n') = p(n). Suppose initially n lies in one of the 5-tuples |p(n)| <= 2; by induction (downwards) on k, we shall eventually descend to the 5-tuple around n = 12, and the algorithm will execute as fast as Reves. For all other n we shall eventually strike some Ti >= 15, and be forced eventually to decrement it by some amount non-optimal for Reves.

The second complication is more subtle: at higher levels, when only some pins are occupied by larger discs, the algorithm must distinguish between k odd and even; but the choice between decrementing by k or k+1 becomes significant. Paradoxically, it appears that the correct decrement is that corresponding to the triangular number nearest n, given by

To motivate this rule, consider the bottom-level functions BABB(n), BAAB(n), illustrated under Checkers_B, Checkers_C. Experimentation suggests (idleness currently precluding proof) that :---

In the same way as earlier we can show that BADB(n) = min(BAAB(n),BABB(n)) = DDDD(n) for 4 of any 5-tuple of n with |p(n)| <= 2.

A curiosity is the man-friendly periodic algorithm Checkers_P, costing exponential time and so very far from optimal, which is actually identical to the optimal solution Reversi_P of a different problem described subsequently.

Reversi Hanoi

This on the face of it appears a more natural variation on the Classic colouring scheme than Domino introduced earlier --- to introduce colour flipping, but keep the alternating colours (yellow and magenta in HanoiVar): It follows that initially the whole stack must alternate. The lurking complication is that m = 3 pins turns out overly economical: at least m = 4 pins are required for a solution to be possible.

The generation of subproblems and our notation for describing them are essentially the same as for Domino: at the top level with no bases coloured, the final stack may be

Solutions to all three puzzles are illustrated by HanoiVar under Reversi_F, Reversi_E, Reversi respectively. We should of course like to be able to claim that these are optimal, or at least conjecture that they are; but the new complication which defeats us is the unwelcome discovery that Frame's hypothesis fails: At this moment an efficient provably optimal algorithm remains apparently feasible, but it will certainly require consideration of a more general class of configurations than those employed earlier. Our current solutions, based on the same strategy outlined for Domino, are necessarily of Frame type and therefore suboptimal, falling short of the best by a time factor which we might reasonably conjecture is not too far above unity. While it is possible to provide times for these suboptimal algorithms, in the same manner as for Rainbow or Domino, we have little incentive to do so: the matrix involved has order 27.

Instead, it is more enlightening to examine some special sub-problems. Reversi_G implements a rather dismal DDDF(n) algorithm, whose only discernable merit is to show that the puzzle is easily (but slowly) solvable with 4 pins: to transfer the stack from left pin to right, start with the Classic 3-pin solution, and replace every move from (say) X to Y by a pair of moves from X to W and W to Y, where W denotes the fourth pin. [In different guise, this algorithm provides a solution to the Four-Star variation introduced earlier, with W the distinguished pin.] Notice that W only ever holds at most one disc, and that the time is 2(2n - 1). Even allowing for the one-disc restriction, this is suboptimal: Reversi_H improves on it with [(4/3)(2n-1/2)] moves.

Three bottom-level problems are illustrated: options Reversi_A,B,C, implementing BABA(n), BABB(n), BAAB(n). Reversi_B is the most interesting, since the others, along with all functions in our doomed attempt to construct an optimal uncoloured solution, can be made to depend on it. It is an optimal solution to the coloured problem (a formal proof of this depends on analysing the recursive structure of the associated move-graph); remarkably, it possesses a periodic algorithm [unlike the others] Reversi_P, with period 4,8 moves for n even,odd:

[The smallest disc moves when t mod 3 = 0 (n even), t mod 8 = 0,1,4,5 (n odd). In the guise of Checkers_P this same algorithm also supplies a (very inefficient) solution to a completely different problem.]

The times for Reversi_A,B,C, respectively are

BABA(n) = (2)3n/2 - 2 for n even,
               (3)3[n/2] - 2 for n odd;
BABB(n) = (2)3n/2 - 2 for n even,
               (4)3[n/2] - 2 for n odd;
BAAB(n) = [(8/3)3n/2 - 2] for n even,
               (4)3[n/2] - 2 for n odd;

We should like to be able to claim that, in some sense, any optimal algorithm must spend most of its time with all the bases covered by large discs which move only rarely. Under this assumption, we can see that the optimal uncoloured time must in the limit be within a constant factor of the optimal coloured time, which we already know to be roughly (31/2)n. Thus we should know the "complexity" of the harder problem, even though we presently lack an optimal algorithm.

Sadly, although the assumption seems intuitively plausible, we presently know of no decently precise formulation, let alone proof. Some idea of its elusiveness is provided by the (presumptive) optimal algorithm for Reve's, where for all but a fraction 1/k of the time, the k largest discs remain stacked neatly on a single pin!

Demo Variation Programming

The sytem has been deliberately designed so that new variations may be easily implemented by a programmer with the most elementary knowledge of Java. A reasonably accessible example is the source code for Cyclic and its variations, mostly developed in the super-class CyclicDefn, and currently located at lines 263--321 of the source file HanoiLib.java. The intending implementer is advised to study this with a view to hacking it to his own specification.

Briefly, the program code comprises a class (with your own fresh identifier, please!), which must be instantiated in the array HanoiLib.list[ ] in order to appear for selection in the variation menu of the property window. The new class must extend the abstract class HanoiDefn [or an existing subclass, see below] and override the methods:

name( ) with the name of the variation;
tran(tower) invoking the algorithm transferring the stack;
check(X, Y) validating the move of a disc from pin X to pin Y;
reshade(disc) changing the disc colour when it moves;
init(m,n,defn) initialising the tower with appropriate stack(s);
fin(tower) checking the tower for the correct final stack(s);
while variables
l, m, n provide for the number of stacks, pins, discs per stack.

tran(m, n) is just a shell which calls a (usually recursive) method designed by the user to solve the problem, such as tranR(disc, X, Y, Z) in CyclicDefn. In the course of writing bodies for these methods, the programmer may avail of system features including the following:

move(X, Y) moving the topmost disc from pin X to pin Y;
Disc( ) with properties
shade the current colour (specified as an index in Colour.table[ ]);
above, below those discs currently above and beneath;
diam the diameter (between n+1, 0);
alti the height above the pin base (between 0, n+1);
Pin( ) with properties
shaft, base specifying the (pseudo) Discs acting as pin (diam = 0, above top disc) and base (diam = n+1, below bottom disc);
Tower( ) with properties:
m, n, l the current number of pins, discs, max disc diameter (usually l = n ) ;
pins[ ] the array of Pins in the tower.

Instead of extending HanoiDefn directly, it is possible to provide a new solution to an existing variation by extending the appropriate existing class: for instance, Checkers extends Classic, inheriting reshade( ), init(), fin() from that class, but over-riding by a more elaborate check( ). Notice that check(X, Y) does not test for disc on pin X larger than on Y, nor for X = Y, nor for X empty; all of which are rejected elsewhere by move( ).

The (trace) and (move) toggles are provided to assist in debugging. The trace must be invoked by a call such as tower.trace(name, disc); or trace(name, disc, W, X, Y, Z); in the programmer's transfer method(s). If an erroneous move is detected, it is printed and the simulation halts; if an erroneous final configuration is found, a "Failure" message is printed.

Demo Installation

The demonstration program was originally intended to run as an "applet" called from a web browser, but in practice this is unlikely to be successful. [There appear to be a number of factors militating against this empyrean vision, including: path settings missing from the web server; high-level security settings in the browser; differences in Java system libraries between compiler and user; dodgy scheduling in earlier versions of Java; accidental incompatibilities between Java interpreters; inadequate linkage between browser and local operating system.]

The intending user is therefore advised to instal a Java development system [such as JDK, available from http://java.sun.com/j2se/1.4/ ] and perhaps an application programming environment [such as RealJ]; download the source files

HanoiVar.java
HanoiLib.java
into a separate directory on his local system; then compile and run the demonstration either via the environment, or by opening a command window and executing:
javac HanoiVar.java
java HanoiVar
The program should run under any environment system from JDK 1.1 onwards, but clunky user interaction is a hazard under versions earlier than 1.4.

Known bugs include the display window occasionally freezing, along with all user interaction, particularly after a demonstration has run for many minutes with a large resized display, and the move delay set short (<100 msec) in the property window. The program may be killed from a command window by executing

kill -9 1234
where for 1234 is substituted the run number printed when the program was started; or similar but more user-friendly action taken via the programming environment.

On starting the program an intermittent non-fatal error message may appear, along the lines of

... _initWithWindowNumber: error creating graphics ctxt object ...
This results from the author's chronic inability to master the Java process communication model, and may safely be ignored.

Queries, comments (constructive or otherwise), bug reports, and suggestions for enhancements may be addressed to

W.F.Lunnon (Fred.Lunnon@may.ie)
[on a good day, they might even receive a reply ...].

Demo User Guide

The program opens two windows, both of which should be re-sizable by the user, by clicking and dragging the corner or edge of the frame as usual. [These features can malfunction when the program is run from within a browser.] <HR> <APPLET CODE = "HanoiVar.class" WIDTH = 800 HEIGHT = 300 <! Reconcile; check not too big for page or too small for properties !! > <! Int.Exp. runs as standalone, ignoring init() and parameters ?? > ALT = "Browser understands <APPLET> tag but won't run the applet."> Browser ignores <APPLET> tag! <PARAM NAME = "Variation" VALUE = "1"> <PARAM NAME = "Discs" VALUE = "6"> <PARAM NAME = "Pins" VALUE = "3"> <PARAM NAME = "Firing" VALUE = "Increase"> <PARAM NAME = "Delay" VALUE = "500"> </APPLET> <HR>

The main display shows the pins and discs of the tower as the solution is simulated automatically. The program may be terminated by clicking on the exit button of the display frame. The current run may be re-initialised at any time by choosing a variation from the menu, or by resetting the numbers of discs or pins. To single-step a simulation, set delay to least 333 msec, then toggle Run stop/start.

In manual mode with the Run toggle started (green), a top disc may be moved by left-clicking on its old pin, whence it will disappear; then left-clicking on its new pin, whither it will reappear. No subsequent interaction with the automatic solution is possible: on exit from manual mode, the tower is re-initialised. If an invalid move is made, the Run toggle stops (red), and further moves are prevented until it is clicked to start (green).

The properties window may be hidden by clicking on the exit button of its frame, and called up again by mouse clicking within the display frame. The window comprises the following features, each activated by clicking there. To enter a number into a field, delete it with the backspace key or by highlighting with the mouse, type in the new value and press RETURN.

The Variation menu (scrolling),
selecting any of Classic, Cyclic, Rainbow, Antwerp, Domino, Checkers, Reversi, Reves, Many_Pin, Turtle, Multi_Stack, Four_Star,
or a subsequent selection of individual variations;
The Mode menu,
allowing on completion to Wait, Repeat the same, Increase n;
or (immediately) await user moves in Manual mode;
The Discs field,
setting the number n of the discs (per stack);
The Pins field,
setting the number m of pins (where applicable);
The Time field,
how many moves have occurred so far in the current run;
The Delay field,
slowing down the rate at which moves are displayed;
The Trace and Print toggles,
recording the functions called and moves made in the command window;
The Status field,
signalling the current simulation state: Running, Waiting, Manual input, Success (manual or auto), Failure (auto), Invalid move;
The Draw stop/start toggle,
suspending or reinstating display (slowing the simulation considerably);
The Run stop/start toggle,
interrupting the simulation to wait, or continuing to run it.

A substantial amount of detailed information about the recursive and iterative algorithms used in the solutions is expressed in the transfer functions of the variation classes supplied, and there seems little point in repeating most of this (less precisely, if more succinctly) in this text. Readers who want to understand the algorithms in more detail are urged to: watch the demonstrations; inspect the program code; and study the tracing and moves.

References

<LI> W.F.Lunnon hanoi1/2.tex. <LI> Robert Neale <I>The Temple of Hanoi</I> Games Magazine <B>6</B>(7) 70 (Nov 1982). <LI> Andreas Hinz [shortest paths between configurations] Author: Fred Lunnon

Last update: 12 October 2010