7
This document aims to be an overview of the Freecell Solver architecture. If
8
you have any questions regarding it or want some things to be modified
9
or clarified, please send your request to the Freecell Solver mailing-list.
12
http://groups.yahoo.com/group/fc-solve-discuss/
14
The main author of this document (and Freecell Solver in general) is Shlomi
15
Fish. This document assumes knowledge regarding how to play Freecell and
16
similiar games. Information about how to play them can be found in the
17
documentation of PySol (http://pysol.tsx.org/).
19
This document is distributed under the public domain.
30
1.3.1 card, suit, card number and flipped status
31
________________________________________________
33
A card has a suit and a card number. A suit is one of Hearts, Spades,
34
Diamonds and Clubs, commonly abbreviated as H, S, D and C respectively.
35
The value of each suit in Freecell Solver is:
41
A card number is one of A, 2, 3, 4, 5, 6, 7, 8, 9, 10 (or in some notations
42
T), J, Q, K. A is 1 in Freecell Solver, and the others are in their order,
43
while a card number of 0 is reserved for the empty card. The card number is
44
sometimes referred to in the code as deck. This is an error, which may be
45
fixed in later versions of Freecell Solver.
47
A flipped status indicates whether the card faces down or faces up. In
48
Freecell type games all cards face up, but that's not the case for Gypsy or
52
1.3.2 stack, freecell, foundation
53
_________________________________
55
A heap of cards that is present on the playing board is called a stack in the
56
Freecell Solver terminology. It should not be confused with move stacks (see
57
below), the function call stack, or the Soft-DFS stacks.
59
A freecell is a placeholder for one card. Freecell and Seahaven Towers have 4
60
such freecells, but Der Katzenschwanz and Die Schlange have 8. Freecell Solver
61
supports up to 127 freecells, but their maximal number has to be set at
64
A foundation is the pile where all the cards needs to be moved to at the end
65
of the game, one card at a time starting at Ace, and up to Kings. In Freecell
66
Solver, each foundation is indexed according to its suit. If there is more
67
than one set of foundations, this numbering continues, in the sense that the
68
second hearts is #4, the third hearts is #8, etc.
70
A foundation is sometimes erroneously called a deck in the Freecell Solver
76
A deck is a pack of 52 cards, i.e: 13 cards of each of the four suits. As was
77
mentioned earlier, this term in the source code, sometimes refers to
78
foundations or card suits. Hopefully, this use will be eliminated as the
79
source code will be fixed.
84
A state is a static position of the playing board. That is, it is a snapshot
85
of all the stacks with all the cards they contain, as well as the freecells
86
and the value of the foundations.
88
Freecell Solver has several ways to represent a state in memory and they will
89
be explained in section 3.
91
1.3.5 Moves, Atomic Moves
92
_________________________
94
An atomic move is one of the following:
95
1. Moving a single card from one stack to the other.
96
2. Moving one card from a stack to an unoccupied freecell.
97
3. Moving one card from a freecell on top of a stack.
98
4. Moving one card from the top of one of the stacks to the foundations.
99
5. Moving one card from a freecell to the foundations.
101
Note that PySol also supports moving a card from the foundations back to the
102
stacks or the freecells. Freecell Solver does not support this kind of move
103
yet, and it is questionable whether it will ever will.
105
A move or supermove may also involve moving several cards at once from one
106
stack to the other. This can be either done by using unoccupied freecells and
107
vacant stacks, or in some variants of Freecell (like Relaxed Freecell) it can
110
1.3.6 Move Stacks and Multi-Moves
111
_________________________________
113
Move stacks constitute of an ordered sequence of one or more moves. Move
114
stacks and the way they are managed and handled will be covered in
115
greater detail in section 5.
117
A multi-move is a sequence of moves that aims to accomplish a certain task,
118
such as moving a particular card to the foundations, or moving one card on
119
top of the other. Freecell Solver moves from one state to the other using
120
multi-moves while not storing all of the intermediate states.
122
1.3.7 Canonizing and Normalizing States
123
_______________________________________
125
In order to avoid a situation where Freecell Solver inspects two states which
126
are essentially similiar except for the order of the stacks and freecells,
127
Freecell Solver sorts them in a deterministic order. This process is called
130
However, such states cannot be presented to the user, so it keeps an indexes
131
to the stacks and freecells outside the main data structure, so it can later
132
re-calculate their true positions. Those indexes are maintained along with
133
the stacks and freecells themselves.
135
When a state, or a move that operates on it, is brought from its canonized
136
order to the order that is presented to the user (which maintains a constant
137
position of stacks and freecells) it is called normalizing the move.
142
The functions contained in the card.c are responsible for converting
143
cards between their internal representation in the program and their
144
string representations.
146
There is nothing too sophisticated here: just a lot of parsing,
147
string making, and switch statements. Each function is preceded by
148
a comment that describes it so it should not be very hard to
149
understand. If something is still unclear, let me know by posting a
150
message to the mailing-list.
152
3. The state.h header file
153
==========================
155
3.1 How states are represented in FCS
156
-------------------------------------
158
There are three different ways to represent the states in Freecell Solver.
159
The choice of which one to use is available at compile-time by defining one
160
and only one of the macros DEBUG_STATES, COMPACT_STATES, and
161
INDIRECT_STACK_STATES at compile time.
166
Debug States is the oldest state representation method Freecell Solver had and
167
was already available in version 0.2. It was then called FAST_STATES, which
168
is erroneous because it proven to be much slower than Compact States which
169
will be covered in subsection 3.1.2.
171
It is also slower than Indirect Stack States, and thus should only be used
172
for debugging purposes if at all.
174
In Debug States, a card is represented as a 4-byte data structure:
177
struct fcs_struct_card_t
184
typedef struct fcs_struct_card_t fcs_card_t;
187
A stack is a data structure whose first element is an int that contains the
188
number of the cards in the stack, and the second an array of such cards, whose
189
size is MAX_NUM_CARDS_IN_A_STACK, which is a constant calculated from the
190
maximal number of initial cards in a stack and other parameters.
193
struct fcs_struct_stack_t
196
fcs_card_t cards[MAX_NUM_CARDS_IN_A_STACK];
199
typedef struct fcs_struct_stack_t fc_stack_t;
202
A state is MAX_NUM_STACKS such stacks, MAX_NUM_FREECELLS stand alone cards,
203
and MAX_NUM_DECKS*4 foundations.
added
removed
devel_docs/devel_docs/devel_docs/Architecture.txt
