Skip to main content.

Donald E. Knuth's "Dancing Links"

The "Dancing Links" are a very clever way to do backtracking, and it is non-trivial.

The idea is: write a Sudoku as a so-called "exact cover problem", and solve that with the "Algorithm X", and Dancing Links an implementation of "Algorithm X", which makes use of two way linked lists and sparse matrices.

If you are still not deterred, you should read the Wikipedia entries on

In that order. In the near future I won't provide an English explanation on my own.