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 problems. -- Live well, ~wren