One of the first challenges in the course Introduction to Haskell is to solve the Towers of Hanoi puzzle. Aside from appearing in interviews now and then, the Towers of Hanoi puzzle is a classic problem that might seem intimidating at first glance, but is actually straightforward with some careful thought. Let's walk through the solution generally and then implement it using Haskell.
For those who might not be familiar with the puzzle, it's worth playing a basic version first to familiarize yourself. In short, we have three "towers," or "pegs." On the first peg are three discs of increasing size with the smallest on top and the largest on the bottom. Solving the puzzle requires that one move all three discs to the third peg, moving one at a time while never placing a larger disc on top of a smaller disc.
While the course's statement (PDF) of the problem includes a written version of the algorithm, it's easy enough to derive by thinking in particular about two cases: 1) moving only two discs, and 2) moving three discs.
Suppose we start with only two discs, one small and one large, on the first peg. To move both discs to the second peg, we must first move the small disc to the third peg, then move the large disc to the second peg, and then finally move the small disc to the second peg on top of the large disc. If we labeled each peg in order as A, B, and C and define a move as a tuple of start and end, then we might describe the movements as follows:
-- take the top of peg "A" (the small disc) and move it to the last peg, "C"
(A, C)
-- move the large disc from peg "A" to peg "B"
(A, B)
-- finally, move the smaller disc from "C" to "B"
(C, B)
Before we talk about moving three discs, let's take what we've learned about two discs and begin writing our function. In the problem statement, we're provided with a couple of basic types as well as the expected type signature:
type Peg = String
type Move = (Peg, Peg)
hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]
Our hanoi function will accept the number of discs, and three Peg types, which are simply strings representing the pegs, and will return a list of Move types, which are two-member tuples of strings. Each Move type is simply a starting peg and an ending peg.
Using Peg and Move, here's what our function looks like for two discs:
hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]
hanoi 2 start end temp = [(start, temp), (start, end), (temp, end)]
The hanoi function accepts a starting peg start, a destination peg end, as well as a temporary peg temp which acts as a holding area for in-transit pegs. The pattern of two discs represents our base case. Naturally, we should include patterns for zero and one disc, as well:
hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]
hanoi 0 _ _ _ = []
hanoi 1 start end _ = [(start, end)]
hanoi 2 start end temp = [(start, temp), (start, end), (temp, end)]
Now that we have a working function for two or less discs, let's return to think about the remaining case of how we might move three (or more) discs.
Imagine we have three discs on peg A. To move those three discs to peg B, we would first have to move the upper two discs out of the way using the temporary peg C. Then, we would move the biggest disc from peg A to peg B. Finally, we would move the two discs from peg C to peg B, to be on top of the biggest disc.
Moving one disc is easy enough and we've already gone over how to move two discs above. The trick here is to realize two things. First, moving any number of discs amounts to moving all the discs on top of the biggest disc out of the way, moving the biggest disc to its destination, and then moving all the other discs back on top of the biggest disc. Second, in the process of moving discs from one peg to another, we sometimes treat one peg as a temporary peg and other times treat it as a destination peg.
Let's talk through an example of moving three pegs to make this a little more clear. Peg A starts with three discs, let's call them x, y, and z, understanding that x is the biggest disc, y the second biggest, and z the smallest. First, we need to move y and z out of the way, to peg C. So in this case, peg A is the starting point, peg B is our temporary holding space, and peg C is the destination for our two discs. So we put z on to peg B, move y to peg C, and then move z on top of y on peg C. At this point, we have to move the biggest disc x from peg A to peg B, which is easy. Now that x is in the correct place, we need to move y and z on top of it. This time, we treat peg A as a temporary holding peg and move z on to peg A so that we can move y on top of x on peg B. And finally, we move z on top of y on peg B, having completed the entire move.
Now that we have reviewed a couple of examples step by step, it's probably clear that we're dealing with a recursive function here. The basic idea is that moving any number of discs amounts to moving all the discs on top of the bottom disc out of way, moving the bottom disc, and then moving all those other discs back on top of it. In other words, to move n discs, we first have to move n-1 discs out of the way, move the nth disc to its destination, and then move n-1 discs back on top of that nth disc. In terms of Haskell, the algorithm might look like this:
hanoi n start end temp =
let nMinusOne = subtract 1 n
in hanoi nMinusOne start temp end ++
hanoi 1 start end temp ++
hanoi nMinusOne temp end start
The first line of the function body, i.e., hanoi nMinusOne start temp end, moves n-1 discs to the temporary holding space. The line after moves the largest disc to its destination. And finally, the last line, moves n-1 discs from the temporary peg to the destination as well.
Putting all the pieces together, our full function looks like this:
hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]
hanoi 0 _ _ _ = []
hanoi 1 start end _ = [(start, end)]
hanoi n start end temp =
let nMinusOne = subtract 1 n
in hanoi nMinusOne start temp end ++
hanoi 1 start end temp ++
hanoi nMinusOne temp end start
That's it. We have a solution to the Towers of Hanoi problem. Note that the recursive solution covers the case of two discs, and so I have removed that unnecessary line.