The Tower of Hanoi and Variations
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 leftmost 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 :
 Only one disc shall be moved at a time;
 No disc may be placed on top of a smaller one.
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.
 To transfer n > 0 discs from pin X via pin Y
to pin Z:
 (1) transfer n1 discs from X via Z
to Y;
 (2) move largest disc from X to Z;
 (3) transfer n1 discs from Y via X
to Z.
[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(n1) + 1 + T(n1) for n > 0 and T(0) = 0,
and the unique solution to these equations is T(n) = 2^{n}  1.
Though very directly implementable on computer via any modern programming
language, recursion by largest disc is far from being a manfriendly 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 moves alternately;
 For each other move there is (at most) one legal choice;
 The smallest disc moves always in the same cyclic direction.
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 manfriendly to execute
manually, to the amazement of your friends [the more nerdy, maybe]:
 To transfer n > 0 discs from X via Y to Z:
 Set clock t = 0 initially;
 At time t move smaller disc between pins shown below.
 For n odd:
 t mod 3 = 0: X, Z;
 t mod 3 = 1: Y, X;
 t mod 3 = 2: Z, Y;
 For n even:
 t mod 3 = 0: X, Y;
 t mod 3 = 1: Z, X;
 t mod 3 = 2: Y, Z;
 Increment t and repeat until entire stack on Z .
[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 lefthand base green,
the middle red and the righthand green. This colourscheme emphasises the
rather surprising fact that, throughout the solution :
 The colours of all discs and bases on each pin alternate.
It can be shown that this property characterises the configurations along
the optimal solution, from which we can deduce another manfriendly
"bichromatic" algorithm:
 After each move, the next move avoids reversing the previous move.
[There is only one such colourconsistent 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).
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
 Every disc shall move in the same cyclic direction.
[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 :
 To transfer_right n > 0 discs from pin X via pin Y
to pin Z,
 (1) transfer_left n1 discs from X via Z
to Y;
 (2) move largest disc from X to Z;
 (3) transfer_left n1 discs from Y via X
to Z.
 To transfer_left n > 0 discs from pin X via pin Y
to pin Z,
 (1) transfer_left n1 discs from X via Y
to Z;
 (2) move largest disc from X to Y;
 (3) transfer_right n1 discs from Z via Y
to X;
 (4) move largest disc from Y to Z;
 (5) transfer_left n1 discs from X via Y
to Z.
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(n1) + 1 + C(n1) + 1 + A(n1),
 C(n) = A(n1) + 1 + A(n1),
 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) = (x^{n+2}  y^{n+2})/4(3^{1/2})  1,
 where x = 1+3^{1/2} = 2.7320...
 and y = 13^{1/2} = 0.7320...
 and 3^{1/2} denotes the square root of 3;
with similar formulae for C(n) = 2A(n1) + 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 colourchanging rule is that :
 A disc colour flips as it moves, just when the next larger disc is orange;
It can be shown that, throughout the solution :
 No two discs of consecutive size are both blue;
and that this property characterises configurations along the optimal solution.
The resulting manfriendly "coloured" algorithm is :
 Alternately, move the smallest disc (once or twice) until it is orange;
 For each other move there is just one legal choice;
 Stop when the entire stack has been transferred.
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
 the number of blue discs is (2  3^{1/2}) n
= (0.2680...) n .
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
 No disc may be placed on another of the same colour (red, green or blue).
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 n1 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 firstorder 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) :
 E^{10}  E^{9}  2E^{8} 
7E^{7} + 5E^{6} + 8E^{5} +
14E^{4}  2E^{3}  4E^{2} 
4E  8
 = (E  1)(E^{5}  3E^{2}  2)
(E^{4}  2E^{2}  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 subproblems.
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
E^{5}  3E^{2}  2, or
E^{4}  2E^{2}  6E  4,
where each term is a positive combination of those preceding, must have only
terms which are nonnegative, 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 nonnegative. 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.
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.
Largestdisc induction suggests something along the following lines:
 T33(n,X,Y,Z): To permute 3n > 0 discs cyclically around pins
X > Y > Z > X:
 T31(n1,X,Y,Z): Collect smaller discs from pins
X,Y,Z to Z;
 Until the large discs are in place, alternately
 move(X,Y): move a large disc, e.g. red from
X to Y;
 T11(n1,Z,X,Y): Transfer smaller discs, e.g. from Z to Y;
 T13(n1,X,Y,Z): Redistribute smaller discs from
pin Z to X,Y,Z.
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
 T33(n,X,Y,Z): To permute 3n > 3 discs cyclically around
pins X > Y > Z > X:
 T31(n1,X,Z,Y): Collect smaller discs from Y,X,Z to Y;
 move(X,Z): move large disc from X to Z;
 T11(n1,Y,X,Z): Transfer smaller discs from Y to Z;
 move(Y,X): move large disc from Y to X;
 T11(n1,Z,Y,X): Transfer smaller discs from Z to X;
 move(Z,Y), move(Z,Y): move large disc from Z to Y twice;
 T11(n1,X,Z,Y): Transfer smaller discs from X to Y;
 move(X,Z): move large disc from X to Z;
 T11(n1,Y,X,Z): Transfer smaller discs from Y to Z;
 move(Y,X): move large disc from Y to X;
 T13(n1,Z,Y,X): Distribute smaller discs from Z to Z,Y,X.
Individual subsidiary operations required above are as follows:
 T31(n,X,Y,Z): Collect 3n > 0 discs from pins Z,X,Y to Z;
 T31(n1,X,Z,Y): Collect smaller discs from Y,X,Z to Y;
 move(X,Z): move large disc from X to Z;
 T11(n1,Y,Z,X): Transfer smaller discs from Y to X;
 move(Y,Z): move large disc from Y to Z;
 T11(n1,X,Y,Z): Transfer smaller discs from X to Z;
 T13(n,X,Y,Z): Distribute 3n > 0 discs from pin X to X,Y,Z.
 T11(n1,X,Z,Y): Transfer smaller discs from X to Y;
 move(X,Z): move large disc from X to Z;
 T11(n1,Y,X,Z): Transfer smaller discs from Y to Z;
 move(X,Y): move large disc from X to Y;
 T13(n1,Z,Y,X): Distribute smaller discs from Z to Z,Y,X.
 T11(n,X,Y,Z): Transfer 3n > 0 discs from pin X to Z;
 T11(n1,X,Z,Y): Transfer smaller discs from X to Y;
 move(X,Z), move(X,Z), move(X,Z): move large discs from X to Z;
 T11(n1,Y,X,Z): Transfer smaller discs from Y to Z;
[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 (2^{n})  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.
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 :
 Whenever the largest disc moves, the other discs form consecutive
substacks on the other m  2 pins.
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 nk.
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 kth "triangular" number,
n = 1 + 2 + ... + (k1) + k = k(k+1)/2: first the bottom k
are split off, then the next k1, 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, Frametype solutions are not unique.
The time to transfer n discs by this method is :
 (n  k(k1)/2  1) 2^{k} + 1 moves.
Since k is close to the square root of 2n, this grows very
roughly as (2^{21/2} = 2.6651) raised to the power
n^{1/2}, which is subexponential; 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
_{n}C_{m} = n!/m!(nm)! ;
now assuming m > 2, n > 0,
 Find s such that _{s+m3}C_{m2} = n_{0} <= n <
n_{1} = _{s+m2}C_{m2} ;
 Set k_{0} = _{s+m4}C_{m3},
k_{1} = _{s+m3}C_{m3} ;
 Choose any k in the range
max(k_{0}, k_{1}n_{1}+n) <= k <= min(k_{1}, k_{0}n_{0}+n)
giving the size k = k(m,n) of the bottom substack
[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.
 TM(m,n,X,P,Z): To transfer a stack of n > 0 discs
from pin X to pin Z, via set P of m2 other pins:
 set k = k(m,n): Compute an optimal partition k,nk
of the stack;
 set Y = member(P): Choose new pin Y bearing no disc
smaller than the largest stack disc;
 TM(m,nk,X,P,Y): Transfer nk discs from
X to Y, using all m pins;
 TM(m1,k,X,PY,Z): Transfer k discs from X
to Z, using m1 pins omitting Y;
 TM(m,nk,Y,P,Z): Transfer nk discs from Y
to Z, using all m pins.
An expression for the time in the special case where
n = n_{0} = _{s+m3}C_{m2},
and the only possibility is
k = _{s+m4}C_{m3},
follows from noticing that in any Frametype solution the largest disc makes
1 move, the next (m2) make 2,
the next _{m1}C_{2} make 4, etc,
down to the smallest k making 2^{s1}.
For general n there are a further nn_{0} small discs
making 2^{s}, giving total time
 (n  n_{0}) 2^{s} +
[ SUM_{i=0}^{i=s1} 2^{i}
_{i+m3}C_{m3} ]
 = (1)^{m} + [ (n  n_{0}) +
SUM_{j=0}^{j=m3} (2)^{j}
_{s+m3}C_{m3j} ] 2^{s}
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
(m2)th root of n(m2)!, from which the exact value can be
located by trialanderror adjustment.
An illustrative snapshot of the solution in operation is provided by
the special case n = _{s+m3}C_{m2} above
at exactly halftime, when pin 1 is empty and for 0 <= i <= m2
the substack on pin mi comprises the next
_{s2+i}C_{s2} discs in descending order of size.
For instance, taking m = 6 pins, s = 4,
n = _{7}C_{4} = 35 discs,
the time equals
2^{0} _{3}C_{3} +
2^{1} _{4}C_{3} +
2^{2} _{5}C_{3} +
2^{3} _{6}C_{3} = 1+8+40+160 = 209;
after move 105 there are
 1 disc of size 35 on pin 6,
 3 discs of sizes 34 to 32 on pin 5,
 6 discs of sizes 31 to 26 on pin 4,
 10 discs of sizes 25 to 16 on pin 3,
 15 discs of sizes 15 to 1 on pin 2,
 none on pin 1.
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.
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 i1;
 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,...,l1, and i+1, i1 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 initialfinal 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 3pin problem, transferring the
k discs of the singleton ith 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(n1);
 { HR(1, i); AR(n1, i) }
for i = 1, ..., l1;
 HA(1, 0); RA(n1, 0) };
 HRHA(n) = {
 HAHR(n1);
 HR(1, 0); AR(n1, 0);
 { HA(1, i); RA(n1, i) }
for i = l1, ..., 1 };
 HARA(n) = {
 HR(n1, 0); HA(1, 0);
 { RH(n1, i); RA(1, i) }
for i = 1, ..., l1;
 RAHA(n1) };
 RAHA(n) = {
 { HR(n1, i); HA(1, i) }
for i = l1, ..., 1;
 RH(n1, 0); RA(1, 0);
 HARA(n1) };
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(n1); HR(1, 0);
 AR(n1, 0); HA(1, 1);
 RH(n1, 0); RA(1, 0);
 HARA(n1) } if l = 2;
 HAHA(n) = {
 HAHR(n1); HR(1, 0);
 HA(1, i) for i = l1, ..., 2;
 AH(n1, 0); HA(1, 1); RA(1, 0);
 HARA(n1) } 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 toplevel 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) = 2^{n}  1 =
timing for the classical problem;
 R(n) = timing for the subsidiary problems
HAHR(n) etc;
 P(n) = timing for the toplevel problem
HAHA(n).
By inspection of the pseudocode above it may be seen that R(n)
is independent of which subproblem is chosen; also
 R(1) = l; and for n > 1,
 R(n) = R(n1) + l T(n1) + l I(n1);
 P(n) = 2 R(n1) + T(n1) +
(l + 1) I(n1) if l > 2;
 = 2 R(n1) +
2 T(n1) + 3 I(n1) if l = 2.
Solving the recurrence and substituting,
 R(n) = l T(n) =
l (2^{n}  1);
 P(n) = 0 if n = 0 or l < 2;
 =
l T(n) + T(n1) + 1 =
l (2^{n}  1) + (1/2) 2^{n}
if l > 2;
 =
3 T(n) = 3 (2^{n}  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 timewasting 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 subproblems. 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(n1) + 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 twinstack 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(n1) + f(n1) 1 + 4 = 2 f(n1) + 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 manfriendly
smallestdisc 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^(j1) for 0 < j < n;
h(j) = h(2nj);
g(j) = (j+n+1)mod 2;
l stacks n discs: p = p(l,n) = number of phases = 2(l1)(n1) + 2 for l > 2;
h(0) = 1; h((l1)k) = 3.2^(k1) for 0 < k < n1;
h((l1)k + i) = 2^k for 0 < i < l1;
h((l1)(n1)) = 2^(n2) + 1; h((l1)(n1) + i) = 1; h((l1)n) = 1;
h(j) = h(pj) for j > (l1)n.
g(j) = (j+1)mod l for j mod 2(l1) = 0, 1, ..., l1 when n even;
= (j+1)mod l for j mod 2(l1) = l1, l, ..., 0 when n even, j < (l1)n;
g(j) = (j)mod l for j mod 2(l1) = 0, 1, ..., l1 when n odd;
= (j+2)mod l for j mod 2(l1) = l1, l, ..., 0 when n odd, j < (l1)n;
g((l1)n) = 0;
g(j) = g(pj)mod l, for j > (l1)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.
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) :
 Every disc shall flip as it moves to a new pin;
 No disc may be placed on a disc of a different colour.
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
 (1) on the right, with the colour flipped  DDE(n);
 (2) on the right, with the colour unchanged  DDF(n);
 (3) back on the left, with the colour flipped  EDD(n).
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 subfunctions 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(n1) + 1 + DDA(n1)
 DDF(n) = ADE(n1) + 1 + DAE(n1) + 1 + DDA(n1)
 EDD(n) = ADE(n1) + 1 + DAE(n1) + 1 + DAE(n1) + 1 + DDA(n1)

 ADE(n) = ADE(n1) + 1 + DBA(n1), DDB(n) = ADE(n)
 ADF(n) = ADE(n1) + 1 + DAB(n1) + 1 + ADA(n1), DDA(n) = ADF(n)
 DBE(n) = ABE(n), DAE(n) = DBE(n)

 ADB(n) = ABE(n1) + 1 + DBA(n1)
 ABE(n) = ADB(n1) + 1 + ABA(n1), DAB(n) = ABE(n)
 ABF(n) = ABE(n1) + 1 + DAB(n1) + 1 + ABA(n1), DBA(n) = ABF(n)
 ADA(n) = ABA(n)
 DBB(n) = ABB(n), AAE(n) = DBB(n)

 ABB(n) = ABB(n1) + 1 + ABA(n1), AAB(n) = ABB(n)
 ABA(n) = ABA(n1) + 1 + ABA(n1) + 1 + ABA(n1)
Fortunately, by this stage only one instance remains outstanding where it is
unclear which of two possible breakdowns to use:
ADE(n) = ADE(n1) + 1 + DBA(n1) appears in practice to be preferable to
the alternative ADE(n) = ADF(n1) + 1 + DAB(n1), 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
 E^{6}  5E^{5} + 6E^{4} + 3E^{2}  11E + 6
 = (E  3)(E^{3}  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) 3^{n}.
Two bottomlevel 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) = 3^{n}  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 fullycoloured problem:
its time is (3^{n}  1)/2 for n > 1.
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
3^{n}  1, rather than Classic with a time of
2^{n}  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 nk 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
2^{i} 3^{j} into ascending order of magnitude,
where i, j = 0,1,...; and define a_{n} to be
the nth number in this sequence for n > 0. Now choose k
such that
 3^{k1} <= a_{n}
