Tower of Hanoi with recursion

Problem statement

Assume there are 3 towers and \(D\) disks. And all disks are place at the first tower in a descending order in terms of disk number. It can be illustrated as follows:

1
2
3
4
5
6
7
     [1]             |              |
    [ 2 ]            |              |
      :              |              |
 [   D-1   ]         |              |
[     D     ]        |              |
-----------------------------------------
    Tower 1        Tower 2        Tower 3

The objective is to find out the order of movement to move the entire disks to another tower with constrains:

  • One only disk can be moved at a time
  • Disk \(X\) cannot be placed under disk \(Y\), where \(X\) is greater than \(Y\)

Approach

To move disk \(X\) from tower \(A\) to \(C\), three steps as follows:

  1. Move disks 1 to \(X-1\) from tower \(A\) to \(B\)
  2. Move disk \(X\) from tower \(A\) to \(C\)
  3. Move disks 1 to \(X-1\) from tower \(B\) to \(C\)

Steps (1) and (3) are not a single atomic operation and they can be performed recursively:

  1. Move disks 1 to \(X-2\) from tower \(A\) to \(C\)
  2. Move disk \(X-1\) from tower \(A\) to \(B\)
  3. Move disks 1 to \(X-2\) from tower \(C\) to \(B\)

If there is only one disk to move, step (1) and step (3) can be skipped.

Implementation

We can define a function moveDisks() whose inputs are the number of disks to be moved, tower number that the disks are currently located and tower number that the disks to be moved to:

1
void moveDisks(int nDisks, int from, int to);

It can recursively call the function itself:

1
2
3
4
5
6
7
8
9
10
void moveDisks(int nDisks, int from, int to) {
  int intermediate = 6 - from - to;
  if (nDisks > 1) {
    moveDisks(nDisks - 1, from, intermediate);
  }
  cout << "Move disk " << nDisks << " from tower " << from << " to tower " << to << endl;
  if (nDisks > 1) {
    moveDisks(nDisks - 1, intermediate, to);
  }
}

Here int intermediate = 6 - from - to; is a tricky part. This variable represents the number of intermediate tower to move nDisks - 1 disks. If each tower is numbered with 1, 2, and 3 then relationships between from, to and intermediate can be determined as follows and the forementioned equation reflects these relationships:

From To Intermediate
1 2 3
1 3 2
2 1 3
2 3 2
3 1 2
3 2 3

Test result

1
2
3
4
5
6
7
8
3
Move disk 1 from tower 1 to tower 3
Move disk 2 from tower 1 to tower 2
Move disk 1 from tower 3 to tower 2
Move disk 3 from tower 1 to tower 3
Move disk 1 from tower 2 to tower 1
Move disk 2 from tower 2 to tower 3
Move disk 1 from tower 1 to tower 3