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.

Game on! (17 June 2020)

Continuing from last week

I hope you understand the notation by now; if not please refer to previous posts.

<ch,ic,hc,bf, cb> Ks

<jc> Jc

<ba, bi, gb> 9c

<be,gb > 6h

<ai,ga> Qs

<jg> Ad

<fa, cf> Qc

Now is a good time to take stock and assess the position. Clearly we are doing very well with only 16 cards face-down in the tableau and four rounds left in the stock. We have one “implied” empty column since the Ace of Diamonds can play onto the Two of Hearts on the left. This is worth one turnover in any of the four left-most columns. We also note that:

  • There are only four columns containing at least one face-down card. This is good news when playing for empty columns, but there is a new danger: the possibility of one-hole-no-card. It’s not an immediate problem since the cards in columns b-c-d are “clean”, but it’s still something to bear in mind.
  • We are not close to completing a full suit. This can be “blamed” on having so many unseen cards in the stock, but it sure beats having so many unseen cards in the tableau! Spades and Clubs do look promising with only three cards missing.

So it seems our strategy should be to keep trying to tidy in-suit builds and expose as many face down cards as possible. I generally find once all cards in the tableau are exposed, the complete suits will take care of themselves (barring a series of major accidents). But if you can’t expose all face-down cards then you have to “earn” your suits. How would you continue?

How Can I Win This Game? (Alternative version)

It was a pleasant Sunday afternoon. The sun was shining and he had plenty of spare time on his hands. True, there was the small matter of a chemistry assignment due tomorrow, but that could always be done after dinner. A perfect time to play some more Spider Solitaire.

The play had started well, but things started to sour when four Kings appeared in the third deal. The fourth deal brought no luck either with no face-down cards unable to be exposed. Resigned to his fate, Joe Bloggs reluctantly dealt the last row of ten cards and surveyed his prospects.

How can I win this game? Joe asked himself.

There was some good news: an empty column (or “hole” as he liked to say) was available in the ninth column. And he could turn over a card in Column h. But at this stage of the game Joe realised he would need a good miracle or three to win.

“What is the best card I can hope for in Column h?” Joe asked himself.

This brings him to the bad news: there would be plenty of calculation to look forward to, and given the stock was empty any mistake, no matter how small, could be fatal.

Suddenly Joe Bloggs spots a bird staring at him through the window.

She’s been wallowing in the mud for way too long. Don’t ask me why.

Joe Bloggs briefly considers giving the poor thing a nice warm bath.

“Oink oink,” says the bird.

“87,72,65,84 84,72,69 70,85,67,75?” replies Joe Bloggs.

Through his peripheral vision, Joe Bloggs notices a flock of shiny pigs floating in the air. Thirteen of them shift into the foreground and form the shape of a happy face. After winking at Joe Bloggs, they chase each other in circles for a good half-a-minute. Then they gradually accelerate until whoosh – they shoot up towards the sky!

“Oink oink,” repeats the Bird.

Joe Bloggs stares at the bird again. Perhaps she is trying to tell him something, but he can’t work out exactly what. His chemistry assignment? That wouldn’t make much sense.

Joe studies the cards again. He soon notices that every card in the Spade suit is visible in the tableau. An Ace in column 5 or 6, Deuce and Three in column 6, Four-Five in column 8 and so on. Perhaps it is possible to remove a complete suit of Spades with the correct sequence of moves, regardless of the permutation of face-down cards. Not likely, given they were scattered all over the place, but perhaps his best shot anyhow.

“Aha,” says Joe Bloggs, after some thought. “The correct move sequence is <bg, id, ih, ia, jf, dj, cd, ch, jd, cj, d2=j1, hc, hc, fg, fd, fh, fa, d1=f1, f2=h2, hc, cj>”

Joe Bloggs executes the move sequence <bg, id, ih, ia, jf, dj, cd, ch, jd, cj, d2=j1, hc, hc, fg, fd, fh, fa, d1=f1, f2=h2, hc, cj> and whoosh – he triumphantly slaps the Spade Suit onto the foundations!

True, his position was still very bad after removing the suit of Spades but no matter. He had already won the war: thanks to this hand his skill had improved considerably and the actual result of this game was rendered moot.

How Can I Win This Game?

In the opening phases of the game we are always concerned with turning over new cards and building in-suit. But in the middle-game or end-game things are different.

