JavaScript: Implement the Tower of Hanoi Algorithm

Introduction

The Tower of Hanoi is a classic mathematical puzzle involving three pegs and a number of disks of different sizes. The objective is to move all the disks from the source peg to the target peg, following these rules:

1. Only one disk can be moved at a time.
2. A disk can only be moved if it is the top disk on a peg.
3. No larger disk can be placed on top of a smaller disk.

The problem can be solved recursively, where moving n disks involves:

1. Moving n-1 disks from the source peg to the auxiliary peg.
2. Moving the nth disk from the source peg to the target peg.
3. Moving the n-1 disks from the auxiliary peg to the target peg.

Problem Statement

Create a JavaScript program that:

• Solves the Tower of Hanoi problem for n disks.
• Displays each move (which disk to move from which peg to which peg).

Example:

• Input: 3 disks, pegs labeled A, B, and C.
• Output:

  Move disk 1 from A to C
  Move disk 2 from A to B
  Move disk 1 from C to B
  Move disk 3 from A to C
  Move disk 1 from B to A
  Move disk 2 from B to C
  Move disk 1 from A to C
  

Solution Steps

1. Define the Tower of Hanoi Function:
   • Use recursion to solve the problem.
   • Print each move.
2. Recursive Approach:
   • Move n-1 disks from the source peg to the auxiliary peg.
   • Move the nth disk from the source peg to the target peg.
   • Move n-1 disks from the auxiliary peg to the target peg.

JavaScript Program

Tower of Hanoi Implementation

// JavaScript Program to Implement the Tower of Hanoi Algorithm
// Author: https://www.rameshfadatare.com/

function towerOfHanoi(n, source, target, auxiliary) {
    // Base case: if only 1 disk, move it from source to target
    if (n === 1) {
        console.log(`Move disk 1 from ${source} to ${target}`);
        return;
    }

    // Step 1: Move n-1 disks from source to auxiliary
    towerOfHanoi(n - 1, source, auxiliary, target);

    // Step 2: Move the nth disk from source to target
    console.log(`Move disk ${n} from ${source} to ${target}`);

    // Step 3: Move the n-1 disks from auxiliary to target
    towerOfHanoi(n - 1, auxiliary, target, source);
}

// Example usage: Solve Tower of Hanoi with 3 disks
const numberOfDisks = 3;
towerOfHanoi(numberOfDisks, 'A', 'C', 'B');

Output for 3 Disks

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Explanation

Base Case: When n = 1

• The simplest case occurs when there is only one disk. In this case, simply move the disk from the source peg to the target peg.

Recursive Case: When n > 1

1. Move n-1 Disks from Source to Auxiliary: Recursively solve the problem for n-1 disks, using the target peg as the auxiliary.
2. Move the nth Disk from Source to Target: After moving n-1 disks, move the nth (largest) disk from the source to the target peg.
3. Move n-1 Disks from Auxiliary to Target: Finally, move the n-1 disks from the auxiliary peg to the target peg, using the source peg as auxiliary.

Example for 3 Disks

1. Move disk 1 from A to C
2. Move disk 2 from A to B
3. Move disk 1 from C to B
4. Move disk 3 from A to C
5. Move disk 1 from B to A
6. Move disk 2 from B to C
7. Move disk 1 from A to C

Time Complexity

• The time complexity of the Tower of Hanoi algorithm is O(2^n), where n is the number of disks.
  • This is because for each disk, the algorithm recursively solves the problem for n-1 disks twice and performs one move.

Conclusion

This JavaScript program solves the Tower of Hanoi problem using a recursive approach. The program efficiently handles the recursive steps and prints the sequence of moves required to transfer all disks from the source peg to the target peg. The recursive solution helps break down the problem into smaller, manageable subproblems, making it an excellent example of recursion in action.