## Tower of Hanoi

Color BASIC, Extended Color BASIC, CoCo 3 BASIC, and Disk Extended Color BASIC call all be discussed here.

### Tower of Hanoi

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:

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 CLS20 PRINT "********************"30 PRINT "*                   *"40 PRINT "*  TOWER OF HANOI  *"50 PRINT "*                   *"60 PRINT "********************"70 PRINT80 INPUT "ENTER THE NUMBER OF DISKS";J90 S=1 : B=2 : D=3 : N=J+1100 GOSUB 190110 END120 '130 '140 ' THE ROUTINE BELOW DOES ALL THE WORK AND THE RECUSION COMES FROM150 ' THE FACT THAT IT CALLS ITSELF.  SINCE THIS BASIC IS NOT CAPABLE160 ' 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-1200 IF N=1 THEN GOSUB 300 : GOTO 240210 T=B : B=D : D=T : GOSUB 190 : T=D : D=B : B=T : N=N+1220 GOSUB 300230 T=S : S=B : B=T : GOSUB 190 : T=B : B=S : S=T : N=N+1240 RETURN     ' RETURN TO THE POINT OF THE LAST CALL250 '260 '270 ' THE ROUTINE BELOW HANDLES THE PRINTING OF THE MOVES AND280 ' PROMPTING THE PLAYER FOR THE NEXT MOVE290 '300 PRINT "MOVE TOP DISK ON ";S;" TO ";D;310 INPUT "ENTER FOR NEXT MOVE"; Y320 RETURN` BillO

Posts: 16
Joined: Wed Mar 07, 2018 9:19 am
Location: The deep woods of Central Ontario 