Towers of Hanoi, Made Simple and Easy (3 pegs version)

‘Towers of Hanoi’ is often given as an exercise to better understand recursion, I first came across this exercise a few years back, I tried to solve it, spent the majority of a day on it, and failed completely. I then copy-pasted a solution from Stackoverflow, after I looked it over a couple of times, and convinced myself that I understood it, but in my heart-of-hearts I knew that I didn’t.

Fast-forward a couple of years, and I am in this program, part of their curriculum involves algorithm challenges, and that’s where I met my nemesis again, the dreaded ‘Towers of Hanoi’ challenge, but this time I was determined to fully understand it, as it turns out, it’s surprisingly easy.

The algorithms that I am going to be showing you runs in a time complexity of O(2^n), I wasn’t able to find a better implementation, and I am not sure that it is mathematically possible to get a better result, in terms of time complexity. Here I will be using Ruby to solve the challenge, but the method is valid for any other language.

Tower of Hanoi is a puzzle where we have three rods and a number (n) of disks. The objective of the puzzle is to move the entire stack of disks from the first rod (A) to the third rod (C)

Obeying the following simple rules:

1. Only one disk can be moved at a time.

2. A disk can only be moved if it is the uppermost disk on that rod.

3. Bigger disks may not be placed on top of smaller ones.

Let’s start extremely simple, with one disk to move, obviously if we have one disk, we just move it from A -> C, this would look like this:

And in code it would look like this:

def moveOneDisk(starting, goal)
    puts "#{starting}->#{goal}"
end
moveOneDisk("A","C")

*note: the “puts” command in Ruby is just to output to the console, so here we are just outputting “A -> C”

Ok, let’s go to the next step, what if we wanted to move 2 disk, well it is still very simple, we just:

1) Move the first disk out of the way, A -> B.

2) Move the second disk to the third rod, which is where we want it to be,

A -> C.

3) Finally we move the first disk back on top of the second one, B -> C.

And in code it would look like this:

def moveOneDisk(starting, goal)
    puts "#{starting}->#{goal}"
end
def moveTwoDisks(starting,goal,remaining)
    moveOneDisk(starting,remaining)
    moveOneDisk(starting,goal)
    moveOneDisk(remaining,goal)
end

moveTwoDisks("A","C","B")

The above code would output:

A -> B
A -> C
B -> C

So far so good, well let’s get just a tiny little bit more complex, what if we had 9 disk and we wanted to move them from rod A to rod C. Well believe it or not, we do the exact same thing that we did for the 2 disks, we just:

1) Move everything else except for the last disk out of the way, A -> B

2) Move the 9th disk where we want it to go, A -> C

3) Move everything else back on top of the 9th disk, B -> C

Now you might be thinking to yourself something along the lines of, “Hey I feel like you might have missed a couple of steps, and it also looks like you don’t understand the challenge at all, what happened to moving only one disk at a time?”

The thing is I didn’t miss any steps, nor did I lose my mind, let me show you what I mean, but in order to do that let’s go back to 3 disks.

The steps for moving 3 disks from rod A to rod C, are exactly the same as 9 disks, and they are exactly the same as 2 disks, we just:

1) Move everything else except for the last disk out of the way, A -> B

2) Move the 3rd disk where we want it to go, A -> C

3) Move everything else back on top of the 3rd disk, B -> C

However, the first step is a smaller problem, where our goal is to move 2 disk now, from rod A, to rod B instead of rod C, this is a very simple problem to solve, and we already know how to solve it, because we already did, so we just:

1) Move the first disk out of the way, A -> C.

2) Move the second disk to the second rod, which is where we want it to be,

A -> B.

3) Finally we move the first disk, back on top of the second one, C -> B.

Same thing goes for the 3rd step of the 3 disk problem, where we move the 2 disk back on top of the 3rd disk on rod C, we just:

1) Move the first disk out of the way, B -> A.

2) Move the second disk to the third rod, which is where we want it to be,

B -> C.

3) Finally we move the first disk, back on top of the second one, A -> C.

In code it would look like this:

def moveThreeDisks(starting,goal,remaining)
    moveTwoDisks(starting,remaining,goal)
    moveOneDisk(starting,goal)
    moveTwoDisks(remaining,goal,starting)
end
moveThreeDisks("A","C","B")

If we were to draw a diagram of the steps involved, it would look like this:

So what about the 4 disks problem, its diagram would look something like this:

And it’s code something like this:

def moveOneDisk(starting, goal)
    puts "#{starting}->#{goal}"
end
def moveTwoDisks(starting,goal,remaining)
    moveOneDisk(starting,remaining)
    moveOneDisk(starting,goal)
    moveOneDisk(remaining,goal)
end
def moveThreeDisks(starting,goal,remaining)
    moveTwoDisks(starting,remaining,goal)
    moveOneDisk(starting,goal)
    moveTwoDisks(remaining,goal,starting)
end
def move4Disks(starting,goal,remaining)
    moveThreeDisks(starting,remaining,goal)
    moveOneDisk(starting,goal)
    moveThreeDisks(remaining,goal,starting)
end
move4Disks("A","C","B")

Where the first step and last steps of the 4 disk problem, are calling the entire 3 disk problem, in order to move the 3 disks from A -> B, and then from B -> C.

The outputted result of the above code would look like this:

A->B, A->C, B->C, A->B, C->A, C->B, A->B, A->C, B->C, B->A, C->A,
B->C, A->B, A->C, B->C

Ok, all this is good, I hope you have understood the problem now, and how we solve it, there is just the last step to do. Say we go back to the previous 9 disks problem, we would need 9 functions all calling each other in order to solve this problem, what about a 100 disks? We clearly cannot just keep creating functions for each and every number of disks involved, we need a recursive function.

Our recursive function, might look something like this:

def moveOneDisk(starting, goal)
    puts "#{starting}->#{goal}"
end
def moveNDisks(number,starting,goal,remaining)
    if(number == 1) then
        moveOneDisk(starting,goal)
    else
        moveNDisks(number - 1,starting,remaining,goal)
        moveOneDisk(starting,goal)
        moveNDisks(number - 1, remaining, goal, starting)
    end
end
moveNDisks(9,"A","C","B")

In this code we keep only the “moveOneDisk” function, because it is the only step that is different from the rest, every step from 2 and above involves the same 3 steps we have done again and again.

The moveNDisks function takes in: 1)the number of disks that we have, 2)the starting, 3) goal and 4) helping/remaining rod.

If then number of disks is greater than 1, it calls itself to remove all of the disks except the last one

In this recursive call the goal and remaining are swapped, and the disk count is decreased by one, which has the same effect as calling a function of order (N-1), like in the functions that we previously had.

It then moves the very last disk to the goal road that we want.

And again calls itself recursively to move every disk on top of the last one.

Thank you for reading till the end of this very long article, I hope that it helped you understand the Towers of Hanoi problem well enough that you can implement the solution on your own.

Do spam the clap button 👏, it is a good exercise for your fingers (if you are looking to get Carpal Tunnel Syndrome).