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

[wren ng thornton]

Dan Doel wrote:
> 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.

FWIW, fair choice (interleave) is much slower than unfair choice (mplus) 
in logict. Unfortunately this means you need to know a lot about the 
problem domain to correctly choose between them when maximal performance 
is at stake; just using fair choice everywhere costs too much for many 
problems.

-- 
Live well,
~wren