The source code and example boards are available here.
This program solves an incomplete sudoku board. The algorithm is as follows: the first available empty space is set to 1; if this leads to an unsolvable board, increment the last number, or if 9 is reached, then go back one step. It is considered solved, when all the board is correct and no more empty cells remain.
Most of the boards are solved in less than a second, the hardest board I found (constructed by a mathematican) is solved in around 10 seconds, and took 17 million steps.
Here is an example output of the program:
