Tower of Hanoi Problem in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Tower of Hanoi problem?

To move all disks from the source peg to the destination peg following the rules: only one disk can be moved at a time, a larger disk cannot be placed on top of a smaller disk, and only the top disk of any peg can be moved.

beginner

How many moves are required to solve the Tower of Hanoi problem with n disks?

The minimum number of moves required is 2^n - 1, where n is the number of disks.

intermediate

Explain the recursive approach to solve the Tower of Hanoi problem.

Move n-1 disks from source to auxiliary peg, move the nth (largest) disk from source to destination peg, then move the n-1 disks from auxiliary to destination peg recursively.

beginner

What are the three pegs called in the Tower of Hanoi problem?

Source peg (where disks start), Auxiliary peg (used for temporary storage), and Destination peg (where disks need to be moved).

beginner

Why can't a larger disk be placed on top of a smaller disk in Tower of Hanoi?

Because it violates the problem's rules and the physical intuition that a bigger disk cannot rest on a smaller disk without falling.

What is the base case in the recursive Tower of Hanoi solution?

A When all disks are moved

B When no disks are left on the source peg

C When there is only one disk to move

D When the auxiliary peg is empty

The base case is when there is only one disk to move, which can be moved directly from source to destination.

How many pegs are used in the Tower of Hanoi problem?

A 2

B 3

C 4

D 5

The classic Tower of Hanoi problem uses three pegs: source, auxiliary, and destination.

Which of the following is NOT a rule of the Tower of Hanoi problem?

A A larger disk can be placed on a smaller disk

B Only the top disk of a peg can be moved

C Only one disk can be moved at a time

D Disks must be moved from source to destination

A larger disk cannot be placed on a smaller disk; this is against the rules.

What is the minimum number of moves to solve Tower of Hanoi with 3 disks?

A 7

B 6

C 5

D 8

Minimum moves = 2^3 - 1 = 7.

In the recursive solution, after moving n-1 disks to auxiliary peg, what is the next step?

A Move n-1 disks to destination peg

B Move the largest disk to auxiliary peg

C Move all disks back to source peg

D Move the largest disk to destination peg

The largest disk is moved from source to destination peg after moving n-1 disks to auxiliary.

Describe the recursive steps to solve the Tower of Hanoi problem for n disks.

Think about breaking the problem into smaller parts.

Explain why the minimum number of moves for Tower of Hanoi is 2^n - 1.

Consider how moves increase as disks increase.

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