The Impossible Solitaire, a Python experiment

When I was a child my father taught me a version of the game “Solitaire” in which a deck of cards is used. I never forgot how to play that game, and I still find it compelling even though it is very, very difficult to win. It can be played with a poker deck (52 cards) or with a Spanish deck (48 cards).

For me this was always the version of the Solitaire that I knew. 30 years later I find that it is not at all common (it is very different from other versions of Solitaire that I have found, even the computer implementations). The only reference I found calls it “Solitaire among equals” ("Solitario entre iguales" in Spanish).

The entire deck is shuffled and then the cards are dealt one by one on the table. Once you have three cards on the table, you have the ability to “mount” the second card on top of the first one, but only if the first and third cards match in suit or number. If there is no match, cards are dealt until a match appears between the last card and the card two places back.

"Solitario entre iguales" with poker deck.

This is a game in which nothing can happen for a long time, but when something happens, it can trigger a chain reaction, since with each move (“mount”) you have to recheck the matches in interspersed pairs and "mount" the intermediate cards if necessary.

The objective of the game in its most difficult version is to finish with 2 piles of cards. We can also set the goal of finishing with 3 or less piles, or 5 or less, depending on how difficult we want it to be.

Pretty clear, huh?

Now, the Python experiment

I always had in mind that this game was difficult. I don’t remember any occasion of winning (except when I cheated as a child, trying unsuccessfully to fool my parents…).

A few days ago I was playing this game and I thought about calculating how difficult it is to actually win, at least from an empirical, statistical perspective. That’s where Python comes into play :)

First of all you have to model your cards and deck. I based my implementation on a post from Anthony Tapias. I added some validation logic with the poker card deck in mind, and some pretty prints too.

Cards' value is modeled from 1 to 13 (1 to 10 for actual numbers, 11 is the Jack, 12 is the Queen, and 13 is the King). Cards' suit is modeled as ['Spades', 'Clubs', 'Diamonds', 'Hearts']. It works like this 👇

We also need to model a deck, with its methods for deal cards and for shuffle (and also some pretty prints).

Card shuffling is resolved with random.shuffle (in place). It could also be solved with random.sample if we didn’t want to lose the original order of the deck. It works like this 👇

Note that the cards are dealt from the bottom of the deck.

Now that we have the deck ready and shuffled, we can start playing. The logic of the game is quite simple, but recursive, since each movement can trigger successive “mounts” of cards. Every time there is a match and a card is "mounted" on another, it is necessary to recheck backwards first and then forwards the appearance of new matches (and so on until there are no more matches and we can deal another card).

Note: there is nothing to do when there are two cards or less on the table.

Remember, the game ends when we deal all the cards.

We define three methods:

  • compare_cards : just checks if two cards match in suit or value.
  • play : executes -recursively- the "mount" movement. Recursiveness goes both forward and backward in the list of cards in the table.
  • game : run a full game for a deck. Method game() returns the result of the match (the amount of card piles after drawing all cards).

If we run a game() (in debug mode, not the same code) we get something like this 👇 (loooong image…)

As you will see in the image, this game ended up with 14 piles of cards on the table, therefore, the game was lost :/

Finally, let’s see some statistics of this game (how difficult it is to win) depending on the objective. I’ve simulated a million games with shuffled decks, and let me tell you, this game is hard:

With this experiment I reached 0.111% of victories with objective=2. That's roughly 1 out of 1000 games. With looser goals we can get higher winning chances, with 0.61% of victories with objective=3, and 1.51% of victories with objective=4, and 2.73% of victories with objective=5. Here's the histogram of number of card piles resulting after the games 👇

This increases the probability of winning as we “soften” the desired goal 👇

Last but not least, you have to know that 1 million shuffled decks is a very small number compared to the total number of possible combinations that can be formed with 52 poker cards (which is 52!, that is, 8.06e+67) 🤯

I realize now that my father taught me how to play The Impossible Solitaire… roughly only one in a thousand decks would lead me to victory.

Here you can find an example of a winning deck 👇 (remember to deal from the bottom of the deck, so first card would be the 9 of clubs).

Update (2021.04.11)

During the past few days I couldn't stop thinking about this problem, and the possible solutions it may have. I realized that there is a simple rule by which one can design winning decks.

I have found a simple rule to create decks where only 2 piles of cards are obtained as a result of the game. It is as simple as adding cards, iterating first in the possible values and then in the possible suits, and every time I go through the suites I change the order of them (if I had them ordered as [1,2,3,4] I change it to [3,4,1,2]). This flip ensures that matches are continued when the value changes.

Basically, with this design, I get as many winning decks as the amount of permutations of suits multiplied by the amount of permutations of values, that is 4!*13!. In fact, if we switch the way we design them (first values then suits) and we change the flip function accordingly we get the same number of different winning decks. Then, we can say we have at least 2*4!*13! winning decks (almost 300 trillion!).

But guess what… that amount just represents the 3.706e-55% of the possible decks. Another proof that these solutions exist. Simple check 👇

Another experiment I did was to actually create decks with more complicated logics, looking for a better winning rate. What I tried was to create consecutive five-to-two groups (five cards that turn into two), since card 5 and card 3 match, then card 4 and card 1 match, and then card 5 and card 2 match.

Logic is quite complicated but we ensure winning, getting 100% of victories instead with objective=2. The only drawback is that in the process of designing these decks, many must be discarded due to lack of matches.

100% winning rate!! 😃

This game is still quite impossible, but at least we were able to find almost 300 trillion solutions from a theoretical perspective, plus a 0.111% of random decks (again, a tiny number against the amount of possible decks).

Finally, this exercise was very interesting. See how a game that seems “simple” has such a huge universe of possibilities, see how difficult it is to find an optimal solution.

(some university titles…) :: focused on ai, data, audio & image, machine/deep learning & music :: VP of technology & head of #AI development @globant