Tower of Hanoi Problem

The Tower of Hanoi is a mathematical puzzle consisting of three rods and n disks of different sizes which can slide onto any rod.

The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, making a conical shape. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

Only one disk can be moved at a time.
Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack, i.e., a disk can only be moved if it is the uppermost disk on a stack.
No disk may be placed on top of a smaller disk.

The minimum number of moves required to solve a Tower of Hanoi puzzle is 2ⁿ-1, where n is the total number of disks.

An animated solution of the Tower of Hanoi puzzle for n = 4 can be seen here. Following are the steps that were taken by the proposed solution:

Move disk 1 from 1 to 2
Move disk 2 from 1 to 3
Move disk 1 from 2 to 3
Move disk 3 from 1 to 2
Move disk 1 from 3 to 1
Move disk 2 from 3 to 2
Move disk 1 from 1 to 2
Move disk 4 from 1 to 3
Move disk 1 from 2 to 3
Move disk 2 from 2 to 1
Move disk 1 from 3 to 1
Move disk 3 from 2 to 3
Move disk 1 from 1 to 2
Move disk 2 from 1 to 3
Move disk 1 from 2 to 3

Practice this problem

We can easily solve the Tower of Hanoi problem using recursion. A key to solving this puzzle is recognizing that we can solve it by breaking the problem down into a collection of smaller problems and further breaking those problems down into even smaller problems until a solution is reached.

To move n discs from pole 1 to pole 3:

Move n-1 discs from 1 to 2. This leaves disc n alone on pole 1.
Move disc n from 1 to 3.
Move n-1 discs from 2 to 3, so they sit on disc n.

The algorithm can be implemented as follows in C++, Java, and Python:

C++

#include <iostream>

using namespace std;

void move(int disks, int source=1, int auxiliary=2, int target=3)

{

if (disks > 0)

{

// move `n-1` discs from source to auxiliary using the target

// as an intermediate pole

move(disks - 1, source, target, auxiliary);

// move one disc from source to target

cout << "Move disk " << disks << " from " << source << " —> "

<< target << endl;

// move `n-1` discs from auxiliary to target using the source

// as an intermediate pole

move(disks - 1, auxiliary, source, target);

}

int main()

{

int n = 3;

move(n);

return 0;

}

Download Run Code

Java

class Main

{

public static void move(int disks, int source, int auxiliary, int target)

{

if (disks > 0)

{

// move `n-1` discs from source to auxiliary using the target

// as an intermediate pole

move(disks - 1, source, target, auxiliary);

// move one disc from source to target

System.out.println("Move disk " + disks + " from " + source + " —> " +

target);

// move `n-1` discs from auxiliary to target using the source

// as an intermediate pole

move(disks - 1, auxiliary, source, target);

}

// Tower of Hanoi Problem

public static void main(String[] args)

{

int n = 3;

move(n, 1, 2, 3);

}

Download Run Code

Python

def move(disks, source=1, auxiliary=2, target=3):

if disks > 0:

# move `n-1` discs from source to auxiliary using the target

# as an intermediate pole

move(disks - 1, source, target, auxiliary)

# move one disc from source to target

print(f'Move disk {disks} from {source} —> {target}')

# move `n-1` discs from auxiliary to target using the source

# as an intermediate pole

move(disks - 1, auxiliary, source, target)

# Tower of Hanoi Problem

if __name__ == '__main__':

n = 3

move(n)

Download Run Code

Output:

Move disk 1 from 1 —> 3
Move disk 2 from 1 —> 2
Move disk 1 from 3 —> 2
Move disk 3 from 1 —> 3
Move disk 1 from 2 —> 1
Move disk 2 from 2 —> 3
Move disk 1 from 1 —> 3

The time complexity of the above solution is O(2ⁿ), where n is the total number of disks. If n = 64 and one disk is moved per second, then using the smallest number of moves available will take 2⁶⁴-1 seconds, or roughly 585 billion years to finish the game.

References: https://en.wikipedia.org/wiki/Tower_of_Hanoi

C++

Java

Python

Share this: