In this tutorial, we will learn how to solve the Tower of Hanoi problem using recursion in Swift. We will understand the problem, the rules of the Tower of Hanoi, write an algorithm, and implement it step by step with a complete Swift program and output.

What is the Tower of Hanoi Problem?

The Tower of Hanoi is a mathematical puzzle that consists of three rods and a number of disks of different sizes. The objective is to move all the disks from the source rod to the destination rod using an auxiliary rod, following these rules:

  • Only one disk can be moved at a time.
  • A disk can only be moved if it is the topmost disk on a rod.
  • No larger disk can be placed on top of a smaller disk.

The problem can be solved using recursion by breaking it into smaller subproblems.

Algorithm to Solve Tower of Hanoi

  1. Move n-1 disks from the source rod to the auxiliary rod.
  2. Move the nth (largest) disk from the source rod to the destination rod.
  3. Move the n-1 disks from the auxiliary rod to the destination rod.

This algorithm repeats recursively until there is only one disk to move. For a single disk, the move is direct from the source to the destination.

Step-by-Step Implementation in Swift

1. Define the Recursive Function

Create a recursive function towerOfHanoi that takes the number of disks, and the names of the source, destination, and auxiliary rods as parameters:

</>
Copy
func towerOfHanoi(_ n: Int, _ source: String, _ destination: String, _ auxiliary: String) {
    if n == 1 {
        print("Move disk 1 from \(source) to \(destination)")
        return
    }
    // Placeholder for recursive steps
}

2. Implement the Recursive Logic

Add the logic to move n-1 disks recursively, move the nth disk, and then move n-1 disks from the auxiliary rod to the destination rod:

</>
Copy
func towerOfHanoi(_ n: Int, _ source: String, _ destination: String, _ auxiliary: String) {
    if n == 1 {
        print("Move disk 1 from \(source) to \(destination)")
        return
    }
    // Move n-1 disks from source to auxiliary
    towerOfHanoi(n - 1, source, auxiliary, destination)
    // Move the nth disk from source to destination
    print("Move disk \(n) from \(source) to \(destination)")
    // Move n-1 disks from auxiliary to destination
    towerOfHanoi(n - 1, auxiliary, destination, source)
}

Explanation:

  • if n == 1: Base case that directly moves the smallest disk.
  • towerOfHanoi(n - 1, source, auxiliary, destination): Moves the top n-1 disks to the auxiliary rod.
  • print: Moves the nth (largest) disk directly to the destination rod.
  • towerOfHanoi(n - 1, auxiliary, destination, source): Moves the n-1 disks from the auxiliary rod to the destination rod.

3. Test the Function

Let’s test the function with 3 disks:

</>
Copy
// Test case: Tower of Hanoi with 3 disks
towerOfHanoi(3, "A", "C", "B")

Complete Swift Program for Tower of Hanoi

Here’s the complete Swift program for Tower of Hanoi problem:

main.swift

</>
Copy
import Foundation

// Recursive function to solve Tower of Hanoi
func towerOfHanoi(_ n: Int, _ source: String, _ destination: String, _ auxiliary: String) {
    if n == 1 {
        print("Move disk 1 from \(source) to \(destination)")
        return
    }
    // Move n-1 disks from source to auxiliary
    towerOfHanoi(n - 1, source, auxiliary, destination)
    // Move the nth disk from source to destination
    print("Move disk \(n) from \(source) to \(destination)")
    // Move n-1 disks from auxiliary to destination
    towerOfHanoi(n - 1, auxiliary, destination, source)
}

// Test case: Tower of Hanoi with 3 disks
towerOfHanoi(3, "A", "C", "B")

Output:

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

Xcode Screenshot

Swift Program for Tower of Hanoi Problem