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