[Haskell-cafe] Performance of Knight's Tour

[Daniel Fischer]

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]
>       where
>         legit ps = [t | t <- allTurns ! ps, arr ! t == 0]
>         changes = sortOn (length . legit) (legit (x, y))
>         sortOn = sortBy . comparing

Ah, that!

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.