A Sudoku Solver in Java implementing Knuth’s Dancing Links Algorithm
Dr. Donald Knuth’s Dancing Links Algorithm solves an Exact Cover situation. The Exact Cover problem can be extended to a variety of applications that need to fill constraints. Sudoku is one such special case of the Exact Cover problem.
See also the references, esp. Knuth's original paper.