During my CS education at USUI used Knuth's algorithm X with Dancing Links. Algorithm X with Dancing Links is a fairly efficient educated brute forcing back-tracking algorithm that would let you solve a more general problem called the exact cover problem (other examples besides soduku include tiling a space with polionimoes ). Dancing Links is the name of the data structure used, because what happens is you use a quadruply linked-list (think like a doubly-linked list forward and backwards that make a grid) and are able to hide and show nodes in the list as you traverse the exact-cover problem search space. The main benefit of creating and hiding nodes is saving memory operations like creation and deletion. The reason for the quadruply linked list is, if your search space (usually visualized by a matrix) is fairly sparse then the doubly linked list can save alot of space and also a lot of time ...
Read more...