G'day all.
Quoting Vimal
Well, Dancing Links (DLX) is just a data structure + few techniques to help with the backtrack, after modeling Sudoku as a contraint satisfaction problem.
DLX is one realisation of an algorithm which works on boolean matrices. It's a pointer-based backtracking algorithm with explicit "undo", so that's arguably not the most appropriate realisation in a declarative language, where undo should be close to free. Just for fun, I tried implementing the exact cover algorithm using a more Haskell-esque data realisation. The bit matrix is represented as a pair of maps: one from column to list of rows, and one from rows to list of columns. The first map (column to list of rows) is implemented as a priority search queue keyed on the number of "ones" in each column. This allows fast selection of the smallest column. http://andrew.bromage.org/darcs/sudoku/ I don't claim that it's fast. I didn't spend a lot of time on it. Cheers, Andrew Bromage