Explaining & Visualizing Towers of Hanoi Puzzle

The aim of this page📝 is to help with the understanding of the solution of the Towers of Hanoi puzzle, which is another canonical illustration of recursion theory from the end of the 19th century, the help I would welcome myself first arriving at the problem with just a basic understanding of recursion and binary trees.

4 min readDec 26, 2022

1. For a description — including the visual demonstration of the toy — see prof. Sussman in SICP

This is a second lecture of the series called Lecture 1B: Procedures and Processes; Substitution Model

2. For a solution, see prof. Jeff Erickson both in the CS473 and the “Algorithm” book

See CS 473 > 1. Administrivia, recursion > go to 24:14
In short the pseudo-code solution

Hanoi(n,src, dst,tmp):
if n > 0
    Hanoi(n-1,src,tmp, dst) 
    move disk n from src to dst
    Hanoi(n-1,tmp,dst,src)

As N. Claus (de Siam) pointed out in the pamphlet included with his puzzle, the secret to solving this puzzle is to think recursively. Instead of trying to solve the entire puzzle at once, let’s concentrate on moving just the largest disk. We can’t move it at the beginning, because all the other disks are in the way. So first we have to move those n 1 smaller disks to the spare peg. Once that’s done, we can move the largest disk directly to its destination. Finally, to finish the puzzle, we have to move the n 1 smaller disks from the spare peg to their destination; ignore everything but the bottom disk. So now all we have to figure out is how to — NO!! STOP!! That’s it! We’re done! We’ve successfully reduced the n-disk Tower of Hanoi problem to two instances of the (n 1)-disk Tower of Hanoi problem, which we can gleefully hand to the Recursion Fairy — or carry Lucas’s metaphor further, to the junior monks at the temple. Our job is finished. If we didn’t trust the junior monks, we wouldn’t have hired them; let them do their job in peace.

— for more, see https://github.com/jeffgerickson/algorithms/blob/master/1st%20edition/Chapters/01-recursion.pdf

3. The algorithm is a command — not a query — therefore there is no return value from the function

it took me a while to realize that I am not after a returned value here
this is, therefore, a command type of a function
the command is to move the appropriate disk from an appropriate pin into another appropriate pin
of course, the implementation of the command can be just a print of the solution
…you will do the moving by hand, in case you have the props
for more, see CommandQuerySeparation < bliki

4. The trick is that roles are rotated — and there is a problem with the readability of the algorithm

The essence of the algorithm is that there is a rotation of roles between the pins
Therefore what is defined as a source can be both target and temp in various calls, and vice versa
Took me a while to notice/get this
Also, I was struggling with making this obvious in the code and gave up
My current conclusion is that this is because this is science and not engineering
This is more code as poetry and less code as football
Currently, I am convinced that the mental mode for code at work should be football rather than poetry
Look at the algorithmic solution in #2 and note how optically complicated is it to spot the "role rotation"
In other words, the trick is calling identical parameters in a different order

5. Let’s look into my Python implementation of the algorithm

Running from the command line on 3 disks you’ll get

How many disks you want to solve for (max 8) ?:  3
        ~~> These are the moves for 3 disks
        ~~> The top is disk#1, the bottom is the disk#3

STEP#1
        ~~> Disk #1; A > C
STEP#2
        ~~> Disk #2; A > B
STEP#3
        ~~> Disk #1; C > B
STEP#4
        ~~> Disk #3; A > C
STEP#5
        ~~> Disk #1; B > A
STEP#6
        ~~> Disk #2; B > C
STEP#7
        ~~> Disk #1; A > C
TOTAL
        ~~> you required 7 moves

6. Even though Erickson suggests not to worry about the path to the solution, didactic reasons pull us to visualization tools

First, let’s look into the moves of the disks on pins

— from Data Structure & Algorithms — Tower of Hanoi < tutorialspoint

Second, let’s utilize Recursion Tree Visualizer and visualize the tree itself (use the tool to see the motions of the function calls building it)

Third, the puzzle is not only interesting but also impressive when it comes to visualizing say the solution to 16 disks

Explaining & Visualizing Towers of Hanoi Puzzle

1. For a description — including the visual demonstration of the toy — see prof. Sussman in SICP

2. For a solution, see prof. Jeff Erickson both in the CS473 and the “Algorithm” book

3. The algorithm is a command — not a query — therefore there is no return value from the function

4. The trick is that roles are rotated — and there is a problem with the readability of the algorithm

5. Let’s look into my Python implementation of the algorithm

6. Even though Erickson suggests not to worry about the path to the solution, didactic reasons pull us to visualization tools

LINKS

Written by Pavol Kutaj

No responses yet