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...

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.