The impossible deals
Some deals of solitaire cannot be won. Not hard, not unlucky: there is no order of moves, however clever, that ends with every card home. FreeCell has eight of them among its first million games. In Golf, three deals in four are like that. Which ones are they, and how can anyone know?
What "impossible" means
A deal is impossible when no line of play from the first position wins, even for a player who knows where every card lies. In Klondike, Spider, Golf, Pyramid and TriPeaks some cards are hidden from you, but our solver sees them all. So an impossible deal is one nobody could win even with every card face up.
That is more than "hard", and more than "our solver did not win it": a solver that stops after a set number of positions proves nothing by stopping. Only a win, or a search that has looked at everything, settles a deal.
FreeCell #11982, the famous one
The early Microsoft versions of FreeCell came with 32,000 numbered games. From August 1994 to April 1995 the Internet FreeCell Project shared them among volunteers to find out whether every one could be won. All could, except 11982. Windows XP raised the count to a million, and solver programs have since been through them all. Eight cannot be won: numbers 11982, 146692, 186216, 455889, 495505, 512118, 517776 and 781948.
FreeCell is the one game here we did not check ourselves. Our own solver gives up on 11982, as it must. Open FreeCell #11982 here and the game says it can't be won, then deals a game that can.
How a search proves a deal impossible
A position is the whole table at one moment. A program can list every position a deal can reach: it makes every legal move from every position, remembers each new one, and keeps going until nothing new turns up. If none of them is a win, nobody can win the deal.
The catch is the size of the list. For some games it is small enough:
- Eight Off #465 leads to fewer than 15,000 different positions, and none of them is a win.
- A Baker's Game deal with no way through typically reaches fewer than 5,000 positions. The largest, deal 65814, reaches about 115,000.
- In Golf a position is just how many cards are left in each column and in the stock, and which card is on the pile. The biggest impossible deal among the first 20,000, number 2304, has just over four million positions, and no win among them.
- TriPeaks positions work the same way; a typical winnable deal reaches about 670,000. For every deal not on our list the solver tried every position, and a second, separate program agreed.
Pyramid needed a trick. We first played an easier game, with every stock card face up and free at any time. A deal that cannot be cleared even then cannot be cleared with three passes, and that ruled out 6,602 of the first 20,000 deals. The solver searched 53 more to the end without a win, and gave up on 51. So the Pyramid list is very nearly exact, but not quite.
Klondike and Spider are too big for this: our solver cannot try every position in a reasonable time, so a deal missing from their lists is one we have not won yet, nothing more. Wins are checked too: the game replays each one move by move, with the same code that checks your own moves.
The first impossible deal of each game
Counting from game #1, these are the first deals with no way through. Each link opens that number; the game says it can't be won and deals one that can instead.
- Golf #1: the very first deal. Game #2 can be cleared.
- Baker's Game #10: the first of 25,069 impossible deals among the first 100,000.
- Pyramid #12: the first deal our solver did not win, and it cannot be won.
- TriPeaks #111: the best possible play clears 27 of the 28 cards, and every line that gets that far leaves the 10 of diamonds on top of the left peak, with no 9 or Jack left to put it on.
- Eight Off #465: one of only 71 among the first 50,000.
- FreeCell #11982: the first of eight in a million.
Three games have no proven first. In Seahaven Towers the first deal our solver did not win is #10. In Spider with one suit it is #1, and in Klondike turning one card it is #8. None of these is a proof, and the game says so: open one and you are told it has no known solution, not that it can't be won.
Klondike #2 shows why the difference matters. Turning one card, our solver gave up on it. Turning three, the harder game, it won the same deal. Turning three cards at once lays them down exactly as turning one card three times would, so that winning line works turning one card too. We replayed every such deal as a turn-one game, and 214 of the first 5,000, #2 among them, joined the turn-one list that way. They could be won all along; the solver simply had not found the way.
Two impossible deals up close
Eight Off #465: a search to the last position
Four cards start in the cells: the 2 of diamonds, the 8 of hearts, the Queen of diamonds and the Jack of diamonds. Those two can leave only once the King of diamonds is uncovered, or once every diamond below them is home, and the King of diamonds lies at the bottom of the first column under five cards. No Ace is on top of a column, so no card goes up before the first move.
The hearts are worse. The Ace of hearts lies at the bottom of the second column with the King of hearts directly on it, and the 2 and 3 of hearts lie at the bottom of the third and eighth columns. The King of hearts can leave only for a cell or an empty column, and in Eight Off a column only comes free when every card in it has gone.
Our search went through all 14,688 positions this deal can reach. In about three of every four, all eight cells are full. The most cards ever on the foundations at once is six, and no heart ever reaches its foundation at all.
Pyramid #12: a proof you can do by hand
Some deals can be settled with a pencil. In Pyramid you remove pairs that add up to 13, and an Ace counts as 1, so an Ace can only go with a Queen. Two cards in one line of the pyramid, where one covers the other, can never be removed together.
In Pyramid #12 the Ace of diamonds and the Ace of spades are both in the pyramid, and there is no Queen in the stock. The Queens of clubs, diamonds and spades all lie in one line with both Aces. That leaves a single Queen, the Queen of hearts, for two Aces. Whatever you do, one Ace stays behind, and the pyramid cannot be cleared.
Same cards, different rules
Every game here except Spider uses the Microsoft FreeCell numbering, so a number gives the same 52 cards in the same order, laid out by each game's rules. That makes for some odd pairs.
- FreeCell #11982, the most famous impossible deal, comes out as Baker's Game, where you may only build by suit: our solver won it in 40 moves. It can be won as Seahaven Towers too.
- It works the other way far more often. Baker's Game #10 cannot be won; FreeCell #10 can. Our solver played all 25,069 impossible Baker's Game deals again as FreeCell, with the same cards in the same places, and won 24,832 of them. It is the rule, not the cards.
- FreeCell #1 can be won; Golf #1, the same shuffle, cannot. In Golf all four Aces and all four Kings land in the columns, the first pile card is the 10 of hearts, and none of the seven free cards fits it. Our search of its 179,468 positions found that even the best play leaves six cards on the table.
- Spider deals two packs, so its numbers give different cards, but a Spider number lays out the same ranks in the same places with one, two or four suits. Among the deals our solver missed with one suit are some it won with two, the harder game. Deal #1 is one of them.
What impossible deals look like
Impossible deals do not announce themselves, but some layouts lose far more often than others, and most of the signs can be read before your first move.
- Buried Aces. In Eight Off, three or four Aces at the bottom of columns make a deal nearly fifty times as likely to be impossible as no Ace there. In Baker's Game, 86.7% of deals with 8 cards or fewer on top of the four Aces can be won, against 60.4% with 15 or more.
- Nothing to start with. In Eight Off, 55 of the 71 impossible deals are among the 16,757 where no card goes up before the first move. Kings make no difference there.
- Too many Aces, Queens and Kings in Golf. An Ace goes only on a 2, a King only on a Queen, and nothing goes on a King. With ten or more of these cards dealt into the columns, only 10.2% of deals can be cleared; with six or fewer, 47.5%.
- No partner in Pyramid. In 3,066 of the first 20,000 deals, 15%, some card has no possible partner at all, so the deal is lost before the first move. Pyramid #12 shows that two cards chasing one partner do the same.
- Few links in TriPeaks. Count the pairs one rank apart among the ten face-up cards. With three or fewer, about one deal in nine cannot be won; with eight or more, one in 64.
These are odds, not verdicts. Even the worst TriPeaks openings are won nine times in ten, and most impossible TriPeaks deals are near misses: in 2,616 of them the best possible play clears 27 of the 28 cards. You cannot tell an impossible deal by its looks alone. Only a search can.
Why deal them at all?
Shuffling a pack is easy. Knowing whether a shuffle can be won takes a solver and a lot of computing. So most places deal whatever the shuffle gives and say nothing, and a player who loses an impossible game never learns that nobody could have won it. In Golf that is three games in four; in Baker's Game, one in four.
Here no deal reaches you until our solver has won it and the game has replayed the win. New game picks only from those lists. A number you type is checked first, and if it is proven impossible, you see a message like this one:
Game #465 can't be won, so here is game #…, which can be won.
The second number is a winnable game picked at random. For a number our solver has not won, the message says it has no known solution instead, because "can't be won" is a proof and "no known solution" is not.
So when you lose a game here, there was always a way through to find. Undo and Restart are there to look for it.
Where the numbers come from
The FreeCell results are public work by other solvers. Every other number here comes from our own solver, deal lists and searches. How many games can be won, game by game. Why we made Fair Solitaire.