Note that it still only contains bullets, and will be filled with more
info as time goes by. I depreciated a previos summary on which I focused
on too many minor points and organized the material chronlogically instead
of logically.
In any case, comments, suggestions, flames are welcome. Please post them
to the list.
Regards,
Shlomi Fish
The Freecell Solver 0.2 Architecture:
-------------------------------------
* A DFS scan - give pseudo-code.
* Several tests to get to subsequent moves - give some examples.
* Outputs the intermediate boards to the screen.
The State Collection Representation:
------------------------------------
* B-search based merge to add the sort margin instead of qsort.
* Pointers to structs instead of a vector of whole structs.
* A balanced binary tree.
* A hash table.
- Using a 4-byte wide XOR as the hash function.
- Using MD5 as the hash function.
The State Representation:
-------------------------
* Chars and half-chars instead of shorts and ints.
* Pointers to stacks instead of a vector of stacks.
- A cache of stacks.
* Remember the original stack and freecell locations using the
"Indexes out of Bounds of Main Data Structure"<tm> - anti-patent
pending technology.
Abstracting the Game:
---------------------
* Variable number of Freecells and Stacks.
* The game play options:
- Empty stacks filled by any card/kings only/none,
- Sequences are built by suit/alternate colour/rank
the is_parent_card() macro.
- Unlimited sequence move.
* Presets: setting those settings automatically by selecting a preset.
Scans:
------
* The original Hard-DFS scan.
* A*
* Soft-DFS rev. 1.
* Soft-DFS rev. 2.
* The BFS optimization scan.
Move Stacks:
------------
* In the beginning, the user had to deduce what had happened between two
subsequent states.
* That was:
A. Not comfortable.
B. Even harder for a Freecell implementation to do on its own.
* I created the concept of move stacks, which each test loaded with the moves
that were it performed.
* Those stacks were later collected into one stack, to get the total move
stack from the initial board to the final solution.
----------------------------------------------------------------------
Shlomi Fish shlomif_at_vipe.technion.ac.il
Home Page:
http://t2.technion.ac.il/~shlomif/
Home E-mail: shlomif_at_techie.com
If:
1. A is A
2. A is not not-A
does it imply that
1. B is B
2. B is not not-B
Received on Wed Oct 31 2001 - 09:18:23 IST