Klotski is a sliding block puzzle: You have ten wooden blocks of different sizes to slide around on a game board, so that the largest block gets to the exit. I had one of these puzzles as a kid, but never managed to solve it; more recently, I bought one as a birthday present for one of my brothers. The passing years had not noticeably improved my ability to solve the puzzle by hand, but I do have a degree in computer science now, and it struck me that Klotski looked like it might have a state space small enough to make a simple brute-force search feasible.

Full text: pdf