Another way to solve Sudoku is to understand that it is an instance of the Exact...

Another way to solve Sudoku is to understand that it is an instance of the Exact Cover problem [1]. Basically, solving a 3x3 Sudoku grid is nothing more than finding 9 "sheets" of each number which superimpose exactly on top of the grid.

For example (2x2 sudoku = 4 sheets):

is:

    1...   .2..   .3..   ...4
    .1..   ...2   3...   ..4.
    ..1. + .2.. + ...3 + 4...
    ...1   2...   ..3.   .4..

or even:

    x...   .x..   .x..   ...x
    .x..   ...x   x...   ..x.
    ..x. + .x.. + ...x + x...
    ...x   x...   ..x.   .x..
    x...   .x..   ..x.   ...x <- number row

where the last "number row" does not belong to the grid but serves to indicate the number of the sheet.

This explains how sudoku relates to the Exact Cover problem. Now, there is a good algorithm by Knuth to solve Exact Cover, which is known as Algorithm X [2].

Algorithm X is just an algorithm but Knuth has also invented a very efficient implementation of it, called Dancing Links or DLX for short [3]. DLX is described in a very good and very readable paper by Knuth himself [4]. This is one of the first serious papers I ever read and it was a real joy, mind-opener.

[1] https://en.wikipedia.org/wiki/Exact_cover

[2] https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X

[3] https://en.wikipedia.org/wiki/Dancing_Links

[4] http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color...