[Haskell-cafe] Sudoku solving

[Antoine Latter]

I'm a relatively new to Haskell, so I figured I needed to write a Sudoku solver.

The key features of this solver are:

  * It's longer than other Haskell Sudoku solvers I've seen around

  * It fails to solve many solvable puzzles

Fantastic!

link: http://panicsonic.blogspot.com/2007/04/sudoku-solving.html

The approach:  Because I'm new to Haskell, the traditional
guess-and-check method of Sudoku solving would involving things like
backtracking down a search path, which is still in the realm of
Haskell Black Magic.  Instead, I cast the problem into successive
function applications on data - A Sudoku puzzle is represented as an
array of constraints on the values of cells.  The constraints are
reduced via analysis of the surrounding constraints until the puzzle
is solved (or not).

For those who like references: my approach is similar to "Solving
Sudoku Puzzles with Rewritting Rules" by Gustavo Santos-Garcia and
Miguel Palomino, 2005, Electronic Notes in Theoretical Computer
Science.  My main rules and techniques  can be considered as
generalizations on some of their rules and techniques - except their
solver can solve all solvable puzzles (with the help of a
guess-and-check rule).

Thanks for taking a look,
Antoine