# 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).

## How to play?

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

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 :)

## The cards and deck

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.

## The game

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 :/

## Some stats

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) 🤯

## Conclusion

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)

## Manually designing winning decks

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 👇

## Optimizing decks

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!! 😃

## Conclusion 2

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

## More from Haldo Spontón

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