Tower of Hanoi Problem in DSA Javascript - Build from Scratch

Tower of Hanoi Problem

📖 Scenario: Imagine you have three rods and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks neatly stacked in ascending order of size on one rod, the smallest at the top, making a conical shape.The goal 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 or on an empty rod.No disk may be placed on top of a smaller disk.

🎯 Goal: You will write a JavaScript program that prints the steps to solve the Tower of Hanoi puzzle for 3 disks. Each step will show which disk moves from which rod to which rod.

📋 What You'll Learn

Create a variable numDisks with the value 3.

Create a function towerOfHanoi that takes n, fromRod, toRod, and auxRod as parameters.

Use recursion inside towerOfHanoi to print the steps to move disks.

Print each move in the format: Move disk X from rod Y to rod Z.

💡 Why This Matters

🌍 Real World

The Tower of Hanoi problem helps understand recursion, a key concept in programming and problem solving.

💼 Career

Recursion and problem decomposition are important skills for software developers, especially in algorithm design and coding interviews.

1

Set up the number of disks

Create a variable called numDisks and set it to 3.

DSA Javascript

# Your code here

Hint

Use const to declare numDisks and assign it the value 3.

2

Define the Tower of Hanoi function

Define a function called towerOfHanoi with parameters n, fromRod, toRod, and auxRod.

DSA Javascript

const numDisks = 3;

// Define the towerOfHanoi function here
# Your code here

Hint

Use recursion to move n-1 disks to the auxiliary rod, then move the nth disk, then move the n-1 disks from auxiliary to target rod.

3

Call the Tower of Hanoi function

Call the function towerOfHanoi with arguments numDisks, 'A', 'C', and 'B' to start the solution.

DSA Javascript

const numDisks = 3;

function towerOfHanoi(n, fromRod, toRod, auxRod) {
    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);
}

// Call the function to solve the puzzle
# Your code here

Hint

Call towerOfHanoi with numDisks and rods 'A', 'C', 'B' in that order.

4

Print the solution steps

Run the program to print the steps to move 3 disks from rod A to rod C following the Tower of Hanoi rules.

DSA Javascript

const numDisks = 3;

function towerOfHanoi(n, fromRod, toRod, auxRod) {
    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);
}

towerOfHanoi(numDisks, 'A', 'C', 'B');

// Run the program to see the output
# Your code here

Hint

Check the console output for the correct sequence of moves.

Practice

1. What is the minimum number of moves required to solve the Tower of Hanoi problem with 3 disks?

easy

A. 7

B. 6

C. 8

D. 9

Solution

1. Step 1: Understand the formula for minimum moves

   The minimum moves required for n disks is 2^n - 1.

2. Step 2: Calculate for 3 disks

   For 3 disks, minimum moves = 2^3 - 1 = 8 - 1 = 7.

3. Final Answer:

   7 -> Option A

4. Quick Check:

   2^3 - 1 = 7 [OK]

Hint: Use formula 2^n - 1 for minimum moves [OK]

Common Mistakes:

• Forgetting to subtract 1
• Using n instead of 2^n - 1
• Confusing number of disks with moves

2. Which of the following is the correct base case condition in a recursive Tower of Hanoi function in JavaScript?

easy

A. if (n < 0) return;

B. if (n === 1) moveDisk();

C. if (n > 1) return;

D. if (n === 0) return;

Solution

1. Step 1: Identify base case for recursion

   The recursion stops when there are no disks to move, i.e., n === 0.

2. Step 2: Check the options

   if (n === 0) return; correctly returns when n is 0, stopping recursion.

3. Final Answer:

   if (n === 0) return; -> Option D

4. Quick Check:

   Base case is n === 0 [OK]

Hint: Base case stops recursion at zero disks [OK]

Common Mistakes:

• Using n === 1 as base case incorrectly
• Not stopping recursion causing infinite calls
• Using invalid conditions like n < 0

3. What will be the output sequence of moves for 2 disks in the Tower of Hanoi problem using this code snippet?

