Freecell is played with a standard 52-card deck. At the beginning of play, all cards are dealt to 8 columns (7 cards each in the first four columns and 6 cards each in the other four) facing up.

Besides the columns (which will also be referred to as stacks), there are also four places to hold temporary cards (known as “freecells”) and four foundations, in which it is possible to place cards of the same suit starting from Aces and ending with Kings.

Sequences of cards on the tableau are built by placing cards on top of cards of a higher rank and of a different colour (black or red).

An atomic move consists of any of the following:

It is customary and helpful to group the movement of an entire sequence of cards, by moving intermediate cards to freecells or vacant columns. This will be referred to as a sequence move. If a sequence move involves temporarily moving a card to an empty column, it is known as a supermove.

You should probably play a few games of Freecell, in case you did not already, because knowing the rules alone is not enough to have an intuitive feel of it. There are many available Freecell implementations for various systems, and you should have no problems finding one that you can use. (Chances are that it is already installed on your system.)

There are several strategies that become apparent after a large amount of playing Freecell. One of them, is uncovering top cards so a card can be moved to the foundations. Another one, is doing the same only to move it to a parent card, or for it to serve as the basis of another sequence.

Another technique, that can be helpful at times is moving a card from the freecells back to the tableau, so it can serve as the base for another sequence.

FILL IN

The game Freecell is not the only Solitaire of its kind nor is the first historically. Using Freecell as a basis, several similar Solitaire variants can be constructed by adjusting some of the basic rules:

Below you can find a table that summarized the essential properties of a large number of Solitaire games similar to Freecell. Their names were taken from PySol, which is a free Solitaire suite written in Python. ^[2]

FILL IN the table

As I ran and thought about solving Freecell I reached several conclusions. One of them was that moving card at a time would probably be too slow to be effective, and that when going from one board layout to the another, I should probably perform several moves at once (such a composite of several moves is known as a meta-move). That way, I would hopefully reach a solution more quickly.

Then, I speculated whether it would be better to searching "Depth First" or "Breadth First". By depth first, I mean that whenever the solver reaches a new state (a state is a particular configuration of the cards on the board), it will try to recurse into further states before withdrawing from it. Breadth first means that the states would be scanned according to their vicinity to the initial state: first the states that are reachable from it one move, then those that are reachable in two, etc.

I concluded that the number of states in every depth probably expands by a very large factor, and the nearest solution is relatively deep, so the latter strategy would not be very wise to follow. A depth first search has a greater chance of returning a valid path to the solution in a reasonable time.

Another thing I thought about was that I should store the states that were already encountered in the search, so they won't be checked again and again. This would require implementing a collection of previous states

A short time after I ran, I started coding the solver in Perl 5. I wrote classes to represent a card and an entire Freecell board, and made sure I could input and output boards from and to text.

Then I started to write the algorithm. There were several guiding principles in the code:

The first C version I wrote was not identical to the Perl version algorithmically. As some things were more accessible in C than they were in Perl (or vice versa), I was able to take advantage of them (or was unable to).

                        struct struct_card_t
                        {
                        short card_num;   /* card_num is the rank */
                        short deck;       /* I erroneously referred to the suit as a deck */
                        };

                        typedef struct struct_card_t card_t;

                    

                        struct struct_stack_t
                        {
                        int num_cards;
                        card_t cards[19];
                        };

                        typedef struct struct_stack_t fc_stack_t;

                    

                        struct struct_state_t
                        {
                        fc_stack_t stacks[8];
                        card_t freecells[4];
                        int decks[4];  /* I also called the foundations decks. :-) */
                        };

                        typedef struct struct_state_t state_t;

                    

                        #define pop_stack_card(state, s, into) \
                        into = (state).stacks[(s)].cards[(state).stacks[(s)].num_cards-1]; \
                        (state).stacks[(s)].cards[(state).stacks[(s)].num_cards-1] = empty_card; \
                        (state).stacks[(s)].num_cards--;

                    

                        Solve-State(state, prev_states, ret)
                        if (state == empty_state)
                        Push(ret, state)
                        return SOLVED
                        for each move possible on state
                        new_state <- apply(state, move)
                        if (new_state in prev_states)
                        ; Do nothing
                        else
                        add new_state to prev_states
                        if (Solve-State(new_state, prev_states, ret) == SOLVED)
                        Push(ret, state)
                        return SOLVED
                        return UNSOLVED

                        Freecell-Solver(init_state)
                        if (Solve-State(init_state, Null, ret) == SOLVED)
                        print "State was solved"
                        while (state <- Pop(ret))
                        print state
                        else
                        print "I could not solve this board";

                    

Implementing a game AI system requires collecting the positions of the game that were reached so far, in order to mark them and make sure they are not visited times and again.