< 3^{k};
that is,
 k = 1 + [log(a_{n})/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(a_{1} + ... + a_{n});
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.
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".
 Three pins in a row, a single stack of discs;
 Each disc may coloured any of three colours A,B,C;
 Each time a disc moves, its colour flips to the next in cyclic order;
 A disc may move only onto a larger disc of the same colour;
 Initially, all discs stacked on the lefthand pin, coloured A;
 Finally, all discs to be stacked on the righthand pin, coloured A.
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):
 Via Cyclic_R, transfer all but largest disc from pin X
to Y, colour B;
 Move largest disc from X to Z to X to Z;
 Via Cyclic_L reversed, transfer all but largest disc from
Y to Z.
Alternatively, the subsidiary transfers can be interchanged
(the Brandonbug variation):
 Via Cyclic_L reversed, transfer all but largest disc from
X to Y, colour C;
 Move largest disc from X to Z to X to Z;
 Via Cyclic_R, transfer all but largest disc from pin Y
to Z.
The (optimal) time for either is easily computed from that for Cyclic:
for n discs, A(n1) + C(n1) + 3 moves.
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 Frametype 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 :
 Each disc has one of two fixed colours;
 The colours of all discs on each pin alternate.
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 Frametype,
costs time 137 moves against 129 for Reves. At n = 21, the fastest
Frametype solution costs 337 against 321  we do not know whether the
former is optimal, though according to Korf the latter is.
An Frametype algorithm may be developed for this problem by combining
the solution given earlier for Reves with the colouredbase 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 kth and k+1th
triangular numbers, then temporarily stacks the nk 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
 the triangular numbers T_{k} = k(k+1)/2,
 the semisquare numbers S_{k} = [(k+1)^{2}/2];
