Tom on the Internet

Freecell Solver

Freecell

When I was young, I decided to play a lot of Freecell.

I had Windows computers as a teenager and they all had a version of Freecell. Freecell was great because it worked without internet, and it was boring enough that my parents didn't really consider it gaming. I'd play it while listening to MP3s in Winamp.

I don't know how many games I played, but I was never a great player. I could solve most of the games I played, but not all.

Many, many years later, I became a programmer and I started to think back about the computer games I played as a kid. I realized I could now program many of the games I used to play. The thought was exciting. I wished I could go back and talk to the men who'd written the old games I played. What editor did they use? Were they writing in C? Were they excited to be able to write programs?

One day, I believe while I was taking a shower, I started thinking more about Freecell. Could I write a program that would solve Freecell games? It seemed like I could.

A Basic Implementation In My Head

Here's how I thought about writing a Freecell solver. Most of my initial thoughts ended up being pretty close to the mark.

  1. Given a game board, collect all possible moves.
  2. Give each possible move a weight. The higher the better. A move would be considered better if it put a card in the top right (which, it turns out, is called the foundation).
  3. Repeat until the game is won.

This basic algorithm is a good first approximation of the problem and it lingered in my head until I decided I had to try it out. When I finally did, I realized my simple algorithm would not be enough, but I was on the right track.

A Working Implementation

My working implementation has a few pieces:

  1. The A* search algorithm.
  2. A priority queue.
  3. A heuristic.

I wrote it in TypeScript and run it with Bun.

The A* algorithm is a pathfinding technique that helps the solver efficiently search for a solution by always exploring the most promising moves first. The priority queue keeps track of which game states to explore next, and the heuristic is my custom way of measuring how close a board is to being solved.

A priority queue is a data structure that allows you to efficiently retrieve the highest priority item. In this case, it helps us quickly find the next best move based on the heuristic's weight.

A heuristic is a function that estimates the cost of reaching the goal from a given game state. In this case, it helps us determine how close a board is to being solved.

Step by Step

  1. A deck of cards is shuffled.
  2. The cards are placed on a Freecell board.
  3. Every possible move on the current board is weighted using the heuristic (more on that soon).
  4. All possible moves are placed into a priority queue with their weights.
  5. The next best move becomes the game state.
  6. Repeat until done (or until we've seen over 200,000 game states at which point I surrender).

The Heuristic

The heuristic is turns out is the secret sauce. It's the most important part of solving Freecell.

My heuristic weights a game board by looking at:

  • Cards Left
  • Buried Cards
  • Disorder
  • Low Cards
  • Foundation Gaps
  • Missing Suit
  • Can Move to Foundation
  • Free Cells
  • Empty Columns

Basically, my heuristic is my way of saying "how close is this game to being solved?". And since it's mine, it has all my own biases.

Closing Thoughts

This was fun.

I've built a Freecell solver that can solve most games. I just ran it and solved 100 games in 33 seconds. Most of those games were solved in well under a second, but some games took 5 or 6 seconds. My solver is great at some boards, and not great at others.

The A* algorithm is such a great tool and one that I'm sure I'll keep using.