The Museum of HP Calculators


Hanoi for the HP-32S

This program is by Peter Niessen and is used here by permission.

This program is supplied without representation or warranty of any kind. Peter Niessen and The Museum of HP Calculators therefore assume no responsibility and shall have no liability, consequential or otherwise, of any kind arising from the use of this program material or any part thereof.

Overview

I wrote this program some years ago to understand how to do recursion on a machine/language without local variables. I should try this in assembler one day.

In Hanoi, monks are busy shifting a set of disks between three locations according to rules. When they are finished, this world ends. In the beginning, a number N of disks with decreasing diametre is stacked at position 1:

  |              |              |
  X              |              |
 XXX             |              |
XXXXX            |              |
  1              2              3

The objective is to move them to position 3, where smaller disks must always be above bigger disks.

The program does it for you:
Use XEQ H and enter 
A=3 R/S
B=1 R/S
C=3 R/S
R/S
and it will display the necessary steps
S=1 R/S
T=3 R/S (move disk from source 1 to target 3)
S=1 R/S
T=2 R/S
S=1 R/S
T=3 R/S
...
S=1 R/S
T=3 R/S

Due to limitations of memory/XEQ nesting, the maximum number of disks to be moved is 6.

There is an iterative solution which consists of moving the smallest disk as far as possible to the right (1 being right of 3) without touching the same disk in two consecutive moves. This results in

1->3
1->2
3->2
1->3
2->1
2->3
1->3

Alternatively, there's a recursive procedure: 1. Move N-1 disks to the non-target position 2. Move the one disk left on the source to the target 3. Move the N-1 disks on the non-target position to the target

If Q is the source and Z is the target, then the non target is given by 6-Q-Z. On the HP28 a program MOVE would look like thus the following:

<< -> n q z <<
IF n 1 > THEN
n 1 -
q
6 q - z -
MOVE
1 q z MOVE
n 1 -
6 q - z -
MOVE
ELSE
q 1 DISP
z 2 DISP
END
>> >>

Since the HP32 and basically all non 28, 38, 48 machines don't know the concept of local variables, they have to be emulated using a stack. This is what the program below does. It uses the variables A-R, or rather (1)-(18), as local variables. For each call of the routine M, we need to store n, q and z:

HP32 VAR A B C D E F G H I J K L M N O P Q R 
i / 10   0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1
i mod 1  1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8
Meaning  n q z n q z n q z n q z n q z n q z
Nesting  1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 

They are stored consecutively, beginning at what's called the block address, stored in U. To get n, q, z one adds 0, 1, 2 to U and stores it in the i register for indirect addressing. Thus, to access the variable n in the current call of M

XEQ B		; block address
XEQ A		; offset of n
RCL (i) -> gives you n

To prepare the call
MOVE(n-1, q, 6-q-z)

you have to address the memory of the next nesting level:

n
1 -
XEQ N		; next block address
XEQ A		; offset of n
STO(i)

which will store n-1 at the right place in the next block, ready for
the next call of M.

What's what?

LBL H: Main program. Calls M(n, q, z)
LBL M: The move routine. If n=1, displays the move, else calls itself
    M(n-1, q, 6-q-z);
    M(1, q, z);
    M(n-1, 6-q-z, z);

LBL D: The display routine.
LBL B: Puts the current block address into i
LBL N: Puts the next block address into i
LBL A: Adds the offset of n to i
LBL Q: Adds the offset of q to i
LBL Z: Adds the offset of z to i
LBL C: common part of A, Q, Z

Variables:
A-R: the local variable/stack
S: to display the Source
T: to display the Target
U: nesting level=block number
Z: number of moves

Have fun!

Listing

### Program which solves the ,,towers of Hanoi'' recursively. 
### PN Sun Jul 11 14:09:49 UTC 2004

H01 LBL H	; main routine, H like hanoi
H02 CLVARS	; create space
H03 INPUT A	; enter number of disks to be moved
H04 INPUT B	; source stick
H05 INPUT C	; target stick
H06 0		; initialise the block index with 0
H07 STO U	; 
H08 XEQ M	; Move (a, b, c)
H09 VIEW Z	; number of moves is displayed, end
H10 RTN		; 015.0 Bytes; CHKSUM = 0194