By this stage a decent player will be able to evaluate the position. After performing some multi-dimensional calculus on the back of an envelope, he she or it will be able to estimate winning chances and decide on a plan of action.

Unfortunately, an in-depth discussion of multidimensional calculus is beyond the scope of this post but a useful general principle is the following:

  • If things are going okay, we should continue to play our normal game. Turn over new cards, build in-suit whenever possible, and start thinking about removing complete suits.
  • If the game is going badly, start looking for miracles. You need them to win, and miracles never occur if you don’t look for them.

Conversely if the game is going extremely well, you might consider playing safe, but that’s another lesson for another time.

In the diagram position you don’t need a Grandmaster Title from the International Federation of Spider Solitaire to work out the prospects are bleak. The stock is exhausted, several cards are yet to be exposed etc, etc. But all hope is not lost if you excuse the terrible cliché. We can quickly obtain an empty column and turn over cards in columns a or h. Since we probably need good cards to win, we might ask ourselves “if we could call the next card what is the best case scenario when turning over column a or h?”

A closer look reveals all cards in the Spade suit are already exposed. Assuming we focus all our effort into removing a full suit of Spades how much luck do we need? Perhaps a good card or two in column a, or perhaps we can tidy things up a little and hope for luck on the next deal – no scratch that, the stock’s already empty.

It turns out we don’t need any luck – it is possible to remove the Spades without exposing any new cards. Of course, we need to expose cards to win the game eventually, but the point is we are guaranteed to remove Spades regardless of the permutation of unseen cards. One sequence would be: is <bg, id, ih, ia, jf, dj, cd, ch, jd, cj, d2=j1, hc, hc, fg, fd, fh, fa, d1=f1, f2=h2, hc, cj>. Whoosh – the Spade suit goes onto the foundations!

If you found this sequence of moves well done. Of course, it might be possible to do better than that – remembering that removing one suit is not synonymous with winning the game. But at least it’s a fallback position: we can choose this option if we find nothing better.

Avid readers might have recognised the exact same position from an earlier post, and would keenly deduce the game is winnable since I managed to beat it without undo. If you spotted this then again well done 😊

Game on (10 June 2020)

Continuing from last week

We have two guaranteed turnovers and there are no tricks to improve that. At least we get some in-suit builds. We also have the ability to connect the K-Q-J-0 of clubs (an action we considered last week, but rejected)

<be,bc,eb,hc,ij,bi,be,fb>  Js

<je,fj> Ac

<fc,ib,ij,ih> 6d

<ig> 0s

<e2=h1, ih> 4s

<gh,gh> 7s

Our position has improved considerably. We have turned over 6 more cards and we still have two empty column and two turnovers.

You may be wondering why I shifted the King of Diamonds onto an empty column. This is an example of long-term planning: We have to shift the king sooner or later and it’s easy to do so when there are plenty of empty columns to go around. Note also the column contained an off-suit K-Q combination so if we only had one empty column then it would be difficult to shift it later. For the same reason I chose not to shift the K-Q of clubs in column ‘b’. I am essentially trying to guard against the dreaded “one-hole-no-card” scenario in the future.

I also took care to swap columns ‘e’ and ‘h’. This is because an in-suit Q-J of Hearts will be easier to shift if a King later appears at the right moment.

The question of when to dump a King onto an empty column is difficult to answer (let alone explain to someone like Captain oBVIOUS). Until you gain more experience (or epiphanies!) a good general guideline is the following:

  • If you find yourself unable to turn over a new card despite having one or more empty columns then chances are you are not taking maximum advantage from a position of strength.

Yes, there will be occasions when you have a rough start and have to fight tooth and nail just for an empty column. Then you find there is no real opportunity to avoid one-hole-no-card. But that means you never had a position of strength to begin with.

The above guideline does not refer to Kings specifically. Consider dumping a King onto an empty column when:

  • You are afraid of one-hole-no-card, or
  • You still have reasonable chances of recovering an empty column (a different empty column unless you can complete a full suit!)

Anyways back to the game. What would be your next action? (Hint: tidy up in-suit builds using reversible moves first!)

WordPress new editor

On June 1, the good folk at WordPress retired their old editor and transitioned to the new one. Not sure how many writers voted for this but if that’s the sixth level of Jumanji in 2020 then I’m not complaining.

