Tower of Hanoi Variations

A long, long time ago (1993) I spent a few weeks at a summer residential governor’s school, hosted by the college of William and Mary.  I remember only fragments of that time:  Playing capture-the-flag across the campus.  Some kind of fancy asteroids game.  Recording professors' answering machine messages and editing them to make them say funny things.

During one programming class, I remember the professor describing a linear congruential generator for pseudorandom numbers.  I thought to myself, "That can't be the best way, I came up with that on my own at home."  Then, being young, I said that out loud.  I think the professor said something to the effect of "Yes, you're very smart, now shut up."

I also remember helping to solve a variation of the Tower of Hanoi, and getting my name in a published paper.

You should already know what the Tower of Hanoi puzzle is.  If not, you know how to use Google: I'm not going to describe it to you here.

You probably didn't need a diagram for how to swap something.

This variation was pretty simple: As in the classic puzzle you can move the smallest disk to any other peg.  But the other disks can only be moved by swapping them with the next-smallest disk (and only when the two swapped disks are at the tops of their stacks).  This variation was introduced in 1944, and as far as Professor Stockmeyer could determine no algorithmic solution had been published (and he has looked around pretty thoroughly).  You can try it out at this demo site I made, by choosing the variation called "Swapping".

I hadn't thought about this for years, and then I go and watch two 3blue1brown videos about the Tower (part 1 and part 2) and the whole thing comes trickling back.

We were given a challenge: if we could produce a correct algorithm to solve this variation, then the professor would put our names on the paper he was going to publish.  It wasn't easy, but after some days we managed to find the solution.  The rest, as they say, is in the International Journal of Computer Mathematics.

Classic Tower of Hanoi solution

The classic Tower has a simple recursive solution:  Consider the biggest disk.  You want to get it from peg A to peg C, so first move everything else off of it and onto peg B.  Now you can move the big one to C, then move everything else from B to C.  The "move everything else" steps are where the recursion comes in, because doing that is just solving the puzzle again but with a slightly smaller tower.

Here's a notation that will help:  We'll list the positions of the disks from biggest to smallest, in a single string.  So we start out at "AAAA..." and we want to end up at "CCCC...".  The classic solution is to first go from AAAA... to ABBB... (by recursion), then to CBBB..., then to CCCC....

There's another variation, mentioned in the 3blue1brown videos, where you can only move disks to the right, except that you can also move a disk from the last peg to the first.  This might be called the Cyclic Tower of Hanoi, and it has a solution that's different from, but similar to, the classic Tower.  The difference is that here you can't just move the big disk from A to C.  It has to go to B first.  So you move everything else to C, move the big disk to B, move everything else to A, move the big disk to C, then move everything else to C.  This involves "move everything else" three times, so overall it takes more moves.  Using our notation, this means we go from AAAA... to ACCC... to BCCC... to BAAA... to CAAA... to CCCC....

Our variation involved swapping, and was a little more complicated.  Suppose we're going to implement a function "solve", which moves a tower from A to C.  To move the big disk to C you can't just get "everything else" out of the way.  You need the second-biggest disk to be on C, for the swap to work.  That is, we need to get from AAAA... to ACBB....  Let's ignore how to do that for a moment, and just say we have a function that does that, called "unfold".  Basically the function "unfold" takes a stack "AAAA..." and moves to "CBBB...", where the biggest disk of that stack is on one peg, and the rest of that stack is on another.  Suppose we also have the reverse function, "fold".

So the overall solution function, "solve", can work by first calling "unfold" to set up the big-disk swap (ACBB...), then doing that swap (CABB...), then calling "fold" to tidy everything up (CCCC...).  This is a good start, but unlike with the classic and cyclic variations, our "unfold" function isn't just a smaller version of the overall solution.  We still need to define it.

To implement "unfold", how do we get from AAAA... to CBBB...?  As before we've got to move the big disk from A to C.  So we start by going from AAAA... to ACBB..., then swap to CABB..., then somehow get from CABB... to CBBB....  The first part is easy, we call "unfold" on the sub-tower.  This last part is new, though.  Now we need some algorithm that can insert a disk underneath a stack.  That is, it needs to get from something like ABBB... to BBBB.... This requires another function, let's call that "insert".  We'll also need "extract", the inverse of this function (so we can implement "fold").

To implement "insert", how do we get from ABBB... to BBBB...?  The big disk needs to get from A to B, so we need to set things up for that swap.  This means we need to go from ABBB... to ABCC..., swap to BACC..., and then go from BACC... to BBBB....  Finally we have all the tools we need:  The first step there is just moving a whole tower (BB... to CC...), which is the "solve" function we're ultimately building.  The last step is "fold" (ACC... to BBB...).

How the five functions call each other.

So our solution involves five functions: "solve", "unfold", "fold", "insert", and "extract".  The paper rigorously describes why this solution is optimal, but I prefer to simply note that there aren't really any other options.  For the implementation of each function, the biggest disk really does need to move to the right place, and it can only get there if every other disk is set up just right.  It seems to me that it's optimal because it only makes necessary moves.

I made a site that demonstrates this and a few other variations of the Tower of Hanoi, at the link below.

Tower of Hanoi Variations