'===========================================================================
' Subject: TOWER OF HANOI (4 SOLUTIONS)      Date: 06-28-00 (18:14)       
' Author:  D. J. Tuttle                      Code: QB, QBasic, PDS        
' Origin:  Dtuttle25@aol.com               Packet: ALGOR.ABC
'===========================================================================
'TOWER25.BAS for QBasic by D. J. Tuttle

'Tower of Hanoi -- four solutions

'This program demonstrates four solutions to the Tower of Hanoi puzzle.
'
'methods of solution:
'                     1. mechanical solution
'                     2. binary number sequence
'                     3. binary Gray code
'                     4. recursion

'The Tower of Hanoi is a famous puzzle invented over a hundred years ago
'by the French mathematician Edouard Lucas.  A favorite in the field of
'recreational mathematics the puzzle is also well-known among programmers
'as a classic example of recursion.
'
'The puzzle consists of a set of disks and three upright rods.  The disks,
'which are of increasing size, begin stacked in the shape of a pyramid on
'the first rod.  The objective is to transfer the pyramid of disks to the
'third rod in the fewest possible moves while following these rules:
'         Only one disk may be moved at a time.
'         No disk may be placed on top of a smaller disk.
'         The second rod may be used to temporarily hold disks.
'
'The original version of the puzzle, sold as a toy in 1883, had eight disks.
'
'The Tower of Hanoi puzzle is based on the "Tower of Brahma" -- a mythical
'tower of sixty-four gold disks at a temple in Benares, India.  According
'to legend the temple priests are at work, day and night, methodically
'tranferring the disks in the manner described in the puzzle.  When the
'task is completed the world will vanish in a clap of thunder.
'(from reference 1, p. 304)

'The methods of solution demonstrated in this program solve the puzzle in
'the minimum number of moves.  All four methods generate the identical
'sequence of moves.
'
'To solve the puzzle for one disk requires just one move.  As each additional
'disk is added to the puzzle the number of moves required for each previous
'disk is doubled.
'
'For example:
'
'The disks are numbered starting with the smallest (disk 1 = smallest disk).
'
'solving a tower of one disk:    move disk 1 from rod 1 to rod 3
'  number of moves per disk
'    disk 1 is moved 1 time
'
'
'
'solving a tower of two disks:   move disk 1 from rod 1 to rod 2
'                                move disk 2 from rod 1 to rod 3
'                                move disk 1 from rod 2 to rod 3
'  number of moves per disk
'    disk 2 is moved 1 time
'    disk 1 is moved 2 times
'
'
'
'solving a tower of three disks: move disk 1 from rod 1 to rod 3
'                                move disk 2 from rod 1 to rod 2
'                                move disk 1 from rod 3 to rod 2
'                                move disk 3 from rod 1 to rod 3
'                                move disk 1 from rod 2 to rod 1
'                                move disk 2 from rod 2 to rod 3
'                                move disk 1 from rod 1 to rod 3
'  number of moves per disk
'    disk 3 is moved 1 time
'    disk 2 is moved 2 times
'    disk 1 is moved 4 times
'
'
'
'and so on.
'
'Disk 1, the smallest disk, is always moved the greatest number of times
'while the largest disk is always moved just once.
'
'solving a tower of eight disks:
'  number of moves per disk
'    disk 8 is moved   1 time   (or 2 ^ 0)
'    disk 7 is moved   2 times  (or 2 ^ 1)
'    disk 6 is moved   4 times  (or 2 ^ 2)
'    disk 5 is moved   8 times  (or 2 ^ 3)
'    disk 4 is moved  16 times  (or 2 ^ 4)
'    disk 3 is moved  32 times  (or 2 ^ 5)
'    disk 2 is moved  64 times  (or 2 ^ 6)
'    disk 1 is moved 128 times  (or 2 ^ 7)
'                    ---
'                    255 total moves
'
'The number of moves per disk (1, 2, 4, 8, ...) is a geometrical progression
'based on a factor of 2.  So it should not be surprising that some methods
'used to solve the puzzle are based directly on binary (base 2) numbers.
'
'The total number of moves is the sum of the terms of the geometric series
'representing how many times each disk is moved.
'
'The geometric series is 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + ... + 2 ^ (n - 1).
'            disk size: largest           to           smallest
'
'A quick way to sum the terms of the geometric series listed above is with
'the formula (2 ^ n) - 1 where n is the number of disks.
'
'Table of the minimum number of moves to solve the Tower of Hanoi puzzle:
'
'                disks      minimum number of moves
'                 (n)             (2 ^ n) - 1
'                -----    --------------------------
'                   1                              1
'                   2                              3
'                   3                              7
'                   4                             15
'                   5                             31
'                   6                             63
'                   7                            127
'                   8                            255
'                   9                            511
'                 ...                            ...
'                  15                         32,767
'                 ...                            ...
'                  64     18,446,744,073,709,551,615

'references:
' 1) "The Tower of Hanoi" in MATHEMATICAL RECREATIONS AND ESSAYS by
'    W.W. Rouse Ball & H.S.M. Coxeter, (The Macmillan Company, 1967),
'    pp. 303 - 305

' 2) Chapter 6, "The Icosian Game and the Tower of Hanoi" in THE SCIENTIFIC
'    AMERICAN BOOK OF MATHEMATICAL PUZZLES & DIVERSIONS by Martin Gardner,
'    (Simon and Schuster, 1959), pp. 55 - 62
'
' 3) "The curious properties of the Gray code and how it can be used to
'    solve puzzles" in the Mathematical Games column by Martin Gardner,
'    SCIENTIFIC AMERICAN Magazine, Aug. 1972, pp. 106 - 109

'suggestions for programmers:
'
' 1. Several options are available by setting the value of a Constant.
'    These options include:
'
'       - method of solution
'       - number of disks in the puzzle
'       - color of disks
'       - label disks by number?
'       - color of disk number labels
'       - show intermediate steps in disk transfer?
'       - rods in shape of triangle for solution 4?
'       - viewing angle
'
' 2. The program, as written, supports up to fifteen disks (32,767 moves
'    which is the limit of integer numbers).  A few changes would allow
'    more disks.
'
'    Keep in mind, however, that the relationship between the number of
'    disks and the minimum number of moves required to solve the puzzle is
'    geometric.  The number of moves required quickly becomes astronomical.
'
'    n.b. Solving the sixty-four disk version of the Tower of Hanoi puzzle
'    would require more than 18 quintillion moves.  This number is so large
'    that a computer capable of making a thousand moves per second would
'    take more than half a billon years to complete the puzzle.  A futuristic
'    supercomputer capable of making a trillion moves per second could solve
'    the puzzle in a more reasonable period of time -- about seven months.
'    It might not, however, be advisable to let the computer program run to
'    completion (see the short story "The Nine Billion Names of God" by
'    Arthur C. Clarke).

