Re: [Haskell-cafe] Performance of Knight's Tour

1 Mar 2010

      2010/3/1 Daniel Fischer :
...
Am Montag 01 März 2010 19:29:45 schrieb Artyom Kazak:
...
2010/3/1 Daniel Fischer :
...
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...
Strangely,
$ echo "62 59" | time ./knights > /dev/null
0.10user 0.08system 0:00.17elapsed 101%CPU
$ echo "65 59" | time ./knights > /dev/null
0.08user 0.07system 0:00.17elapsed 96%CPU
, so it's a thing of the second dimension predominantly (the size plays a
small role, too).
As I said, I don't understand it, but looking at the allocation figures:
70*59: 97,970,072 bytes allocated in the heap
18*60: 12,230,296 bytes allocated in the heap
19*60: 2,374,148,320 bytes allocated in the heap
19*61: 13,139,688 bytes allocated in the heap
60*61: 71,771,324 bytes allocated in the heap
61*61: 72,965,428 bytes allocated in the heap
it seems that something is kicked out of the registers when the second
dimension is 60 and the first > 18.
Very strange.
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

My version gives answer for 60, 60 in one second. But if both
dimensions are >60, it won't finish.
Yes, very strange.