Two weeks ago, I add came up with an interesting algorithm for solving Hidato which basically involves decomposing the board the grid (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 implementing the algorithm compared to the work it would require, I started thinking what will be the simplest way to solve such puzzles, as opposed to efficient.
At first I’ve looked at general purpose constraint solvers, and decided to tackle Sudoku instead as it’s a bit simple to define in terms of constraints. I considered several libraries but in the end I’ve settled on plainly using Prolog. I chose Prolog because as a logic programming language, constraints are its bread and butter. I although 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-grid contain different integers. As mangling with lists in prolog isn’t fun, I’ve wrote a python program that outputs all the prolog statements with hardcoded references to the variables which 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