[Haskell-cafe] The Knight's Tour: solutions please
wren ng thornton
wren at freegeek.org
Mon Dec 1 23:48:21 EST 2008
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
More information about the Haskell-Cafe