### Tower of Hanoi

Posted:

**Sun Mar 11, 2018 5:08 pm**A short program that utilizes pseudo recursion techniques to solve the ancient game of "Tower of Hanoi". I wrote the original of this for a pdp11 in C more than 33 years ago. This COCO version (can be ported to other BASICs with ease) simulates recursion in and environment that is not capable of recursion.

According to Wikipedia the Tower of Hanoi:

Two challenges for you.

1) This program, as simple as it is, is infallible. It can be proven mathematically (and I'm not going to do that here) that the shortest solution to the Tower of Hanoi" is 2^n - 1 moves, where n is the number of disks to be moved. This program always does it in 2^n-1. Here is your challenge. Use a stack of 4 or more coins or disks, record your moves, then compare to your COCO running this program.

2) See if you can figure out how it works. How complicated could it be? After all, it only boils down to about 14 lines of code.

Have fun!

According to Wikipedia the Tower of Hanoi:

Consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1) Only one disk can be moved at a time.

2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.

3) No disk may be placed on top of a smaller disk.

Two challenges for you.

1) This program, as simple as it is, is infallible. It can be proven mathematically (and I'm not going to do that here) that the shortest solution to the Tower of Hanoi" is 2^n - 1 moves, where n is the number of disks to be moved. This program always does it in 2^n-1. Here is your challenge. Use a stack of 4 or more coins or disks, record your moves, then compare to your COCO running this program.

2) See if you can figure out how it works. How complicated could it be? After all, it only boils down to about 14 lines of code.

Have fun!

- Code: Select all
`10 CLS`

20 PRINT "********************"

30 PRINT "* *"

40 PRINT "* TOWER OF HANOI *"

50 PRINT "* *"

60 PRINT "********************"

70 PRINT

80 INPUT "ENTER THE NUMBER OF DISKS";J

90 S=1 : B=2 : D=3 : N=J+1

100 GOSUB 190

110 END

120 '

130 '

140 ' THE ROUTINE BELOW DOES ALL THE WORK AND THE RECUSION COMES FROM

150 ' THE FACT THAT IT CALLS ITSELF. SINCE THIS BASIC IS NOT CAPABLE

160 ' OF TRUE RECURSIVE CALLS, WE NEED TO DO A LITTLE HOUSEWORK

170 ' BEFORE WE GO INTO AND AFTER WE RETURN FROM EACH CALL.

180 '

190 N=N-1

200 IF N=1 THEN GOSUB 300 : GOTO 240

210 T=B : B=D : D=T : GOSUB 190 : T=D : D=B : B=T : N=N+1

220 GOSUB 300

230 T=S : S=B : B=T : GOSUB 190 : T=B : B=S : S=T : N=N+1

240 RETURN ' RETURN TO THE POINT OF THE LAST CALL

250 '

260 '

270 ' THE ROUTINE BELOW HANDLES THE PRINTING OF THE MOVES AND

280 ' PROMPTING THE PLAYER FOR THE NEXT MOVE

290 '

300 PRINT "MOVE TOP DISK ON ";S;" TO ";D;

310 INPUT "ENTER FOR NEXT MOVE"; Y

320 RETURN