[Haskell-cafe] Sudoku Solver

[ajb at spamcop.net]

G'day all.

Quoting Vimal <j.vimal at gmail.com>:

> 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