'Send comments and questions to this email address: dtuttle25@aol.com

DECLARE SUB Initialization ()
DECLARE SUB Process ()
DECLARE SUB Summary ()
DECLARE FUNCTION ZFUNCBin$ (Number AS INTEGER)
DECLARE SUB ZSUBDelay (value AS SINGLE)
DECLARE SUB ZSUBDrawDigit (Col AS SINGLE, Row AS SINGLE, Digit AS INTEGER)
DECLARE SUB ZSUBDrawDisk (Col AS INTEGER, Row AS INTEGER, Height AS INTEGER, Radius AS INTEGER, Hue AS INTEGER, ToroidFlag AS INTEGER)
DECLARE SUB ZSUBDrawNumber (Col AS INTEGER, Row AS INTEGER, Number AS INTEGER)
DECLARE SUB ZSUBDrawScreen ()
DECLARE SUB ZSUBMoveDisk (RodFrom AS INTEGER, RodTo AS INTEGER, Dir AS INTEGER)
DECLARE SUB ZSUBSolution1 ()
DECLARE SUB ZSUBSolution2 ()
DECLARE SUB ZSUBSolution3 ()
DECLARE SUB ZSUBSolution4 (RodFrom AS INTEGER, RodTo AS INTEGER, RodTemp AS INTEGER, DiskCount AS INTEGER)

CONST FALSE = 0, TRUE = NOT FALSE
CONST PI = 3.141593         '= 180 * PI / 180 = pi radians = half circle

'----------------------------------------------------------------------------
'Options:
CONST METHOD = 1            'method of solution (range 1 to 4)
CONST NUMBEROFDISKS = 4     'number of disks (range 1 to 15)
CONST DISKHUE = 4           'disk color (range 1 to 14)
CONST SHOWNUMBER = TRUE     'show disk number labels (TRUE/FALSE)
CONST NUMBERHUE = 7         'color of disk number labels (range 1 to 15)
CONST SHOWTRANSFER = TRUE   'show intermediate steps in disk transfer (TRUE/FALSE)
CONST TRIANGLE4 = FALSE     'rods in shape of triangle for solution 4 (TRUE/FALSE)
CONST ASPECT = .4           'simulated 3D viewing angle (decimal value, range 0 to 1)
'----------------------------------------------------------------------------

CONST MAXCOL = 4 + (NUMBEROFDISKS + 1) * 2 * 3 + 4
CONST TRAPEZOIDX = 4
CONST TRIANGLESIZE = 2
CONST VIEWPORTBORDER = 8, VIEWPORTBG = 0
CONST BORDER = 7, BG = 8
CONST PAINTHUE = 15
CONST RODHUE = 8
CONST HIGHLIGHTHUE = 15
CONST DELAY = .25
CONST H1$ = "Number of Disks = ##"
CONST H2$ = "#####"
CONST H3$ = "##"

DIM SHARED TriangleStep AS INTEGER
DIM SHARED MaxRow AS INTEGER
DIM SHARED TrapezoidY AS SINGLE
DIM SHARED MoveCount AS INTEGER
DIM SHARED TransitDisk AS INTEGER, TransitPosition AS INTEGER
DIM SHARED GraphicAdjust AS SINGLE

DIM SHARED EscKey AS STRING * 1

DIM SHARED Disk(1 TO NUMBEROFDISKS) AS INTEGER
DIM SHARED RodRow(1 TO 3) AS INTEGER, RodCol(1 TO 3) AS INTEGER
DIM SHARED TowerSize(1 TO 3) AS INTEGER
DIM SHARED TopSize(1 TO 3) AS INTEGER
DIM SHARED TransitRow(1 TO 9) AS INTEGER, TransitCol(1 TO 9) AS INTEGER
DIM SHARED DirTable(1 TO 3, 1 TO 3) AS INTEGER

CALL Initialization
CALL Process
CALL Summary

SYSTEM

'END OF MAIN PROGRAM

