Tower of Hanoi Problem in DSA Go - Execution Trace

Concept Flow - Tower of Hanoi Problem

Start with all disks on Source

↓

Move top n-1 disks from Source to Auxiliary

↓

Move largest disk from Source to Destination

↓

Move n-1 disks from Auxiliary to Destination

↓

All disks moved to Destination in order

↓

End

The problem moves disks step-by-step: first move smaller disks to auxiliary, then largest disk to destination, then smaller disks from auxiliary to destination.

Execution Sample

DSA Go

package main

import "fmt"

func TowerOfHanoi(n int, source, auxiliary, destination string) {
    if n == 1 {
        fmt.Println("Move disk 1 from", source, "to", destination)
        return
    }
    TowerOfHanoi(n-1, source, destination, auxiliary)
    fmt.Println("Move disk", n, "from", source, "to", destination)
    TowerOfHanoi(n-1, auxiliary, source, destination)
}

func main() {
    TowerOfHanoi(3, "Source", "Auxiliary", "Destination")
}

This recursive function prints the steps to move n disks from source to destination using auxiliary.

Execution Table

Step	Operation	Disks Moved	From Peg	To Peg	Visual State
1	Move disk 1	1	Source	Destination	Source: [3,2] Auxiliary: [] Destination: [1]
2	Move disk 2	2	Source	Auxiliary	Source: [3] Auxiliary: [2] Destination: [1]
3	Move disk 1	1	Destination	Auxiliary	Source: [3] Auxiliary: [2,1] Destination: []
4	Move disk 3	3	Source	Destination	Source: [] Auxiliary: [2,1] Destination: [3]
5	Move disk 1	1	Auxiliary	Source	Source: [1] Auxiliary: [2] Destination: [3]
6	Move disk 2	2	Auxiliary	Destination	Source: [1] Auxiliary: [] Destination: [3,2]
7	Move disk 1	1	Source	Destination	Source: [] Auxiliary: [] Destination: [3,2,1]
8	End	-	-	-	All disks moved to Destination in order

💡 All disks moved from Source to Destination following Tower of Hanoi rules

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
Source Peg	[3,2,1]	[3,2]	[3]	[3]	[]	[1]	[1]	[]	[]
Auxiliary Peg	[]	[]	[2]	[2,1]	[2,1]	[2]	[]	[]	[]
Destination Peg	[]	[1]	[1]	[]	[3]	[3]	[3,2]	[3,2,1]	[3,2,1]

Key Moments - 3 Insights

Why do we move n-1 disks to the auxiliary peg before moving the largest disk?

Because the largest disk cannot be placed on a smaller disk, we first clear the way by moving smaller disks (n-1) to the auxiliary peg as shown in steps 1 to 3 in the execution_table.

Why do we move disks back and forth between pegs instead of directly moving all disks to the destination?

The rules allow only one disk moved at a time and no larger disk on smaller disk. So we use the auxiliary peg as temporary storage to rearrange disks safely, as seen in steps 5 and 6.

How do we know when the problem is solved?

When all disks are stacked in order on the destination peg, which is shown in the final visual state after step 7 in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the state of the Auxiliary peg after Step 3?

A [2]

B []

C [2,1]

D [1]

💡 Hint

Check the 'Visual State' column in row for Step 3 in execution_table.

At which step is the largest disk moved from Source to Destination?

A Step 3

B Step 4

C Step 5

D Step 7

💡 Hint

Look at the 'Operation' and 'Disks Moved' columns in execution_table.

If we had 2 disks instead of 3, how many steps would the execution_table show before 'End'?

A 3

B 5

C 7

D 1

💡 Hint

Recall the recursive pattern and number of moves for n disks is 2^n - 1.

Concept Snapshot

Tower of Hanoi moves n disks from Source to Destination using Auxiliary.
Rules: move one disk at a time, no larger disk on smaller disk.
Recursive steps:
1) Move n-1 disks Source->Auxiliary
2) Move largest disk Source->Destination
3) Move n-1 disks Auxiliary->Destination
Total moves = 2^n - 1.

Full Transcript

The Tower of Hanoi problem moves disks from one peg to another with rules that only one disk moves at a time and no larger disk can be placed on a smaller disk. The process uses recursion: first move n-1 disks to auxiliary peg, then move the largest disk to destination, then move n-1 disks from auxiliary to destination. The execution table shows each move step-by-step with the state of all pegs. The variable tracker shows how the disks on each peg change after every move. Key moments clarify why we move smaller disks first and how we know the problem is solved. The visual quiz tests understanding of peg states and move counts. The snapshot summarizes the recursive solution and rules.

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