//************************************************************************** // N-Queens Solutions ver3.3 takaken 2023/03/07 //************************************************************************** #include #include #include #define MAXSIZE 25 #define MINSIZE 2 #define i64 __int64 //********************************************** // Check Unique Solutions //********************************************** void Check(int* board, int size, int topb, int posA, int bitB, int posC, i64* count8, i64* count4, i64* count2) { int pos1, pos2, bit1, bit2; // 90-degree rotation if (board[posA] == 1) { for (pos1 = 1, bit2 = 2; pos1 < size; pos1++, bit2 <<= 1) { for (pos2 = size - 1, bit1 = 1; board[pos1] != bit1 && board[pos2] != bit2; pos2--, bit1 <<= 1); if (board[pos1] != bit1) return; if (board[pos2] != bit2) break; } if (pos1 == size) { (*count2)++; return; } } // 180-degree rotation if (board[size - 1] == bitB) { for (pos1 = 1, pos2 = size - 2; pos1 < size; pos1++, pos2--) { for (bit2 = topb, bit1 = 1; board[pos1] != bit1 && board[pos2] != bit2; bit2 >>= 1, bit1 <<= 1); if (board[pos1] != bit1) return; if (board[pos2] != bit2) break; } if (pos1 == size) { (*count4)++; return; } } // 270-degree rotation if (board[posC] == topb) { for (pos1 = 1, bit2 = topb >> 1; pos1 < size; pos1++, bit2 >>= 1) { for (pos2 = 0, bit1 = 1; board[pos1] != bit1 && board[pos2] != bit2; pos2++, bit1 <<= 1); if (board[pos1] != bit1) return; if (board[pos2] != bit2) break; } } (*count8)++; } //********************************************** // First queen is inside //********************************************** void Inside(int size, int x0, int x1, i64* unq, i64* ttl) { int board[MAXSIZE]; int mask, left, right; int posA, bitB, posC, last, topb, side, gate; i64 count8, count4, count2; int y, i; int s_mask[MAXSIZE]; int s_left[MAXSIZE]; int s_right[MAXSIZE]; int s_bits[MAXSIZE]; int bits, bit; // first check if (x1 >= (x0 - 1) && x1 <= (x0 + 1)) return; if (x0 > 1 && (x1 == 0 || x1 == (size - 1))) return; // Initialize mask = (1 << size) - 1; count8 = count4 = count2 = 0; // ControlValue last = size - 1; topb = 1 << last; side = topb | 1; gate = (mask >> x0) & (mask << x0); posA = last - x0; bitB = topb >> x0; posC = x0; // y0: 000001110 (select) // y1: 111111111 (select) board[0] = 1 << x0; board[1] = 1 << x1; mask = mask ^ (board[0] | board[1]); left = board[0] << 2 | board[1] << 1; right = board[0] >> 2 | board[1] >> 1; y = i = 2; // y(=2) -> posA (N = 4) if (posA == 2) { bits = mask & ~(left | right); goto NEXT3; } //------------------------- // y(=2) -> posC //------------------------- if (posC == 1) goto NEXT2; mask = mask ^ side; NEXT1: if (i == posC) { mask |= side; goto NEXT2; } bits = mask & ~(left | right); if (bits) { s_mask[i] = mask; s_left[i] = left; s_right[i] = right; PROC1: bits ^= bit = -bits & bits; board[i] = bit; s_bits[i++] = bits; mask = mask ^ bit; left = (left | bit) << 1; right = (right | bit) >> 1; goto NEXT1; BACK1: bits = s_bits[--i]; if (bits) { mask = s_mask[i]; left = s_left[i]; right = s_right[i]; goto PROC1; } } if (i == y) goto FINISH; goto BACK1; //------------------------- // posC -> posA //------------------------- NEXT2: bits = mask & ~(left | right); if (bits) { s_mask[i] = mask; s_left[i] = left; s_right[i] = right; PROC2: bits ^= bit = -bits & bits; board[i] = bit; s_bits[i++] = bits; mask = mask ^ bit; left = (left | bit) << 1; right = (right | bit) >> 1; if (i == posA) { if (mask & topb) goto BACK2; if (mask & 1) { if ((left | right) & 1) goto BACK2; bits = 1; } else { bits = mask & ~(left | right); if (!bits) goto BACK2; // check of lastline bits and gate if (!(gate & mask & ~(left << (last - i) | right >> (last - i)))) goto BACK2; } goto NEXT3; } else { goto NEXT2; } BACK2: bits = s_bits[--i]; if (bits) { mask = s_mask[i]; left = s_left[i]; right = s_right[i]; goto PROC2; } } if (i == y) goto FINISH; if (i > posC) goto BACK2; goto BACK1; //------------------------- // posA -> last //------------------------- NEXT3: if (i == last) { board[i] = bits; Check(board, size, topb, posA, bitB, posC, &count8, &count4, &count2); goto BACK3; } s_mask[i] = mask; s_left[i] = left; s_right[i] = right; PROC3: bits ^= bit = -bits & bits; board[i] = bit; s_bits[i++] = bits; mask = mask ^ bit; left = (left | bit) << 1; right = (right | bit) >> 1; bits = mask & ~(left | right); if (!bits) goto BACK3; // check of lastline bits and gate if (!(gate & mask & ~(left << (last - i) | right >> (last - i)))) goto BACK3; goto NEXT3; BACK3: bits = s_bits[--i]; if (bits) { mask = s_mask[i]; left = s_left[i]; right = s_right[i]; goto PROC3; } if (i == y) goto FINISH; if (i > posA) goto BACK3; goto BACK2; FINISH: *unq += count8 + count4 + count2; *ttl += count8 * 8 + count4 * 4 + count2 * 2; } //********************************************** // First queen is in the corner //********************************************** void Corner(int size, int x1, i64* unq, i64* ttl) { int board[MAXSIZE]; int mask, left, right; int posA, last; i64 count8; int y, i; int s_mask[MAXSIZE]; int s_left[MAXSIZE]; int s_right[MAXSIZE]; int s_bits[MAXSIZE]; int bits, bit; // Initialize mask = (1 << size) - 1; count8 = 0; // ControlValue last = size - 1; posA = x1; // y0: 000000001 (static) // y1: 011111100 (select) board[0] = 1; board[1] = bit = 1 << x1; mask = mask ^ (1 | bit); left = 1 << 2 | bit << 1; right = 1 >> 2 | bit >> 1; y = i = 2; //------------------------- // y(=2) -> posA //------------------------- mask = mask ^ 2; NEXT1: if (i == posA) { mask |= 2; goto NEXT2; } bits = mask & ~(left | right); if (bits) { s_mask[i] = mask; s_left[i] = left; s_right[i] = right; PROC1: bits ^= bit = -bits & bits; board[i] = bit; s_bits[i++] = bits; mask = mask ^ bit; left = (left | bit) << 1; right = (right | bit) >> 1; goto NEXT1; BACK1: bits = s_bits[--i]; if (bits) { mask = s_mask[i]; left = s_left[i]; right = s_right[i]; goto PROC1; } } if (i == y) goto FINISH; goto BACK1; //------------------------- // posA -> last //------------------------- NEXT2: bits = mask & ~(left | right); if (bits) { if (i == last) { board[i] = bits; count8++; goto BACK2; } s_mask[i] = mask; s_left[i] = left; s_right[i] = right; PROC2: bits ^= bit = -bits & bits; board[i] = bit; s_bits[i++] = bits; mask = mask ^ bit; left = (left | bit) << 1; right = (right | bit) >> 1; goto NEXT2; BACK2: bits = s_bits[--i]; if (bits) { mask = s_mask[i]; left = s_left[i]; right = s_right[i]; goto PROC2; } } if (i == y) goto FINISH; if (i > posA) goto BACK2; goto BACK1; FINISH: *unq += count8; *ttl += count8 * 8; } //********************************************** // Search of N-Queens //********************************************** void NQueens(int size, i64* unique, i64* total) { int i, x0, x1; i64 unq[MAXSIZE], ttl[MAXSIZE]; // Initialize (omp memory) for (i = 0; i < size; i++) unq[i] = ttl[i] = 0; // First queen is in the corner // y=0: 000000001 (static) // y=1: 011111100 (select) #pragma omp parallel for for (x1 = 2; x1 < (size - 1); x1++) { Corner(size, x1, &unq[x1], &ttl[x1]); } // First queen is inside // y=0: 000001110 (select) // y=1: 111111111 (select) for (x0 = 1; x0 < size / 2; x0++) { #pragma omp parallel for for (x1 = 0; x1 < size; x1++) { Inside(size, x0, x1, &unq[x1], &ttl[x1]); } } // Totalling (omp memory -> shared memory) for (i = 0; i < size; i++) { *unique += unq[i]; *total += ttl[i]; } } //********************************************** // Format of Used Time //********************************************** void TimeFormat(clock_t utime, char* form) { int dd, hh, mm; double ftime, ss; ftime = (double)utime / CLOCKS_PER_SEC; mm = (int)ftime / 60; ss = ftime - (double)(mm * 60); dd = mm / (24 * 60); mm = mm % (24 * 60); hh = mm / 60; mm = mm % 60; if (dd) sprintf_s(form, 20, "%4d %02d:%02d:%05.2f", dd, hh, mm, ss); else if (hh) sprintf_s(form, 20, " %2d:%02d:%05.2f", hh, mm, ss); else if (mm) sprintf_s(form, 20, " %2d:%05.2f", mm, ss); else sprintf_s(form, 20, " %5.2f", ss); } //********************************************** // N-Queens Solutions MAIN //********************************************** int main(void) { int size; i64 unique, total; clock_t starttime; char form[20]; printf("<------ N-Queens Solutions -----> <---- time ---->\n"); printf(" N: Total Unique days hh:mm:ss.--\n"); for (size = MINSIZE; size <= MAXSIZE; size++) { starttime = clock(); unique = total = 0; NQueens(size, &unique, &total); TimeFormat(clock() - starttime, form); printf("%2d:%16I64d%16I64d %s\n", size, total, unique, form); } return 0; }