The Classical Towers of Hanoi - an initial position of all disks is on post 'A'. Fig. 1 The solution of the puzzle is to build the tower on post 'C'. Fig. 2 The Arbitrary Towers of Hanoi - at start, disks can be in any position provided that a bigger disk is never on top of the smaller one (see Fig. 3). At the end, disks should be in another arbitrary position. * ) Fig. 3 | |
Solving the Tower of Hanoi
| |
| |
Solving the Tower of Hanoi - 'regular' to 'perfect'Let's start thinking how to solve it. Fig. 4 From that position we have to move disk 4 from 'A' to 'C' and move by some magic the 3 disk-high tower from 'B' to 'C'. So think back. Forget the disks bigger than 3. Fig. 5 Forget for the moment disk 3 (see Fig. 6). To be able to put disk 2 on peg 'A'
we need to empty peg 'A' (above the thin blue line), disks smaller than disk 2
stacked on peg 'B'. So, our goal now is to put disk 1 on peg 'B'. Fig. 6 So let's move it. Fig. 7 The steps above are made by the algorithm implemented in Towers of Hanoi when one clicks the "Help me" button. This button-function makes analysis of the current position and generates only one single move which leads to the solution. It is by design. When the 'Help me' button is clicked again, the algorithm repeats all steps of the analysis starting from the position of the biggest disk - in this example disk 4 - and generates the next move - disk 2 from peg 'C' to peg 'A'. Fig. 8 If one needs a recursive or iterative algorithm which generates the series of moves for solving arbitrary Towers of Hanoi then one should use a kind of back track programming, that is to remember previous steps of the analysis and not to repeat the analysis of the Towers from the ground. But this is another story. |