Such a position (also known as a state) has a 1-to-1 representation of the current state of the game. A solver, human or computerized, given an intermediate position in such form would be able to solve it without any other information.

The states collection of Freecell Solver evolved quite a bit since the first version, and I believe many lessons about programming efficient data structures can be learned from this evolution. By playing around with it, I was able to witness great speed improvements, and also come up with very good insights about what data structures would comprise of a good collection or dictionary.

The initial perl version sported a states collection implemented as an unordered list. I kept an array of states (it could have been a linked list, too) and whenever I encountered a newly visited state, I added it to the end of the array. To search for the existence of a state in the state collection, the list was scanned element by element.

Assuming a comparison and an assignment are O(1) operations (an assumption which would be kept for the rest of this chapter), then it can be seen that an insertion takes O(1) time while a lookup take O(n) time. Since we encounter many states, then we want the lookup to be as fast as possible. But in this case it is O(n).

O(n) is the worst possible lookup complexity for a collection, and as more states are collected, it will become worse and worse to lookup one in it. I became aware of this fact, as I noticed that the perl program ran very slowly. O(n) lookup is in most cases very unacceptable and you should avoid it whenever possible.

The first C version featured a sorted array as a states collection. In order to avoid the costly operation of incrementing all the positions of the higher states by 1, whenever a new state was added, I kept a sort margin that contained several unsorted states at the end.

A new state was first added to the end of the sort margin. When enough states were collected there, I merged the sort margin into the main array, by using the ANSI C qsort() function. This entire scheme had an acceptable running time.

Let's analyse the complexity of everything involved. Lookup can be done using a binary search on the sorted part followed by a linear search on the unsorted part. Since the unsorted part is at most a constant number of items, then going over it is O(1) and the entire operation is that of a binary search which is an O(log(n)) operation.

Assuming the number of elements collected in the sort margin is k, then adding k elements, would take O(n*log(n)) time, since the function qsort() uses Quick-Sort which has this complexity on average.^[3] O(n*log(n)) divided by a constant is still O(n*log(n)) so an insertion of an element is O(n*log(n)).

The accumulative time for adding n elements is O(n²*log(n)) which is the time for insertion multiplied by n.

I took a course about data structures and algorithms, the semester after I coded the first version of Freecell Solver. There I learned about the large complexity involved in quick-sorting, and that there was a better algorithm for merging two arrays: Merge. The Merge algorithm works like this:

This algorithm runs in linear time. I decided to use a variation of the algorithm, due to the fact that the sort margin could become so much smaller than the main array.

In my variation, the sort margin is scanned linearly, but the index of the corresponding element in the main array is found using a binary search. Once found, all the elements up to it, are copied as is without comparison. That way, one can hopefully save a lot of comparisons.

To facilitate the merge, the sort margin was kept sorted all the times, and middle elements pushed some of the elements forward.

Lookup now is still O(log(n)), but this time insertion was reduced to O(n) time. (the merging operation is O(n) and it is done every constant number of elements) The accumulative time now is O(n²) which is O(n) multiplied by n.

This scheme ran much faster than the qsort one - by a factor of 3 or so. While the qsort() scheme was adequate to give good results most of the time, a merge of the sort margin was a much wiser choice, algorithmically.

Freecell Solver 0.2 managed the states collection as an array in which the states' structs appeared one adjacent to the other. I also passed the entire struct as a parameter to solve_for_state. When I tried to run it on Microsoft Windows NT, I realized that sometimes the program ran out of stack. This was because it descended into a relatively large depth, while passing all the structs in it. To avoid it, I decided to pass pass pointers to the stacks, and to store the states as an array of pointers.

I did not want to individually malloc the structs, because I knew memory was often allocated in powers of 2, and so I can have a lot of it wasted. I first tried to allocate the states by allocating them from the end of one array that was realloced when necessary. However, I realized (after a long and frantic debugging session) that the newly allocated array may not retain its original place in memory, thus causing the pointers that were already collected to become defunct.

To avoid this, I devised a better scheme, in which I allocate the states in packs of constant size, and allocate more packs as necessary. Since the packs contain more than one state, and their size can be adjusted to accommodate for the whims of the underlying memory management, it was a good solution as could be found. ^[4]

With this management of memory, I converted the states collection to use an array of pointers instead of an array of structs. Not only did it consume less stack space, but it also ran much faster. The reason is that swapping and re-organizing pointers (which take 4 or 8 bytes each) is done much more quickly than re-organizing large structs. Plus, passing pointers on the stack is more efficient than passing and duplicating entire stacks.

This time the algorithmic order of growth was not reduced, but still there can be a difference of heaven and earth between a large O(n²) and a small O(n²)...