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

Luke Palmer lrpalmer at gmail.com
Sun Aug 22 16:15:02 EDT 2010


On Sun, Aug 22, 2010 at 1:18 PM, Daniel Fischer
<daniel.is.fischer at web.de> wrote:
> On Sunday 22 August 2010 20:12:16, Vladimir Matveev wrote:
>> I think the problem is with terribly inefficient data representation.
>
> Worse, it's a terribly inefficient algorithm.
> The constraints are applied too late, so a huge number of partial boards
> are created only to be pruned afterwards. Since the ratio between obviously
> invalid rows and potentially valid rows is large, the constraints should be
> applied already during the construction of candidate rows to avoid
> obviously dead branches.

I've written a sudoku solver myself, and IIRC I used lists.  It always
gave an answer within a second.  So I believe Daniel has correctly
identified the problem -- you need to prune earlier.

Luke


More information about the Haskell-Cafe mailing list