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

[Bertram Felgenhauer]

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

Yes, there is a solution. After changing

  successors n b = sortWith (length . succs) . succs

to

  successors n b = sortWith (length . (succs =<<) . succs) . succs

in the LogicT solution, it finds one with no backtracking at all.

This heuristic fails on other n though, n=8 and n=66 at least.

The obvious next step,

  successors n b = sortWith (length . (succs =<<) . (succs =<<) . succs) . succs

works without backtracking up to n=100.

These improved heuristics don't come cheap though. Here are some timings
for n = 100:

  LogicT  :  0.48 user 0.00 system 0:00.48 elapsed
  LogicT' :  2.16 user 0.00 system 0:02.16 elapsed
  LogicT'': 13.84 user 0.01 system 0:13.86 elapsed

Bertram