gmane.comp.lang.haskell.cafe

oleg | 2 Dec 09:29

The Knight's Tour: solutions please


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.

Here are the results:
for n=99, the first line of the board is

   1 4 2885 214 309 6 311 216 307 8 315 218 305 10 319 220 303 12 2021
222 301 14 1727 224 299 16 1699 226 297 18 1561 228 295 20 1247 230
293 22 1227 232 291 24 1165 234 289 26 1007 236 287 28 965 238 285 30
775 240 283 32 759 242 281 34 625 244 279 36 559 246 277 38 543 248
275 40 455 250 273 42 435 252 271 44 407 254 269 46 377 256 267 48 365
258 65 50 63 60 67 52 55

time is 0m0.730s

n=100

    1 4 205 9996 209 6 207 9940 211 8 9897 9900 213 10 9895 9906 215
12 9809 9880 217 14 9807 9740 219 16 9799 9072 221 18 8445 8864 223 20
8443 8378 225 22 8347 8352 227 24 8331 7860 229 26 7863 7844 231 28
7749 7754 233 30 7735 7742 235 32 7733 7320 237 34 677 640 239 36 597
568 241 38 535 540 243 40 517 500 245 42 473 452 247 44 371 358 249 46

(Continue reading)

headers

ChrisK | 2 Dec 13:39

Re: The Knight's Tour: solutions please

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

(Continue reading)

headers

Bertram Felgenhauer | 2 Dec 20:26

Re: Re: The Knight's Tour: solutions please

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

(Continue reading)