/*****************************************************************************/ /* HEXMINO(11*19+1) 全解数の推定(モンテカルロ法風) 2001/03/09 by takaken */ /*****************************************************************************/ /* BOARD MAP [ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][ 10][ 11][ 12] 13 14 15 16 17 18 19 20 21 22 23 [ 24][ 25] 26 27 28 29 30 31 32 33 34 35 36 [ 37][ 38] 39 40 41 42 43 44 45 46 47 48 49 [ 50][ 51] 52 53 54 55 56 57 58 59 60 61 62 [ 63][ 64] 65 66 67 68 69 70 71 72 73 74 75 [ 76][ 77] 78 79 80 81 82 83 84 85 86 87 88 [ 89][ 90] 91 92 93 94 95 96 97 98 99 100 101 [102][103] 104 105 106 107 108 109 110 111 112 113 114 [115][116] 117 118 119 120 121 122 123 124 125 126 127 [128][129] 130 131 132 133 134 135 136 137 138 139 140 141 [142] 143 144 145 146 147 148 149 150 151 152 153 [154][155] 156 157 158 159 160 161 162 163 164 165 166 [167][168] 169 170 171 172 173 174 175 176 177 178 179 [180][181] 182 183 184 185 186 187 188 189 190 191 192 [193][194] 195 196 197 198 199 200 201 202 203 204 205 [206][207] 208 209 210 211 212 213 214 215 216 217 218 [219][220] 221 222 223 224 225 226 227 228 229 230 231 [232][233] 234 235 236 237 238 239 240 241 242 243 244 [245][246] 247 248 249 250 251 252 253 254 255 256 257 [258][259] [260][261][262][263][264][265][266][267][268][269][270][271] */ #include #include #include #define TEST 0 #define DB_SIZE4 2000003 #define DB_SIZE3 1000003 #define DB_SIZE2 500009 #define DB_SIZE1 100003 #define HEAVY4 7 #define HEAVY3 7 #define HEAVY2 7 #define HEAVY1 7 #define DB_FULL4 (DB_SIZE4 * 4 / 5) #define DB_FULL3 (DB_SIZE3 * 4 / 5) #define DB_FULL2 (DB_SIZE2 * 4 / 5) #define DB_FULL1 (DB_SIZE1 * 4 / 5) typedef unsigned char u08; typedef unsigned short u16; typedef unsigned long u32; typedef unsigned __int64 u64; typedef struct { long count; u64 silhouette1; u08 silhouette2; } ptndb_t; ptndb_t PTNDB1[DB_SIZE1], PTNDB2[DB_SIZE2]; ptndb_t PTNDB3[DB_SIZE3], PTNDB4[DB_SIZE4]; long COUNT; long COUNT1, DB_CNT1, SE_CNT1; long COUNT2, DB_CNT2, SE_CNT2; long COUNT3, DB_CNT3, SE_CNT3; long COUNT4, DB_CNT4, SE_CNT4; int BLANK; int PIECE[35], USED[35]; int MAP[280]; u08 BOARD[35], PAINT[35]; u64 FORM[216]; u64 *FORM_TOP[35], *FORM_END[35]; u64 *HISTORY[34]; u64 CHECK1 = 0x0002002; /* blank=1 */ u64 CHECK2 = 0x4005002; /* blank=2 */ u64 CHECK3 = 0x0006004; /* blank=2 */ int TYPE[35][8][5] = { 13,26,39,52, 0, /* □□□□□□ */ 1, 2, 3, 4, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2,13,14,15, /* □□□　　　 */ 1,13,14,26,27, /* □□□　　　 */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,13,26,39,52, /* □□□□□　 */ 1,14,27,40,53, /* □　　　　　 */ 9,10,11,12,13, 13,14,15,16,17, 1, 2, 3, 4,13, 1, 2, 3, 4,17, 13,26,39,51,52, 13,26,39,52,53, 1,12,13,14,26, /* 　□□　　　 */ 1,13,14,15,27, /* □□□　　　 */ 12,13,14,25,26, /* 　□　　　　 */ 12,13,14,26,27, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,12,13,24,25, /* 　　□□　　 */ 1,14,15,28,29, /* 　□□　　　 */ 12,13,24,25,37, /* □□　　　　 */ 13,14,27,28,41, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,12,13,26,27, /* 　□□　　　 */ 1,14,15,26,27, /* □□　　　　 */ 12,13,14,25,27, /* 　□□　　　 */ 2,13,14,15,27, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,13,26,38,39, /* 　□□　　　 */ 1,14,27,40,41, /* 　□　　　　 */ 10,11,12,13,23, /* 　□　　　　 */ 13,14,15,16,29, /* □□　　　　 */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11,12,13,14,25, /* 　　□　　　 */ 12,13,14,15,27, /* □□□□　　 */ 12,13,26,27,39, /* 　□　　　　 */ 13,14,25,26,39, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11,12,13,14,26, /* 　　□　　　 */ 12,13,14,15,26, /* □□□□　　 */ 12,13,14,26,39, /* 　　□　　　 */ 13,25,26,27,39, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3,13,26, /* □□□□　　 */ 1, 2, 3,16,29, /* □　　　　　 */ 1, 2,13,26,39, /* □　　　　　 */ 1, 2,15,28,41, 13,23,24,25,26, 13,26,27,28,29, 13,26,37,38,39, 13,26,39,40,41, 1, 2, 3,14,27, /* □□□□　　 */ 1, 2, 3,15,28, /* 　□　　　　 */ 11,12,13,26,39, /* 　□　　　　 */ 13,14,15,26,39, 13,24,25,26,27, 13,24,25,26,39, 13,25,26,27,28, 13,26,27,28,39, 1, 2,13,14,27, /* □□□　　　 */ 1, 2,14,15,27, /* □□　　　　 */ 1,12,13,14,27, /* 　□　　　　 */ 1,13,14,15,26, 11,12,13,25,26, 12,13,25,26,27, 13,14,15,26,27, 13,14,25,26,27, 1, 2,13,15,26, /* □□□　　　 */ 1, 2,13,15,28, /* □　□　　　 */ 1, 2,13,26,27, /* □　　　　　 */ 1, 2,15,27,28, 1,13,26,27,28, 1,14,25,26,27, 11,13,24,25,26, 13,15,26,27,28, 1, 2,13,25,26, /* 　□□□　　 */ 1, 2,15,28,29, /* 　□　　　　 */ 1,13,24,25,26, /* □□　　　　 */ 1,14,27,28,29, 11,12,13,24,37, 13,14,15,28,41, 13,24,25,26,37, 13,26,27,28,41, 1, 2,14,26,27, /* □□□　　　 */ 1, 2,14,27,28, /* 　□　　　　 */ 1,13,25,26,27, /* □□　　　　 */ 1,14,26,27,28, 11,12,13,24,26, 2,13,14,15,26, 2,13,14,15,28, 13,14,15,26,28, 1,11,12,13,24, /* 　　□□　　 */ 1,13,25,26,38, /* □□□　　　 */ 1,14,15,16,29, /* □　　　　　 */ 1,14,27,28,41, 11,12,13,23,24, 12,13,25,37,38, 13,14,15,28,29, 13,14,27,40,41, 1,11,12,13,25, /* 　　□□　　 */ 1,14,15,16,28, /* □□□　　　 */ 12,13,14,24,25, /* 　□　　　　 */ 12,13,14,27,28, 12,13,24,25,38, 12,13,26,27,40, 13,14,25,26,38, 13,14,27,28,40, 1,11,12,13,26, /* 　　□□　　 */ 1,14,15,16,27, /* □□□　　　 */ 11,12,13,25,38, /* 　　□　　　 */ 11,12,13,26,27, 13,14,15,25,26, 13,14,15,27,40, 13,25,26,27,38, 13,25,26,27,40, 1, 2, 3, 4,15, /* □□□□□　 */ 11,12,13,14,15, /* 　　□　　　 */ 13,25,26,39,52, 13,26,27,39,52, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3,13,16, /* □□□□　　 */ 1,13,26,39,40, /* □　　□　　 */ 1,14,27,39,40, 3,13,14,15,16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3,14,15, /* □□□□　　 */ 1,12,13,14,15, /* 　□□　　　 */ 12,13,25,26,39, 13,14,26,27,39, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2,11,12,13, /* 　　□□□　 */ 1, 2,15,16,17, /* □□□　　　 */ 13,25,26,38,51, 13,26,27,40,53, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2,12,13,14, /* 　□□□　　 */ 1, 2,14,15,16, /* □□□　　　 */ 12,13,25,26,38, 13,14,26,27,40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2,13,14,26, /* □□□　　　 */ 1, 2,14,15,28, /* □□　　　　 */ 12,13,24,25,26, /* □　　　　　 */ 13,14,26,27,28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2,14,27,40, /* □□□　　　 */ 10,11,12,13,26, /* 　□　　　　 */ 13,14,15,16,26, /* 　□　　　　 */ 13,26,38,39,40, /* 　□　　　　 */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,12,13,14,25, /* 　□□　　　 */ 1,12,13,25,26, /* □□□　　　 */ 1,13,14,15,28, /* □　　　　　 */ 1,13,14,25,26, 1,13,14,27,28, 1,14,15,27,28, 11,12,13,24,25, 13,14,15,27,28, 1,12,13,26,39, /* 　□□　　　 */ 1,14,15,27,40, /* □□　　　　 */ 10,11,12,13,25, /* 　□　　　　 */ 11,12,13,14,27, /* 　□　　　　 */ 12,13,14,15,25, 13,14,15,16,27, 13,25,26,39,40, 13,26,27,38,39, 1,13,25,26,39, /* 　□□　　　 */ 1,14,27,28,40, /* 　□　　　　 */ 10,11,12,13,24, /* □□　　　　 */ 11,12,13,14,24, /* 　□　　　　 */ 12,13,14,15,28, 12,13,26,39,40, 13,14,15,16,28, 13,14,26,38,39, 1, 2, 3, 4,14, /* □□□□□　 */ 1, 2, 3, 4,16, /* 　□　　　　 */ 10,11,12,13,14, 12,13,14,15,16, 12,13,26,39,52, 13,14,26,39,52, 13,26,38,39,52, 13,26,39,40,52, 1, 2, 3,12,13, /* 　□□□□　 */ 1, 2, 3,16,17, /* □□　　　　 */ 1,10,11,12,13, 1,14,15,16,17, 12,13,25,38,51, 13,14,27,40,53, 13,26,38,39,51, 13,26,39,40,53, 1, 2, 3,13,14, /* □□□□　　 */ 1, 2, 3,15,16, /* □□　　　　 */ 1,11,12,13,14, 1,13,14,15,16, 1,13,14,26,39, 1,13,14,27,40, 13,25,26,38,39, 13,26,27,39,40, 1, 2, 3,13,15, /* □□□□　　 */ 1, 2, 3,14,16, /* □　□　　　 */ 1,13,26,27,39, 1,14,26,27,40, 2,12,13,14,15, 12,13,26,38,39, 2,13,14,15,16, 13,14,26,39,40, 1, 2,12,13,15, /* 　□□□　　 */ 1, 2,13,15,16, /* □□　□　　 */ 1,13,26,27,40, 1, 3,14,15,16, 1,14,26,27,39, 12,13,25,38,39, 2, 3,13,14,15, 13,14,27,39,40, 1, 2,12,13,25, /* 　□□□　　 */ 1, 2,15,16,29, /* □□　　　　 */ 1,12,13,25,38, /* □　　　　　 */ 1,14,15,28,41, 12,13,23,24,25, 13,14,27,28,29, 13,25,26,37,38, 13,26,27,40,41, 1, 2,12,13,26, /* 　□□□　　 */ 1, 2,15,16,28, /* □□　　　　 */ 12,13,14,25,38, /* 　□　　　　 */ 12,13,14,27,40, 12,13,26,27,28, 13,14,24,25,26, 13,24,25,26,38, 13,26,27,28,40 }; /**********************************************************/ /* Display (for TEST) */ /**********************************************************/ void Display(void) { int i, j, pos, num, shift, map[272]; u08 bit, *board, temp[34]; u16 *board_bit2, piece_bit2; u64 *board_bit1, *form, piece_bit1; for (i=0; i<34; i++) { bit = 0; for (j=7; j>=0; j--) { pos = i * 8 + j; bit <<= 1; if (MAP[pos]) bit |= 1; map[pos] = 0; } temp[i] = bit; } board = temp; for (i=0; i<35; i++) { while (*board == 0xff) board++; for (shift=0,bit=1; *board & bit; bit<<=1) shift++; board_bit1 = (u64 *)board; form = HISTORY[i]; piece_bit1 = *form << shift; *board_bit1 |= piece_bit1; piece_bit1 = *form; for (pos=(board-temp)*8+shift; piece_bit1; pos++, piece_bit1>>=1) if (piece_bit1 & 1) map[pos] = i + 1; if (form == FORM) { board_bit2 = (u16 *)(board + 8); piece_bit2 = (u16)((u16)2 << shift); *board_bit2 |= piece_bit2; map[(board-temp)*8+shift+65] = i + 1; } } system("cls"); for (i=24; i>=13; i--) { for (j=0; j<=234; j+=13) { pos = i + j; num = map[pos]; if (map[pos+1] == num) { printf("%s", (map[pos-13]==num && map[pos-12]==num)? " ": "+"); printf(" "); } else printf("+---"); } printf("%s\n", (i==24)? "": "+"); for (j=0; j<=234; j+=13) printf("%s", (map[i+j-13] == map[i+j])? " ": "| "); printf("%s\n", (i==24)? "": "|"); } for (i=0; i<19; i++) printf("+---"); printf("+"); getchar(); } /**********************************************************/ /* Blank % 6 */ /**********************************************************/ void Paint(int pos) { int byte, shift; u08 bit; byte = pos >> 3; shift = pos & 7; bit = (u08)(1 << shift); if (PAINT[byte] & bit) return; PAINT[byte] |= bit; BLANK++; Paint(pos - 13); Paint(pos + 1); Paint(pos + 13); Paint(pos - 1); } int BlankCheck(u08 *board, int shift) { int i; i = board - BOARD - 2; if (i < 1) i = 1; for ( ; i<=32; i++) PAINT[i] = BOARD[i]; BLANK = 0; Paint(((board - BOARD) << 3) | shift); return BLANK % 6; } /**********************************************************/ /* BackTrack-4 */ /**********************************************************/ void BackTrack4(u08 *board, int depth) { int i, shift, piece; u08 bit; u16 *board_bit2, piece_bit2; u64 *board_bit1, piece_bit1, *form, *fend, check; if (depth == 35) { COUNT4++; #if TEST Display(); #endif } else { while (*board == 0xff) board++; for (shift=0,bit=1; *board & bit; bit<<=1) shift++; board_bit1 = (u64 *)board; check = CHECK1 << shift; if ((*board_bit1 & check) == check) return; check = CHECK2 << shift; if ((*board_bit1 & check) == check) return; check = CHECK3 << shift; if ((*board_bit1 & check) == check) return; for (i=28; i<35; i++) { if (USED[i]) continue; piece = PIECE[i]; for (form=FORM_TOP[piece],fend=FORM_END[piece]; formcount == -1) break; if (address->silhouette1==*board_bit1 && address->silhouette2==*board_bit2) return address->count; hash = (hash + 491) % DB_SIZE4; } COUNT4 = SE_CNT4 = 0; BackTrack4(board, depth); if (SE_CNT4 >= HEAVY4 && DB_CNT4 < DB_FULL4) { address->count = COUNT4; address->silhouette1 = *board_bit1; address->silhouette2 = *board_bit2; DB_CNT4++; } return COUNT4; } /**********************************************************/ /* BackTrack-3 */ /**********************************************************/ void BackTrack3(u08 *board, int depth) { int i, shift, piece; u08 bit; u16 *board_bit2, piece_bit2; u64 *board_bit1, piece_bit1, *form, *fend, check; while (*board == 0xff) board++; for (shift=0,bit=1; *board & bit; bit<<=1) shift++; board_bit1 = (u64 *)board; check = CHECK1 << shift; if ((*board_bit1 & check) == check) return; check = CHECK2 << shift; if ((*board_bit1 & check) == check) return; check = CHECK3 << shift; if ((*board_bit1 & check) == check) return; if (depth == 28) { if (BlankCheck(board, shift)) return; COUNT3 += DataBase4(board, depth); } else { for (i=21; i<28; i++) { if (USED[i]) continue; piece = PIECE[i]; for (form=FORM_TOP[piece],fend=FORM_END[piece]; formcount == -1) break; if (address->silhouette1==*board_bit1 && address->silhouette2==*board_bit2) return address->count; hash = (hash + 491) % DB_SIZE3; } COUNT3 = SE_CNT3 = 0; BackTrack3(board, depth); if (SE_CNT3 >= HEAVY3 && DB_CNT3 < DB_FULL3) { address->count = COUNT3; address->silhouette1 = *board_bit1; address->silhouette2 = *board_bit2; DB_CNT3++; } return COUNT3; } /**********************************************************/ /* BackTrack-2 */ /**********************************************************/ void BackTrack2(u08 *board, int depth) { int i, shift, piece; u08 bit; u16 *board_bit2, piece_bit2; u64 *board_bit1, piece_bit1, *form, *fend, check; while (*board == 0xff) board++; for (shift=0,bit=1; *board & bit; bit<<=1) shift++; board_bit1 = (u64 *)board; check = CHECK1 << shift; if ((*board_bit1 & check) == check) return; check = CHECK2 << shift; if ((*board_bit1 & check) == check) return; check = CHECK3 << shift; if ((*board_bit1 & check) == check) return; if (depth == 21) { if (BlankCheck(board, shift)) return; COUNT2 += DataBase3(board, depth); } else { for (i=14; i<21; i++) { if (USED[i]) continue; piece = PIECE[i]; for (form=FORM_TOP[piece],fend=FORM_END[piece]; formcount == -1) break; if (address->silhouette1==*board_bit1 && address->silhouette2==*board_bit2) return address->count; hash = (hash + 491) % DB_SIZE2; } COUNT2 = SE_CNT2 = 0; BackTrack2(board, depth); if (SE_CNT2 >= HEAVY2 && DB_CNT2 < DB_FULL2) { address->count = COUNT2; address->silhouette1 = *board_bit1; address->silhouette2 = *board_bit2; DB_CNT2++; } return COUNT2; } /**********************************************************/ /* BackTrack-1 */ /**********************************************************/ void BackTrack1(u08 *board, int depth) { int i, shift, piece; u08 bit; u16 *board_bit2, piece_bit2; u64 *board_bit1, piece_bit1, *form, *fend, check; while (*board == 0xff) board++; for (shift=0,bit=1; *board & bit; bit<<=1) shift++; board_bit1 = (u64 *)board; check = CHECK1 << shift; if ((*board_bit1 & check) == check) return; check = CHECK2 << shift; if ((*board_bit1 & check) == check) return; check = CHECK3 << shift; if ((*board_bit1 & check) == check) return; if (depth == 14) { if (BlankCheck(board, shift)) return; COUNT1 += DataBase2(board, depth); } else { for (i=7; i<14; i++) { if (USED[i]) continue; piece = PIECE[i]; for (form=FORM_TOP[piece],fend=FORM_END[piece]; formcount == -1) break; if (address->silhouette1==*board_bit1 && address->silhouette2==*board_bit2) return address->count; hash = (hash + 491) % DB_SIZE1; } COUNT1 = SE_CNT1 = 0; BackTrack1(board, depth); if (SE_CNT1 >= HEAVY1 && DB_CNT1 < DB_FULL1) { address->count = COUNT1; address->silhouette1 = *board_bit1; address->silhouette2 = *board_bit2; DB_CNT1++; } return COUNT1; } /**********************************************************/ /* BackTrack-0 */ /**********************************************************/ void BackTrack0(u08 *board, int depth) { int i, shift, piece; u08 bit; u16 *board_bit2, piece_bit2; u64 *board_bit1, piece_bit1, *form, *fend, check; while (*board == 0xff) board++; for (shift=0,bit=1; *board & bit; bit<<=1) shift++; board_bit1 = (u64 *)board; check = CHECK1 << shift; if ((*board_bit1 & check) == check) return; check = CHECK2 << shift; if ((*board_bit1 & check) == check) return; check = CHECK3 << shift; if ((*board_bit1 & check) == check) return; if (depth == 7) { if (BlankCheck(board, shift)) return; COUNT += DataBase1(board, depth); } else { for (i=0; i<7; i++) { if (USED[i]) continue; piece = PIECE[i]; for (form=FORM_TOP[piece],fend=FORM_END[piece]; form=0; j--) { board <<= 1; if (MAP[i*8+j]) board |= 1; } BOARD[i] = board; PAINT[i] = 0xff; } /* PIECE, USED */ for (i=0; i<35; i++) { PIECE[i] = i; USED[i] = 0; } } int main(void) { long sum, cnt; double ave, k = 1588729539261710000000.0; /* =35C7×28C7×21C7×14C7÷2 */ time_t start_time; char *file_name = "hexmino.txt"; FILE *fp; start_time = time(NULL); srand(start_time); Initialize(); for (sum=0,cnt=1; cnt<=100; cnt++) { /* TRY SEARCH */ Shuffle(); COUNT = 0; BackTrack0(BOARD, 0); sum += COUNT; ave = (double)sum / (double)cnt; /* WRITE RESULT */ printf("%3d: %e (%5d, %6d, %6d, %7d) COUNT=%5d TIME=%6ds\n", cnt, k * ave ,DB_CNT1, DB_CNT2, DB_CNT3, DB_CNT4, COUNT, time(NULL)-start_time); if (cnt == 1) fp = fopen(file_name, "wt"); else fp = fopen(file_name, "at"); fprintf(fp, "%3d: %e (%5d, %6d, %6d, %7d) COUNT=%5d TIME=%6ds\n", cnt, k * ave , DB_CNT1, DB_CNT2, DB_CNT3, DB_CNT4, COUNT, time(NULL)-start_time); fclose(fp); } return 0; }