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:

http://www.mangst.com/projects/sudoku-solver