M01 LBL M	; recursive subroutine MOVE
M02 1		; increase block index by 1
M03 STO+ U	; to create space for a new set of local variables
M04 XEQ B	; calculate block address
M05 XEQ A	; calculate offset of a
M06 RCL(i)	; get the number of disks into the X register
M07 1		; 1
M08 x=y?	; compare with one, if so
M09 GTO D	; move one disk and display
M10 XEQ B	; else, get the current block address
M11 XEQ A	; get the address of number of disks
M12 RCL(i)	; get the number of disks, 
M13 1		; 1
M14 -		; is subtracted
M15 XEQ N	; and addressed in the next block
M16 XEQ A	; at the position of the number of disks
M17 STO(i)	; and stored
M18 XEQ B	; address
M19 XEQ Q	; the source
M20 RCL(i)	; and retrieve it
M21 XEQ N	; address the next block
M22 XEQ Q	; address the source
M23 STO(i)	; and store
M24 6		; start calculation of the intermediate storage
M25 XEQ B	; get the current block
M26 XEQ Q	; get the address of the source
M27 RCL-(i)	; 6-q
M28 XEQ B	; get the current block
M29 XEQ Z	; get the address of the target
M30 RCL-(i)	; 6-q-z
M31 XEQ N	; address the next block
M32 XEQ Z	; address the target
M33 STO(i)	; store it
M34 XEQ M	; call MOVE (a-1, q, 6-q-z) recursively!
M35 XEQ N	; get the next block
M36 XEQ A	; get the number of disks
M37 1		; 1 ist stored 
M38 STO(i)	; in the next block
M39 XEQ B	; get block address
M40 XEQ Q	; get the address in the source
M41 RCL(i)	; get the source
M42 XEQ N	; next block
M43 XEQ Q	; get address of the source
M44 STO(i)	; store the source in the next block
M45 XEQ B	; get the current block address
M46 XEQ Z	; get the target address
M47 RCL(i)	; get the target
M48 XEQ N	; get the next block address
M49 XEQ Z	; get the target address
M50 STO(i)	; store the target in the next block
M51 XEQ M	; MOVE (1, q, z)
M52 XEQ B	; prepare the call of MOVE (a-1, 6-q-z, z)
M53 XEQ A	;
M54 RCL(i)
M55 1
M56 -
M57 XEQ N
M58 XEQ A
M59 STO(i)
M60 6		; 6
M61 XEQ B
M62 XEQ Q
M63 RCL-(i)	; 6-q
M64 XEQ B
M65 XEQ Z
M66 RCL-(i)	; 6-q-z
M67 XEQ N
M68 XEQ Q
M69 STO(i)
M70 XEQ B
M71 XEQ Z
M72 RCL(i)
M73 XEQ N
M74 XEQ Z
M75 STO(i)
M76 XEQ M	; MOVE (a-1, 6-q-z, z)
M77 1		; reduce the block address
M78 STO- U	; by one
M79 RTN		; done! 118.5 Bytes, CHKSUM=48EB

D01 LBL D	; Display routine
D02 XEQ B	; fetch the source
D03 XEQ Q	;
D04 RCL(i)
D05 STO S	; store in S
D06 VIEW S	; show it
D07 1
D08 STO+ i	; address the target
DO9 RCL(i)	; get the target
D10 STO T	; store in T
D11 VIEW T	; display
D12 1		; increase the number 
D13 STO+ Z	; of moves
D14 STO- U	; move is done now, decrease the number of blocks by 1 (D12)
D15 RTN		; 022.5 Bytes, CHKSUM=B6D2

B01 LBL B	; calculates the current block address
B02 RCL U	; fetch block index (3 × (U-1) + 1)
B03 1
B04 -
B05 3
B06 ×
B07 1
B08 +
B09 STO i
B10 Rv		; roll down, is important because M expects old X reg.
B11 RTN		; 016.0 Bytes, CHSKUM=28A6

N01 LBL N	; calculates the next block address
N02 3		; which is 3 × U + 1
N03 RCL× U
N04 1
N05 +
N06 STO i
N07 Rv		; see B10
N08 RTN		; 012.0 Bytes, CHKSUM=6B7C

A01 LBL A	; address the number of disks
A02 0		; by adding zero to i
A03 GTO C	; in routine COMMON, 004.5 Bytes, CHKSUM=D9F1

Q01 LBL Q	; address the source
Q02 1		; by adding one to i
Q03 GTO C	; in routine COMMON, 004.5 Bytes, CHKSUM=400A

Z01 LBL Z	; address the target
Z02 2		; by adding 2, 003.0 Bytes, CHKSUM=4934

C01 LBL C	; COMMON for A, Q, Z
C02 STO+ i	; update index register
C03 Rv		; see B10
C04 RTN		; 006.0 Bytes, CHKSUM=6104

Go back to the software library
Go back to the main exhibit hall