Tutorial 025 Towers of Hanoi

Tutorial 025 TOWERS OF HANOI - recursion to the rescue.....

The Towers of Hanoi is an intriguing puzzle about which you can find lots more on the net using Google. Here are several programs written to help you understand its solution.

Richard Russell's clever demonstration program HANOI, written in 1982 for the BBC micro, is all over in a flash using BB4W on a modern PC. In the following modification I have added PROCcontrol and the other unnumbered lines so that its possible to see what's going on. Start with a small number of discs if you are unfamiliar with the problem, which is to move all the discs of a tapered tower from one postion to another in single disc moves, which at no time place a larger disc on top of a smaller one.

Its worth rehearsing Towers of Hanoi away from the computer on the kitchen table with suitable disclike objects (of increasing base radius) on say three table mats to act as your "holders". (Tins, bottles and pill-boxes will do very well). The three mats can be in an equilateral triangle as the empty starting pegs' positions are essentially equivalent. Work up from two discs; five discs take a very long time to solve. Allow several hours is the advice given in "Computer science for A Level" by Ray Bradley, which made me feel a lot better! The mind boggles....

You will see that the procedure employed below is recursive (it calls itself) and by adding a counter I've made it easier to see that a number of such calls occur before anything happens.

   10 REM. "THE TOWERS OF HANOI"
   20 REM. R.T.RUSSELL, 08-08-1982: BBC BASIC
      :
      REM: Unnumbered lines added by Richard Weston 15-05-2003
      REM: (and line 150 modified) to slow down the display on a modern pc
      REM: PROCcontrol added to give control options
   30 :
      i=0
      delay$=""
   40 DIM DISC$(13),SIZE(3)
   50 FOR DISC=1 TO 13
   60   DISC$(DISC)=STRING$(DISC," ")+STR$DISC+STRING$(DISC," ")
   70   IF DISC>=10 DISC$(DISC)=MID$(DISC$(DISC),2)
   80   DISC$(DISC)=CHR$17+CHR$(128+DISC-(DISC>7))+DISC$(DISC)+CHR$17+CHR$128
   90 NEXT DISC
100 :
110 MODE 3
120 INPUT "Number of discs (1-13): "F
130 IF F>13 RUN
140 FOR N=F TO 1 STEP -1:PROCPUT(N,1):NEXT
150 PRINT TAB(0,1)"Press SPACE to start, halt and restart":A=GET
      PRINTTAB(0,3)"Press q to finish quickly"
160 OFF
170 PROCHANOI(F,1,2,3)
180 PRINTTAB(0,22);
      PRINT"Press SPACE to go again"
      G=GET
      RUN
190 END
200 ;
210 DEF PROCHANOI(A,B,C,D)
      IF A=0 ENDPROC
      PROCcontrol
220 PROCHANOI(A-1,B,D,C)
230 PROCTAKE(A,B):PROCPUT(A,C)
240 PROCHANOI(A-1,D,C,B)
250 ENDPROC
260 ;
270 DEF PROCPUT(DISC,PILE)
280 PRINTTAB(13+26*(PILE-1)-DISC,20-SIZE(PILE))DISC$(DISC);
290 SIZE(PILE)=SIZE(PILE)+1
300 ENDPROC
310 ;
320 DEF PROCTAKE(DISC,PILE)
330 SIZE(PILE)=SIZE(PILE)-1
340 PRINTTAB(13+26*(PILE-1)-DISC,20-SIZE(PILE))STRING$(2*DISC+1," ");
350 ENDPROC
      :
      DEF PROCcontrol
      i+=1
      PRINTTAB(1,23);i
      IF delay$<>"q" THEN
        SOUND1,-8,i,1
        delay$=INKEY$(80)
        IF delay$=" " THEN
          G=GET
        ENDIF
      ENDIF
      ENDPROC

A simpler version, which just shows the moves, comes from SG Brewer's (ageist!) "Program's in BBC Basic for Young Mathematicians" :

      REM: Hanoi
      MODE8
      VDU14:REM: paged mode on - use shift key to scroll down
      INPUT"Starting Pole; 1,2 or 3 : "A
      INPUT"Finishing Pole; 1,2 or 3 : "B
      REPEAT
        i=0
        INPUT"Number of discs : "N
        PROCswitch(N,A,B)
      UNTIL FALSE
      END
      :
      DEF PROCswitch(N,A,B)
      C=6-A-B
      IF N=1 THEN
        PRINT A;".....";B
      ELSE
        PROCswitch(N-1,A,C)
        PROCswitch(1,A,B)
        PROCswitch(N-1,C,B)
      ENDIF
      ENDPROC

Here is the output for three discs:

Starting Pole; 1,2 or 3 : 1
Finishing Pole; 1,2 or 3 : 2
Number of discs : 3
         1.....2
         1.....3
         2.....3
         1.....2
         3.....1
         3.....2
         1.....2
You see that it takes seven moves to reposition the three discs.

If necessary you can take such a printout to the kitchen table to help you!

The following little program shows you how many moves it takes to solve the problem as the number of discs increases:

      REM:Tower of Hanoi Moves
      REM: Richard Weston afterJan Gulberg ("From the Birth of Numbers")
      MODE8
      PRINT'" Tower of Hanoi";
      PRINT" - number of moves required for n discs"
      PRINT'TAB(9)"n"TAB(17)"moves"'
      FOR n=1 TO 20
        moves=(2^n)-1
        PRINTn,moves
      NEXT n

Here is the output copied from the display using Ctr-TAB :

Tower of Hanoi - number of moves required for n discs

         n       moves

         1         1
         2         3
         3         7
         4        15
         5        31
         6        63
         7       127
         8       255
         9       511
        10      1023
        11      2047
        12      4095
        13      8191
        14     16383
        15     32767
        16     65535
        17    131071
        18    262143
        19    524287
        20   1048575

You can check this out using Richard Russell's program, up to 13 discs. The later ones will keep you busy at the kitchen table.

Recursion!

As an example of a very simple recursive program, to show you how such programs act, here is one given by Jim McGregor and Alan Watt in their excellent "Advanced Programming Techniques for the BBC Micro".

      REM: Intro to recursion
      REM: R Weston after McGregor & Watt
      MODE8
      INPUT'"Input a small integer : " n
      PROCprintupto(n)
      END
      :
      DEF PROCprintupto(n)
      IF n=0 THEN ENDPROC
      PROCprintupto(n-1)
      PRINT n
      ENDPROC

With an output:

Input a small integer : 6
         1
         2
         3
         4
         5
         6

By adding two extra lines:

      REM: Intro to recursion
      REM: R Weston after McGregor & Watt
      MODE8
      i=0
      INPUT"Input a smallish integer : " n
      PROCprintupto(n)
      END
      :
      DEF PROCprintupto(n)
      i=i+1
      PRINT"Yes ";i
      IF n=0 THEN ENDPROC
      PROCprintupto(n-1)
      PRINT n
      ENDPROC

we get the output :

Input a smallish integer : 5
Yes 1
Yes 2
Yes 3
Yes 4
Yes 5
Yes 6
         1
         2
         3
         4
         5
>
This shows how six calls are necessary to PROCprintupto before the condition n=0 is met, then the process unwinds printing the required number sequence. A cunning process of which more later....

Next Tutorial

Richard Weston's Homepage