Tower of Hanoi Problem in DSA Go - 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.Your task 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: Write a Go program that uses recursion to solve the Tower of Hanoi problem for 3 disks. The program should print each move step-by-step, showing which disk moves from which rod to which rod.

📋 What You'll Learn

Create a variable numDisks with the value 3

Create a recursive function towerOfHanoi with parameters n int, from string, to string, and aux string

Inside towerOfHanoi, print the move steps in the format: Move disk X from Y to Z

Call towerOfHanoi with numDisks, "A", "C", and "B"

Print all moves to solve the puzzle

💡 Why This Matters

🌍 Real World

The Tower of Hanoi problem helps understand recursion, which is used in many computer science problems like sorting, searching, and navigating file systems.

💼 Career

Understanding recursion and problem-solving with recursive functions is essential for software developers, especially in algorithm design and optimization.

1

Create the number of disks variable

Create a variable called numDisks and set it to 3.

DSA Go

// Create a variable called numDisks and set it to 3
// Your code here

Hint

Use numDisks := 3 to create the variable.

2

Define the recursive Tower of Hanoi function

Define and implement the recursive function called towerOfHanoi with parameters n int, from string, to string, and aux string. Use base case if n == 1 to print Move disk 1 from %s to %s. Recursively call to move n-1 disks from from to aux, print move for disk n from from to to, then recursively move n-1 from aux to to.

DSA Go

package main

import "fmt"

func towerOfHanoi(n int, from string, to string, aux string) {
    // Your code here
}

func main() {
    numDisks := 3
}

Hint

Use recursion with base case n == 1 and recursive calls to move disks.

3

Call the Tower of Hanoi function in main

Inside the main function, call towerOfHanoi with arguments numDisks, "A", "C", and "B".

DSA Go

package main

import "fmt"

func towerOfHanoi(n int, from string, to string, aux string) {
    if n == 1 {
        fmt.Printf("Move disk 1 from %s to %s\n", from, to)
        return
    }
    towerOfHanoi(n-1, from, aux, to)
    fmt.Printf("Move disk %d from %s to %s\n", n, from, to)
    towerOfHanoi(n-1, aux, to, from)
}

func main() {
    numDisks := 3
    // Call towerOfHanoi here
    // Your code here
}

Hint

Call the function with numDisks, "A", "C", and "B".

4

Print the moves to solve the Tower of Hanoi

Run the program to print all the moves required to solve the Tower of Hanoi puzzle for 3 disks.

DSA Go

package main

import "fmt"

func towerOfHanoi(n int, from string, to string, aux string) {
    if n == 1 {
        fmt.Printf("Move disk 1 from %s to %s\n", from, to)
        return
    }
    towerOfHanoi(n-1, from, aux, to)
    fmt.Printf("Move disk %d from %s to %s\n", n, from, to)
    towerOfHanoi(n-1, aux, to, from)
}

func main() {
    numDisks := 3
    towerOfHanoi(numDisks, "A", "C", "B")
    // Program prints moves automatically
    // Your code here
}

Hint

Run the program to see the moves printed step-by-step.

Practice

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

easy

A. 6

B. 9

C. 8

D. 7

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 D

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
• Confusing number of disks with moves

2. Which of the following Go function signatures correctly represents the Tower of Hanoi recursive function?

easy

A. func towerOfHanoi(n string, from int, to int, aux int)

B. func towerOfHanoi(n int, from string, to string, aux string)

C. func towerOfHanoi(n int, from int, to int)

D. func towerOfHanoi(n int, from string, to string)

Solution

1. Step 1: Identify parameters needed for Tower of Hanoi

   We need number of disks (int), and names of three rods (strings): from, to, auxiliary.

2. Step 2: Match function signature

   func towerOfHanoi(n int, from string, to string, aux string) matches with n as int and three string rods. Others miss parameters or have wrong types.

3. Final Answer:

   func towerOfHanoi(n int, from string, to string, aux string) -> Option B

4. Quick Check:

   Correct parameters and types = func towerOfHanoi(n int, from string, to string, aux string) [OK]

Hint: Tower of Hanoi needs 4 params: disks and 3 rods [OK]

Common Mistakes:

• Using wrong parameter types
• Missing auxiliary rod parameter
• Using fewer than 4 parameters

3. What will be the output of the following Go code snippet for Tower of Hanoi with 2 disks?

func towerOfHanoi(n int, from string, to string, aux string) {
    if n == 1 {
        fmt.Printf("Move disk 1 from %s to %s\n", from, to)
        return
    }
    towerOfHanoi(n-1, from, aux, to)
    fmt.Printf("Move disk %d from %s to %s\n", n, from, to)
    towerOfHanoi(n-1, aux, to, from)
}

func main() {
    towerOfHanoi(2, "A", "C", "B")
}

medium

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

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

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

D. Move disk 1 from B to C
Move disk 2 from A to C
Move disk 1 from A 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 A

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: Trace recursion carefully for small n [OK]

Common Mistakes:

• Swapping auxiliary and target rods
• Printing moves in wrong order
• Confusing disk numbers

4. Identify the error in the following Tower of Hanoi Go function and select the correct fix:

func towerOfHanoi(n int, from string, to string, aux string) {
    if n == 0 {
        return
    }
    towerOfHanoi(n-1, from, to, aux)
    fmt.Printf("Move disk %d from %s to %s\n", n, from, to)
    towerOfHanoi(n-1, aux, to, from)
}

medium

A. Remove base case entirely

B. Change base case to if n == 1 and adjust recursive calls accordingly

C. Swap 'to' and 'aux' in first recursive call

D. Change print statement to use 'aux' instead of 'to'

Solution

1. Step 1: Analyze recursive calls and base case

   Base case with n==0 is okay, but first recursive call uses wrong rod order: it should move disks from 'from' to 'aux' using 'to' as auxiliary.

2. Step 2: Correct first recursive call

   Swap 'to' and 'aux' in first recursive call to towerOfHanoi(n-1, from, aux, to).

3. Final Answer:

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

4. Quick Check:

   Correct rod order in recursion = Swap 'to' and 'aux' in first recursive call [OK]

Hint: First recursive call moves disks to auxiliary rod [OK]

Common Mistakes:

• Confusing auxiliary and target rods
• Incorrect base case condition
• Wrong print statement parameters

5. You want to solve the Tower of Hanoi problem for 4 disks but print only the moves where disk 1 is moved. Which modification to the Go recursive function below will achieve this?

func towerOfHanoi(n int, from string, to string, aux string) {
    if n == 1 {
        fmt.Printf("Move disk 1 from %s to %s\n", from, to)
        return
    }
    towerOfHanoi(n-1, from, aux, to)
    fmt.Printf("Move disk %d from %s to %s\n", n, from, to)
    towerOfHanoi(n-1, aux, to, from)
}

hard

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

B. Change base case to n == 0 and print only in recursive calls

C. Remove the print statement in the base case

D. Print only when from == "A" and to == "C"

Solution

1. Step 1: Understand when disk 1 moves are printed

   Disk 1 moves are printed only in base case when n == 1.

2. Step 2: Modify print statements to print only for disk 1

   Add an if condition around print statements to print only when n == 1, skipping other disks.

3. Final Answer:

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

4. Quick Check:

   Print only disk 1 moves = Add an if condition to print only when n == 1 inside the function [OK]

Hint: Print only when disk number is 1 inside recursion [OK]

Common Mistakes:

• Removing base case print
• Printing based on rod names instead of disk number
• Changing base case incorrectly