if T_{k} <= n < T_{k+1}, then
S_{k} 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
 n = S_{k} + p
where [(k+1)/2] < p < [(k+2)/2] unless n is triangular;
large n with small p are distant from triangular numbers.
For example, centred on S_{4} = 12 midway between
T_{4} = 10, T_{5} = 15
is the 5tuple 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 :
 DDDD(n) = Reves(n) just when  p(n)  <= 2.
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' = nk, nk1 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 5tuples p(n) <= 2;
by induction (downwards) on k, we shall eventually descend to the
5tuple around n = 12, and the algorithm will execute as fast as Reves.
For all other n we shall eventually strike some T_{i} >= 15,
and be forced eventually to decrement it by some amount nonoptimal 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
 j = [(2n+1/4)^{1/2}],
for which n  T_{j} < j/2.
To motivate this rule, consider the bottomlevel functions BABB(n),
BAAB(n), illustrated under Checkers_B, Checkers_C.
Experimentation suggests (idleness currently precluding proof) that :
 When j is even, odd then BABB(n) <=, >= BAAB(n)
respectively;
In the same way as earlier we can show that BADB(n) =
min(BAAB(n),BABB(n)) = DDDD(n) for 4 of any 5tuple of n with
p(n) <= 2.
A curiosity is the manfriendly 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.
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):
 Every disc shall flip as it moves to a new pin;
 No disc may be placed on a disc of the same colour.
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
 (1) on the right, with the colour unchanged  DDDF(n);
 (2) on the right, with the colour flipped  DDDE(n);
 (3) back on the left, with the colour flipped  EDDD(n).
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:
 For Reversi there are in general no optimal solutions with
