Mahjongg Solitaire
Back in the very early days of personal computing I ran across a solitaire-style game called Mahjongg. For a little while I was quite addicted but was very frustrated that the version of the game I was playing would present boards that were not solvable. This just seemed cruel and unfair. I decided to write a version what would use only boards that could be won.
The first step was to generate winnable boards. I wrote a very simple algorithm to generate all possible winnable boards. I started it executing and no output appeared. I waited a few minutes and nothing. I let it run all afternoon and still nothing. This was my first introduction to polynomial-time algorithms. After 24-hours with no results I finally did some calculations by hand and realized it would take weeks to get an answer. So I went back to the drawing board and developed a different approach.
I had a big insight while designing this game. I wanted to include an Undo move feature. The obvious approach that I had seen others use was to keep a stack where each item is the current game state. To undo a move you pop an item off the stack. The downside is that if the game state is large and you have a lot of moves the stack can take up a lot of memory. Looking for an alternative I had the insight that it wasn't really necessary to save the entire game state if you just save the sequence of moves that were made. To "undo" a move, you actually replay the entire game up to the previous move, but without showing any of the moves occurring. Then display the state of the board and it looks like you just did an "undo." This would never have been feasible in the early days of computing when machines were very slow but modern machines are so fast they can replay hundreds of moves before you even have time to look up from the keyboard. This solution was a mental breakthrough for me in leveraging the power of modern processors to achieve a simpler algorithm.
When Java and Swing appeared I got excited about migrating my code to this new language and developed a full-featured version. It has only one tileset but it's my favorite one. It keeps a history of games solved, duration, etc. You can undo moves, get hints when you're stuck, and so on. A fun feature is the ability to view an animation of the solution steps. I recently put it up on SourceForge for anyone to use or copy (MIT license).
