Freecell Solver was available under the public domain when this talk was originally written (now it is under the MIT/Expat licence). This lecture, on the other hand, has now been licensed under the Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) licence (or at your option any later version).
I hereby disclaim any damage that reading this work may cause you, either implicit or explicit, direct or indirect.
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";
The most probable reasons: less memory -> less cache misses, and handling bytes is just as fast as handling ints.
Update: It may also have to do with the limited size of the CPU cache lines, typically 32 bytes on 32-bit x86 CPUs. The more items fit into a cache lines, the less cache misses there are.
Markus Oberhumer (of PySol fame) asked if I thought about converting Freecell Solver to C++. (I suppose he meant with STL, templates and all). Here is a full answer why I'm not going to do it:
I'm more willing to integrate C++-derived features there into the C code. Things like namespaces, (non-inherited) classes, or inline functions. However, for the time being, I'd like to maintain the code as pure C.
For that matter, some of the gcc extensions can prove very useful too, but I cannot use them either.
I hoped you enjoy the lecture, and that it brought or reminded you of important programming insights, as much as developing the program was beneficial for me in this regard.
Update: I originally planned to write a book, but abandoned that idea for various reasons. You can find a copy of the latest draft of the book and some other documentation on the Freecell Solver site
Enjoy!