Tower of Hanoi – Algorithm and Recurrence Equation

The tower of Hanoi is very well known recursive problem, also known as Tower of Lucas. The problem is based on 3 pegs (source, auxiliary and destination) and n disks. Tower of Hanoi is the problem of shifting all n disks from source peg to destination peg using auxiliary peg with the following constraints :

• Only one disk can be moved at a time.
• A Larger disk cannot be placed on a smaller disk.
• The initial and final configuration of the disks are shown in following figures

Story, Fun, Myth, Truth – What not?

Édouard Lucas, a French mathematician, developed the puzzle in 1883. Almost soon, stories about the ancient and magical nature of the puzzle surfaced, including one about an Indian temple in Kashi Vishwanath having a huge chamber with three time-worn pillars in it, encircled by 64 golden disks. Since that time, Brahmin priests have been rotating these disks in line with the unchanging laws of Brahma, fulfilling the order of an ancient prophesy. As a result, the puzzle is also known as the Tower of Brahma. According to legend, the world will end when the final move of the puzzle is completed.

If priests transfers the disks at a rate of one disk per second, with optimum number of moves, then also it would take them 2⁶⁴ – 1 seconds, which is around 585 billion years, which is 42 times the age of the universe as of now.

How it works?

There can be n number of disks on source peg. Let’s trace the problem for n = 3 disks. The trace of the solution is :

Step 1:Move disk C from the src peg to dst peg

Step 2 : Move disk B from the src peg to aux peg

Step 3 :Move disk C from the dst peg to aux peg

Step 4 :Move disk A from the src peg to dst peg

Step 5:  Move disk C from the aux peg to src peg

Step 6:Move disk B from the aux peg to dst peg

Step 7: Move disk C from the src peg to dst peg

Algorithm for Tower of Hanoi

Algorithm for to solve tower of Hanoi problem is mentioned here:

Algorithm HANOI(src, aux, dest, n)
// Description : Move n disks from source peg to destination peg 
// Input : 3 pages, and n disks on source peg
// Output : n disks on destination peg

if n = = 1 then
    Move disk from src to dest
else
    HANOI(src, dest, aux, n – 1)
    HANOI(src, aux, dst, 1)
    HANOI(aux, src, dest, n – 1)
end

Complexity Analysis of Tower of Hanoi

The recursive approach is the best suitable for solving this problem. The recursive formulation for the tower of Hanoi is given as,

Solution to this recurrence is given as,

Step 1: Size of problem is n

Step 2: Primitive operation is to move the disk from one peg to another peg

Step 3: Every call makes two recursive calls with a problem size of n – 1. And each call corresponds to one primitive operation, so recurrence for this problem can be set up as follows:

T(n) = 2T(n – 1) + 1 …(1)

Let us solve this recurrence using forward and backward substitution:

Substitute n by n – 1 in Equation (1),

T(n – 1) = 2T(n – 2) + 1,

By putting this value back in Equation (1),

T(n) = 2[2T(n – 2) + 1] + 1

= 2²T(n – 2) + 2 + 1

= 2²T(n – 2) + (2² – 1) …(2)

Similarly, replace n by n – 2 in Equation (1),

T(n – 2) = 2T(n – 3) +  1,

From Equation (2),

T(n) = 2²[ 2T(n – 3) + 1] + 2 + 1

= 2³T(n – 3) + 2² + 2 + 1

= 2³T(n – 3) + (2³ – 1)

In general,

T(n) = 2^kT(n – k ) + (2^k– 1)

By putting k = n – 1,

T(n) = 2^n–1[T(1)] + (2^{n – 1}– 1)

T(1) indicates problem of size 1. To shift 1 disk from source to destination peg takes only one move, so T(1) = 1.

T(n) = 2^n–1 + (2^{n – 1}– 1)

= 2ⁿ – 1

Thus, T(n) = O(2ⁿ)

Simulation of Tower of Hanoi

Following image shows simulation of the tower of hanoi with tree disks.

Image Source: https://ioecapsule.com/tower-of-hanoi-algorithm-and-implementation/

---

Additional Reading: Simulation