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

[oleg at okmij.org]

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
305 310 251 48 293 286 253 50 291 270 255 52 259 262

time is 0m0.373s

For n=101, time is 0m0.388s

wren ng thornton wrote:
> FWIW, fair choice (interleave) is much slower than unfair choice (mplus)
> in logict. Unfortunately this means you need to know a lot about the
> problem domain to correctly choose between them when maximal performance
> is at stake; just using fair choice everywhere costs too much for many
> problems.

I believe that FBackTrack relieves one from making the above choice:
the ordinary mplus is FBackTrack is both fair and speedy. There is no
longer any need for interleave; btw, interleave does not ensure
completeness, whereas FBackTrack, I conjecture, implements a complete
search procedure: if there is a solution, FBackTrack will eventually
find one. The only `drawback' of using FBackTrack is that the order
of the answers (if there are several) is essentially unpredictable.
Informally, the answers are delivered in the order of the difficulty
of finding them. This drawback is relative however: if we insist that
the sequence of answers of (m1 `mplus` m2) is the concatenation of the
sequences of answers of m1 and then m2, our search procedure is
incomplete.