Tower of Hanoi (alternative version)

“I can’t do it,” sighs the Ninja Monkey.

“Now what?” I ask

“It’s the legend of the Flowers of Hanoi,” replies Monkey. “Something I learnt from the Bad Idea Bears.”

“I know you often mention the Flowers of Hanoi during Spider Solitaire lessons,” says Bad Idea Bear #1. “We asked our friends about it, and eventually figured out the rules.”

This cannot be good. Yes, the Bad Idea Bears have inquisitive minds, an essential quality for anyone who does a Ph. D., but it’s a pity their math fundamentals are 83,72,73,84.

In front of the Monkey are a pile of five flowers, surrounded by a large square. Each flower lies atop another flower of slightly smaller size. There are two more squares of the same size, but do not contain any flowers.”

The Bad Idea Bears say I should be able to shift all the flowers to one of the other squares in 30 moves, but the best I can do is 31.”

“Shouldn’t be too hard,” I say. “After all, thanks to an extremely fast metabolism you are able to complete 200 games of Spider Solitaire in three minutes if you pretend it’s played at the one-suit level. But this puzzle only involves five flowers instead of 104. How hard can it be?”

“But there’s a catch. You can only move one flower at a time – and no flower can be on top of a smaller flower.”

“Of course if this were Spider Solitaire then you can do it in one move, since all flowers are the same colour.”

“Yes that is true,” chuckles Ninja Monkey. “The game does have similarities with Flowers of Hanoi. I find I often need to make many moves just to expose one more card. But perhaps my Random Move algorithms aren’t all they’re cracked up to be.”

“Don’t be too hard on yourself. You’ve already achieved a lot with Four Suit Spider Solitaire. Everybody treats you with respect, and we won $3000 dollars from the Eagle last …”

“For 70,85,67,75,78 sake,” says the Eagle. “You don’t need to bring that up every third day of the month.”

“Why do the Bad Idea Bears think it’s possible in 30 moves?” I ask.

“I was wondering about that as well,” says the Bad Idea Bear #1. “But we finally figured out the pattern. We started by considering what happens with fewer than 5 flowers.”

BIB #1 draws a large circle in the dirt. He chooses two random points A and B on the circle and draws a line connecting the points. The two resulting regions in the circle are labelled 0 and 1.

“With only one flower, it takes one move to shift all flowers from one square to another,” says BIB #2

I nod in agreement. So far no ground-breaking discoveries yet.

BIB #2 draws a new circle in the dirt but with three vertices A,B,C and lines connecting all pairs of points. Now there are four regions numbered 0,1,2,3.

“With two flowers, we need three moves to shift all flowers to a different square.”

Again I nod in agreement.

The Bad Idea Bears draw three more similar diagrams but with four, five, and six vertices and lines connecting all pairs of vertices.

“Continuing in this manner,” says BIB #1, “we find seven moves are required to shift three flowers, fifteen moves for four flowers and thirty moves for five flowers. In every case Ninja Monkey has found a solution with the correct number of moves – except the last one.”

I examine the BIB’s artwork carefully. They have indeed correctly counted 30 regions in the last diagram. And they can draw diagrams faster than the Wise Snail, I’ll give them that.

“At first we thought it should be 29 regions in the last diagram,” says BIB #2 “but we eventually figured out that no three lines should intersect at a single point. Unfortunately Ninja Monkey has never been able to do it in 30 moves. He can do 7 moves with three flowers and 15 moves with four flowers but the best he can do is 31 moves with five flowers.”

I look in the Monkey’s direction – unfortunately he seems to have knocked himself out, and it doesn’t take long to work out why.

Oh well. At least I was brought up right by Mom and Dad. For one thing, I never scratch my 66,85,77 and/or pick my nose in public.

THE END

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 2N – 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 2N – 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.

The Concept of Shape

