This is a little pet project I did a while ago. It’s a FreeCell puzzle‘s solver API.

The idea is to provide a basic validation engine and board management (pretty much like my old chess validation), so people can write FreeCell solvers on top of it. It has basic board setup (of multiple sizes), movement legalisation, and a basic Solver class, which you must derive to create your own solvers.

There’s even a BruteFroceSolver that can solve a few small boards, and that gives you an idea on how to create your own solvers. However, the API is not clear enough yet that children could start playing with it, and that’s the real goal of this project: to get kids interested in solving complex optimisation problems in an easy way.

Freecell is a perfect game for it. Most boards can be solved (only a handful of them were proven – by exhaustion – not solvable), some movements can be rolled back and you can freely re-use cards that have already been placed into the foundations (their final destination) back in the game again.

It’s out of the scope of this project to produce a full-featured graphic interface for kids, but making the API easy enough so they understand the concepts without dragging themselves into idiosyncrasies of C++ is important.

Compiler optimisations

The reason why I did this was to make some of the optimisations compiler engineers have to do more appealing to non-compiler engineers or children with a taste for complex problems. But what does this have to do with compilers? The analogy is a bit far-fetching and somewhat reverse, but it’s interesting nevertheless and it was worth the shot.

Programming languages are transformed into graphs inside the compiler, which should represent the intentions of the original programmer. This graphs are often optimised multiple times until you end up with a stream of instructions representing the source code in the machine language.

Ignore for now the optimisations on those graphs, and focus on the final part: selecting machine instructions that can represent that final graph in the machine language (assembly). This selection can pick any assembly instruction at will, but it has to put them into a very specific order to represent the same semantics (not just syntactic) of the original program. Since many instructions have side effects, pipeline interactions, special flags set or cleaned up, it’s not trivial to produce correct code if you don’t check and re-check all conditions every time. This is a known complex optimisation problem and can be responsible for changes in speed or code size in orders of magnitude.

What does it have to do with the Freecell puzzle? Well, in Freecell, you have a number of cards and you have to put them in a specific order, just like assembly instructions. But in this case, the analogy is reverse: the “sequence” is trivial, but the “instructions” are hard to get.

There are other similarities. For example, you have four free cells, and they can only hold one value at a time. They are similar to registers, and manipulating them, gives you a good taste of how hard it is to do register scheduling when building the assembly result. But in this case, it’s much harder to spill (move the data back to memory, or in this case, card back to cascades), since there are strict rules on how to move cards around.

Reusing cards from the foundations is similar to expanding single instructions into a sequence of them in order to circumvent pipeline stalls. In real compilers you could expand a multiply+add (very useful for digital signal processing) into two instructions: multiply and add, if that gives you some advantage on special cases on special chips. In Freecell, you can use a 9 on top of a 10, to move an 8 from another cascade and free up a card that you need to clean up your freecells (registers).

I’m sure you can find many more similarities, even if you have to skew the rules a bit (or completely reverse them), but that’s not the point. The point is to interest people into complex optimisation techniques without the hassle of learning a whole new section of computer science, especially if that section puts fear in most people in the first place.

2 Replies to “FreeCell puzzles solver API”

  1. Hi,

    thanks for sharing this post – I added it and a link to your solver to the bottom of the other Solitaire solvers list on Freecell Solver’s homepage, where Freecell Solver is the (unfortunately) not too original name of some libraries and some command line programs, that attempt to solve Freecell and similar Solitaire games, all available as free and open source software (FOSS), under the MIT/X11 licence.

    I haven’t taken a closer look at the code, but judging by the license.txt in the master repository it should be GPLv3, which is something that while I can read to get some ideas from, I cannot incorporate directly into my solver.

    Anyway, if you’re interested in discussing automated and non-automated solving and research of Freecell and some other card games, you are welcome to join the fc-solve-discuss Yahoo Group (usable as a mailing list, but also possibly as a web forum) and introduce yourself. There are plenty of interesting discussions there, and it became more active recently. I administer the group but everyone is welcome to subscribe, read the pas messages, and post new ones, as long as they are not spam (which I assume is not the case for you).

    The parallels you make at the bottom of the post between Freecell are interesting, but maybe I’m too tired now to understand them. I often find that I have a hard time for me to understand people, who try to explain their solvers techniques, and it seems that while writing a rudimentary Freecell solver can be done pretty quickly, that’s just the tip of the iceberg, and there are many interesting and non-trivial techniques available.


    Shlomi Fish

    (Sorry if this post came out malformed, but I don’t see a preview button – god damn WordPress).

  2. Oh, I should note that I found this post when searching Google for “Freecell” using the Creative Commons search. I have now placed a blanket CC-by licence on the pages of the Freecell Solver site. Thanks for prompting me to do it.

Comments are closed.