|
November 2000 Programmer's Challenge
FreeCell
Mail solutions to:
progchallenge@mactech.com
Due Date: 11:59pm ET, Wednesday, 1 November 2000
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:
typedef enum {
kNoSuit=0, kSpade, kHeart, kDiamond, kClub
} Suit;
typedef enum {
kNoSpot=0,
kAce, k2, k3, k4, k5, k6, k7, k8, k9, k10,
kJack, kQueen, kKing
} Spot;
typedef struct Card {
Suit suit; /* the suit of the card, kSpade .. kClub */
Spot spot; /* the spot of the card, kAce .. kKing */
} Card;
typedef enum { /* places to move cards from */
sFreeCellA=2,sFreeCellB,sFreeCellC,sFreeCellD,
sTableau0=6,sTableau1,sTableau2,sTableau3,
sTableau4,sTableau5,sTableau6,sTableau7
} Source;
typedef enum { /* places to move cards to */
dHome=1,
dFreeCellA=2,dFreeCellB,dFreeCellC,dFreeCellD,
dTableau0=6,dTableau1,dTableau2,dTableau3,
dTableau4,dTableau5,dTableau6,dTableau7
} Destination;
typedef struct Move { /* move a card from theSource to theDestination */
Source theSource;
Destination theDestination;
} Move;
typedef struct Tableau { /* each Tableau can contain 0..19 cards */
Card theCard[19];
} Tableau;
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 6 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.
Test code for this Challenge is available.
You can get a head start on the Challenge by reading the
Programmer's Challenge mailing list. It will be posted to the list on
or before the 12th of the preceding month. To join, send an email to
listserv@listmail.xplain.com
with the subject "subscribe challenge-A". You can also join the
discussion list by sending a message with the subject "subscribe
challenge-D".
|
Slashdot
Digg
del.icio.us
reddit
newsvine
Y! MyWeb