SUB Initialization STATIC

   DIM I AS INTEGER
   DIM ColSixth AS INTEGER
   DIM Factor AS SINGLE

   'set arrangement of rods
   IF (METHOD = 4) AND (NOT TRIANGLE4) THEN TriangleStep = 0 ELSE TriangleStep = TRIANGLESIZE
  
   MaxRow = 2 + NUMBEROFDISKS + 1 + 2 + 1 + TriangleStep * 3
  
   TrapezoidY = 4.5 + TriangleStep * 3
  
   'fine tune position of disk number labels
   SELECT CASE NUMBEROFDISKS
      CASE 1
         IF (METHOD = 4) AND (TRIANGLE4 = FALSE) THEN Factor = 1.4 ELSE Factor = 2.4
      CASE 2
         IF (METHOD = 4) AND (TRIANGLE4 = FALSE) THEN Factor = 1.3 ELSE Factor = 2
      CASE 3
         IF (METHOD = 4) AND (TRIANGLE4 = FALSE) THEN Factor = 1.2 ELSE Factor = 1.75
      CASE 4
         IF (METHOD = 4) AND (TRIANGLE4 = FALSE) THEN Factor = 1.08 ELSE Factor = 1.55
      CASE 5
         IF (METHOD = 4) AND (TRIANGLE4 = FALSE) THEN Factor = 1.02 ELSE Factor = 1.45
      CASE 6
         IF (METHOD = 4) AND (TRIANGLE4 = FALSE) THEN Factor = .96 ELSE Factor = 1.3
      CASE 7
         IF (METHOD = 4) AND (TRIANGLE4 = FALSE) THEN Factor = .9 ELSE Factor = 1.25
      CASE 8
         IF (METHOD = 4) AND (TRIANGLE4 = FALSE) THEN Factor = .85 ELSE Factor = 1.15
      CASE 9
         IF (METHOD = 4) AND (TRIANGLE4 = FALSE) THEN Factor = .83 ELSE Factor = 1.14
      CASE 10
         IF (METHOD = 4) AND (TRIANGLE4 = FALSE) THEN Factor = .8 ELSE Factor = 1.08
      CASE 11
         IF (METHOD = 4) AND (TRIANGLE4 = FALSE) THEN Factor = .78 ELSE Factor = 1.02
      CASE 12
         IF (METHOD = 4) AND (TRIANGLE4 = FALSE) THEN Factor = .77 ELSE Factor = 1
      CASE 13
         IF (METHOD = 4) AND (TRIANGLE4 = FALSE) THEN Factor = .76 ELSE Factor = .99
      CASE 14
         IF (METHOD = 4) AND (TRIANGLE4 = FALSE) THEN Factor = .75 ELSE Factor = .98
      CASE 15
         IF (METHOD = 4) AND (TRIANGLE4 = FALSE) THEN Factor = .74 ELSE Factor = .95
   END SELECT
   GraphicAdjust = ASPECT * ((348 - 22) / (638 - 194)) * Factor
  
   MoveCount = 0
  
   EscKey$ = CHR$(27)
  
   'disk sizes: Disk(1) = smallest through Disk(NUMBEROFDISKS) = largest
   'all disks start on rod 1
   FOR I = 1 TO NUMBEROFDISKS
      Disk(I) = 1
   NEXT I
  
   RodCol(1) = 4 + NUMBEROFDISKS + 1
   RodCol(2) = MAXCOL \ 2
   RodCol(3) = MAXCOL - RodCol(1)
  
   ColSixth = (RodCol(3) - RodCol(1)) \ 6
  
   TransitCol(1) = RodCol(1)
   TransitCol(2) = RodCol(1) + ColSixth
   TransitCol(3) = RodCol(2) - ColSixth
   TransitCol(4) = RodCol(2)
   TransitCol(5) = RodCol(2) + ColSixth
   TransitCol(6) = RodCol(3) - ColSixth
   TransitCol(7) = RodCol(3)
   TransitCol(8) = RodCol(2) + ColSixth
   TransitCol(9) = RodCol(2) - ColSixth
  
   TransitRow(1) = MaxRow - 2 - (NUMBEROFDISKS + 1)
   TransitRow(2) = TransitRow(1) - TriangleStep
   TransitRow(3) = TransitRow(1) - TriangleStep * 2
   TransitRow(4) = TransitRow(1) - TriangleStep * 3
   TransitRow(5) = TransitRow(1) - TriangleStep * 2
   TransitRow(6) = TransitRow(1) - TriangleStep
   TransitRow(7) = TransitRow(1)
   TransitRow(8) = TransitRow(1)
   TransitRow(9) = TransitRow(1)
  
   'direction table for moving disks between rods
   'used by solution 1 (moves not involving smallest disk) and solution 4
   DirTable(1, 2) = 1: DirTable(1, 3) = -1
   DirTable(2, 1) = -1: DirTable(2, 3) = 1
   DirTable(3, 1) = 1: DirTable(3, 2) = -1
  
   SCREEN 9, , 1, 0
  
   COLOR 7
   PRINT "TOWER25.BAS"
   LOCATE 1, 43
   PRINT "Tower of Hanoi puzzle"
   
   SELECT CASE METHOD
      CASE 1
         COLOR 8
        
         LOCATE 2, 1
         PRINT "ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿"
         PRINT "³                      ³"
         PRINT "³ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄij"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ"
        
         LOCATE 12, 1
         PRINT "ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿"
         PRINT "³                      ³"
         PRINT "ÃÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ"
  
         LOCATE 18, 1
         PRINT "ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿"
         PRINT "³                      ³"
         PRINT "ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ"
    
         COLOR 7
         LOCATE 3, 3
         PRINT "mechanical solution"
         LOCATE 5, 2
         PRINT "Alternate between"
         LOCATE 6, 2
         PRINT "moving the smallest"
         LOCATE 7, 2
         PRINT "disk and making the"
         LOCATE 8, 2
         PRINT "only valid move not"
         LOCATE 9, 2
         PRINT "involving the smallest"
         LOCATE 10, 2
         PRINT "disk."
    
         LOCATE 13, 3
         PRINT USING H1$; NUMBEROFDISKS
         LOCATE 15, 3
         PRINT "smallest disk moves"
         LOCATE 16, 3
         IF (NUMBEROFDISKS AND 1) = 1 THEN PRINT "ccw" ELSE PRINT "cw"
         LOCATE 16, 7
         PRINT "around triangle"

         LOCATE 19, 3
         PRINT "Move Count ="
         LOCATE 19, 18
         PRINT USING H2$; MoveCount
     
      CASE 2
         COLOR 8
       
         LOCATE 2, 1
         PRINT "ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿"
         PRINT "³                      ³"
         PRINT "³ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄij"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ"
        
         LOCATE 12, 1
         PRINT "ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿"
         PRINT "³                      ³"
         PRINT "ÃÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ"
        
         LOCATE 19, 1
         PRINT "ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ"
        
         COLOR 7
         LOCATE 3, 2
         PRINT "binary number sequence"
         LOCATE 5, 2
         PRINT "The binary"
         LOCATE 6, 2
         PRINT "representation of the"
         LOCATE 7, 2
         PRINT "move count tells which"
         LOCATE 8, 2
         PRINT "disk to move."
         LOCATE 9, 2
         PRINT "Disk Number = position"
         LOCATE 10, 2
         PRINT "of first set bit + 1"
        
         LOCATE 13, 3
         PRINT USING H1$; NUMBEROFDISKS
        
         LOCATE 15, 3
         PRINT "all disks move"
         LOCATE 15, 18
         IF (NUMBEROFDISKS AND 1) = 1 THEN PRINT "ccw" ELSE PRINT "cw"
         LOCATE 16, 3
         PRINT "around triangle to"
         LOCATE 17, 3
         PRINT "the next valid rod"

         LOCATE 20, 2
         PRINT "Move Count ="
         LOCATE 20, 19
         PRINT USING H2$; MoveCount
        
         LOCATE 21, 2
         PRINT "bin ="
        
         LOCATE 22, 2
         PRINT "bit    (+ 1) = Disk"
        
      CASE 3
         COLOR 8
       
         LOCATE 2, 1
         PRINT "ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿"
         PRINT "³                      ³"
         PRINT "³ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄij"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ"
        
         LOCATE 12, 1
         PRINT "ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿"
         PRINT "³                      ³"
         PRINT "ÃÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ"
        
         LOCATE 19, 1
         PRINT "ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ";
        
         COLOR 7
         LOCATE 3, 5
         PRINT "binary Gray code"
         LOCATE 5, 2
         PRINT "The binary Gray code"
         LOCATE 6, 2
         PRINT "representation of the"
         LOCATE 7, 2
         PRINT "move count tells which"
         LOCATE 8, 2
         PRINT "disk to move."
         LOCATE 9, 2
         PRINT "Disk Number = position"
         LOCATE 10, 2
         PRINT "of changing bit + 1"
        
         LOCATE 13, 3
         PRINT USING H1$; NUMBEROFDISKS
         LOCATE 15, 3
         PRINT "all disks move"
         LOCATE 15, 18
         IF (NUMBEROFDISKS AND 1) = 1 THEN PRINT "ccw" ELSE PRINT "cw"
         LOCATE 16, 3
         PRINT "around triangle to"
         LOCATE 17, 3
         PRINT "the next valid rod"
        
         LOCATE 20, 2
         PRINT "Move Count ="
         LOCATE 20, 19
         PRINT USING H2$; MoveCount
        
         LOCATE 21, 2
         PRINT "Gray ="
 
         LOCATE 22, 2
         PRINT "Last ="

         LOCATE 23, 2
         PRINT "bit    (+ 1) = Disk"
        
      CASE 4
         COLOR 8
       
         LOCATE 2, 1
         PRINT "ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿"
         PRINT "³                      ³"
         PRINT "³ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄij"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³    ÄÄÄÄÄÄÄÄÄÄÄÄÄÄ    ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "³                      ³"
         PRINT "ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ"
        
         LOCATE 19, 1
         PRINT "ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿"
         PRINT "³                      ³"
         PRINT "ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ"
        
         LOCATE 22, 1
         PRINT "ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿"
         PRINT "³                      ³"
         PRINT "ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ";
        
         COLOR 7
         LOCATE 3, 9
         PRINT "recursion"
         LOCATE 5, 2
         PRINT "Move all except the"
         LOCATE 6, 2
         PRINT "base of the tower to"
         LOCATE 7, 2
         PRINT "another rod.  Next"
         LOCATE 8, 2
         PRINT "move the base.  Then"
         LOCATE 9, 2
         PRINT "put the moved disks"
         LOCATE 10, 2
         PRINT "back on to the base."
         LOCATE 12, 2
         PRINT "This simple idea is"
         LOCATE 13, 2
         PRINT "extended from the full"
         LOCATE 14, 2
         PRINT "tower to towers of"
         LOCATE 15, 2
         PRINT "successively fewer"
         LOCATE 16, 2
         PRINT "disks until only one"
         LOCATE 17, 2
         PRINT "disk is left to move."
        
         LOCATE 20, 3
         PRINT USING H1$; NUMBEROFDISKS
         
         LOCATE 23, 3
         PRINT "Move Count ="
         LOCATE 23, 18
         PRINT USING H2$; MoveCount
        
   END SELECT
  
   LOCATE 25, 4
   PRINT "press <Esc> to exit";
  
   'draw initial screen including graphic window
   CALL ZSUBDrawScreen

   'slight delay so fast computers do not overrun start of program
   CALL ZSUBDelay(.5)