intermediate consecutive stacks.
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 subproblems.
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 3pin 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 FourStar
variation introduced earlier, with W the distinguished pin.]
Notice that W only ever holds at most one disc, and that the
time is 2(2^{n}  1). Even allowing for the onedisc
restriction, this is suboptimal: Reversi_H improves on it with
[(4/3)(2^{n}1/2)] moves.
Three bottomlevel 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 movegraph);
remarkably, it possesses a periodic algorithm [unlike the others] Reversi_P, with period 4,8 moves for n even,odd:
 To transfer n > 0 discs from W via X,Y
to Z, with bases coloured BABB:
 Set t = 0 initially;
 At move t, move one disc from pin P to Q where
 For n even:
 t mod 4 = 1: P = W; Q = X;
 t mod 4 = 2: P = X; Q = Z;
 t mod 4 = 0: P = Y; Q = W;
 t mod 4 = 3: P = Z; Q = Y;
 For n odd:
 t mod 8 = 0, 3: P = W; Q = X;
 t mod 8 = 1, 6: P = X; Q = Z;
 t mod 8 = 2, 5: P = Y; Q = W;
 t mod 8 = 4, 7: P = Z; Q = Y;}
 Increment t and repeat until the entire stack is on Z .
[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)3^{n/2}  2 for n even,

