ChrisK wrote:
Hmmm... it seems that n=63 is a special case.
oleg@okmij.org wrote:
Yes, there is a solution for n=99 and for n=100 for that matter -- which can be found under one second. I only had to make a trivial modification to the previously posted code
tour n k s b | k > n*n = return b | otherwise = do next <- (foldr mplus mzero).map return $ successors n b s tour n (k+1) next $ insrt next k b I replaced foldl1 mplus with foldr mplus zero.
The old version sees no solution to n=63 quite quickly:
time nice ./fromwiki-63 63 fromwiki-63: Prelude.foldl1: empty list real 0m0.285s user 0m0.172s sys 0m0.026s
That's a bug. When the list of candidates is empty at that point, the program should backtrack, not terminate. In fact there are solutions for n=63. Using the first improved heuristic from my previous mail in this thread:
time ./tour2 63 1 4 143 148 211 6 229 226 241 8 553 578 571 10 551 584 573 12 549 630 643 14 547 670 665 16 545 684 679 18 543 770 765 20 541 816 867 22 539 952 995 24 537 1044 1121 26 535 1208 1231 28 533 1300 1307 30 531 494 489 32 491 404 39 34 37 ... real 0m1.750s user 0m1.564s sys 0m0.008s
The version with the 'tour' given above does not halt after running up to 0.4 GB of RAM, so I killed it.
In fact, replacing foldl1 mplus by foldr mplus mzero fixed that bug. Bertram