END SUB

SUB Process STATIC
 
   SELECT CASE METHOD
      CASE 1
         'mechanical solution
         CALL ZSUBSolution1
      CASE 2
         'binary number sequence solution
         CALL ZSUBSolution2
      CASE 3
         'binary Gray code solution
         CALL ZSUBSolution3
      CASE 4
         'recursive solution
         'from rod 1, to rod 3, using rod 2 temporarily, number of disks
         CALL ZSUBSolution4(1, 3, 2, NUMBEROFDISKS)
   END SELECT
  
END SUB

SUB Summary STATIC

   VIEW

END SUB

SUB Text1

   'mechanical solution to the Tower of Hanoi puzzle
  
   '(from reference 2, p. 59)

   'Arrange the three rods to form a triangle.
   '
   'Move the smallest disk on every other turn -- always in the same
   'direction.  On the remaining turns make the only valid move that does
   'not involve the smallest disk.
   '
   'The following rule will make sure that the tower of disks end up on the
   'third rod: If the number of disks in the puzzle is an odd number then
   'always move the smallest disk counter-clockwise around the triangle; if
   'the number of disks in the puzzle is an even number then always move the
   'smallest disk clockwise around the triangle.

   '(With this solution the even numbered disks move around the triangle in
   'one direction while the odd numbered disks move around the triangle in
   'the opposite direction.)

END SUB

SUB Text2

   'binary number sequence solution to the Tower of Hanoi puzzle

   '(from reference 2, p. 61)

   'Arrange the three rods to form a triangle.
   '
   'Which disk to move, on each turn, is determined by looking at the binary
   'representation of the turn count.  The disk number is equal to one more
   'than the bit position of the first set bit.  All moves are made in the
   'same direction (to the next rod which results in a valid move).
   '
   'The following rule will make sure that the tower of disks end up on the
   'third rod: If the number of disks in the puzzle is an odd number then
   'make all moves counter-clockwise around the triangle; if the number of
   'disks in the puzzle is an even number then make all moves clockwise
   'around the triangle.
  
END SUB

