[Haskell-cafe] The Knight's Tour: solutions please
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.
More information about the Haskell-Cafe