Solve Hanoi for N elements

Hanoi is a simple puzzle, you start with three rods and N disk, on the first rod. Each Disk is a different size. The biggest one is on the bottom, and they are stacked in descending size. The task of this puzzle is to move the whole tower from first rod to last one using few simple rules:
– you can move one disk at a time
– you can put a disk on an empty rod, or stack smaller onto bigger.
– Putting bigger onto smaller disk is not allowed

Lets look on sample solution for N = 3

The game get bit more challenging when we introduce more disk. Fortunately we can use dynamic programming bottom-up approach to solve any Hanoi size.

Solution for N = 1 is obvious, we just move one disk from start position to end and we are done.

N = 2 get a bit more interesting

First we moved the top(blue) element to “center” rod, then we moved the bottom(green) element to final position. The last move was to move blue disk from center rod to final position on top of green disk.

We know now how to move two disk on final rod, can we use this to solve N=3?

First we use the solution for N = 2, to move the top two elements onto temporary rod.
Next we move the third element(red) to final position.
Finally, we use solution for N=2 to move two elements from temporary rod to end rod and stack them on top of red node.

If you look on our first image for N=3 you should see that we have actually done moves {4, 5, 8}. Moves {2, 3, 4}, and {6, 7, 8} was done as a solution of N = 2.
All we have to do was to link moves by moving the third disk.

This solution will work for any N size. Steps required to solve i-th iteration :
– use solution for (i-1) to move elements from start to temporary position
– move last disk from start position to end position
– use solution for (i-1) to move elements from temporary rod to end rod

However, there is one more issue we need to look at.

Solution for N = 4

When we look at this, our N=3 is not exactly a solution for this problem. We know how to move from position 1 to position 3. This however require us to do two moves:
– move three elements from position 1 to position 2
– move three elements from position 2 to position 3

We can solve this by having three variables (start, temporary, end). Our solution should use this variable as rod index.

What will happen when we solve these two sub problems of size N=3?

Indexes for this sub-problem
start = 1
temporary = 3
end = 2

Second sub-problem

This time we have indexes:
start = 2
temporary = 1
end = 3

Move N=4 summary

Let’s define quadruple as (N, start, temporary, end).
This means if we have quadruple(8, 3, 1, 2) our current hanoi size is 8, start rod is 3, end rod is 2 and for temporary we will use rod 1.
Solving any Hanoi tower start from quadruple(N, 1, 2, 3).

Now we will define solution tree for Hanoi 4.

• Number on the left define N size of a sub-problem.
• Green – start position
• Blue – temporary rod
• red – destination rod

From this tree we can see that:
– whenever we move to the left branch, we swap end position with temporary (red with blue)
– whenever we move to the right we swap start with temporary (green with blue)

To solve (N, start, temporary, end) we are doing three steps:
– solve (N-1, start, end, temporary)
– move one disk from start to end
– solve (N-1, temporary, start, end)
We repeat it until N = 1

fun solveHanoi(
    n: Int,
    hanoi: List<ArrayDeque<Int>>,
    start: Int = 0, temp: Int = 1, dest: Int = 2
): List<ArrayDeque<Int>> {
    if (n == 0) return hanoi

    if (n == 1) {
        moveOne(hanoi, start, dest)
    }

    if (n > 1) {
        solveHanoi(n - 1, hanoi, start, dest, temp)
        moveOne(hanoi, start, dest)
        solveHanoi(n - 1, hanoi, temp, start, dest)
    }

    return hanoi
}

And method that move one element, and also validate if there is no invalid move (larger element on smaller)

fun moveOne(
    hanoi: List<ArrayDeque<Int>>, 
    i: Int, j: Int
) {
    if (hanoi[i].isEmpty()) return
    val v = hanoi[i].removeFirst()
    if (hanoi[j].isNotEmpty() && hanoi[j].first() < v) {
        throw RuntimeException("Invalid move: $i -> $j")
    } else {
        hanoi[j].add(0, v)
    }
}

This method generate Hanoi for selected N:

fun genHanoi(n: Int): List<ArrayDeque<Int>> {
    val towers = listOf(
        ArrayDeque<Int>(),
        ArrayDeque<Int>(),
        ArrayDeque<Int>()
    )
    for (i in 1..n) {
        towers[0].add(i)
    }
    return towers
}

Finally main method:

fun main() {
    val n = 30
    val hanoi = genHanoi(n)
    val result = solveHanoi(n, hanoi)

    while (result[2].isNotEmpty()) {
        println(result[2].removeFirst())
    }
}