SUB Text3

   'binary Gray code solution to the Tower of Hanoi puzzle

   '(from reference 3)
  
   'Arrange the three rods to form a triangle.
   '
   'Which disk to move, on each turn, is determined by looking at the Gray
   'code representation of the turn count.  The disk number is equal to one
   'more than the bit position which changed from the previous turn count.
   'All moves are made in the same direction (to the next rod which results
   'in a valid move).
   '
   'The following rule will make sure that the tower of disks end up on the
   'third rod: If the number of disks in the puzzle is an odd number then
   'make all moves counter-clockwise around the triangle; if the number of
   'disks in the puzzle is an even number then make all moves clockwise
   'around the triangle.
  
   'Gray codes are a way of representing the counting numbers (0, 1, 2, ...)
   'where each successive number differs from the previous number at a single
   'position and by a difference, at that position, of one unit.
   '
   'For example:
   '                 counting    standard       binary
   '                  number      binary       Gray code
   '                 --------    --------      ---------
   '                    0            0             0
   '                    1            1             1
   '                    2           10            11
   '                    3           11            10
   '                    4          100           110
   '                    5          101           111
   '                    6          110           101
   '                    7          111           100
   '                    8         1000          1100
   '
   'converting to binary Gray code:
   '
   'To convert a standard binary number to its Gray code equivalent process
   'each bit, one at a time, from right to left.  Leave the current bit
   'unchanged if the bit to the immediate left is 0; toggle (invert) the
   'current bit if the bit to the immediate left is 1.
   '
   'Or use the formula:
   'Gray code (n) = n ^ (n >> 1) = N XOR (N \ 2)
   '
   'Gray codes are named after Frank Gray -- an engineer who worked for Bell
   'Labs in the 1950s.

END SUB

SUB Text4

   'recursive solution to the Tower of Hanoi puzzle
 
   'from any good programming text

   'This is the method of solution preferred by programmers.
   '
   'Recursion is a programming technique of breaking a problem down into
   'a series of similar problems of diminishing complexity.  The process of
   'redefining the problem into smaller pieces continues until an end
   'condition is reached.  To implement recursion a routine usually calls
   'itself.
   
   'Here is part of the entry for recursion in the Jargon File (aka The
   'Hacker's Dictionary):
   '
   '     recursion n. See recursion.
   '
   'The Jargon File ("a comprehensive compendium of hacker slang illuminating
   'many aspects of hackish tradition, folklore, and humor") is both a book
   'and an electronic text file.  The text file, which is free, is widely
   'available on the Internet.

   'The question "What is recursion?" was answered this way in one of the
   'comp lang newsgroups:
   '
   '        The following (allegorical) illustration might make it
   '        a little easier to understand:
   '
   '        "It was a dark and stormy night. The wind howled in the
   '        rigging, the rain beat down and the ship pitched and
   '        rolled on the ocean, a thousand miles from land. 'BOSUN!'
   '        cried the Captain; 'Pour yourself a tot of rum and tell
   '        us a story to lift our spirits'. The bosun sat down on a
   '        coil of rope, poured himself a generous measure, and
   '        began:  "It was a dark and stormy night. The wind howled
   '        in the rigging .................
   '
   '        and so on, until the rum runs out.
   '
   'Apparently the end condition in this example of recursion is when the
   'supply of rum is exhausted.
 
   'Using recursion to solve the Tower of Hanoi puzzle:
   '
   'The three rods do not need to be arranged in the shape of a triangle
   'with this method.
   '
   'At some point, during the solution of the puzzle, the following position
   'must be reached (the example uses four disks):
   '
   '                                     *
   '                                    ***
   '                *******            *****
   '                 rod 1             rod 2             rod 3
   '
   'That is, the largest disk is by itself on rod 1, all the smaller disks
   'are on rod 2 and rod 3 is empty.  This will allow the largest disk to
   'be moved to the destination rod (rod 3) on the next move.
   '
   'This suggests a pattern for the solution of the puzzle.  For a tower
   'of n disks move the top n - 1 disks (the smaller disks) to a temporary
   'storage rod, move the remaining (base) disk to the destination rod and
   'then put the tower of n - 1 disks back on to the base.
   '
   'In the example a tower of four disks has been redefined as a tower of
   'three disks on top of a base disk.  Transferring a tower of three disks
   'is slightly simpler than transferring a tower of four disks.
   '
   'This pattern will work for any size tower of disks and can be extended,
   'in succession, to solve towers containing fewer and fewer disks.
   '
   'Therefore solving a tower of four disks includes solving a tower of three
   'disks which includes solving a tower of two disks which includes,
   'finally, moving a single disk.
   '
   'This reducing a problem to a series of smaller and smaller related steps
   'is tailor-made for a recursive solution.  The routine to transfer a
   'tower of disks repeatedly calls itself with a diminishing number of disks
   'to transfer and with different rods to use for the transfers.  The end
   'condition -- the point where the routine stops calling itself -- is
   'when just a single disk, not a tower of disks, is to be moved.
   '
   'The main variables in a recursive routine cannot be static.  Otherwise
   'the (still pending) values of the previous instance of the routine will
   'be overwritten.
  
   '(The pattern for solving the puzzle mentioned above -- move the top n - 1
   'disks off the base, move the base and then move the n - 1 disks back on
   'to the base -- leads to two observations:
   '
   'The largest disk, of course, is moved near the halfway point -- between
   'the two transfers of the tower made up of NUMBEROFDISKS - 1 disks.
   '
   'Everytime a new disk is added to the puzzle the number of moves required
   'to solve the puzzle is one more than 2 times the number of moves required
   'to solve the previous puzzle.  For example, 7 moves are required to solve
   'a tower of three disks while 15 moves (7 * 2 + 1) are required for a
   'tower of four disks.  The tower of NUMBEROFDISKS - 1 disks in the new
   'puzzle (the same number of disks as the full tower in the previous
   'puzzle) is moved twice and the new (largest) disk is moved one time.)

END SUB

FUNCTION ZFUNCBin$ (Number AS INTEGER) STATIC

   'returns a 15-byte string with the binary representation of Number
  
   DIM TempNumber AS INTEGER
   DIM Bin AS STRING

   TempNumber = Number
   Bin$ = ""

   DO
      Bin$ = CHR$((TempNumber AND 1) + 48) + Bin$
      TempNumber = TempNumber \ 2
   LOOP UNTIL TempNumber = 0

   ZFUNCBin$ = LEFT$("              ", 15 - LEN(Bin$)) + Bin$

END FUNCTION

SUB ZSUBDelay (value AS SINGLE) STATIC

   CONST SPD = 86400   'seconds per day
 
   DIM DelayValue AS SINGLE
   DIM TimeCheck1 AS SINGLE, TimeCheck2 AS SINGLE
 
   DelayValue = value
 
   TimeCheck1 = TIMER
 
   WHILE DelayValue > 0
     
      DO
         TimeCheck2 = TIMER
      LOOP WHILE TimeCheck1 = TimeCheck2
     
      IF TimeCheck2 > TimeCheck1 THEN
         DelayValue = DelayValue - (TimeCheck2 - TimeCheck1)
      ELSE
         'midnight
         DelayValue = DelayValue - (SPD - TimeCheck1) - TimeCheck2
      END IF
     
      TimeCheck1 = TimeCheck2
     
   WEND

