Nov 00 Challenge
Volume Number: 16
Issue Number: 11
Column Tag: Programmer's Challenge
Programmer's Challenge
by Bob Boonstra, Westford, MA
FreeCell
Those of you who spend time on the Dark Side might have encountered a solitaire game
called FreeCell packaged with a prominent operating system by Mr. Bill. Your
Challenge this month is to produce a FreeCell player.
The prototype for the code you should write is:
kNoSuit=0, kSpade, kHeart, kDiamond, kClub
typedef enum {
kNoSpot=0,
kAce, k2, k3, k4, k5, k6, k7, k8, k9, k10,
kJack, kQueen, kKing
Suit suit; /* the suit of the card, kSpade .. kClub */
Spot spot; /* the spot of the card, kAce .. kKing */
typedef enum { /* places to move cards from */
sFreeCellA=2,sFreeCellB,sFreeCellC,sFreeCellD,
sTableau0=6,sTableau1,sTableau2,sTableau3,sTableau4,sTableau5,
sTableau6,sTableau7
typedef enum { /* places to move cards to */
dHome=1,
dFreeCellA=2,dFreeCellB,dFreeCellC,dFreeCellD,
dTableau0=6,dTableau1,dTableau2,dTableau3,
dTableau4,dTableau5,dTableau6,dTableau7
typedef struct Move { /* move a card from theSource to theDestination
*/
Source theSource;
Destination theDestination;
typedef struct Tableau { /* each Tableau can contain 0..13 cards */
Card theCard[13];
long /* numMoves */ FreeCell(
const Tableau theTableau[8], /* the cards as initially
dealt */
Move theMoves[], /* return your moves in order here
*/
long maxMoves /* storage is
preallocated for maxMoves theMoves */
);
The FreeCell game is different from many solitaire games in a couple of respects.
First, all of the cards are visible, so winning the game is more a matter of strategy
than of luck. Second, while there are FreeCell deals that cannot be solved, nearly every
game can be won, as contrasted with less than half of other popular solitaire games.
FreeCell starts with the playing Cards dealt face up into 8 piles called Tableaus. All 52
Cards are used, which means that the first four Tableaus receive seven Cards, and the
remaining four Tableaus receive six Cards. The object of the game is to move all of the
Cards onto four "Home" piles, one for each Suit, played in order from Ace up to King.
You also have available four temporary locations, or "Free Cells", each of which can
hold one Card. A Move consists of one of the following:
• moving an Ace from a Free Cell or from the top of a Tableau to an empty
Home pile
• moving the next higher Card of a Suit from a Free Cell or from the top of a
Tableau to the Home pile for that Suit
• moving a Card from the top of a Tableau to an empty Free Cell
• moving a Card from the top of a Tableau or a Free Cell to an empty Tableau
• moving a Card from the top of a Tableau or from a Free Cell to the top of a
Tableau, where the Suit of the Card on top of the destination Tableau has the
opposite color of the Card being moved, and where the Spot of the Card on top of
the destination Tableau is one higher than the Spot of the Card being moved.
Cards can be moved to or from a Free Cell, but each Free Cell can hold only one Card.
Cards can be moved to the Home piles, never back from the Home piles. Cards can be
moved to or from the top of a Tableau, but they can only be moved to a Tableau if the
Suit colors alternate and if the Card value (Spot) decreases by one. Any Card from a
Free Cell or the top of another Tableau may be placed on an empty Tableau.
Your FreeCell routine will be called with the Cards dealt into the 8 Tableaus. Your task
is to generate a sequence of Moves that solve the puzzle, returning them in theMoves.
Each Move consists of a Source and a Destination. It is not necessary to specify the Card
being moved, because the Source uniquely identifies the Card at any given point in the
game. FreeCell should return the number of Moves generated, or zero if you are unable
to solve the puzzle.
Your solution will be awarded 10,000 points for each puzzle it solves correctly, and
penalized 1 point for each millisecond of processor time required to solve the puzzle.
This will be a native PowerPC Challenge, using the CodeWarrior Pro 5 environment.
Solutions may be coded in C, C++, or Pascal.
This Challenge was suggested by Peter Lewis, who wins 2 Challenge points for the
suggestion. More information on the game FreeCell can be found at
http://www.freecell.org.
Three Months Ago Winner
Congratulations once again to Ernst Munter (Kanata, Ontario) for submitting the
winning entry to the August Longest Word Sort Challenge. Ernst's entry was the fastest
of the seven entries submitted, and was just under 40% faster than the second-place
entry by Jonny Taylor.
The Longest Word Sort Challenge required contestants to sort a sequence of lines of text
based on the length of words in each line. The line with the longest word was to be
considered greater than any other line. Among lines with longest words of the same
length, the comparison was to be based on the next longest word, etc. Among lines with
words of exactly the same length, the order was to be based on an alphanumeric
comparison of words, in order of length, and then in order of occurrence.
The key to Ernst's solution is the LineDescriptor that he uses to profile each line of
text. The LineDescriptor contains a packed description of the number of words of each
length contained in the line. This allows Ernst to compare lines by comparing the
numeric line profile values, using a single subtraction in the
LineDescriptor::IsLessThan routine to compare the number of words of several
lengths. In the event the LineDescriptors match exactly, the CompText routine
compares the words of each line as text, in order of word length. This Challenge
allowed the use of assembly language, and Ernst used one line of it in the BitsNeeded
routine, which is used by Text::ComputeFieldSizes to calculate the width of the packed
field needed to hold the number of words of a particular length.
Jonny Taylor's second-place solution uses a combination of sorting techniques,
starting with a radix sort to partially sort the list based on the lengths of the 16
longest words in each line, and then using a quicksort algorithm to sort groups of lines
with identical word lengths. Jan Schotsman's third place solution uses a merge sort to
compare groups of up to 32 lines, starting with a comparison of the lengths of the 16
longest words in each line, and resorting to a more careful comparison when
necessary. This Challenge certainly produces an interesting variety of approaches to
an unusual sorting problem. The table below lists, for each of the solutions submitted,
the cumulative execution time in milliseconds. It also provides the code size, data size,
and programming language used for each entry. As usual, the number in parentheses
after the entrant's name is the total number of Challenge points earned in all
Challenges prior to this one.
Name Time (msecs) Code Size Data Size Lang
Ernst Munter (631) 168 3384 330 C++