[Haskell-cafe] Performance of Knight's Tour

[Artyom Kazak]

2010/3/1 Daniel Fischer <daniel.is.fischer at web.de>:
> In the algorithm. You investigate far too many dead ends. Since for larger
> boards, the number of dead ends increases fast, larger boards take much
> much longer.
> With one little change, I get
> ...
> For a reason I don't understand, if the second dimension is 60 and the
> first is > 18, it takes much longer,
>...
> The magic change:
>
>     e ((x, y), arr) p = [(t, arr // [(t, p)]) | t <- changes]
>       where
>        legit ps = [t | t <- allTurns ! ps, arr!t == 0]
>         changes = map snd $ sort [(length $ legit t, t) | t <- allTurns !
> (x, y), arr ! t == 0]
>
> investigate squares with fewer options first.
>

Wow! Thanks you!
By the way, I didn't notice the difference between (59, 59) and (60,
60) on my machine...