(3)3^{[n/2]}  2 for n odd;
 BABB(n) = (2)3^{n/2}  2 for n even,

(4)3^{[n/2]}  2 for n odd;
 BAAB(n) = [(8/3)3^{n/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 (3^{1/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!
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 superclass CyclicDefn,
and currently located at lines 263321 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 overriding
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.
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;
highlevel 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 userfriendly action taken via the programming
environment.
On starting the program an intermittent nonfatal 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 ([email protected])
[on a good day, they might even receive a reply ...].
The program opens two windows, both of which should be resizable 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 reinitialised at
any time by choosing a variation from the menu, or by resetting the numbers
of discs or pins.
To singlestep 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
leftclicking on its old pin, whence it will disappear; then leftclicking 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 reinitialised.
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.

Sun Microsystems' Java JDK download.

RealJ Java application development environment.

M. Kolar's Directory of Hanoi Programs.

Eric Weisstein's Treasure Trove of Mathematics.

Paul Stockmeyer's papers, including
 an extensive Hanoi bibliography;
 Variations on the FourPost Tower of Hanoi Puzzle.

A. S. Fraenkel's Combinatorial Games bibliography.
 W. W. Rouse Ball & H. S. M. Coxeter
Mathematical Recreations and Essays ed 12 316,
University of Toronto (1982).
 M. D. Atkinson The Cyclic Towers of Hanoi
Info. Proc. Letters 13(3), 118119 (1981).
 W. Feller An Introduction to Probability Theory an its
Applications, vol I ed. 2 Wiley (1957).
Info. Proc. Letters 13(3), 118119 (1981).
 Richard E. Korf Lineartime Diskbased Implicit Graph Search,
J. ACM 55(6) 2665 (2008).
 Steven Minsker The Towers of Hanoi Rainbow Problem
Journal of Algorithms 10(1) 119 (1989).
 Steven Minsker The Towers of Antwerpen Problem
Information Processing Letters 38(2) 107111 (1991).
 Victor Mascolo U.S. patent application
Feb. 1, 2007, Serial No.11/701,454.
 Craig Turner Towers of Hanoi on Graphs and Digraphs
thesis, Georgia College (1995). [Useful short bibliography]
<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