[Haskell-cafe] Performance of Knight's Tour
daniel.is.fischer at web.de
Mon Mar 1 16:21:01 EST 2010
Am Montag 01 März 2010 21:40:16 schrieb Artyom Kazak:
> Maybe we were compiling with different options? I compiled with -O2
> -fvia-C -optc-O3.
> Oh, I know! I slightly changed the code.
> import Data.Ord
> e ((x, y), arr) p = [(t, arr // [(t, p)]) | t <- changes]
> legit ps = [t | t <- allTurns ! ps, arr ! t == 0]
> changes = sortOn (length . legit) (legit (x, y))
> sortOn = sortBy . comparing
I also tried that, that gets stuck for different values.
With a little debugging output, I saw that it got stuck in a dead-end,
always advancing a few steps and then backtracking. I'm now considering
also the grand-children, that speeds things up and enters fewer dead-ends,
but so far I haven't found a valuation which doesn't enter a dead-end for
some values. I have an idea, though, also consider the distance from the
border, try squares near the border first.
> My version gives answer for 60, 60 in one second. But if both
> dimensions are >60, it won't finish.
> Yes, very strange.
More information about the Haskell-Cafe