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.