Tower of Hanoi Algorithm Solution in TypeScript

A Step-by-Step Approach to Master the Classic Problem

Problem

The Tower of Hanoi is a puzzle game with three rods and n disks, each a different size.

All the disks start off on the first rod in a stack. They are ordered by size, with the largest disk on the bottom and the smallest one at the top.

The goal of this puzzle is to move all the disks from the first rod to the last rod while following these rules:

  • You can only move one disk at a time.
  • A move consists of taking the uppermost disk from one of the stacks and placing it on top of another stack.
  • You cannot place a larger disk on top of a smaller disk.

Write a function that prints out all the steps necessary to complete the Tower of Hanoi. You should assume that the rods are numbered, with the first rod being 1, the second (auxiliary) rod being 2, and the last (goal) rod being 3.

For example, with n = 3, we can do this in 7 moves:

Move 1 to 3
Move 1 to 2
Move 3 to 2
Move 1 to 3
Move 2 to 1
Move 2 to 3
Move 1 to 3

The Tower of Hanoi is a classic problem in computer science and mathematics. It involves moving disks of different sizes from one rod to another, following specific rules. The puzzle’s beauty lies in its simplicity and the recursive nature of its solution.

Problem Explanation

The Tower of Hanoi puzzle consists of three rods and n disks, each of a different size. Initially, all disks are stacked on the first rod, ordered by size, with the largest at the bottom and the smallest at the top. The goal is to move all the disks from the first rod to the third rod, following these rules:

  1. Only one disk can be moved at a time.
  2. A disk can only be placed on top of a larger disk or an empty rod.
  3. The disks must be moved following these constraints until all are transferred to the last rod.

Approach to the Solution

The Tower of Hanoi is best solved using a recursive approach. The key idea is to break the problem into smaller subproblems. Here’s how you can think about it:

  1. Move n-1 disks from the first rod to the second rod using the third rod as an auxiliary.
  2. Move the nth (largest) disk from the first rod to the third rod.
  3. Finally, move the n-1 disks from the second rod to the third rod using the first rod as an auxiliary.

TypeScript Implementation

Here’s how you can implement the Tower of Hanoi in TypeScript:

function towerOfHanoi(n: number, fromRod: number, toRod: number, auxRod: number): void {
    if (n === 1) {
        console.log(`Move disk 1 from rod ${fromRod} to rod ${toRod}`);
        return;
    }

    towerOfHanoi(n - 1, fromRod, auxRod, toRod);
    console.log(`Move disk ${n} from rod ${fromRod} to rod ${toRod}`);
    towerOfHanoi(n - 1, auxRod, toRod, fromRod);
}

// Example usage:
const n = 3; // Number of disks
towerOfHanoi(n, 1, 3, 2);
Step-by-Step Explanation
Base Case: If there is only one disk (n === 1), move it directly from the source rod to the target rod. This is the simplest case.

Recursive Case: If there are more than one disk, the function calls itself twice:

First, to move n-1 disks from the source rod to the auxiliary rod.
Second, to move the largest disk directly to the target rod.
Finally, it moves the n-1 disks from the auxiliary rod to the target rod.
Output
For n = 3, the output will be:

Move disk 1 from rod 1 to rod 3
Move disk 2 from rod 1 to rod 2
Move disk 1 from rod 3 to rod 2
Move disk 3 from rod 1 to rod 3
Move disk 1 from rod 2 to rod 1
Move disk 2 from rod 2 to rod 3
Move disk 1 from rod 1 to rod 3

Conclusion

The Tower of Hanoi problem is a brilliant example of how recursion can simplify complex problems. By breaking down the problem into smaller, manageable parts, you can achieve the goal with elegance. The TypeScript code provided offers a straightforward implementation that prints the sequence of moves needed to solve the puzzle.

“Complex problems are best tackled by simplifying them into smaller, manageable tasks.” — Burhanuddin Mulla Hamzabhai

If you like this, please think about buying me a coffee! ☕️.

Burhanuddin’s Code Compendium

Thank you for being a part of the Burhanuddin’s Code Compendium community! Before you go: