The Museum of HP Calculators The Museum of HP Calculators
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.
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!
### 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, decrease 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 R↓ ; 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 R↓ ; 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 R↓ ; see B10 C04 RTN ; 006.0 Bytes, CHKSUM=6104
Go back to the software library