June, 2014

Constraint based sudoku solver

A few weekends ago I decided to give solving Sudoku a try. In case you aren’t familiar with Sudoku, here is what an unsolved board looks like

from wikipedia

And here is a solved one

from wikipedia

Sudoku, of size 3 is pretty easy. Make a snapshot of the board, pick a random open cell, find out what its available possibilities are and set it to a value. To figure out it’s possibilities you need get the cells “group”. This means all the values of the 3×3 cell it’s in, as well as all the values of the row that it’s in and the columns that it’s in.

Based on what is available, you can choose a number that isn’t taken, plop it in down, and then recursively repeat. If nothing is available, and the board isn’t empty, you messed up and the recursion will backtrack.

Let’s get solvin’


Read more

, ,