Is Every Game of Solitaire Winnable?

The Problem

There are as many possible games of Solitaire as there are permutations of a deck of cards. That’s something like 8 * 10⁶⁷ possible games, or 8 followed by 67 zeros. It’s an impossibly large number — seeing it written out is absurd:

80000000000000000000000000000000000000000000000000000000000000000000

If you shuffle a deck of cards well and lay them out to play Solitaire, you will probably be the only person to ever play that game of Solitaire.

How can we prove or disprove that all of these permutations are winnable?

Terminology

A quick index of the terminology I’ll use throughout the proof:

• Tableau: The main playing area, the seven columns.
• Stockpile: After dealing the cards onto the tableau, the remaining cards left in the deck make up the stockpile. You draw cards from the stockpile to play them during the game.
• Foundation Piles: You win classic Solitaire by filling up the foundation piles above the tableau. Each foundation pile corresponds to one of the four suits (spades, hearts, clubs, and diamonds). After starting a foundation pile with an ace of any suit, you continue adding cards of the same suit in ascending order.

The Proof

Introduction

A brute force approach, going through each permutation of solitaire and verifying that it is winnable, is out of the question given the number of possibilities — even for a computer.

If you’ve played solitaire frequently, your gut feeling is probably that not every permutation is winnable. Unfortunately, gut feelings are not enough to satisfy mathematicians and critical thinkers.

I plan to use what mathematicians call a proof by contradiction. These are proofs that use a specific example to show a hypothesis is false. For instance, if we consider a hypothesis: “there are no prime numbers larger than 100”, identifying that 101 is a prime number and larger than 100 is a valid proof by contradiction.

Proof

Consider a permutation of solitaire where the tableau is arranged in the following manner, before any moves have been made:

There are no possible moves within this tableau, because red cards cannot be placed on to red cards, there are no kings and open columns, and there are no aces to begin foundation piles.

Now consider that the stockpile contains the following:

and the remaining unidentified cards are faced down in the tableau arranged in any manner.

The red cards in the stockpile cannot be played because the only cards in the tableau are red, there are no open columns to place the kings, and there are no aces to begin stockpiles. That leaves us with:

• A black 6 cannot be placed on to a red 2, 6, 9, or Queen.
• A black 9 cannot be placed on to a red 2, 6, 9, or Queen.
• A black Queen cannot be placed on to a red 2, 6, 9, or Queen.
• A black King cannot be placed on to a red 2, 6, 9, or Queen, and there are no open columns to place the Kings on to.

This permutation has no possible moves from the very beginning, and if there are no possible moves the permutation cannot be won. Since this permutation that cannot be won exists, not every permutation of Solitaire is winnable.

Conclusion

Thank you very much for taking the time to read this article!

If you found it interesting, consider becoming a follower of mine. My content is a mix of “shower thoughts” like this, commentary on my software engineering career, and the technology career space in general!