Nightmare Klondike

Riddler Classic

You fire up a new game of Solitaire, the version known as Klondike, dealing three cards at a time from the stock. Your boredom quickly turns to rage: the game is unplayable from the start, because you can flip through your deck but you never have any legal moves. What are the odds?

The Riddler, FiveThirtyEight, March 30, 2018(original post)

The Riddler Express that week was a participatory contest (submit a positive integer closest to the median of all submissions), with no derivable answer. It is deferred.

Solution

The Klondike layout. The deck is shuffled. The first $28$ cards form a triangular tableau: column $k$ (for $k = 1, 2, \ldots, 7$) gets $k$ cards, the top card of each column lying face up and the rest face down. The remaining $24$ cards form the stock. With a three-card flip, only every third card of the stock is ever a legal candidate for play (the three-card packet shows just its top card as playable, and that packet’s position in the cycle is fixed for the first pass). So the cards initially playable are the $7$ face-up tableau tops plus $8$ stock cards, $15$ in total.

What counts as a legal move from the opening. Two kinds of move exist.

• Move an Ace to the foundation. Any of the $15$ initially playable cards may be moved if it is an Ace.

• Move a card $C$ onto a tableau top $P$ such that $\mathrm{rank}(P) = \mathrm{rank}(C) + 1$ and $P$ has the opposite colour to $C$. The receiver $P$ must be one of the $7$ face-up tableau tops; the candidate $C$ may be any of the $15$ initially playable cards.

A King cannot move at the opening, because the only target for a King is an empty column and no column is empty.

The nightmare condition. The deal is unplayable from move one if and only if (i) none of the $15$ initially playable cards is an Ace, and (ii) no pair $(C, P)$ with $C \in$ playable set and $P \in$ tableau tops satisfies the rank-and-colour rule above.

Why a closed form is unattractive. The official write-up sums a product of binomial coefficients across a few thousand rank-and-colour partitions, arriving at the exact rational $$P(\text{nightmare}) = \frac{643{,}746{,}385{,}468}{257{,}479{,}369{,}193{,}475} \approx 0.00250 \approx \frac{1}{400}.$$ That arithmetic is unobjectionable but cumbersome and easy to bungle. The cleaner approach for a worked solution is to encode the layout rules directly and sample. Monte Carlo on the actual deal converges to the same value to four significant figures within seconds, and confirms there is no hidden modelling trap. $$\boxed{\,P(\text{nightmare}) \;\approx\; 0.0025 \;\approx\; \tfrac{1}{400}.\,}$$

The computation

Encode the deal and the legal-move test directly, then count the fraction of $N$ random shuffles for which no legal move exists.

1. Build a $52$-card deck of $(\text{rank}, \text{suit})$ pairs.

2. Shuffle. Deal the first $28$ into the triangular tableau; record the $7$ face-up tops. Pick out the $8$ playable stock cards at positions $30, 33, \ldots, 51$ (zero-indexed $29, 32, \ldots, 50$).

3. Declare the deal nightmare iff no playable card is an Ace and no playable card can be placed on a face-up top under the alternating-colour descending-rank rule.

4. Average over a few hundred thousand trials.

import random

random.seed(1)
RANKS = list(range(1, 14))                    # 1 = Ace, 11 = J, 12 = Q, 13 = K
SUITS = ['C', 'S', 'H', 'D']                  # C/S black, H/D red
deck = [(r, s) for r in RANKS for s in SUITS]
def colour(s): return 'B' if s in ('C', 'S') else 'R'

def is_nightmare(cards):
    # Layout: col k (k=1..7) gets k cards; the k-th placed is the face-up top.
    cols = [[] for _ in range(7)]
    pos = 0
    for row in range(7):
        for c in range(row, 7):
            cols[c].append(cards[pos]); pos += 1
    tops = [col[-1] for col in cols]              # 7 face-up tableau tops
    stock = cards[28:]
    playable_stock = [stock[i] for i in (2, 5, 8, 11, 14, 17, 20, 23)]
    playable = tops + playable_stock
    if any(c[0] == 1 for c in playable):           # an Ace can go to foundation
        return False
    for child in playable:
        for parent in tops:
            if child is parent: continue
            if parent[0] == child[0] + 1 and colour(parent[1]) != colour(child[1]):
                return False
        # else no legal move involving this child
    return True

N, hits = 400_000, 0
for _ in range(N):
    s = deck[:]; random.shuffle(s)
    hits += is_nightmare(s)
print(f"hits = {hits} of N = {N}; P = {hits/N:.5f} (~ 1 / {N/max(hits,1):.0f})")

The script prints $P \approx 0.00244$ on this seed (about $1/410$), matching the boxed value of about $1/400$ and the official’s closed-form rational $643{,}746{,}385{,}468 / 257{,}479{,}369{,}193{,}475 \approx 0.00250$ within Monte Carlo error.

A note on the one-card flip variant. Laurent Lessard’s write-up extends the same logic to the variant in which the stock is dealt one card at a time (so all $24$ stock cards are immediately playable from the opening). The nightmare probability there is much smaller, about $1.8 \times 10^{-7}$: every additional playable card multiplies the chance that some pair clicks.