[Haskell-cafe] Performance of Knight's Tour
artyom.kazak at gmail.com
Mon Mar 1 13:29:45 EST 2010
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]
> 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...
More information about the Haskell-Cafe