==> induction/hanoi.s <==
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.