Sunday, January 11, 2009

SudokuSolver released

I've developed a bit of an addiction recently. Thankfully, it's not alcohol-related. But like drinking, it does take up time and money.

If you're not familiar with the puzzle game Sudoku, you've probably at least seen it either in your daily newspaper or somewhere online. The goal is: given a square board 9 cells high and 9 cells wide, fill each row, column, and 3 by 3 sub-square with all the numbers 1 through 9. No number can be repeated in any of those three places. For example, the number 5 can't appear more than once in the same row. The board starts with some cells already filled in to give you a starting point. The less completed cells you start with, the harder the puzzle is.

After solving enough of these, I thought it would be an interesting exercise to write a program which solves them automatically! As I got deep into creating the algorithm, one data structure stood out as being the keystone--sets.

In mathematics, a set is a collection of numbers where:

  1. the order the numbers are in does not matter and

  2. no number can be repeated.

For example, this is a set:
{ 3, 7, 5, 9 }

Since order doesn't matter, this is the same set as the one above:
{ 9, 3, 7, 5 }

But this is NOT a set because there are two 7s:
{ 9, 3, 7, 5, 7 }

In this algorithm, sets are useful when trying to figure out what number a cell should be. The algorithm can be summarized with this pseudo-code:

while board is not complete
for each cell in board
if cell is empty
possibleValues = findPossibleValues(cell)
if size of possibleValues == 1
cell.empty = false
cell.value = possibleValues[0];

function findPossibleValues(cell)
possibleValues = new set{1,2,3,4,5,6,7,8,9}

for each rowcell in cell's row
if rowcell is not empty
//if possibleValues doesn't contain rowcell.value, then nothing happens
possibleValues -= rowcell.value

for each colcell in cell's column
if colcell is not empty
possibleValues -= colcell.value

for each squarecell in cell's square
if squarecell is not empty
possibleValues -= squarecell.value

return possibleValues

Given a current board state, for each cell in the board, a set containing all values the cell could possibly be is created. If this set only contains one number, then that's the only number the cell can be, so we fill in the cell with that number. This keeps repeating until all cells are filled in. (There are some other tricks that have to be taken into account, but this is the most fundamental part of the algorithm.)

If you'd like to try it out or look at the source code, you can download it here:

No comments: