Towers of Hanoi, Simplified in J
Vector 12:3, page 27
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 27
Introduction¶
Towers of Hanoi is a classic puzzle comprised of three pegs and a stack of different-sized discs, as depicted below in its starting state with 4 discs:
|| || ||
==== || ||
====== || ||
======== || ||
========== || ||
-----------------------------------------------
START PARK GOAL
The objective is to get all discs onto the GOAL peg by moving one disc at a time, using the PARK peg temporarily, without ever placing a larger disc on top of a smaller disc.
The general solution (for N discs) is well-known:
Move N-1 discs to the PARK peg
Move the Nth disc to the GOAL peg
Move N-1 discs to the GOAL peg
This recursive algorithm specifies how to solve the N-disc puzzle in terms of the (N-1)-disc puzzle (twice), which uses the same algorithm for one less disc with PARK as GOAL (in the first step) and with START as PARK (in the last step), both of which in turn use the same algorithm for one less disc, etc. Ultimately, the 1-disc puzzle is easily solved by just moving one disc (and no move is needed for 0-discs).
Accordingly, the Towers of Hanoi puzzle is often used to illustrate recursion, e.g. [1] in APL, [2] in APL2, and [3] in J. It is typically programmed either by representing pegs or by representing discs or both. (See Appendix.) Here, however, we will represent moves for the Towers of Hanoi, which enables a simplified program definition, as well as a mnemonic solution.
Moves for Towers of Hanoi¶
The three basic ways to move a disc between pegs are named (arbitrarily) A, B, and C, as shown below:
B
<--------------------------->
|| || ||
|| A || C ||
|| <-----------> || <-----------> ||
|| || ||
|| || ||
-------------------------------------------
START PARK GOAL
Note that although a move may occur in either direction, only one will be legal since the other direction would place a larger disc on top of a smaller one. So there is no ambiguity in this representation.
Program to Solve Towers of Hanoi¶
Here is a generalized J program to generate a sequence of moves to solve the Towers of Hanoi puzzle for any number of discs.
It uses the following utility conjunctions for ease in reading:
Else =. ` NB. Else is Tie, which ties two verbs together
If =. @. NB. If is Agenda, which selects first verb
NB. on left if verb on right returns 0 (false)
NB. or second verb if 1 (true)
The main program requires two inputs: the names of the moves (corresponding to the diagram above) and the number of discs (a positive integer). Its definition is:
Hanoi =. ((Park Hanoi ]-1:),Move,(Goal Hanoi ]-1:)) Else Move If (]=1:)
NB. Hanoi is a recursive program which will call itself
NB. (twice) or else just do subprogram Move
NB. if the right input (]) equals 1.
NB. Each recursive part executes Hanoi with names of
NB. moves in a new order (from subprogram on its left)
NB. and one less number of discs (on its right),
NB. then the results are joined with Move.
As specified in the first step of the algorithm (above), subprogram Park exchanges the first two moves (e.g. A and B) in order to move N-1 discs from the START peg to the PARK peg (instead of the GOAL peg):
As specified in the second step of the algorithm, subprogram Move returns the second move (e.g. B) which moves the largest disc to the GOAL:
And, as specified in the last step of the algorithm, subprogram Goal exchanges the last two moves (e.g., B and C) in order to move N-1 discs from the PARK peg (instead of the START peg) to the GOAL peg:
Examples¶
'ABC' Hanoi 1 NB. Solve Hanoi with moves 'ABC'
B NB. for 1 disc
'ABC' Hanoi 2 NB. Solve for 2 discs
ABC
'ABC' Hanoi 3 NB. 3 discs
BACBACB
'ABC' Hanoi 4 NB. 4 discs
ABCABCABCABCABC
'ABC' Hanoi 5 NB. 5 discs
BACBACBACBACBACBACBACBACBACBACB
Mnemonic Solution¶
Notice the patterns in the move sequences. For an odd number of discs, the solution is a sequence of repeated BAC moves with a final B. For an even number of discs, the solution is a sequence of repeated ABC moves. Since the total number of moves for N discs is <:2^N (one less than 2 to the Nth), the solutions are easy to remember. Or, in practice, just repeat the move sequence ABC (for even N) or BAC (for odd N) until the puzzle is solved.
Note that any names may be used for the moves. For instance:
('hop';'skip';'jump') Hanoi 3 NB. Words as moves
┌────┬───┬────┬────┬───┬────┬────┐ NB. for 3 discs
│skip│hop│jump│skip│hop│jump│skip│
└────┴───┴────┴────┴───┴────┴────┘
1 2 3 Hanoi 4 NB. Numbers as moves
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 NB. for 4 discs
Further, notice the symmetry in the solutions. The second half of the move sequence is identical to the complement of the first half reversed. In other words, the sum of the entire sequence and its reverse is all constants:
Efficient Program for Towers of Hanoi¶
The above pattern suggests a more efficient program:
Hanoi =. {~ I NB. Hanoi is (I right input)
NB. From (left input)
I =. M $ P A. i.@3: NB. I is M Reshape Pth Atomic
NB. Permuted Integers 0 1 2
NB. 0 A. 0 1 2 is 0 1 2 and
NB. 2 A. 0 1 2 is 1 0 2
P =. +: @ (2&|) NB. 0 if discs are even or
NB. 2 if discs are odd
M =. <: @ (2&^) NB. Number of moves in solution
Results are the same as for all examples above.
Howard A. Peelle
University of Massachusetts
Amherst, MA 01003 USA
References¶
[1] Peelle, H.A. APL: An Introduction, Holt, Rinehart & Winston, New York, NY 1986 pp. 308–309
[2] Brown, Pakin, & Polivka APL2 At a Glance, Prentice-Hall, Englewood Cliffs, NJ 1988 pp. 321–323
[3] Iverson, K. J Introduction and Dictionary, ISI, Toronto, CA 1994 p. 23
Appendix: Other Programs for Solving Towers of Hanoi¶
Peg Representation in APL (from [1]):
∇ PEGS HANOI N
[1] →0 IF N=0
[2] PEGS[1 3 2] HANOI N-1
[3] 'MOVE FROM ',PEGS[1],' TO ',PEGS[3]
[4] PEGS[2 1 3] HANOI N-1
∇
∇ B ← L IF C
[1] B ← C/L
∇
'ABC' HANOI 3 ⍝ Pegs named 'ABC' for START,PARK,GOAL
MOVE FROM A TO C
MOVE FROM A TO B
MOVE FROM C TO B
MOVE FROM A TO C
MOVE FROM B TO A
MOVE FROM B TO C
MOVE FROM A TO C
Peg and Disc Representation in APL2 (from [2]):
[0] N HANOI NEEDLE
[1] →(N=0)/0
[2] (N-1) HANOI NEEDLE[1 3 2]
[3] 'MOVE DISK' N 'FROM' NEEDLE[1] 'TO' NEEDLE[2]
[4] (N-1) HANOI NEEDLE[3 2 1]
3 HANOI 1 2 3 ⍝ Pegs named 1 2 3 for START,GOAL,PARK
MOVE DISK 1 FROM 1 TO 2 ⍝ Disks names 1 2 3 ...
MOVE DISK 2 FROM 1 TO 3
MOVE DISK 1 FROM 2 TO 3
MOVE DISK 3 FROM 1 TO 2
MOVE DISK 1 FROM 3 TO 1
MOVE DISK 2 FROM 3 TO 2
MOVE DISK 1 FROM 1 TO 2
Peg Representation in J (from [3]):
h=. b`(p,.q,.r)@.c
c=. 1: < [
b=. 2&,@[ $ ]
p=. <:@[ h 1: A. ]
q=. 1: h ]
r=. <:@[ h 5: A. ]
3 h 'ABC' NB. Pegs named 'ABC' for START,GOAL,PARK
AABACCA
BCCBABB
Alternative: Report only pegs to move to and always move (legally) the smaller disc not just moved
h =. # ` (p , m , r) @. c
c =. [ > 0:
m =. 1: { ] NB. p and r same as above
3 h 'ABC' NB. Pegs named 'ABC' for START,GOAL,PARK
BCCBABB NB. Pegs to move to
Disc Representation in J:
H =. (H , >: , H)@<: ` i. @. (< 1:)
H 4 NB. Discs named 1 2 3 4 1 2 1 3 1 2 1 4 1 2
1 3 1 2 1 NB. Incomplete solution
NB. (where to move to?)
Alternative using Power conjunction:
Alternative using binary array:
binary =. #: @ i. @ (2&^)
change =. }. ~: }:
H =. +/"1 @ change @ binary
H 4
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
Complete solution: