Kotlin Program for Tower of Hanoi Puzzle Solution

A Kotlin program for Tower of Hanoi uses a recursive function like fun towerOfHanoi(n: Int, from: String, to: String, aux: String) to move disks between rods and prints each move.

Examples

Input3 disks

OutputMove 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

Input1 disk

OutputMove disk 1 from A to C

Input0 disks

Output

How to Think About It

To solve Tower of Hanoi, think of moving n disks from one rod to another using a helper rod. Move n-1 disks to the helper rod first, then move the largest disk to the target rod, and finally move the n-1 disks from the helper rod to the target rod. This repeats until no disks remain to move.

Algorithm

1

If number of disks is 1, move it directly from source to target and return.

2

Otherwise, move n-1 disks from source to auxiliary rod using target as helper.

3

Move the nth disk from source to target rod.

4

Move the n-1 disks from auxiliary rod to target rod using source as helper.

Code

kotlin

fun towerOfHanoi(n: Int, from: String, to: String, aux: String) {
    if (n == 1) {
        println("Move disk 1 from $from to $to")
        return
    }
    towerOfHanoi(n - 1, from, aux, to)
    println("Move disk $n from $from to $to")
    towerOfHanoi(n - 1, aux, to, from)
}

fun main() {
    val disks = 3
    towerOfHanoi(disks, "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

Dry Run

Let's trace the Tower of Hanoi solution for 3 disks moving from rod A to rod C using rod B as auxiliary.

1

Move 2 disks from A to B using C

Calls towerOfHanoi(2, A, B, C)

2

Move 1 disk from A to C using B

Prints: Move disk 1 from A to C

3

Move disk 2 from A to B

Prints: Move disk 2 from A to B

4

Move 1 disk from C to B using A

Prints: Move disk 1 from C to B

5

Move disk 3 from A to C

Prints: Move disk 3 from A to C

6

Move 2 disks from B to C using A

Calls towerOfHanoi(2, B, C, A)

7

Move 1 disk from B to A using C

Prints: Move disk 1 from B to A

8

Move disk 2 from B to C

Prints: Move disk 2 from B to C

9

Move 1 disk from A to C using B

Prints: Move disk 1 from A to C

Step	Action
1	Move 2 disks from A to B using C
2	Move disk 1 from A to C
3	Move disk 2 from A to B
4	Move disk 1 from C to B
5	Move disk 3 from A to C
6	Move 2 disks from B to C using A
7	Move disk 1 from B to A
8	Move disk 2 from B to C
9	Move disk 1 from A to C

Why This Works

Step 1: Base case moves one disk

When only one disk remains, the function moves it directly from the source rod to the target rod using println.

Step 2: Recursive call moves n-1 disks

The function calls itself to move the top n-1 disks to the auxiliary rod, freeing the largest disk to move.

Step 3: Move largest disk

After moving n-1 disks, the largest disk is moved from source to target rod.

Step 4: Move n-1 disks to target

Finally, the function moves the n-1 disks from auxiliary rod to target rod, completing the puzzle.

Alternative Approaches

Iterative approach using stack

kotlin

fun towerOfHanoiIterative(n: Int, from: String, to: String, aux: String) {
    val totalMoves = (1 shl n) - 1
    val rods = mapOf('A' to from, 'B' to aux, 'C' to to)
    for (i in 1..totalMoves) {
        val fromRod = rods[((i and (i - 1)) % 3) + 'A'.code.toChar()] ?: ""
        val toRod = rods[(((i or (i - 1)) + 1) % 3) + 'A'.code.toChar()] ?: ""
        println("Move disk from $fromRod to $toRod")
    }
}

fun main() {
    towerOfHanoiIterative(3, "A", "C", "B")
}

This method uses bitwise operations and loops but is less intuitive and harder to understand than recursion.

Using data classes to represent rods and disks

kotlin

data class Rod(val name: String, val disks: MutableList<Int> = mutableListOf())

fun moveDisk(from: Rod, to: Rod) {
    val disk = from.disks.removeAt(from.disks.size - 1)
    to.disks.add(disk)
    println("Move disk $disk from ${from.name} to ${to.name}")
}

fun towerOfHanoi(n: Int, from: Rod, to: Rod, aux: Rod) {
    if (n == 1) {
        moveDisk(from, to)
        return
    }
    towerOfHanoi(n - 1, from, aux, to)
    moveDisk(from, to)
    towerOfHanoi(n - 1, aux, to, from)
}

fun main() {
    val n = 3
    val rodA = Rod("A", MutableList(n) { n - it })
    val rodB = Rod("B")
    val rodC = Rod("C")
    towerOfHanoi(n, rodA, rodC, rodB)
}

This approach models rods and disks explicitly, making the code more object-oriented but slightly longer.

Complexity: O(2^n) time, O(n) space

Time Complexity

The function makes two recursive calls for n-1 disks plus one move, resulting in 2^n - 1 moves, so time complexity is exponential O(2^n).

Space Complexity

The recursion stack depth is n, so space complexity is O(n) due to call stack usage.

Which Approach is Fastest?

Recursive approach is simplest and most intuitive; iterative methods exist but are more complex and not faster in big-O terms.

Approach	Time	Space	Best For
Recursive	O(2^n)	O(n)	Simplicity and clarity
Iterative with stack	O(2^n)	O(n)	Avoiding recursion but more complex
Object-oriented with data classes	O(2^n)	O(n)	Clear modeling of rods and disks