Comment
Comments
Comments in green were written by me. Comments in blue were not written by me.
@Danila P.: I think I have pushed VB.Net to its limit!
I moved the board from byte cells to 64 bit integer bitmaps (1 for each row);
using 8, 9, 10 variables for the 'active' rows instead of an array to reduce memory access.
I also partitioned the '9' and '10' search so other computers (I have a 6c/12t i7 3930K and a few quad cores) can assist using a mapped network drive.
All 2,332 distinct solutions of the '8' puzzle (12c/24t) now 16 secs (was 26 sec).
I have ported most of it to C ... just need to get the multi-threading working!
I moved the board from byte cells to 64 bit integer bitmaps (1 for each row);
using 8, 9, 10 variables for the 'active' rows instead of an array to reduce memory access.
I also partitioned the '9' and '10' search so other computers (I have a 6c/12t i7 3930K and a few quad cores) can assist using a mapped network drive.
All 2,332 distinct solutions of the '8' puzzle (12c/24t) now 16 secs (was 26 sec).
I have ported most of it to C ... just need to get the multi-threading working!
Lord Sméagol
on /blog/119
on /blog/119
(Scanning for free space from top to bottom, left to right)
Only place 1x1 in one octant; The tests are simple, the savings are huge.
Even size: 8->36, 11->66, 12->78, 15->120
. . . . . . . . . .
. . . . . . . . . .
. . \ x x x x x . .
. . + \ x x x x . .
. . + + \ x x x . .
. . # # # # # # . .
. . # # # # # # . .
. . # # # # # # . .
. . . . . . . . . .
. . . . . . . . . .
Odd size: 9->45, 10->55, 13->91, 14->105
. . . . . . . . . . .
. . . . . . . . . . .
. . \ x x x x x x . .
. . + \ x x x x x . .
. . + + \ x x x x . .
. . = = = * x x x . .
. . # # # # # # # . .
. . # # # # # # # . .
. . # # # # # # # . .
. . . . . . . . . . .
. . . . . . . . . . .
+ No symmetry check needed
\ Check transpose only
= Check vertical flip only
* Check all 7 symmetries
. 1x1 impossible here
x don't place 1x1 here
# backtrack if 1x1 not placed yet
'8' 2,332 distinct: (12c/24t) 26 sec, (1t) 3m56s
'9' 216,285 distinct: (12c/24t) 3h32m41s, (1t) [32.2 hours estimated]
12c/24t is only getting a 9x improvement over single thread :(
I need to think about making an asm version :)
on /blog/119