INDEX
N Queens Problem (number of Solutions)Version 3.1 (July/2003), Version 3.3 (March/2023)
- 1. Basic Source code and Total Solutions
-
#include <stdio.h>
int SIZE, MASK, COUNT;
void Backtrack(int y, int left, int down, int right)
{
int bitmap, bit;
if (y == SIZE) {
COUNT++;
} else {
bitmap = MASK & ~(left | down | right);
while (bitmap) {
bit = -bitmap & bitmap;
bitmap ^= bit;
Backtrack(y+1, (left | bit)<<1, down | bit, (right | bit)>>1);
}
}
}
int main(void)
{
SIZE = 10; /* <- N */
COUNT = 0; /* result */
MASK = (1 << SIZE) - 1;
Backtrack(0, 0, 0, 0);
printf("N=%d -> %d\n", SIZE, COUNT);
return 0;
}
Board Image and Bit Field:
- - - - - Q - - 00000100 0: Start
- - - Q - - - - 00010000 1: |
- - - - - - Q - 00000010 2: |
Q - - - - - - - 10000000 3: | Back Tracking
- - - - - - - Q 00000001 4: |
- Q - - - - - - 01000000 5: |
- - - - Q - - - 00001000 6: |/
- - Q - - - - - 00100000 7: Last
- 2. Unique Solutions
-
A unique solution is a minimum value in 8 ways of rotation and reverse.
- - - - Q 0
- - Q - - 2
Q - - - - 4 ---> 0 2 4 1 3 (Unique judgment value)
- - - Q - 1
- Q - - - 3
First queen is not here(X). [N>=2]
X X X - - - X X X - -
- - - - - - - - - - -
- - - - - - - - - - -
- - - - - - - - - - -
- - - - - - - - - - -
- - - - - -
If first queen is in the corner, a queen is not here(X).
- - - - X Q
- Q - - X -
- - . - X -
- - - . X -
- - - - A -
- - - - - -
First queen is inside, a queen is not here(X).
X X X X x Q X X
X - - - x x x X
C - - x - x - x
- - x - - x - -
- x - - - x - -
x - - - - x - A
X - - - - x - X
X X B - - x X X
If a queen is not in A and B and C, all Solutions is Unique.
Judgment value is investigated when that is not right.
90-degree rotation. (A)
180-degree rotation. (B)
270-degree rotation. (C)
-
- 3. Total Solutions from Unique Solutions
-
If first queen is in the corner.
Total Solutions = Unique Solutions X 8.
If first queen is inside.
If 90-degree rotation is same pattern as the original.
Total Solutions = Unique Solutions X 2.
Else if 180-degree rotation is same pattern as the original.
Total Solutions = Unique Solutions X 4.
Else
Total Solutions = Unique Solutions X 8.
-
- 4. Completed Source code
-
-- Download nqueens.c (ver3.1 2003) <- recursive
-- Download nqueens2.c (ver3.2 2011) <- non-recursive + OpenMP (Unstable)
-- Download nqueens3.c (ver3.3 2023/03/07) <- non-recursive + OpenMP (Perfect)
-- More high-speed program is here. (by deepgreen)
Version 3.3 (MAR/2023) 2023/03/13
<------ N-Queens Solutions -----> <---- time ---->
N: Total Unique days hh:mm:ss.--
2: 0 0 0.00
3: 0 0 0.00
4: 2 1 0.00
5: 10 2 0.00
6: 4 1 0.00
7: 40 6 0.00
8: 92 12 0.00
9: 352 46 0.00
10: 724 92 0.00
11: 2680 341 0.00
12: 14200 1787 0.00
13: 73712 9233 0.00
14: 365596 45752 0.01
15: 2279184 285053 0.04
16: 14772512 1846955 0.22
17: 95815104 11977939 1.33
18: 666090624 83263591 9.15
19: 4968057848 621012754 1:21.10
20: 39029188884 4878666808 12:41.56
21: 314666222712 39333324973 1:44:33.37
22: 2691008701644 336376244042 14:45:03.08
23: 24233937684440 3029242658210 5 10:37:12.97
CPU i7-10870H 2.21GHz 8-core 16-thread
RAM 16.0GB 2933MHz
Visual Studio Community 2022
INDEX
|