exact-cover is a Haskell library that implements a fast solver
for exact cover problems using
Algorithm X as described in the
paper Dancing Links, by Donald Knuth, in
Millennial Perspectives in Computer Science, P159, 2000.
See exact-cover on Hackage
for more information.
You will need to set the buildExamples flag to build the executable samples.
e.g. on stack, do
stack build --flag exact-cover:buildExamples
After setting the buildExamples flag above, the sudoku example can be run with
stack exec sudoku
Interesting sudoku puzzles that one might use to try out the solver:
-
Unsolvable “puzzle” that took Peter Norvig’s solver 1439 seconds to prove that there is no solution:
.....5.8....6.1.43..........1.5........1.6...3.......553.....61........4......... -
Finnish mathematician Arto Inkala’s 2006 puzzle
85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4...53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97.. -
A compilation of resources, which includes lists of “hardest sudokus”.