Tower of Hanoi

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

Tower of Hanoi

Postby BillO » 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:

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
User avatar
BillO
 
Posts: 12
Joined: Wed Mar 07, 2018 9:19 am
Location: The deep woods of Central Ontario

Return to CoCo BASIC

Who is online

Users browsing this forum: No registered users and 0 guests

cron