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

[Stephen Tetley]

Hello Kashyap

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).

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.

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.


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


Best wishes

Stephen