G'day all.
Quoting Vimal <[EMAIL PROTECTED]>:
> 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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
