The problem

The Tower of Hanoi, is the name of a puzzle invented by the french mathematician Édouard Lucas in 1883. We will solve it in code and using recursion.

It’s played like this: imagine we have three towers and want to move a pile of discs stacked from top to bottom smallest to largest, from one tower to another. The catch is that:

• We can only move one disc at a time.
• A larger disc can not cover a smaller disc.

We want to represent our solution in code by outputting an array of tupples of each of the moves that we make.

An algorithm to solve the puzzle

Moving a pile of just one or two discs is straight forward. However, we observe that moving 3 or more discs requires a lot of moves and is not a random affair.

Moving 3 discs:

[('a','b'),('a','c'),('b','c'),('a','b'),('c','a'),('c','b'),('a','b')]

And 4 discs is still more involved:

[('a','c'),('a','b'),('c','b'),('a','c'),('b','a'),('b','c'),('a','c'),('a','b'),('c','b'),('c','a'),('b','a'),('c','b'),('a','c'),('a','b'),('c','b')]

Yet, there is a pattern, and it’s mostly recursive. We will use this algorithm:

1. Move n - 1 discs from a to c
2. Move 1 disc for a to b
3. Move n - 1 discs from c to b

Starting to code

The word Tower adds semantic meaning. Perhaps most useful where we have multiple uses of Char for different types of things, which is actually not the case here.

type Tower = Char
type Move = (Tower, Tower)

Having a type signature makes it very clear what data we take in and what we produce, and is generally very helpful.

hanoi :: Integer -> Tower -> Tower -> Tower -> [Move]

Base case/s

We always use base cases to end the recursion. And here we return not just a data structure but some values as well.

hanoi 0 _ _ _ =  []
hanoi 1 a b _ =  [(a, b)]

Recursive cases

As per our algorithm, we have three different types of call. The first is recursive. The second just calls the base case directly and the third is again recursive.

hanoi n a b c =
  let nMinusOne = (n - 1)
    in
    hanoi nMinusOne a c b ++ -- algorithm case 1
    hanoi 1 a b c ++         -- algorithm case 2
    hanoi nMinusOne c b a    -- algorithm case 3

Let’s look inside each of the calls. Starting with a function call having 3 discs.

hanoi 3 'a' 'b' 'c'

hanoi nMinusOne a c b

• We don’t return any values for the first recursion but we do set nMinusOne to 2.

With hanoi 2 'a' 'c' 'b'

• We have changed the order of our arguments/ towers.

• We set nMinusOne to 1. Now we can a producing values using our base case, like so:

• hanoi 1 a c b produces [(‘a’, ‘b’)]

• hanoi 1 a b c produces [(‘a’, ‘c’)]

• hanoi 1 c b a produces [(‘b’, ‘c’)]

hanoi 1 a b c

Note that this happens within the same function call, so here there is no recursion. It’s just a base case returning values.

1. hanoi 1 a b c ++ produces [(‘a’, ‘b’]

hanoi nMinusOne c b a

Now we recur again with n still being 2. I think that is because nMinusOne is lexically scoped at the a, so it will always be 2 however many discs we might have.

The arguments now are: ‘c’ ‘b’ ‘a’.

1. hanoi 1 a c b produces [(‘c’, ‘a’)]
2. hanoi 1 a b c produces [(‘c’, ‘b’)]
3. hanoi 1 c b a produces [(‘a’, ‘b’)]

And our final result

Our final result is the concatenation, using ++ of each of the arrays that we produced from our three calls.

λ> hanoi 3 'a' 'b' 'c'

[('a','b'),('a','c'),('b','c'),('a','b'),('c','a'),('c','b'),('a','b')]

Of course, we could also call hanoi 4 'a' 'b' 'c', or hanoi 5 'a' 'b' 'c' etc.

References

I was looking at:

• https://ocw.mit.edu/courses/6-0001-introduction-to-computer-science-and-programming-in-python-fall-2016/resources/lecture-6-recursion-and-dictionaries/ and https://enocom.dev/blog/solving-the-towers-of-hanoi-with-haskell