Bad jokes aside, we have over 100 content blocks for publishing virtually any post, wider collection of block patterns, built in templates, blah blah blah blah … okay can’t say I’ve read the new specs in detail. So I’ll try to figure things out without reading the instructions … so we can align an image to the centre as usual. If you align an image to the left or right then you have surrounding text alongside it, and there are also options of wide width and full width. Give me a minute to work out what all of them do. And I think I will cheat by allowing myself to click 85,78,68,79 or Ctrl-Z whenever I do something and don’t like the results! Or alternatively I might throw my hands in the air and shout 65,72,72 70,85,67,75 73,84 it’s too hard.

Somebody mentioned changes like:

  • Like buttons appearing at the bottom of each comment
  • Videos within tweets don’t work.
  • The sidebar with the subscription function, search function, and other stuff is still there; it’s just at the bottom of the page or of the post.

Unfortunately I can’t add any meaningful comments. For one thing like buttons appearing at the bottom of each comment are irrelevant, since I very rarely get comments even for silly short stories. There seem to be other features such as “stick to the top of the blog” or “pending review” and I’m trying to figure out what’s the point of all this 83,72,73,84?

I do agree with the sentiment that WordPress likes to change the rules at the last minute, especially when the number of days between today and 1st of January 1970 is a power of a prime number and the moon is three quarters full. Perhaps someone who is more clever than I can work out the exact detailed programmatic specificity (to borrow a phrase from Kevin Rudd). One thing I noticed is that when I wanna stick a picture inside a post I often (but not always) need to save the picture as a temporary image, but the new editor seems to have solved this problem(*). Of course my sample size is very small, so I don’t wanna jinx it too much 😊

(*) but if you wanna cut and paste text and images then it won’t work. You have to do them separately.

What are your thoughts about the new editor?

Game on! (3 June, 2020)

Here is the position from last week

The first order of business is to shift the J-0-9 in Column ‘c’ onto the Q of Clubs. This illustrates the concept of “duplication vs diversification”. We already have three exposed Queens so can easily afford to use up one of them. But we don’t have an exposed Four. By diversifying we give ourselves more opportunities to reveal cards since any exposed Three can later play onto the Four of clubs. Even if we don’t expose a Three we also get the option of shifting some junk in Column ‘a’ (one empty column is not enough to shift the 8-7-6-5-4-3-2 without some “stepping stones”).

Note also that procrastination is not possible. Any legal action must spend our only empty column, so we must make the choice now: shift the J-0-9 or leave it – and all the signs point to the former.

We next shift the Jh-0s-9s-8s onto the Q of Hearts using much the same reasoning: procrastination is impossible, we build in-suit with Q-J of Hearts and again diversify, exposing a Ten. This Ten is especially useful since it gives us an option of shifting the 9h-8d-7d even if a bad card turned up.

The next order of business is to look for opportunities to “tidy up”. We have 8d-7c and 8s-7d in the first two columns which suggests it may be possible to build in-suit with 8-7 of Diamonds. It turns out this is possible, using “stepping stones” in columns ‘c’ and ‘g’. Note that we have to temporarily break up the 7-6 of Clubs to achieve this. Also observe that we can now procrastinate in column ‘a’ since it is possible to shift 8d-7d onto the Nine of Spades after using up the empty column.

At this stage the obvious choice is to shift the Two of Clubs onto the empty column, since that takes care of the last hidden card in Column ‘e’. This would improve our chances of winning back an empty column on the next round.

An advanced player might consider filling the empty column with the Q-J-0 of clubs. The reason is we already have a King of Clubs exposed, so if things go well it might be possible to exchange the Q-J-0 of Clubs with the Q of Hearts in Column ‘b’ without fear of losing the empty column. Unfortunately it is not possible to connect the K-Q-J-0 of Clubs immediately without compromising our position – no wait up, it is possible! We can shift the J-0 of Diamonds onto the Queen of Spades, then shift the Jack of Hearts plus 0-9-8-7-6-5-4-3-2 of various suits onto the other Queen of Hearts, which means we are not losing an in-suit build after all. Then we dump the Queen of Hearts onto the empty column and move the Q-J-0 of Clubs onto the King.

This is a far-sighted play but does not have the advantage of clearing the last face-down card in any column. It’s close, but I vote for the simple option of dumping the Two of Clubs. We are nowhere near completing a full suit of Clubs and our immediate concern is turnovers and empty columns. The K-Q-J-0 of Clubs can wait.