END SUB

SUB ZSUBDrawDigit (Col AS SINGLE, Row AS SINGLE, Digit AS INTEGER) STATIC

   SELECT CASE Digit
      CASE 0
         LINE (Col - .4, Row - .8)-(Col + .4, Row - .7666), NUMBERHUE, BF
         LINE (Col - .4, Row - .1333)-(Col + .4, Row - .1), NUMBERHUE, BF
         LINE (Col + .25, Row - .8)-(Col + .4, Row - .1), NUMBERHUE, BF
         LINE (Col - .4, Row - .8)-(Col - .25, Row - .1), NUMBERHUE, BF
      CASE 1
         LINE (Col - .1, Row - .8)-(Col + .1, Row - .1), NUMBERHUE, BF
      CASE 2
         LINE (Col - .4, Row - .8)-(Col + .4, Row - .7666), NUMBERHUE, BF
         LINE (Col - .4, Row - .4666)-(Col + .4, Row - .4333), NUMBERHUE, BF
         LINE (Col - .4, Row - .1333)-(Col + .4, Row - .1), NUMBERHUE, BF
         LINE (Col + .25, Row - .8)-(Col + .4, Row - .4333), NUMBERHUE, BF
         LINE (Col - .4, Row - .4666)-(Col - .25, Row - .1), NUMBERHUE, BF
      CASE 3
         LINE (Col - .4, Row - .8)-(Col + .4, Row - .7666), NUMBERHUE, BF
         LINE (Col - .4, Row - .4666)-(Col + .4, Row - .4333), NUMBERHUE, BF
         LINE (Col - .4, Row - .1333)-(Col + .4, Row - .1), NUMBERHUE, BF
         LINE (Col + .25, Row - .8)-(Col + .4, Row - .1), NUMBERHUE, BF
      CASE 4
         LINE (Col - .4, Row - .4666)-(Col + .4, Row - .4333), NUMBERHUE, BF
         LINE (Col + .25, Row - .8)-(Col + .4, Row - .1), NUMBERHUE, BF
         LINE (Col - .4, Row - .8)-(Col - .25, Row - .4333), NUMBERHUE, BF
      CASE 5
         LINE (Col - .4, Row - .8)-(Col + .4, Row - .7666), NUMBERHUE, BF
         LINE (Col - .4, Row - .4666)-(Col + .4, Row - .4333), NUMBERHUE, BF
         LINE (Col - .4, Row - .1333)-(Col + .4, Row - .1), NUMBERHUE, BF
         LINE (Col + .25, Row - .4666)-(Col + .4, Row - .1), NUMBERHUE, BF
         LINE (Col - .4, Row - .8)-(Col - .25, Row - .4333), NUMBERHUE, BF
      CASE 6
         LINE (Col - .4, Row - .8)-(Col + .4, Row - .7666), NUMBERHUE, BF
         LINE (Col - .4, Row - .4666)-(Col + .4, Row - .4333), NUMBERHUE, BF
         LINE (Col - .4, Row - .1333)-(Col + .4, Row - .1), NUMBERHUE, BF
         LINE (Col + .25, Row - .4666)-(Col + .4, Row - .1), NUMBERHUE, BF
         LINE (Col - .4, Row - .8)-(Col - .25, Row - .1), NUMBERHUE, BF
      CASE 7
         LINE (Col - .4, Row - .8)-(Col + .4, Row - .7666), NUMBERHUE, BF
         LINE (Col + .25, Row - .8)-(Col + .4, Row - .1), NUMBERHUE, BF
      CASE 8
         LINE (Col - .4, Row - .8)-(Col + .4, Row - .7666), NUMBERHUE, BF
         LINE (Col - .4, Row - .4666)-(Col + .4, Row - .4333), NUMBERHUE, BF
         LINE (Col - .4, Row - .1333)-(Col + .4, Row - .1), NUMBERHUE, BF
         LINE (Col + .25, Row - .8)-(Col + .4, Row - .1), NUMBERHUE, BF
         LINE (Col - .4, Row - .8)-(Col - .25, Row - .1), NUMBERHUE, BF
      CASE 9
         LINE (Col - .4, Row - .8)-(Col + .4, Row - .7666), NUMBERHUE, BF
         LINE (Col - .4, Row - .4666)-(Col + .4, Row - .4333), NUMBERHUE, BF
         LINE (Col + .25, Row - .8)-(Col + .4, Row - .1), NUMBERHUE, BF
         LINE (Col - .4, Row - .8)-(Col - .25, Row - .4333), NUMBERHUE, BF
   END SELECT
        
END SUB

SUB ZSUBDrawDisk (Col AS INTEGER, Row AS INTEGER, Height AS INTEGER, Radius AS INTEGER, Hue AS INTEGER, ToroidFlag AS INTEGER) STATIC

   'hidden surface removal using "painting" technique
 
   CIRCLE (Col, Row), Radius, PAINTHUE, PI, 0, ASPECT
   CIRCLE (Col, Row - Height), Radius, PAINTHUE, 0, PI, ASPECT
   LINE (Col - Radius, Row - Height)-(Col - Radius, Row), PAINTHUE
   LINE (Col + Radius, Row - Height)-(Col + Radius, Row), PAINTHUE
   PAINT (Col, Row - .5), PAINTHUE, PAINTHUE
 
   CIRCLE (Col, Row), Radius, Hue, PI, 0, ASPECT
   CIRCLE (Col, Row - Height), Radius, Hue, 0, PI, ASPECT
   LINE (Col - Radius, Row - Height)-(Col - Radius, Row), Hue
   LINE (Col + Radius, Row - Height)-(Col + Radius, Row), Hue
   PAINT (Col, Row - .5), 0, Hue
  
   CIRCLE (Col, Row - Height), Radius, Hue, PI, 0, ASPECT
  
   IF ToroidFlag THEN CIRCLE (Col, Row - Height), 1, Hue, , , ASPECT

END SUB

