Two weeks ago, I came up with an interesting algorithm for solving Hidato, which basically involves decomposing the board grid (which can be square, hexagonal, or any other shape) into classes of pieces and then arranging them (maybe I’ll write a detailed post on it in the future). So while pondering whether it would be interesting enough to go forward and actually implement the algorithm, compared to the work it would require, I started thinking about what would be the simplest way to solve such puzzles, as opposed to the most efficient way.
At first I looked at general-purpose constraint solvers and decided to tackle Sudoku instead, as it’s a bit simpler to define in terms of constraints. I considered several libraries, but in the end I settled on simply using Prolog. I chose Prolog because, as a logic programming language, constraints are its bread and butter. I also kind of liked it, as I haven’t done anything in Prolog for quite a few years.
Describing Sudoku in terms of constraints is extremely simple. You need to state that every cell is in a given range and that all rows, columns, and sub-grids contain different integers. Since mangling with lists in Prolog isn’t fun, I wrote a Python program that outputs all the Prolog statements with hardcoded references to the variables that build up the board. It’s ugly but dead simple. The script gets the dimensions of the sub-grid.
Continue reading Solving Sudoku using Python and Prolog