Towers of Hanoi from a Random Start

There’s a well-known problem called the Towers of Hanoi, in which n disks, all different sizes, are placed onto three rods to form towers. The goal is to move between various configurations while following two rules.

1. You may only move one disk at a time, and must place that disk onto a tower before you can pick up a new one.
2. You may never place a larger disk on top of a smaller disk.

The famous version of this problem starts with all the disks on the first tower, and then asks you to move them all to the last tower. How many moves are required? It’s a famous example of recursion (if you’re a computer programmer) or induction (if you’re a mathematician). The key realization is that at some point, you must move the largest ring to the final tower, and to do this, the entire stack of n - 1 disks must reside on the middle tower. Since the location of the largest disk doesn’t affect your ability to move smaller disks, this sub-problem is identical to the original problem, but with one fewer disk. To solve the problem for n disks, then, you simply solve an identical problem for n - 1 disks, take one move to move the largest disk over, and then solve the n - 1 problem again. Conclusion: solving the classic problem requires one fewer move than the nth power of 2.

But we can ask more questions than this. Lately, I’ve been pondering the case where, instead of starting with all disks in the first tower, we start with some arbitrary starting configuration. What can we say about this problem?

One might first wonder how many legal configurations there are in the first place. This isn’t a difficult question, because the only choice you have is which disks are part of which towers. The order of the disks in that tower is completely determined by the rules. So the number of legal configurations is equal to the nth power of 3. You can compare this to the solution to the classic problem, which (including the start and finish) goes through a number of configurations equal to the nth power of 2. So with one disk, you go through 2 of the 3 configurations in the course of solving the problem. But with more disks, there are more and more unreached configurations, and the number grows exponentially. There’s a lot of space here for interesting things to happen.

We can build an algorithm for solving such an arbitrary instance of the Towers of Hanoi.

1. If the largest disk is already on the right tower, ignore it and start these instructions over considering only the smaller disks.
2. Run this same algorithm to move the smaller disks to the auxiliary tower.
3. Move the largest disk to the target tower.
4. Run this same algorithm to move the smaller disks to the target tower.

A little thought should show you that all of these moves are necessary, since you can’t move the largest disk if there are any smaller disks on either the pole you move it from or the pole you move it to. This looks much like the algorithm for solving the classic problem, except for step 1. In some cases a disk may already be in the location you want to move it to. In that case, there’s no need to move it. Indeed, this algorithm proves that the classic problem is a worst-case scenario, because in the classic problem, step 1 will never apply, so you can never skip steps.

The Haskell code for this is pretty simple:

solve = go 3
  where
    go _ [] = []
    go i (n : ns)
      | n /= i = clear ++ [(1, i)] ++ stack
      | otherwise = first (+ 1) <$> go i ns
      where
        aux = 6 - n - i
        clear = first (+ 1) <$> go aux ns
        stack = first (+ 1) <$> go i ((const aux) <$> ns)

Having a computational implementation of a solver, we can start to ask more problems. For example, how many moves does it take, on average, to solve a problem chosen uniformly from all possible configurations. The answer is surprisingly clean: exactly 2/3 of the moves it takes to solve the classic problem. Is that surprising? A little at first… but not really, since there’s a 2/3 chance that each disk would need to be moved onto the target tower.

That’s all I have. My point here, I think, is that the Towers of Hanoi, despite being very well known, presents some additional questions beyond just those you’ll typically see. Many other math puzzles behave similarly, and it’s always a good idea to ask yourself is you see any other interesting phenomena worth investigating.