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.