Monthly Archives: January 2009

Puzzle Solver

I’ve posted my first working puzzle solver here. It is based on a flexible framework with a high degree of abstraction, with the idea of adding new puzzle types easily; so performance is not the main goal. So far, it can solve Sudoku and Kakuro type puzzles; it will be fairly straightforward to build brute solvers (guess-and-check) for puzzles of the type where you fill a grid with one of a small number of tokens and there is only a single solution.

At one point I was considering creating a constraint language in which declarative rules could be expressed in a shorthand notation, but this is beginning to seem like a lot of work with a dubious payoff. For now, all the constraints are expressed as Java programs. My current plan is to add more puzzle types (perhaps including some simple word puzzles at some point), and then to evaluate whether there is any benefit in further abstraction.