[Haskell-cafe] Re: The Knight's Tour: solutions please

[Bertram Felgenhauer]

ChrisK wrote:
> Hmmm... it seems that n=63 is a special case.
>
> oleg at 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