SUB ZSUBDrawNumber (Col AS INTEGER, Row AS INTEGER, Number AS INTEGER) STATIC

   DIM RowAdjust AS SINGLE, ColAdjust AS SINGLE
  
   RowAdjust = GraphicAdjust * (Number + 1) / 2
  
   IF Number < 10 THEN
      ColAdjust = 0
      CALL ZSUBDrawDigit(Col + ColAdjust, Row + RowAdjust, Number)
   ELSE
      ColAdjust = .5
      CALL ZSUBDrawDigit(Col - ColAdjust, Row + RowAdjust, Number \ 10)
      CALL ZSUBDrawDigit(Col + ColAdjust, Row + RowAdjust, Number MOD 10)
   END IF

END SUB

SUB ZSUBDrawScreen STATIC
  
   DIM I AS INTEGER
   DIM Rod AS INTEGER
  
   'clear and size graphic viewport
   VIEW (194, 22)-(638, 348), VIEWPORTBG, VIEWPORTBORDER
   WINDOW SCREEN (-.5, 0)-(MAXCOL + .5, MaxRow + 1)

   'draw trapezoid and leading edge
   PSET (0, MaxRow), BORDER
   LINE -(TRAPEZOIDX, MaxRow - TrapezoidY), BORDER
   LINE -(MAXCOL - TRAPEZOIDX, MaxRow - TrapezoidY), BORDER
   LINE -(MAXCOL, MaxRow), BORDER
   LINE (0, MaxRow)-(MAXCOL, MaxRow + .75), BG, BF
   LINE (0, MaxRow)-(MAXCOL, MaxRow + .75), BORDER, B
   PAINT (MAXCOL / 2, MaxRow - .5), BG, BORDER
  
   RodRow(1) = MaxRow - 2
   RodRow(2) = RodRow(1) - TriangleStep * 3
   RodRow(3) = RodRow(1)

   TowerSize(1) = 0
   TowerSize(2) = 0
   TowerSize(3) = 0

   'default value (no disk on rod) is larger than largest disk
   'makes comparison easier
   TopSize(1) = NUMBEROFDISKS + 1
   TopSize(2) = NUMBEROFDISKS + 1
   TopSize(3) = NUMBEROFDISKS + 1

   'draw disks located on rods
   FOR I = NUMBEROFDISKS TO 1 STEP -1
      IF NOT Disk(I) = 0 THEN
         Rod = Disk(I)
         CALL ZSUBDrawDisk(RodCol(Rod), RodRow(Rod), 1, I + 1, DISKHUE, FALSE)
         IF SHOWNUMBER THEN CALL ZSUBDrawNumber(RodCol(Rod), RodRow(Rod), I)
         RodRow(Rod) = RodRow(Rod) - 1
         TowerSize(Rod) = TowerSize(Rod) + 1
         TopSize(Rod) = I
      END IF
   NEXT I
  
   'draw rods on top of tower of disks
   FOR I = 1 TO 3
      CALL ZSUBDrawDisk(RodCol(I), RodRow(I), NUMBEROFDISKS + 1 - TowerSize(I), 1, RODHUE, FALSE)
   NEXT I

   'draw disk (if any) in transit
   IF NOT TransitDisk = 0 THEN
      CALL ZSUBDrawDisk(TransitCol(TransitPosition), TransitRow(TransitPosition), 1, TransitDisk + 1, DISKHUE, TRUE)
      IF SHOWNUMBER THEN CALL ZSUBDrawNumber(TransitCol(TransitPosition), TransitRow(TransitPosition), TransitDisk)
   END IF
  
   'wait for vertical retrace
   'REMmed out (inactivated); reactivate if graphics are not smooth
   'WAIT &H3DA, 8
   'WAIT &H3DA, 8, 8
 
   'update screen
   PCOPY 1, 0

   IF INKEY$ = EscKey$ THEN SYSTEM

END SUB

SUB ZSUBMoveDisk (RodFrom AS INTEGER, RodTo AS INTEGER, Dir AS INTEGER) STATIC

   DIM DiskNumber AS INTEGER
  
   SELECT CASE METHOD
      CASE 1
         MoveCount = MoveCount + 1
         LOCATE 19, 18
         PRINT USING H2$; MoveCount
      CASE 2, 3
         '
      CASE 4
         MoveCount = MoveCount + 1
         LOCATE 23, 18
         PRINT USING H2$; MoveCount
   END SELECT
  
   DiskNumber = TopSize(RodFrom)
  
   'mark disk not on rod
   Disk(DiskNumber) = 0
  
   'show transfer of disk from RodFrom to RodTo
   IF SHOWTRANSFER THEN
      'mark disk in transit
      TransitDisk = DiskNumber
      TransitPosition = (RodFrom - 1) * 3 + 1
     
      'show intermediate steps
      CALL ZSUBDrawScreen
      DO
         TransitPosition = TransitPosition + Dir
         IF TransitPosition = 0 THEN TransitPosition = 9
         IF TransitPosition = 10 THEN TransitPosition = 1
         CALL ZSUBDrawScreen
      LOOP UNTIL TransitPosition = (RodTo - 1) * 3 + 1
     
      'mark disk not in transit
      TransitDisk = 0
   END IF
  
   'mark disk on new rod
   Disk(DiskNumber) = RodTo

   'show disk on new rod
   CALL ZSUBDrawScreen
  
   'if SHOWTRANSFER is selected then pause slightly between disks
   IF SHOWTRANSFER THEN CALL ZSUBDelay(DELAY)

END SUB

SUB ZSUBSolution1 STATIC

   'mechanical solution (see Text1 for description)
  
   DIM SmallestDir AS INTEGER, SmallestRod AS INTEGER
   DIM EveryOtherMove AS INTEGER
   DIM RodFrom AS INTEGER, RodTo AS INTEGER, MoveDir AS INTEGER

   'set direction to move smallest disk
   'In this program counter-clockwise is -1 while clockwise is +1.
   IF (NUMBEROFDISKS AND 1) = 1 THEN SmallestDir = -1 ELSE SmallestDir = 1
  
   SmallestRod = Disk(1)
   EveryOtherMove = FALSE

   DO

      IF NOT EveryOtherMove THEN
         'move smallest disk (in SmallestDir direction)
         RodFrom = SmallestRod
         SmallestRod = SmallestRod + SmallestDir
         IF SmallestRod = 0 THEN SmallestRod = 3
         IF SmallestRod = 4 THEN SmallestRod = 1
         RodTo = SmallestRod
         MoveDir = SmallestDir
      ELSE
         'make only valid move not involving smallest disk
         SELECT CASE SmallestRod
            CASE 1
               RodFrom = 2: RodTo = 3
           CASE 2
               RodFrom = 1: RodTo = 3
            CASE 3
               RodFrom = 1: RodTo = 2
         END SELECT
         IF TopSize(RodFrom) > TopSize(RodTo) THEN SWAP RodFrom, RodTo
         MoveDir = DirTable(RodFrom, RodTo)
      END IF
     
      'move disk
      CALL ZSUBMoveDisk(RodFrom, RodTo, MoveDir)
     
      'toggle EveryOtherMove
      EveryOtherMove = NOT EveryOtherMove
  
   LOOP UNTIL TowerSize(3) = NUMBEROFDISKS

