Free Cell is the solitaire card game that Paul Alfille introduced to the PLATO system in 1978. Jim Horne, at Microsoft, changed the name to FreeCell and reimplemented the game for DOS, then Windows.
This version introduced 32000 numbered deals. (The FreeCell FAQ tells this history.)
As the game became popular, Jim Horne disclosed the algorithm, and other implementations of FreeCell began to reproduce the Microsoft deals.
These deals are numbered from 1 to 32000. Newer versions from Microsoft have 1 million deals, numbered from 1 to 1000000; some implementations allow numbers outside that range.
The algorithm uses this linear congruential generator from Microsoft C:
- randn is in range 0 to 32767.
- Rosetta Code has another task, linear congruential generator, with code for this RNG in several languages.
The algorithm follows:
- Seed the RNG with the number of the deal.
- Create an array of 52 cards: Ace of Clubs, Ace of Diamonds, Ace of Hearts, Ace of Spades, 2 of Clubs, 2 of Diamonds, and so on through the ranks: Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King. The array indexes are 0 to 51, with Ace of Clubs at 0, and King of Spades at 51.
- Until the array is empty:
- Choose a random card at index ≡ next random number (mod array length).
- Swap this random card with the last card of the array.
- Remove this random card from the array. (Array length goes down by 1.)
- Deal this random card.
- Deal all 52 cards, face up, across 8 columns. The first 8 cards go in 8 columns, the next 8 cards go on the first 8 cards, and so on.
Order to deal cards | Game #1 | Game #617 |
---|---|---|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
JD 2D 9H JC 5D 7H 7C 5H KD KC 9S 5S AD QC KH 3H 2S KS 9D QD JS AS AH 3C 4C 5C TS QH 4H AC 4D 7S 3S TD 4S TH 8H 2C JH 7D 6D 8S 8D QS 6C 3D 8C TC 6S 9C 2H 6H |
7D AD 5C 3S 5S 8C 2D AH TD 7S QD AC 6D 8H AS KH TH QC 3H 9D 6S 8D 3D TC KD 5H 9S 3C 8S 7H 4D JS 4C QS 9C 9H 7C 6H 2C 2S 4S TS 2H 5D JC 6C JH QH JD KS KC 4H |
Deals can also be checked against FreeCell solutions to 1000000 games. (Summon a video solution, and it displays the initial deal.)
Write a program to take a deal number and deal cards in the same order as this algorithm. The program may display the cards with ASCII, with Unicode, by drawing graphics, or any other way.
#include <windows.h> #include <iostream> //-------------------------------------------------------------------------------------------------- using namespace std; //-------------------------------------------------------------------------------------------------- class fc_dealer { public: void deal( int game ) { _gn = game; fillDeck(); shuffle(); display(); } private: void fillDeck() { int p = 0; for( int c = 0; c < 13; c++ ) for( int s = 0; s < 4; s++ ) _cards[p++] = c | s << 4; } void shuffle() { srand( _gn ); int cc = 52, nc, lc; while( cc ) { nc = rand() % cc; lc = _cards[--cc]; _cards[cc] = _cards[nc]; _cards[nc] = lc; } } void display() { char* suit = "CDHS"; char* symb = "A23456789TJQK"; int z = 0; cout << "GAME #" << _gn << endl << "=======================" << endl; for( int c = 51; c >= 0; c-- ) { cout << symb[_cards[c] & 15] << suit[_cards[c] >> 4] << " "; if( ++z >= 8 ) { cout << endl; z = 0; } } } int _cards[52], _gn; }; //-------------------------------------------------------------------------------------------------- int main( int argc, char* argv[] ) { fc_dealer dealer; int gn; while( true ) { cout << endl << "Game number please ( 0 to QUIT ): "; cin >> gn; if( !gn ) break; system( "cls" ); dealer.deal( gn ); cout << endl << endl; } return 0; } //--------------------------------------------------------------------------------------------------
Output:
GAME #1 ======================= JD 2D 9H JC 5D 7H 7C 5H KD KC 9S 5S AD QC KH 3H 2S KS 9D QD JS AS AH 3C 4C 5C TS QH 4H AC 4D 7S 3S TD 4S TH 8H 2C JH 7D 6D 8S 8D QS 6C 3D 8C TC 6S 9C 2H 6H GAME #617 ======================= 7D AD 5C 3S 5S 8C 2D AH TD 7S QD AC 6D 8H AS KH TH QC 3H 9D 6S 8D 3D TC KD 5H 9S 3C 8S 7H 4D JS 4C QS 9C 9H 7C 6H 2C 2S 4S TS 2H 5D JC 6C JH QH JD KS KC 4H
OOP version
This is written using a more object-oriented approach than the version above.
#include <string> // std::string #include <iostream> // std::cout #include <sstream> // std::stringstream #include <vector> // std::vector using namespace std; //------------------------------------------------------------------------------ class Random { public: void init(uint32_t seed) { _seed = seed; } int roll() { return (_seed = (_seed * MULT + INCR) & MASK) >> 16; } private: int _seed; enum { MULT = 214013, INCR = 2531011, MASK = (1U << 31) - 1 }; }; //------------------------------------------------------------------------------ class Card { public: Card(int value) : _value(value) { } int suit() const { return _value % 4; } int rank() const { return _value / 4; } string str() const { stringstream s; s << _ranks[rank()] << _suits[suit()]; return s.str(); } private: int _value; const char* _suits = "CDHS"; const char* _ranks = "A23456789TJQK"; }; //------------------------------------------------------------------------------ class Deck { public: Deck(int seed) { _random.init(seed); for (int i = 0; i < 52; i++) _cards.push_back(Card(51 - i)); for (int i = 0; i < 51; i++) { int j = 51 - _random.roll() % (52 - i); swap(_cards[i], _cards[j]); } } string str() const { stringstream s; for (int i = 0; i < _cards.size(); i++) s << _cards[i].str() << (i % 8 == 7 || i == 51 ? "\n" : " "); return s.str(); } private: vector<Card> _cards; Random _random; }; //------------------------------------------------------------------------------ int main(int argc, const char * argv[]) { { Deck deck(1); cout << "Deck 1" << endl << deck.str() << endl; } { Deck deck(617); cout << "Deck 617" << endl << deck.str() << endl; } return 0; }
- Output:
Deck 1 JD 2D 9H JC 5D 7H 7C 5H KD KC 9S 5S AD QC KH 3H 2S KS 9D QD JS AS AH 3C 4C 5C TS QH 4H AC 4D 7S 3S TD 4S TH 8H 2C JH 7D 6D 8S 8D QS 6C 3D 8C TC 6S 9C 2H 6H Deck 617 7D AD 5C 3S 5S 8C 2D AH TD 7S QD AC 6D 8H AS KH TH QC 3H 9D 6S 8D 3D TC KD 5H 9S 3C 8S 7H 4D JS 4C QS 9C 9H 7C 6H 2C 2S 4S TS 2H 5D JC 6C JH QH JD KS KC 4H
Content is available under GNU Free Documentation License 1.2.