[Haskell-cafe] Simple Sudoku solver using Control.Monad.Logic
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.
More information about the Haskell-Cafe