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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe