Table of Contents
Terms used throughout the Code
An extended state is canonised by its stacks being uniquely sorted according to their contents, and an array of indexes describing their original locations sorted accordingly. This is done to make sure no two states with the same permutation of states exist.
The number of successive state → state.parent operations it take to reach the initial state which is the base of the states graph.
In Depth-First-Search (DFS): the position of the state in the recursion stack.
A false impossible is an initial board position for which the solver reports as impossible to solve, yet can be solved in some way. A false impossible may be considered a bug depending on the context.
A meta-moves-based scan can potentially have false impossibles, while an atomic moves one (which does not prune in any way) cannot.
See False Impossible.
Short for "fc_solve_" or "freecell_solver_".
a generic name of the API used by the programmer who wishes to utilise the Freecell Solver library in his application. Named after the prefix of the functions of this library.
The states in the state collection form a directed graph. Each link is a state → derived state relationship.
A Depth-First Search scan that uses procedural recursion. Since suspending a scan and resuming it are O(d) operations (where d is the depth) instead of O(1) for Soft-DFS its use is deprecated. As a result of this, Hard-DFS was removed from the code, and when being specified, it is implemented by Soft-DFS.
Hard-DFS was the original scan supported by Freecell Solver 0.2.0.
A collection of soft threads, that should generally be placed in one system thread. Hard thread contains resources that soft threads from different hard threads would interfere with each other in allocating. Hard threads contain a collection of state packs, and various counters and other variables.
An initial board, a collection of states and all
the scans associated with it. An instance is
initialised whenever one wishes to solve new board.
By using command line parameters it is possible to
configure it to solve the board in many ways.
Instance logic is implemented in
intrface.c
, and the user API
is implemented in lib.c
. Users
are advised to make use of the command line
interface in cmd_line.c
.
An initial layout of the board that cause the solver to terminate the scan prematurely (due to limitations on the iterations and the such) without determining whether the board was solvable or not.
the number of states checked by a scan, or by all the scans of a hard thread or of an instance. An iterations limit (called num_times in the code) is used to restrict a soft thread, hard thread or instance from running too long, and to allocate time quotas for different soft threads.
A move that consists of several individual moves done as one, to move from state to a derived state. Some of the Freecell tests and all of the Simple Simon tests generate meta-moves.
A one-time displacements of cards from stacks to stacks, from stacks to freecells, or from freecells to stacks. Also contain some special moves such as those for canonising stacks, and separators. Also see Move Stacks.
A sequence of moves implemented in its own object
(check move.c
and
move.h
).
normalisation is the opposite of canonisation. It is meant to bring the stacks and freecells to their absolute locations. It is normally done only when presenting a state to the user or to a code that uses the API.
The state from which one state in the state graph was initially derived from. It is possible that this state would eventually be reached from a different state, but its parent in that case, remains the same.
A structure specifying the type of game
according to number of stacks, number
of freecells, number of decks, whether
kings can be placed in empty stacks, if
sequences have unlimited moves, and how
stacks are built by. Defined in
preset.c
.
A set of command line arguments to be
processed as if they were given on the
command line. Can be used to shorten
command lines. For instance "-l
cool-jives" or "-l john-galt-line" load
the presets "cool-jives" and
"john-galt-line" respectively.
Implemented mostly in
cmd_line.c
.
Let's suppose state DEST has been derived from state SRC. If the SRC.depth+1 is less than DEST.depth than DEST's parent will be reassigned to SRC. (if reparenting is enabled)
A depth-first search scan that does not utilise procedural recursion. In Freecell Solver, this utilises a stack of records, each containing the current state, the current test, the list of derived states, and other information. This deviates from the standard scheme that puts every state at the end of one stack scheme (that exists in LM-Solve for example) and is harder to maintain, but can be fine-tuned and conserve resources more easily.
A singular continuous scan operating on a states collection. It can be Soft-DFS, Hard-DFS or Best First Search. There could be any number of soft threads in a hard thread.
Move Stacks (refer to them)
Columns of the Freecell-like games.
The stack used for maintaining the Soft-DFS recursion.
The environment recursion stack.
The position of the game at any given situation. A state accurately describes the contents of the stacks, freecells, and foundations at any given time. A human seeing a state can solve the game from it without further information.
A collection that collects every state once and only once. It can be sought of as an associative array (or a map) of keys (the fcs_state_t) to values (fcs_state_extra_info_t)
A grouping of tests/move funcs that dictate which one should be performed one after the and placed into the same derived states list. Afterwards, this list can be randomised, or prioritised.
A function that accepts a source state as input and fills a list of derived states according to the moves it can perform. Each game type has several type of tests, which can be ordered and grouped according to input from the user. Now the term "move function/func" is preferred.