DAY 9
1

## 老掉牙的 N 皇后問題

``````#include <bits/stdc++.h>
#include "omp.h"
using namespace std;

// 這個範例使用的棋盤大小為 12 x 12。
int N = 12;

// 判斷 (r, c) 能不能放新的皇后。
bool can_put(vector<int> &position, int r, int c) {
for (int i = 0; i < r; i++) {
if (position[i] == c) return false;
if (position[i]-c == i-r) return false;
if (position[i]-c == r-i) return false;
}
return true;
}

// 計算給定目前的盤面 position[0..row_id-1]，總共有幾組解。
int count_nqueen(vector<int> &position, int row_id) {
if (row_id == N) return 1;
int num_solutions = 0;

// 枚舉第 row_id 列的每一個位置，放一隻皇后試試看。
for (int i = 0; i < N; i++) {
vector<int> p2 = position;
if (can_put(p2, row_id, i)) {
p2[row_id] = i;
num_solutions += count_nqueen(p2, row_id+1);
}
}
return num_solutions;
}

int main(void) {
vector<int> position(N);
int count = count_nqueen(position, 0);
printf("%d\n", count);
return 0;
}
``````

``````real	0m1.734s
user	0m1.730s
sys	0m0.000s
``````

`count_nqueen()` 裡面的 for loop 上面加入

``````#pragma omp parallel for reduction(+:num_solutions)
``````

``````real	0m0.603s
user	0m3.180s
sys	0m0.368s
``````

``````real	0m0.499s
user	0m3.079s
sys	0m0.009s
``````

``````int main(void) {
int count = 0;
#pragma omp parallel for reduction(+:count)
for (int i = 0; i < N; i++) {
vector<int> position(N);
position[0] = i;
count += count_nqueen(position, 1);
}
printf("%d\n", count);
return 0;
}
``````