Is there an algorithm for solving the Hanoi tower puzzle for any number of towers?
induction/hanoi Added material
Problem
Is there an algorithm for solving the Hanoi tower puzzle for any number of towers? Is there an equation for determining the minimum number of moves required to solve it, given a variable number of disks and towers?
Show solution
The best way of thinking of the Towers of Hanoi problem is inductively.
To move n disks from post 1 to post 2, first move (n-1) disks
from post 1 to post 3, then move disk n from post 1 to post 2, then move
(n-1) disks from post 3 to post 2 (same procedure as moving (n-1) disks
from post 1 to post 3). In order to figure out how to move (n-1) disks
from post 1 to post 3, first move (n-2) disks . . . .
As far as an algorithm which straightens out any legal position is
concerned, the algorithm would go something like this:
1. Find the smallest disk. Call the post that it's on post 1.
2. Find the smallest disk which is not on post 1. This disk is, say,
size k. (I am calling the smallest disk size 1 here.) Call the post
that disk k is on post 2. Disks 1 through (k-1) are then all stacked up
correctly on post 1 disk k is on top of post 2. This follow from the
fact that the disks are in a legal postition.
3. Move disks 1 through (k-1) from post 1 to post 2, ignoring the other
disks. This is just the standard Tower of Hanoi problem for (k-1)
disks.
4. If the disks are not yet correctly arranged, repeat from step 1.
In fact, this gives the straightening with the fewest number of moves.
With 3 towers, for N number of disks, the formula for the minimum number of
moves to complete the puzzle correctly is:
(2^N) - 1
This bit of ancient folklore was invented by De Parville in 1884.
``In the great temple at Benares, says he, beneath the dome which
marks the centre of the world, rests a brass plate in which are
fixed three diamond needles, each a cubit high and as thick as
the body of a bee. On one of these needles, at the creation,
God placed sixty-four discs of pure gold, the largest disc resting
on the brass plate, and the others getting smaller and smaller
up to the top one. This is the Tower of Bramah. Day and night
unceasingly the priests transfer the discs from one diamond needle
to another according to the fixed and immutable laws of Bramah,
which require that the priest on duty must not move more than one
disc at a time and that he must place this disc on a needle so
that there is no smaller disc below it. When the sixty-four
discs shall have been thus transferred from the needle on which
at the creation God placed them to one of the other needles,
tower, temple, and Brahmins alike will crumble into dust, and
with a thunderclap the world will vanish.'' (W W R Ball,
MATHEMATICAL RECREATIONS AND ESSAYS, p. 304)
This has been discussed by several authors, e.g.
Er, Info Sci 42 (1987) 137-141.
Graham, Knuth and Patashnik, _Concrete_Mathematics_.
There are many papers claiming to solve this, and they are probably
all correct but they rely on the unproven "Frame's conjecture".
In particular, for the 4 peg case the conjecture states that an optimal
solution begins by forming a substack of the k smallest discs, then moving
the rest, and then moving those k again; k to be determined.
Here is a extensible bc program that does the same work. The output
format is not that great. We get 300 numbers as output. The first
hundred represent N, the next 100 represent f(N) and the last hundred
represent i, which is the number of discs to move to tmp1 using f(N).
For convenience, I have here some values for N <= 48. Enjoy.
Sharma
N 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
f(N) 1 3 5 9 13 17 25 33 41 49 65 81 97 113 129 161 193 225 257
i 0 1 1 2 2 3 3 4 5 6 6 7 8 9 10 10 11 12 13
N 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
f(N) 289 321 385 449 513 577 641 705 769 897 1025 1153 1281 1409 1537 1665
i 14 15 15 16 17 18 19 20 21 21 22 23 24 25 26 27
N 36 37 38 39 40 41 42 43 44 45 46 47 48
f(N) 1793 2049 2305 2561 2817 3073 3329 3585 3841 4097 4609 5121 5633
i 28 28 29 30 31 32 33 34 35 36 36 37 38
/* This is the bc program that gives f(N) for 4 peg case */
w = 101; /* This represents the number of disks */
m[0] = 0;
m[1] = 1;
m[2] = 3;
m[3] = 5;
m[4] = 9;
m[5] = 13;
m[6] = 17;
/* f(n) is the function that gives the min # of moves for 4 peg case */
define f(n) {
return (m[n]);
}
/* g(n) is the function that fives the min # of moves for 3 peg case */
define g(n) {
return (2^n - 1);
}
/* x(n) is the Optimization Routine */
define x(n) {
auto j
auto r
auto i
if(n == 1) return (1);
j = f(1) + g(n-1);
for(i = 2; i < n; i++) {
r = f(i) + g(n-i);
if(r < j) { j = r; d = i; }
}
return (j);
}
/* main program */
for(q = 4; q < w; q++) {
t = x(q-1);
m[q] = 2 * t + 1;
d[q] = d;
};
/*This for loop prints the number of discs from 1 <= n <= w*/
for(q = 1; q < w; q++) {
q;
}
/*This for loop prints f(n) for 1 <= n <= w */
for(q = 1; q < w; q++) {
m[q];
}
/*This for loop prints i for 1 <= n <= w
i represents the number of disks to be moved to tmp location using f(n)
N-i-1 will be moved using g(n) */
for(q = 1; q < w; q++) {
d[q];
}
--
sharma@sharma.warren.mentorg.com
There is a solution to the Tower of Hanoi problem which does not require
recursion. On odd-numbered moves, move the smallest sized disk clockwise.
On even-numbered moves, make the single other move which is possible.
Additional material
In the Towers of Hanoi puzzle, is it possible to determine how many
moves into a solution we are simply by looking at the current disk
position (without actually going through a full solution until hitting
a matching position)?
For example, in a three disk version, if there is one disk on each of
the three posts, then we are 2 moves into the solution (but I only know
that because I walked through the solution until I got that position).
Is there an algorithm that works for any number of disks that doesn't
involve reworking the puzzle?
-- Peter Blaskowski <pblask@millcomm.com>
Here's a recursive algorithm that calculates how many moves it will
take to bring all the disks onto one peg. Since just seeing a config
doesn't tell you whether you're two moves into a solution or two moves
away from a solution, that's the best we can manage (but see the
Afterward).
Let's say that we have M disks numbered by size. Look at the numbers
of the lowest disks on each peg. Obviously, M is the highest label,
let N be the second-highest. So, you can divide the process of
getting all of the disks onto the M-peg into three steps: moving all
of the disks less than N onto the third peg, moving N to the M peg,
and moving the disks less than N onto the M peg. The second step
requires one move (obviously), and the third step requires
2^(N-1)-1 moves (by the normal means of solving Towers of Hanoi).
The first step can be calculated by this same process by ignoring
all the disks larger than N-1 and imagining a "virtual" disk of
highest value on the third peg (so as to force all the remaining
disks to go to that peg). In this new process, the value of M is
decreased by at least one, so we know that the process will end
eventually.
Not only does this process tell you how many moves you are away
from a completely stacked peg, but it will give you the ideal set
of moves to reach that goal.
Afterward: If you have your puzzle with one disk on each peg, but
you know that you eventually want to stack the disks onto the third
peg, then this process will work if you imagine that there is a
new largest disk at the bottom of the third peg. Since this procedure
comes up with the shortest path, that will obviously be the one that
doesn't move this fourth peg [Editor: presumably "fourth disk", the
imagined largest one], so it will lead you to your desired goal.
-- Matthew Daly <daly@PPD.Kodak.COM>
I've seen 3 answers, all going back to the recursion routine; but that
wasn't what P.B. wanted.
I know of a deterministic approach (I've found it in a big 2-volume
book by the name "Winning Games" or the like, quite rare ...). It
involved representing the disks' positions as a string in base 3.
Now, when you start all disks are on bar 0, say, so the string is all
zeros. Next you move the smallest disk to bar 2, so the last place
changes to 2, and so on.
If you trace this line you'll see there's a way to tell the state of
the problem by the arrangement of the disks (the string), and vice
versa - to tell what position is right at a required step.
I used to teach this procedure long time ago when I'd finished telling
the pupils how fun it is to program the recursive routine to solve the
problem, thus blowing out much of the air the wise scheme holds for
many starting programmers.
-- A.E. <elazari@netvision.net.il>
[ Editor: the 2-volume book is presumably _Winning Ways for your
Mathematical Plays_ by Berlekamp, Conway and Guy. ]
rogerj@goya.its.rpi.edu (Diversion (Jeff Rogers)) writes:
>What is the optimal solution to a towers of Hanoi style problem where you
>have N towers and M disks?
>The solution is trivial for M<N, and well known for N=3, but what about for
>larger numbers?
>Does increasing N above 3 give any substantial decrease in the solution
>time? I'd guess the solution would remain O(2^M), but I'm not sure.
I'm not sure it is in the FAQ, but it does come up fairly regularly.
As far as I know, the state is this:
- No one has a non-backtracking strategy for N>3 that has been proven
optimal.
- A fairly simple, presumably optimal, strategy exists for N=4. This
may generalize to larger N.
The strategy is move some of the disks to one of the intermediate
pegs, then move the remainding disks to the target peg using the
strategy 3 pegs, then move the disks from the intermediate peg to the
last peg. The first and last part can use all four pegs. The problem
is now: How many disks [Editor: "pegs" in the original] must be moved
to the intermediate peg? It appears that the optimal is
n-round((sqrt(8*n+1)-1)/2) (though this has not been proven). It also
appears that it doesn't matter what kind of rounding you use: up, down
or to nearest yield the same number of moves in all the cases I have
tried (except when n=2, where rounding down means you move all pieces
in the first step, thus getting you nowhere). As a pseudo-Pascal
algorithm it is:
procedure hanoi4(n,peg1,peg2,peg3,peg4);
var a;
begin
if n=1 then writeln("from ",peg1," to ",peg4)
else begin
a := round((sqrt(8*n+1)-1)/2);
hanoi4(n-a,peg1,peg2,peg4,peg3);
hanoi3(a,peg1,peg2,peg4);
hanoi4(n-a,peg3,peg1,peg2,peg4)
end
end;
procedure hanoi3(n,peg1,peg2,peg3);
begin
if n=1 then writeln("from ",peg1," to ",peg3)
else begin
hanoi3(n-1,peg1,peg3,peg2);
writeln("from ",peg1," to ",peg3);
hanoi3(n-1,peg2,peg1,peg3)
end
end;
A table of the required number of moves for small values of n is shown
below
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
moves 1 3 5 9 13 17 25 33 41 49 65 81 97 113 129 161 193 225 257
The number of moves is approximately (a-1)*2^a+1, where a =
(sqrt(8*n+1)-1)/2. If a is integral, this value is exact. This happens
for n = 1, 3, 6, 10, 15 etc. (the triangular numbers). Since a is
O(sqrt(n)) we get O(sqrt(n)*2^sqrt(n)) moves, which is much better
than the O(2^n) moves required with three pegs.
-- Torben Mogensen <torbenm@diku.dk>, November 1993
[ Editor: an explanation of the basic three-peg puzzle, June 1995. ]
The tower of hanoi puzzle originally consisted of 64 disks that had to
be moved from one peg to another (See below), it was figured that when
all the disks had been moved, the world would end.
Rules:
You have three pegs. On the leftmost peg are 3 disks of
increasingly smaller size. The object is to move them to the rightmost
peg. You can only move one disk at a time, and while a smaller disk can
go onto a larger disk, a larger disk CANNOT go onto a smaller one.
Example:
Starting Position:
x x x
xxx x x
xxxxx x x
xxxxxxx x x
====================================================
First Move:
x x x
x x x
xxxxx x x
xxxxxxx x xxx
====================================================
Second Move:
x x x
x x x
x x x
xxxxxxx xxxxx xxx
====================================================
Third Move:
x x x
x x x
x xxx x
xxxxxxx xxxxx x
====================================================
Fourth Move:
x x x
x x x
x xxx x
x xxxxx xxxxxxx
====================================================
Fifth Move:
x x x
x x x
x x x
xxx xxxxx xxxxxxx
====================================================
Sixth Move:
x x x
x x x
x x xxxxx
xxx x xxxxxxx
====================================================
Seventh Move:
x x x
x x xxx
x x xxxxx
x x xxxxxxx
====================================================
Now, aren't you glad I didn't do the 64 disk version!
There is a very nice recursive routine for solving a Tower of
hanoi or arbitrary size. If you want it, let me know, and I'll
get it out of my archives.
-- Charles Serfoss <vecmor@rahul.net>