## Sudoku Solver

There are many ways of solving Sudoku programmatically. The first attempt would be to replicate what people do. In any empty cell list all possible candidates. If there is only one candidate then fill the cell with that candidate. The dual of this procedure is: if in any row or column or box there exists a number that can go into only one cell then fill that cell with that number. Mathematically speaking there is a bipartite graph linking cells to numbers. If there exists a node with only one arc then that arc ties the source and destination.

But a more brute force technique would be: Consider the first empty cell. Fill it with smallest candidate number based on the existing partly filled Sudoku. Then consider the next cell until all cells are covered. If there is a cell that has no candidate then back track; replace the last filled cell with the next candidate solution. If that cell has run out of candidates back track another step and so on.

Turns out that this ‘crude’ algorithm is only less than 200 lines of C++ and has worked for the small sample set that I tried. Check it out at The Sunday Programmer