Tower of Hanoi Problem in DSA Go

Mental Model

Move disks one by one from one peg to another, never placing a bigger disk on a smaller one.

Analogy: Imagine moving a stack of different sized plates from one table to another using a third empty table, moving only one plate at a time and never putting a bigger plate on a smaller plate.

Peg A: [3, 2, 1]
Peg B: []
Peg C: []
(Disks are stacked with 3 at bottom, 1 at top)

Dry Run Walkthrough

Input: 3 disks on Peg A, move all to Peg C using Peg B

Goal: Move all disks from Peg A to Peg C following the rules

Step 1: Move disk 1 from Peg A to Peg C

Peg A: [3, 2]
Peg B: []
Peg C: [1]

Why: Smallest disk moves first to free up bigger disks

Step 2: Move disk 2 from Peg A to Peg B

Peg A: [3]
Peg B: [2]
Peg C: [1]

Why: Move next bigger disk to free the largest disk

Step 3: Move disk 1 from Peg C to Peg B

Peg A: [3]
Peg B: [2, 1]
Peg C: []

Why: Place smallest disk on top of disk 2 on Peg B

Step 4: Move disk 3 from Peg A to Peg C

Peg A: []
Peg B: [2, 1]
Peg C: [3]

Why: Move largest disk to target peg

Step 5: Move disk 1 from Peg B to Peg A

Peg A: [1]
Peg B: [2]
Peg C: [3]

Why: Free disk 2 to move to Peg C

Step 6: Move disk 2 from Peg B to Peg C

Peg A: [1]
Peg B: []
Peg C: [3, 2]

Why: Move disk 2 on top of largest disk on Peg C

Step 7: Move disk 1 from Peg A to Peg C

Peg A: []
Peg B: []
Peg C: [3, 2, 1]

Why: Place smallest disk on top to complete the stack

Result:

Peg A: []
Peg B: []
Peg C: [3, 2, 1]
All disks moved to Peg C in correct order

Annotated Code

DSA Go

package main

import "fmt"

type Peg string

func towerOfHanoi(n int, from Peg, to Peg, aux Peg) {
    if n == 0 {
        return
    }
    towerOfHanoi(n-1, from, aux, to) // move n-1 disks to auxiliary peg
    fmt.Printf("Move disk %d from %s to %s\n", n, from, to) // move nth disk to target peg
    towerOfHanoi(n-1, aux, to, from) // move n-1 disks from auxiliary to target peg
}

func main() {
    disks := 3
    towerOfHanoi(disks, Peg("Peg A"), Peg("Peg C"), Peg("Peg B"))
}

if n == 0 { return }

stop recursion when no disks to move

towerOfHanoi(n-1, from, aux, to)

move top n-1 disks to auxiliary peg

fmt.Printf("Move disk %d from %s to %s\n", n, from, to)

move the largest disk to target peg

towerOfHanoi(n-1, aux, to, from)

move n-1 disks from auxiliary peg to target peg

Output

Move disk 1 from Peg A to Peg C

Move disk 2 from Peg A to Peg B

Move disk 1 from Peg C to Peg B

Move disk 3 from Peg A to Peg C

Move disk 1 from Peg B to Peg A

Move disk 2 from Peg B to Peg C

Move disk 1 from Peg A to Peg C

Complexity Analysis

Time: O(2^n) because each disk move doubles the number of moves needed

Space: O(n) due to recursion stack depth equal to number of disks

vs Alternative: No simpler approach exists; this is the minimal number of moves required

Edge Cases

0 disks

No moves are made, function returns immediately

DSA Go

if n == 0 {
        return
    }

1 disk

Single move from source to target peg

DSA Go

towerOfHanoi(n-1, from, aux, to)

When to Use This Pattern

When you see a problem about moving stacked items with size constraints and recursive moves, reach for the Tower of Hanoi pattern because it solves the minimal move sequence elegantly.

Common Mistakes

Mistake: Trying to move multiple disks at once violating the size rule
Fix: Always move only one disk at a time and never place a bigger disk on a smaller one

Mistake: Not using recursion to break down the problem into smaller subproblems
Fix: Use recursion to move n-1 disks before and after moving the largest disk

Summary

It solves the problem of moving disks between pegs following size rules using recursion.

Use it when you need to move stacked items with constraints on order and size.

The key insight is to move smaller stacks out of the way recursively to free the largest disk.

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