First things first. What is a sudoku puzzle? Sudoku is a number-placement puzzle based on logic that originated in Japan. The objective is to fill a 9x9 grid with digits so that each row, column, and box (3x3 subgrids that compose the grid) contains all of the digits from 1 to 9. You start from a partially populated grid, and add number after number using logic considerations.

Sudoku can be interpreted, from a computer science perspective, as a problem that fits in the exact cover category. Donald Knuth, the author of The Art of Computer Programming (and many other wonderful books), has devised an algorithm, called Algorithm X, to solve problems in this category. A beautiful and efficient implementation of Algorithm X, called Dancing Links, which harnesses the power of circular doubly-linked lists, can be used to solve sudoku. The beauty of this approach is that all it requires is a mapping between the structure of the sudoku, and the Dancing Links algorithm, and without having to do any of the logic deductions normally needed to solve the puzzle, it gets to the solution at the speed of light.

Many years ago, when my free time was a number greater than zero, I wrote a Dancing Links sudoku-solver in C#, which I still have archived somewhere, which was great fun to design and code. I definitely encourage you to check out the literature and code your own solver, it's a great exercise, if you can spare the time.

In this example's solution though, we're going to use a search algorithm used in conjunction with a process that, in artificial intelligence, is known as constraint propagation. The two are quite commonly used together to make a problem simpler to solve. We'll see that in our example, they are enough for us to be able to solve a difficult sudoku in a matter of milliseconds.