Finally we should also consider shifting the Two of Hearts into the empty column and then building 3s-2c. It’s always good practice to consider every legal option and search for any edge, no matter how small. In this case, I’m not seeing it. Two of Clubs it is.

Our final action is <hi,cf,ib,a6=b1,eh>. That’s quite a lot of work for one card. And we get a … drumroll dlrdlrdlrldrdlrdlrdlr … THREE OF HEARTS, 70,85,67,75 YEAH!!!!

This is clearly one of the best cards we could hope for. Of course the game is far from winning but two empty columns puts us in a strong position. How would you continue?

The Big 104 (alternative version)

The Grand Master, the principal adviser to the King, had maintained a blog about Spider Solitaire for a whole year.

“Thank you, Grand Master, for this most wonderful blog,” said the King. “I enjoyed reading your silly stories. However I can’t claim it has improved my game tremendously so I can only offer you a small reward.”

The King gives the Grand Master a sack of wheat.

“How dare you offer such a modest reward for the world’s best blog on Spider Solitaire!” replied Spider GM. “As far as I know, I am the world’s best player of Four Suit Spider Solitaire sans boop. This is a travesty!”

“What nonsense!” retorted the King. “I have several men who can wield a mean deck of cards – or two.”

The King corrected himself at the last minute, recalling that Spider Solitaire was played with 104 cards, not 52.

The Grand Master offered to play a 30-game match against each of the top ten players chosen by the King. A 30-game match would consist of 15 games by each player, Four-Suit sans boop and whoever won more games would win the match. Spider GM offered “draw odds” to every player, meaning that if both won the same number of games it was tantamount to the Spider GM losing the match. Not surprisingly Spider GM wiped the floor with each and every one of them.

Sensing the King was utterly humiliated, the Spider GM suggested the following deal: he had to publish one blog post for the first card, twice that for the second card, twice that for the third, and so on. Once all 104 cards in Spider Solitaire were accounted for, Spider GM would enjoy 104 consecutive nights in a palace with 104 dancing girls per night. Spider GM was allowed to count the 104 articles he had already written towards the however-many-were-required needed to reach his end goal.

The King knew the arrogant 66,65,83,84,65,82,68 had a couple of blog posts lined up already, perhaps between 50 and 100, but reluctantly agreed to the bargain.

THIS IS GONNA BE WILD, the Grand Master thought to himself. He was well on the way to completing the next square, which will be marked 128.

youarehere

THE END

The big 104

Hooray! I reached my 104th post in my Spider Solitaire blog after starting in May last year. Some of you may be wondering why I didn’t choose a nice round number like 100 instead of 104. Here’s a hint: Spider Solitaire is played with two decks. Each deck contains 13 ranks and 4 suits. I’ll let you do the math 😊

This blog started after I “busted” a rogue Spider Solitaire server that punished a player who accumulated too many wins. I then wrote a short story trilogy to explain my findings in language accessible to the layman and the rest, if you pardon the cliché, is history.

I try to post at least once a week. Throw in a couple of silly stories per month, plus a walkthrough of a game of Spider Solitaire with one update per week (which I am currently doing right now). There may be occasional news articles, such as Facebook’s new “care emoji” or Microsoft’s 30th anniversary of Solitaire. With 52 weeks per calendar year, it was not hard to achieve the 104-post milestone within the first year.

Not surprisingly the vast majority of likes come from my silly stories. The likers are mostly fellow bloggers who also write stories – and I have to admit they write much better than I do. So perhaps I should be the one learning from them 😊 Unfortunately I don’t have a lot of traction with the serious strategy articles, but maybe one day something might turn up. Occasionally, I get a like from something that isn’t a short story (like Actually Autistic Blogs liking my post on Facebook’s so-called Care Emoji). And yes, there is the occasional spam comment or two such as a link to a random Russian porn site.

My next milestone is 128 blog posts. Having already filled in 7 out of 104 squares in the diagram below, I’m already 6.73% of the way towards achieving my ultimate goal. Given that I enjoy playing and writing about Spider Solitaire much more than work this should be a walk in the park if you excuse the terrible cliché!

youarehere

Do you have a favourite article from this blog so far? If you think this blog is generally-all-round-awesome you are allowed to simultaneously vote for every blog post 😉😉😉Please let me know in the comments below!