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)

More detailed explanation (Japanese)

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.


More detailed explanation (Japanese)

4. Completed Source code

-- Download nqueens1.c   <- Basic Code
-- Download nqueens2.c   <- Recursive + OpenMP
-- Download nqueens3.c   <- Non-recursive + OpenMP (ver3.3 2023/03/07 High speed)
  
 for Visual Studio Community  nqueens3.zip  Open nqueens3.sln 
When installing Visual Studio Community (free),
please check at least the following two modules:

    (Sorry the image is in Japanese.)
Please research how to build it and how to use it yourself.
-- 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