Tower of Hanoi

The Tower of Hanoi is a simple mathematical problem or puzzle. You are given three rods and a number of discs of different sizes. The puzzle starts with all discs on a single rod. Your aim is to move all of them to a different rod according to various rules:

• Only one disc can be moved at a time
• No disc can sit atop a smaller disc.

It is not hard to show that with N discs, we can achieve the goal in 2^N – 1 moves. The simplest proof is to observe that with N discs we need to perform the following three steps: (i) shift the top N-1 discs to an empty rod (ii) shift the bottom disc to the other empty rod, (iii) shift the top N-1 discs onto the bottom disc. By mathematical induction one easily establishes the formula 2^N – 1. Note that we are essentially reducing the problem with N discs to a problem with N-1 discs.

With similar reasoning one can show that any random position of discs can be obtained (as long as no disc covers a smaller disc). The proof is left as an exercise for the reader.

The Tower of Hanoi is an example of shifting a large pile of items with limited resources. If you are not familiar with this puzzle, you will probably be surprised by the fact that only three rods are required no matter how many discs you start with. Avid readers of this blog may have come across terms like “Tower-Of-Hanoi manoeuvres” from previous posts, so if you were unsure what the fuss was all about, then now you know 😊.

In Spider Solitaire we are often confronted with the problem of shifting large sequences of cards with limited resources. A simple example is shown below: A complete suit of Spades is visible but can we actually clear the suit with only one empty column?

The answer is yes. We can shift the Eight of Diamonds onto the Nine of Diamonds in column six, build the J-0-9 of Spades onto the K-Q in column 2, move the 8-7-6-5 of Spades from column five onto the 9 of Spades, swap the 4H and 4S on top of both the Spade Fives and finally add the Ace of Spades from Column three to complete the suit.

Going back to the Hanoi puzzle, with a small number of rods a monkey could probably luck his way into a solution by making random moves, but once you get a decent size pile of discs the random move strategy doesn’t work so well! Also, with random moves it is difficult to prove that e.g. 30 moves or less is impossible given five discs. Similar considerations apply to Spider Solitaire. Since the above example is relatively simple, a monkey could probably complete a suit of Spades by repeated trial and error, assuming he only makes moves that are “reversible”. But with a more complex problem, the monkey won’t do so well.

If you want more practice with “Tower-of-Hanoi manoeuvres” I recommend the following exercise: set up the diagram above, ignoring any face-down cards or cards not in sequence (for instance in column two you keep only the K-Q of spades).  Then try to minimise the number of in-suit builds using only reversible moves (you should be able to get pretty close to zero). From this new position pretend you’ve just realised your mistake and try to clear the Spades using only reversible moves. This exercise should give you an idea of why empty columns are so valuable.

Note that all this carries the assumption of no 1-point penalty per move (commonly used in many implementations of Spider Solitaire). If there was such a penalty then we would have to think twice about performing an extra 50 moves just for the sake of one more in-suit build. But for now we’ll keep things simple.