Any experienced player will be familiar with various card configurations. We all know that suited connectors are good, but offsuit builds are less flexible. 75,73,78,71,83 tend to stink etc. Even a beginner quickly learns that with an empty column it is possible to shift an off-suit sequence of length 2, but not 3. These are examples of basic “shapes”.

I use the term “shape” rather loosely, and was inspired by use of a similar term in Sensei’s Library for the game of Go. For instance, two eyes live, empty triangle is usually bad etc. Shape is basically describing fundamental patterns that occur repeatedly and there is no reason we can’t apply similar terms for Spider Solitaire (or Chess or even Toy Blast or any other mathematical board game).

Basic shapes

The diagram below shows a sample game after a fresh round of 10 cards is dealt. Here are some examples of shape:

  • We have a suited connector in columns 2 (good shape). If only we can remove that blasted 10 of diamonds then we can easily expose a card.
  • We have an off-suit 4-5 in column 7 (bad shape!) so we cannot expose a card even if we had a spare Six.
  • Column 6 has no face-down cards. In this situation you should ask yourself “can I guarantee an empty column even if I were willing to trash my game state in every other way possible?” In this case, the answer is yes. Note that any column with at least one face down card means we cannot guarantee an empty column unless we play pokies … I mean get lucky.

shape-1

Shapes are not just restricted to single columns. Here are some examples involving two or more columns:

  • We have three kings. This suggests columns 1,3,5 will be used as “junk piles” i.e. if we shift as much 83,72,73,84 as possible onto them then it is easier to clear other columns.
  • We drew three sevens, no sixes or eights in the last 10 cards. The bugbear of every Spider player. Fortunately an Eight is available in column 6.
  • Columns 7 and 9 have a Five-Four combination. Note that if we were able to swap the Fours we would get an extra in-suit build. This requires us to find a third five or an empty column.
  • We have an 8-9 of Hearts combination in columns 6 and 8. This is similar to the previous dot point except Column 8 is missing an off-suit Eight.
  • We have an A-2 of Hearts in columns 4 and 10. Note that this will not be reversible, so you might wanna immediately reread the blog post on procrastination before reading further.

The latter points are particularly important. As soon as you see two connected cards in-suit in different columns you should ask yourself if it is possible to build in-suit (with the help of Tower-of-Hanoi manoeuvres). Most of the time you will require an empty column or two, but on occasion it might be possible even without any empty column. You probably don’t want a 68,73,67,75,72,69,65,68 named 68,73,67,75 saying “Alert” every single time whenever he sees two suited connectors in different columns, but with enough practice spotting this situation should become second nature.

shape-2

In the second example above we have some advanced shapes:

  • Column 1 has a 7H-6H-8C combination. This means as soon as the 8C is moved, we are guaranteed to have a legal play of 7H-6H onto wherever the 8C happens to land. Of course it is even better if we replace the 8C with 8H. Note that this advantage disappears if we move any other Seven onto the 8C first.
  • Column 6 is similar. If we shift the KH onto an empty column we can immediately get it back by moving the QD onto it.
  • Column 10 has a pair of sevens and this is generally bad shape. If, for instance, a King lands on column 10 on the next round, the player may find himself with a shortage of Sevens later on. Note that if we were able to shift any six onto the 7D then this is less of a problem.

Finally, recall that having all cards in a suit exposed in various columns is an example of good shape (or at least something to look out for).

Going Back To The Story

In the previous story 68,73,67,75 (who probably mastered the Tower of Hanoi puzzle at age six) was able to immediately spot opportunities to gain suited builds at no cost. Harry kept a close eye on completing full suits. Both are examples of team members paying attention to basic shapes. As a result, Tom was able to focus on the short-term goals of exposing cards and getting empty columns. Unfortunately nobody saw the plot twist coming on Monday, and Project Manager 2 was forced to record a “no-result” instead of a well-deserved victory. But we all know that 83,72,73,84 happens even to the best of us!

Until next time, happy Spider Solitaire playing – and remember not to play too much Spider at work 😊