Explain the methods used to solve the Tower of Hanoi problem.

The Tower of Hanoi is a classic mathematical puzzle consisting of three pegs and a set of disks of different sizes. The objective of the puzzle is to move the entire stack of disks from one peg (the source peg) to another peg (the target peg), while following these rules:

Only one disk can be moved at a time.
Each move consists of taking the top disk from one of the pegs and placing it on top of another peg.
No disk may be placed on top of a smaller disk.

The initial configuration has all the disks stacked in decreasing order of size on one peg. The challenge is to move this entire stack to another peg by using the destination peg as an intermediate step if necessary.

There are two methods to solve this problem which are as follows:

Iterative approach
Recursive approach

Iterative approach

The iterative approach to solving the Tower of Hanoi problem involves simulating the recursive steps of the algorithm using an iterative loop and a stack data structure.

Here’s a step-by-step explanation of the iterative approach:

Create an empty stack to store the disk movement states.
Push the initial movement state onto the stack. This state represents the movement of all disks from the source peg to the target peg using the auxiliary peg.
While the stack is not empty, do the following:
- Pop a movement state from the stack.
- If the number of disks in the movement state is 1, directly move the disk from the source peg to the target peg.
- If the number of disks is greater than 1, push three subproblems onto the stack in reverse order:
  - Moving n-1 disks from the auxiliary peg to the target peg using the source peg as the auxiliary. Moving the largest disk from the source peg to the target peg.
  - Moving n-1 disks from the source peg to the auxiliary peg using the target peg as the auxiliary.
Repeat steps 3 until the stack is empty.

The iterative approach essentially emulates the recursive steps of the Tower of Hanoi algorithm by using a stack to keep track of the states of each movement. Instead of making recursive function calls, the algorithm pushes subproblems onto the stack and processes them iteratively.

By following this iterative approach, the Tower of Hanoi problem can be solved efficiently without relying on explicit recursion.

The following code will help us better understand this iterative method.

class DiskMove:
    def __init__(self, n, source, target, auxiliary):
        self.n = n  # Number of disks to be moved
        self.source = source  # Source peg
        self.target = target  # Target peg
        self.auxiliary = auxiliary  # Auxiliary peg
def iterativeHanoi(n, source, target, auxiliary):
    stack = []  # Stack to store disk movement states
    stack.append(DiskMove(n, source, target, auxiliary))
    while stack:
        move = stack.pop()
        if move.n == 1:
            print(f"Move disk 1 from {move.source} to {move.target}")
        else:
            # Push the subproblems onto the stack in reverse order
            stack.append(DiskMove(move.n - 1, move.auxiliary, move.target, move.source))
            stack.append(DiskMove(1, move.source, move.target, move.auxiliary))
            stack.append(DiskMove(move.n - 1, move.source, move.auxiliary, move.target))
# Example usage:
n = 3  # Number of disks
source = "A"  # Source peg
target = "C"  # Target peg
auxiliary = "B"  # Auxiliary peg
iterativeHanoi(n, source, target, auxiliary)

Code explanation

Lines 1–6: These lines of code define a class called DiskMove with an initializer method that sets the number of disks (n) to be moved and the source, target, and auxiliary pegs (source, target, auxiliary) as instance variables.
Lines 8–20: These lines of code implement an iterative solution for the Tower of Hanoi problem. It uses a stack to store disk movement states, pops a state from the stack, and performs the necessary movements based on the number of disks (n) and the source, target, and auxiliary pegs. It pushes subproblems onto the stack in reverse order to ensure the correct order of movements.

Recursive approach

The recursive approach to solving the Tower of Hanoi problem involves breaking down the problem into smaller subproblems. Here’s a step-by-step explanation of the recursive algorithm:

Base case: If there is only one disk to be moved, simply move it from the source peg to the target peg.
Recursive case: If there are more than one disk, follow these steps:
- Move n-1 disks from the source peg to the auxiliary peg, using the target peg as the temporary peg.
- Move the remaining largest disk from the source peg to the target peg.
- Move the n-1 disks from the auxiliary peg to the target peg, using the source peg as the temporary peg. This recursive process continues until all the disks are moved from the source peg to the target peg, following the rules of the Tower of Hanoi puzzle.

The recursive solution is concise and elegant as it relies on the recursive nature of the problem.

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

You TubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources