[Haskell-cafe] My knight's tour does not seem to end

C K Kashyap ckkashyap at gmail.com
Sun Oct 10 06:31:10 EDT 2010


Thank you Stephen,

> Quite probably the algorithm is working correctly just that for boards
>>5 it takes a pathologically long time (for boards <= 5 I haven't
> checked the answer is correct just that it is computed).

I checked it out with 5 and looks like the answer is correct also :)

> In the first message I was looking for places where the input data
> grew or stayed constant size rather than got pruned. If you have
> runaway recursive a first debugging step is often to look for errors
> in pruning. Unfortunately I read the code wrongly, apologies again.

no problem :)

> To get it to work better, an improved search strategy would help, also
> better data structure that allows efficient indexing would be nice.
> That said, a clever algorithm can do a lot without indexing - you
> might want to search for Richard Bird's Sudoku slide presentation
> which is expanded in his new book.

Did you mean this
http://www.cs.tufts.edu/~nr/comp150fp/archive/richard-bird/sudoku.pdf?
Also, is this the book -
http://www.flipkart.com/pearls-functional-algorithm-design-richard-book-0521513383
I dont have this book ... but looks like its a must have.

> This paper has search strategies in a lazy setting and a version of n-Queens:
>
> Thomas Nordin and Andrew Tolmach - Modular Lazy Search for Constraint
> Satisfaction Problems
> http://web.cecs.pdx.edu/~apt/jfp01.ps
>

This is probably what I like (and dislike - in a nice way) - my quest
to master Haskell has been like traversing through a ever expanding
tree :)
Very different from a bunch of "learn over a weekend" language!!!



-- 
Regards,
Kashyap


More information about the Haskell-Cafe mailing list