[Haskell-cafe] The Knight's Tour: solutions please

Dan Doel dan.doel at gmail.com
Mon Dec 1 18:01:08 EST 2008

On Monday 01 December 2008 1:39:13 pm Bertram Felgenhauer wrote:
> As one of the posters there points out, for n=100 the program doesn't
> actually backtrack if the 'loneliest neighbour' heuristic is used. Do any
> of our programs finish quickly for n=99? The Python one doesn't.

Nothing I tried finished. Do you have any figures on how much backtracking 
needs to be done to find a solution for n=99 (there is a solution, right?)? I 
tweaked the continuation version to print k when it backtracks, and it 
continuously spit out numbers around 9790. I get the feeling it doesn't matter 
how fast your backtracking infrastructure is in this case as long as you use 
the same general algorithm.

On a long shot, I even tried using Logic's alternate bind based on fair 
choice, but that didn't seem to be any better.

-- Dan

More information about the Haskell-Cafe mailing list