END SUB

SUB ZSUBSolution2 STATIC

   'binary number sequence solution (see Text2 for description)
  
   DIM BitPosition AS INTEGER, BitMask AS INTEGER
   DIM DiskNumber AS INTEGER
   DIM RodFrom AS INTEGER, RodTo AS INTEGER, MoveDir AS INTEGER

   'set direction to move all disks
   'In this program counter-clockwise is -1 while clockwise is +1.
   IF (NUMBEROFDISKS AND 1) = 1 THEN MoveDir = -1 ELSE MoveDir = 1
  
   DO

      MoveCount = MoveCount + 1
      LOCATE 20, 19
      PRINT USING H2$; MoveCount
     
      'determine first bit of MoveCount which is set
      BitPosition = 0
      BitMask = 1
      WHILE (MoveCount AND BitMask) = 0
         BitPosition = BitPosition + 1
         BitMask = BitMask * 2
      WEND
     
      'show MoveCount in binary
      LOCATE 21, 9
      PRINT ZFUNCBin$(MoveCount)
     
      'highlight first set bit
      COLOR HIGHLIGHTHUE
      LOCATE 21, 23 - BitPosition
      PRINT "1";
     
      COLOR 7
      LOCATE 22, 6
      PRINT USING H3$; BitPosition
     
      'disk number equals bit position + 1
      DiskNumber = BitPosition + 1
     
      LOCATE 22, 22
      PRINT USING H3$; DiskNumber
     
      'find next rod which is a legal move
      RodFrom = Disk(DiskNumber)
      RodTo = RodFrom
      DO
         RodTo = RodTo + MoveDir
         IF RodTo = 0 THEN RodTo = 3
         IF RodTo = 4 THEN RodTo = 1
      LOOP UNTIL TopSize(RodFrom) < TopSize(RodTo)
    
      'move disk
      CALL ZSUBMoveDisk(RodFrom, RodTo, MoveDir)
    
   LOOP UNTIL TowerSize(3) = NUMBEROFDISKS

END SUB

SUB ZSUBSolution3 STATIC

   'binary Gray code solution (see Text3 for description)
  
   DIM LastGrayCode AS INTEGER, GrayCode AS INTEGER
   DIM Result AS INTEGER
   DIM BitPosition AS INTEGER, BitMask AS INTEGER
   DIM DiskNumber AS INTEGER
   DIM RodFrom AS INTEGER, RodTo AS INTEGER, MoveDir AS INTEGER

   'set direction to move all disks
   'In this program counter-clockwise is -1 while clockwise is +1.
   IF (NUMBEROFDISKS AND 1) = 1 THEN MoveDir = -1 ELSE MoveDir = 1
  
   LastGrayCode = MoveCount XOR (MoveCount \ 2)
  
   DO

      MoveCount = MoveCount + 1
      LOCATE 20, 19
      PRINT USING H2$; MoveCount
     
      'calculate Gray code for MoveCount
      GrayCode = MoveCount XOR (MoveCount \ 2)
     
      LOCATE 21, 9
      PRINT ZFUNCBin$(GrayCode)
     
      LOCATE 22, 9
      PRINT ZFUNCBin$(LastGrayCode)
     
      'isolate the one bit which changed since last move
      Result = GrayCode XOR LastGrayCode
     
      'find position of changed bit
      BitPosition = 0
      BitMask = 1
      WHILE (Result AND 1) = 0
         BitPosition = BitPosition + 1
         Result = Result \ 2
         BitMask = BitMask * 2
      WEND
     
      'highlight changed bit
      COLOR HIGHLIGHTHUE
      LOCATE 21, 23 - BitPosition
      IF (GrayCode AND BitMask) = 0 THEN PRINT "0" ELSE PRINT "1"
     
      'update value of LastGrayCode
      LastGrayCode = GrayCode
     
      COLOR 7
      LOCATE 23, 6
      PRINT USING H3$; BitPosition
     
      'disk number equals bit position + 1
      DiskNumber = BitPosition + 1
    
      LOCATE 23, 22
      PRINT USING H3$; DiskNumber
      
      'find next rod which is a legal move
      RodFrom = Disk(DiskNumber)
      RodTo = RodFrom
      DO
         RodTo = RodTo + MoveDir
         IF RodTo = 0 THEN RodTo = 3
         IF RodTo = 4 THEN RodTo = 1
      LOOP UNTIL TopSize(RodFrom) < TopSize(RodTo)
   
      'move disk
      CALL ZSUBMoveDisk(RodFrom, RodTo, MoveDir)
   
   LOOP UNTIL TowerSize(3) = NUMBEROFDISKS

END SUB

SUB ZSUBSolution4 (RodFrom AS INTEGER, RodTo AS INTEGER, RodTemp AS INTEGER, DiskCount AS INTEGER)

   'solution using recursion (see Text4 for description)
  
   IF DiskCount = 1 THEN
      'move disk
      CALL ZSUBMoveDisk(RodFrom, RodTo, DirTable(RodFrom, RodTo))
   ELSE
      'move tower of disks except for the base
      CALL ZSUBSolution4(RodFrom, RodTemp, RodTo, DiskCount - 1)
      'move the base
      CALL ZSUBMoveDisk(RodFrom, RodTo, DirTable(RodFrom, RodTo))
      'put the moved tower of disks back on the base
      CALL ZSUBSolution4(RodTemp, RodTo, RodFrom, DiskCount - 1)
   END IF

END SUB