How to solve the Towers of Hanoi puzzle

The Classical Towers of Hanoi - an initial position of all disks is on post 'A'.

Towers
Fig. 1

The solution of the puzzle is to build the tower on post 'C'.

Towers
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.  * )

Towers
Fig. 3

Solving the Tower of Hanoi

'Solution' shortest path

Recursive Solution:

1. Identify biggest discrepancy (=disk N)

2. If moveable to goal peg Then move
      Else

3.   Subgoal: set-up (N−1)-disk tower on non-goal peg.

4. Go to 1.  ...


Some authors use the term "regular" position for any of the 3n disk arrangements that obey the rule of no disk on top of a smaller disk, and "perfect" position for one of the 3 disk arrangements with all disks on a single peg. Then the above algorithm is optimal between a regular position and a perfect position, or between a perfect position and a regular position, but not between two regular positions.

P.K. Stockmeyer


Solving the Tower of Hanoi - 'regular' to 'perfect'

Let's start thinking how to solve it.
Let's, for the sake of clarity, assume that our goal is to set a 4 disk-high tower on peg 'C' - just like in the classical Towers of Hanoi (see Fig. 2).
Let's assume we 'know' how to move a 'perfect' 3 disk-high tower.
Then on the way of solving there is one special setup. Disk 4 is on peg 'A' and the 3 disk-high tower is on peg 'B' and target peg 'C' is empty.

Towers
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.
Disk 3 is on peg 'C'. We need disk 3 on peg 'B'. To obtain that, we need disk 3 in place where it is now, free peg 'B' and disks 2 and 1 stacked on peg 'A'. So our goal now is to put disk 2 on peg 'A'.

Towers
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'.
As we can see, this is an easy task because disk 1 has no disk above it and peg 'B' is free.

Towers
Fig. 6

So let's move it.

Towers
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'.

Towers
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.

Romek



*) Mind that this setup may be not on the shortest path between the start and the end of the classical Towers. This can happen if one has made some wrong moves while resolving the classical Towers.