function towerOfHanoi(n, from, to, aux) {
  if (n === 0) return;
  towerOfHanoi(n - 1, from, aux, to);
  console.log(`Move disk ${n} from ${from} to ${to}`);
  towerOfHanoi(n - 1, aux, to, from);
}
towerOfHanoi(2, 'A', 'C', 'B');

medium

A. "Move disk 2 from A to C"
"Move disk 1 from B to A"
"Move disk 2 from C to B"

B. "Move disk 2 from A to B"
"Move disk 1 from A to C"
"Move disk 2 from B to C"

C. "Move disk 1 from A to B"
"Move disk 2 from A to C"
"Move disk 1 from B to C"

D. "Move disk 1 from A to C"
"Move disk 2 from A to B"
"Move disk 1 from C to B"

Solution

1. Step 1: Trace recursive calls for n=2

   First move disk 1 from A to B, then disk 2 from A to C, then disk 1 from B to C.

2. Step 2: Match output with options

   "Move disk 1 from A to B" "Move disk 2 from A to C" "Move disk 1 from B to C" matches the exact sequence of moves printed by the code.

3. Final Answer:

   "Move disk 1 from A to B" "Move disk 2 from A to C" "Move disk 1 from B to C" -> Option C

4. Quick Check:

   Correct move sequence for 2 disks = "Move disk 1 from A to B" "Move disk 2 from A to C" "Move disk 1 from B to C" [OK]

Hint: Follow recursion calls step-by-step [OK]

Common Mistakes:

• Mixing source and auxiliary rods
• Confusing disk numbers in moves
• Ignoring order of recursive calls

4. Identify the error in this Tower of Hanoi recursive function and select the fix:

function towerOfHanoi(n, from, to, aux) {
  if (n === 1) {
    console.log(`Move disk 1 from ${from} to ${to}`);
    return;
  }
  towerOfHanoi(n - 1, from, to, aux);
  console.log(`Move disk ${n} from ${from} to ${to}`);
  towerOfHanoi(n - 1, aux, to, from);
}

medium

A. Swap 'to' and 'aux' in the first recursive call

B. Change base case to n === 0

C. Remove the second recursive call

D. Add an extra console.log before recursion

Solution

1. Step 1: Analyze recursive calls

   The first recursive call should move n-1 disks from 'from' to 'aux' using 'to' as auxiliary, but here 'to' and 'aux' are swapped.

2. Step 2: Correct the argument order

   Swapping 'to' and 'aux' in the first recursive call fixes the logic to move disks correctly.

3. Final Answer:

   Swap 'to' and 'aux' in the first recursive call -> Option A

4. Quick Check:

   Correct recursive call order fixes error [OK]

Hint: Check recursive call parameters carefully [OK]

Common Mistakes:

• Mixing auxiliary and target rods
• Incorrect base case causing infinite recursion
• Removing necessary recursive calls

5. You want to solve the Tower of Hanoi problem for 4 disks but only want to print moves where disk 1 is moved. How would you modify this function?

function towerOfHanoi(n, from, to, aux) {
  if (n === 0) return;
  towerOfHanoi(n - 1, from, aux, to);
  console.log(`Move disk ${n} from ${from} to ${to}`);
  towerOfHanoi(n - 1, aux, to, from);
}

hard

A. Change base case to n === 1 and print only then

B. Add an if condition to print only when n === 1 inside the function

C. Remove recursive calls and print only disk 1 move

D. Print all moves but filter output outside the function

Solution

1. Step 1: Understand the requirement

   We want to print moves only when disk 1 moves, but still perform all recursive calls to solve the problem.

2. Step 2: Modify print statement with condition

   Add an if condition to print only when n === 1, so other moves are not printed but recursion continues.

3. Final Answer:

   Add an if condition to print only when n === 1 inside the function -> Option B

4. Quick Check:

   Conditional print inside recursion solves problem [OK]

Hint: Use if (n === 1) to print selectively [OK]

Common Mistakes:

• Changing base case breaks recursion
• Removing recursive calls stops solution
• Filtering output outside misses recursion logic