Tower of Hanoi solution using recursion in java

Tower of hanoi is one of the basic questions to learn recursion and very commonly asked interview question at beginner and intermediate level.

Section in this post:

1. Problem statement
2. Iterative solution
3. Alternate iterative solution
4. Recursive solution
5. Java Implementation

The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower, and sometimes pluralised) is a mathematical game or puzzle. It consists of three rods, and a number of 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, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.
2. 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.
3. No disk may be placed on top of a smaller disk.

 With three disks, the puzzle can be solved in seven moves. The minimum number of moves required to solve a Tower of Hanoi puzzle is 2ⁿ - 1, where n is the number of disks.

Iterative solution

 

Alternate moves between the smallest piece and a non-smallest piece. When moving the smallest piece, always move it to the next position in the same direction (to the right if the starting number of pieces is even, to the left if the starting number of pieces is odd). If there is no tower position in the chosen direction, move the piece to the opposite end, but then continue to move in the correct direction. For example, if you started with three pieces, you would move the smallest piece to the opposite end, then continue in the left direction after that. When the turn is to move the non-smallest piece, there is only one legal move. Doing this will complete the puzzle in the fewest number of moves.

 

Simpler statement of iterative solution

 

Alternating between the smallest and the next-smallest disks, follow the steps for the appropriate case:
For an even number of disks:

• make the legal move between pegs A and B

• make the legal move between pegs A and C
• make the legal move between pegs B and C
• repeat until complete

For an odd number of disks:

• make the legal move between pegs A and C
• make the legal move between pegs A and B
• make the legal move between pegs C and B
• repeat until complete

In each case, a total of 2ⁿ-1 moves are made.

Equivalent iterative solution

 

Another way to generate the unique optimal iterative solution:

Number the disks 1 through n (largest to smallest).

• If n is odd, the first move is from the Start to the Finish peg.
• If n is even, the first move is from the Start to the Using peg.

Now, add these constraints:

• No odd disk may be placed directly on an odd disk.
• No even disk may be placed directly on an even disk.
• Never undo your previous move (that is, do not move a disk back to its immediate last peg).

Considering those constraints after the first move, there is only one legal move at every subsequent turn.

The sequence of these unique moves is an optimal solution to the problem equivalent to the iterative solution described above.

Recursive solution

 

A key to solving this puzzle is to recognize that it can be solved 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. For example:

• label the pegs A, B, C — these labels may move at different steps
• let n be the total number of discs
• number the discs from 1 (smallest, topmost) to n (largest, bottommost)

To move n discs from peg A to peg C:

1. move n−1 discs from A to B. This leaves disc n alone on peg A
2. move disc n from A to C
3. move n−1 discs from B to C so they sit on disc n

The above is a recursive algorithm, to carry out steps 1 and 3, apply the same algorithm again for n−1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for n = 1. This step, moving a single disc from peg A to peg B, is trivial.

Below is my Java code to solve the problem recursively.

Class TowerOfHanoi:

public class TowerOfHanoi {

  public static void solveHanoi(int nTop, char fromTower, char midTower,
                              char toTower) {
    if (nTop == 1){
      System.out.println("Disk 1 from " + fromTower + " to " + toTower);
    }else {
      solveHanoi(nTop - 1, fromTower, toTower, midTower);
      System.out.println("Disk " + nTop + " from " + fromTower 
                 + " to " + midTower);
      solveHanoi(nTop - 1, midTower, fromTower, toTower);
    }
  }

  public static void main(String[] args) {
    int nDisks = 3;
    solveHanoi(nDisks, 'A', 'B', 'C');
  }
}

output :
===================================================================
Disk 1 from A to C
Disk 2 from A to B
Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A
Disk 2 from B to C
Disk 1 from A to C