38. Tower of Hanoi
Introduction
The Tower of Hanoi problem is to move a set of n different-sized disks from one peg to another, moving one disk at a time, using an intermediate peg if necessary. At all times no larger disk may sit on top of a smaller disk.
For example, moving 3 disks from peg 0 to peg 1 can be done as follows:
- move disk 0 from peg 0 to peg 1
- move disk 1 from peg 0 to peg 2
- move disk 0 from peg 1 to peg 2
- move disk 2 from peg 0 to peg 1
- move disk 0 from peg 2 to peg 0
- move disk 1 from peg 2 to peg 1
- move disk 0 from peg 0 to peg 1
The description of the moves can be shortened if we observed that in moving a disk from peg A to peg B, it is always the top disk on peg A that is moved. Thus the 3-disk problem can be solved as follows:
0 1 0 2 1 2 0 1 2 0 2 1 0 1
Legend has it that a group of priests has been solving the 64-disk problem since the beginning of time, and when they finish, the world will come to an end.
An Initial Solution
There is a simple recursive solution to the n-disk problem: First, move disks 0 to n-2 from peg 0 to peg 2 , then move disk n-1 from peg 0 to peg 1 , then move disks 0 to n-2 from peg 2 to peg 1 . If there is just one disk, the one disk can be moved from peg 0 to peg 1 straightaway.
This can be implemented as an ambivalent function: the right argument is the number of disks; the left argument are 3 integers of the pegs (from, to, via), with a default of 0 1 2 .
H←{
⍺←0 1 2
0=⍵:0 2⍴0
(⍺[0 2 1] ∇ ⍵-1)⍪(2↑⍺)⍪(⍺[2 1 0] ∇ ⍵-1)
}
H 3
0 1
0 2
1 2
0 1
2 0
2 1
0 1
From the definition of H , it is easy to see that
the n-disk problem requires ¯1+2*n moves.
If n=0 , there
are 0 moves (0=¯1+2*0).
If n=k-1 requires ¯1+2*k-1 moves,
then n=k requires the following
numbers of moves:
¯1+2*k-1 (⍺[0 2 1] ∇ ⍵-1) 1 (2↑⍺) ¯1+2*k-1 (⍺[2 1 0] ∇ ⍵-1)
for a total of ¯1+2*k moves. A similar argument shows that the n-disk problem requires ¯1+2*n calls of the function H .
≢∘H¨ ⍳10 0 1 3 7 15 31 63 127 255 511 ¯1 + 2 * ⍳10 0 1 3 7 15 31 63 127 255 511
Singly Recursive Solutions
The two recursive steps in H differ only in the labelling of the pegs. Therefore we can replace them with a single recursive call, and do two relabellings of the pegs to get the effect of two recursions. That is function H1 below.
Moreover, in verb H1 the left argument is unchanged
in the recursion; that is, the left argument is
always
We saw previously that on the n-disk problem the doubly recursive H required ¯1+2*n calls. In the singly recursive H1 and H2 , the n-disk problem requires n calls. Benchmarks on the 10-disk problem demonstrate the difference this makes.
H1←{⍺←0 1 2 ⋄ 0=⍵:0 2⍴0 ⋄ 0 2 1[t]⍪0 1⍪2 1 0[t←⍺ ∇ ⍵-1]}
H2←{0=⍵:0 2⍴0 ⋄ 0 2 1[t]⍪0 1⍪2 1 0[t←∇ ⍵-1]}
(H ≡ H1)¨ ⍳10
1 1 1 1 1 1 1 1 1 1
(H ≡ H2)¨ ⍳10
1 1 1 1 1 1 1 1 1 1
Non-Recursive Solutions
We now proceed to derive non-recursive solutions to the problem.
The results of verbs H , H1 , and H2 are rows of the 6-row matrix A (the 6 different ways of moving from peg i to peg j where i and j can be 0 , 1 , or 2). Thus a more efficient representation for the solutions is to encode the moves as row indices of A , the integers from 0 to 5 .
A← 6 2 ⍴ 0 1 0 2 1 0 1 2 2 0 2 1 A 0 1 0 2 1 0 1 2 2 0 2 1 A ⍳ H2 1 0 A ⍳ H2 2 1 0 5 A ⍳ H2 3 0 1 3 0 4 5 0 A ⍳ H2 4 1 0 5 1 2 3 1 0 5 4 2 5 1 0 5 A ⍳ H2 5 0 1 3 0 4 5 0 1 3 2 4 3 0 1 3 0 4 5 0 4 3 2 4 5 0 1 3 0 4 5 0
Judicious alignment of the indices reveals a pattern:
1: 0 2: 1 0 5 2: 1 0 5 3: 0 1 3 0 4 5 0 3: 0 1 3 0 4 5 0 4: 1 0 5 1 2 3 1 0 5 4 2 5 1 0 5 4: 1 0 5 1 2 3 1 0 5 4 2 5 1 0 5 5: 0 1 3 0 4 5 0 1 3 2 4 3 0 1 3 0 4 5 0 4 3 2 4 5 0 1 3 0 4 5 0
To get from A ⍳ H2 n-1 to A ⍳ H2 n , intersperse the result for n with 1 5 2 if n is even and with 0 3 4 if n is odd. Thus:
H3←{0=⍵:⍬ ⋄ ¯1↓,((2*⍵-1)⍴(2|⍵)⌷2 3⍴1 5 2 0 3 4),⍪0,⍨∇ ⍵-1}
H3 3
0 1 3 0 4 5 0
(A ⍳ H2 3) ≡ H3 3
1
(A∘⍳∘H2 ≡ H3)¨ ⍳10
1 1 1 1 1 1 1 1 1 1
H3 n works by appending a scalar to the result
of
The list of numbers to be stitched (repetitions
of
xn f ... f x3 f x2 f x1 ⊃ f / xn ... x3 x2 x1
Moreover, we can avoid incorporating into f the appending and dropping of scalar, if we start out with an “extra” scalar and drop it only at the end:
⊃ f / xn ... x3 x2 x1 ¯1 ↓ ⊃ g / xn ... x3 x2 x1 atom
In H4 below, the function g is (, ,⍤0) (ravel stitch).
H4←{¯1↓⊃(,,⍤0)/⍵,⍨(⌽2*⍳⍵)⍴¨⌽⍵⍴(0 3 4)(1 5 2)}
(H3 ≡ H4)¨ ⍳10
1 1 1 1 1 1 1 1 1 1
arg←{⍵,⍨(⌽2*⍳⍵)⍴¨⌽⍵⍴(0 3 4)(1 5 2)}
arg 1
┌─┬─┐
│0│1│
└─┴─┘
arg 2
┌───┬─┬─┐
│1 5│0│2│
└───┴─┴─┘
arg 3
┌───────┬───┬─┬─┐
│0 3 4 0│1 5│0│3│
└───────┴───┴─┴─┘
arg 4
┌───────────────┬───────┬───┬─┬─┐
│1 5 2 1 5 2 1 5│0 3 4 0│1 5│0│4│
└───────────────┴───────┴───┴─┴─┘
arg 5
┌───────────────────────────────┬───────────────┬
│0 3 4 0 3 4 0 3 4 0 3 4 0 3 4 0│1 5 2 1 5 2 1 5│...
└───────────────────────────────┴───────────────┴
┬───────┬───┬─┬─┐
...│0 3 4 0│1 5│0│5│
┴───────┴───┴─┴─┘
There is another possibility. The pattern in H4 is:
¯1 ↓ ⊃ g / xn ... x3 x2 x1 atom
In an intermediate stage, when g is being applied,
xi g yi
g “knows” from yi alone what xi has to be: the length of yi determines the length of xi , and the leading scalar of yi (0 or 1) determines whether 1 5 2 or 0 3 4 should be ravel-stitched. This suggests another solution: a monad is applied n times to the vector ,1 .
H5←{¯1↓{⍵(,,⍤0)⍨(≢⍵)⍴(⊃⍵)⊃(1 5 2)(0 3 4)}⍣⍵,1}
(H4 ≡ H5)¨ ⍳10
1 1 1 1 1 1 1 1 1 1
rsa←{⍵(,,⍤0)⍨(≢⍵)⍴(⊃⍵)⊃(1 5 2)(0 3 4)}
rsa 1
0 1
rsa rsa 1
1 0 5 1
rsa rsa rsa 1
0 1 3 0 4 5 0 1
rsa⍣3 ,1
0 1 3 0 4 5 0 1
H5 3
0 1 3 0 4 5 0
Conclusion
The Tower of Hanoi problem can be solved in a variety of ways, with a wide variation in efficiency.
- H double recursion
- H1 single recursion
- H2 single recursion monad
- H3 single recursion, scalar representation
- H4 non-recursive, reduction
- H5 non-recursive, power
Appeared in J in
[107,
108].