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 fi

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): 1324 3142 4213 2431 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 https://en.wikipedia.org/wiki/Exact_cover [2] https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X [3] https://en.wikipedia.org/wiki/Dancing_Links https://en.wikipedia.org/wiki/Dancing_Links [4] http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color...