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

[ChrisK]

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

The version with the 'tour' given above does not halt after running up to 0.4 GB 
of RAM, so I killed it.

Though having no solution may be tied to starting in the corner.

-- 
Chris