next up previous
Next: Conclusions Up: An unsolvable instance of Previous: Introduction

An unsolvable instance of Free Cell

Consider the following starting position of Free Cell.

2 2 2 2 A A A A
8 8 8 8 7 7 7 7
K K K K 6 6 6 6
Q Q Q Q 5 5 5 5
J J J J 4 4 4 4
10 10 10 10 3 3 3 3
9 9 9 9

This position does not have a solution. Actually, a somewhat more general result will be proved.

Proposition 1. Every starting position of FreeCell, fulfilling the following properties, does not have a solution.

Proof. To show that there is no solution to the given starting position, the following invariants are postulated.

Note that these invariants hold for the given starting position. Now, suppose that the invariants hold for an arbitrary position. We now claim, that for any legal move of a single card from this position, the invariants also hold for the position after the move.

The first thing to note is that the move cannot be a move of a King or a Seven. Look at a King card. It must belong to one of the first four columns. The three other columns of the first four can contain at most three Queens, Jacks, 10s, and 9s. Thus, a Queen, a Jack, a 10, and a 9 must belong to the column of the King or be on a free cell. There are two cases. The first case is that each of these cards is on a free cell. Now, the King cannot be moved, as there is no free cell, and it certainly cannot be moved to a home cell.The second case is that there is at least one free cell. Now, the column with the King must contain a Queen, Jack, 10, or 9. Look at the highest card below the King that belongs to the column. This must be a Queen, because each Jack, 10, and 9 in the column lies below a card of value one higher. Note that this Queen is below the King, hence the King is not the bottom card of the column, hence cannot be moved. With a similar argument, we see that Sevens cannot be moved.

As Aces, 8s, and 2s lie above Kings and Sevens, the move cannot be a move with such a card. Hence, we also cannot move an Ace to a home cell, and as home cells do not contain Aces, no other card can be moved to a home cell to.

It is not possible to move a Queen, Jack, 10, or 9 to one of the last four columns, as these are not empty, and do not contain a King, Queen, Jack, or 10. Similarly, we cannot move a 6, 5, 4, or 3 to one of the first four columns.

Now, verifying that the invariants hold for the position after the move is straightforward for all but the one-but-last invariant. Suppose that, after moving a card of value x, a column contains two cards of the same value. As we assumed that no column contained two cards of the same value before the move, the card must be moved to a column that contained already a card of value x. Now, this last card must lie below a card of value one higher, call this x+1. Also, the bottom card of the column, before the move, must have had value x+1 (by the rules of FreeCell). So, the column contained two cards of value x+1 before the move; contradiction. It follows that the one-but-last invariant holds after the move.

We now have shown that whatever sequence of legal moves we make, the invariants will remain valid for the resulting positions. It follows that we never can move any card to a home cell, hence the starting position has no solution. Q.E.D.



next up previous
Next: Conclusions Up: An unsolvable instance of Previous: Introduction



Hans Bodlaender
Fri Jul 12 16:18:16 MDT 1996