[Haskell-cafe] Re: The Knight's Tour: solutions please
haskell at list.mightyreason.com
Tue Dec 2 07:39:13 EST 2008
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.
More information about the Haskell-Cafe