[Haskell-cafe] The Knight's Tour: solutions please
bertram.felgenhauer at googlemail.com
Tue Dec 2 03:29:27 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?)?
Yes, there is a solution. After changing
successors n b = sortWith (length . succs) . succs
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
More information about the Haskell-Cafe