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:

- the order the numbers are in does not matter and
- 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

## No comments:

Post a Comment