[Haskell-cafe] Re: Simple Sudoku solver using Control.Monad.Logic

[Johannes Waldmann]

> sudoku solver using the LogicT monad. 
> [...] works but it is  extremely slow, 

Any sudoku should be easily solvable by a program 
that always case-splits on the unknown that has the fewest
remaining possible assignments. 

The proper general framework for this is "finite domain constraint systems",
Cf. Chapter 5 ("Local notions of consistency") 
of Apt: Principles of Constraint Programming
http://homepages.cwi.nl/~apt/books.html

I'm sure you know that, and the question was about using
a backtracking monad.

I am not sure that the Logic(T) monad (transformer) is efficient
in solving FD constraint systems.
If you just write down all the constraints (as you should)
and then simply "Control.Monad.Logic.Class.interleave" them,
then you're probably getting some different (and inefficient) 
search strategy.

So you'd have to prescribe the evaluation strategy somehow -
but once you do this, it's not longer logic programmings
(since it's becoming functional).

J.W.