Klotski Solver

One winter I found myself addicted to the game Klotski. To win, slide blocks until the big red piece reaches the bottom.

➜

Klotski is one of those frustrating Flappy bird-esque, can't-quite-quit games, that eats away at every ounce of my mental energy. I couldn't quite solve some tricky levels, but didn't want to fully cheat, so I wrote a solver in C++ as a compromise.

I used a BFS to find the optimal solution with a couple very primitive performance choices. It was suprisingly quick to solve the puzzles through a exhaustive search.

At the time I had only just learned about graph traversal algorithms and had no idea that it was possible to treat a solution space as a graph. Discovering that on my own felt like a pretty big revelation, even though in hindsight it now feels quite elementary.

I'm sure other's have more fault-tolerant solvers, but you can find it below if you want to use it. There's a brief description in the code of how to set up the board, I know a desperate soul trying to finish one last level can figure it out.