Next: An unsolvable instance Up: An unsolvable instance of Previous: An unsolvable instance of

Introduction

One of the additional programs, that are included with Windows'95, Microsofts operating system for personal computers, is a (computer program that simulates a) card puzzle game, called FreeCell. In this card game, the player is given an arrangement of all 52 cards of a standard deck of cards in eight columns, i.e., four columns with seven cards, and four columns with six cards. The cards are shown open face, i.e., the player knows the exact location of all cards. Additionally, there are four free cells, and four home cells. The object of the game is to move all cards to the home cells, moving cards one at the time, under the following rules:

• Any card that is at the bottom of a column can be moved to an empty free cell. A free cell can contain at most one card.
• An Ace may be moved to an empty home cell. Other cards may be moved to a home cell that contains the preceding card of the same suit. E.g., after the Ace of Hearts is moved to a home cell, one can then move the 2 of Hearts to a home cell, etc. Cards at a home cell cannot be moved anymore.
• Any card that is at the bottom of a column or at a free cell can be moved to an empty column.
• Any card that is at the bottom of a column or at a free cell can be moved to the bottom of a column whose bottom card is of a contrasting color, and one higher in value.
For completeness: the order of the cards is, from high to low: King, Queen, Jack, 10, 9, 8, 7, 6, 5, 4, 3, 2, Ace. Red suits are Hearts and Diamonds, and black suits are Spades and Clubs.

As an example, look at the opening setup in Figure 1.

Possible moves in the starting position shown above are e.g., moving the Ace of Spades to a home cell, or moving the five of Hearts below the Six of Spades. When we would move the Seven of Clubs to a free cell, we can then move the 2 of Spades and the 3 of Spades to the home cell with the Spades. (Note: this position 21803 is solvable.)

Object of the game is to move such that finally all cards are on the home cells.

In the Help-file of the program, the following statement is made:

It is believed (although not proven) that every game is winnable.

This note disproves this conjecture, by showing a starting position for Free Cell that cannot be won.

Actually, recently, it was verified by a computer search that even one instance generated by the Freecell program is not winnable [ The Internet FreeCell Project, link no longer functional].

Next: An unsolvable instance Up: An unsolvable instance of Previous: An unsolvable instance of

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