學校課程/平行程式

批改娘 10026. Fast N-Queen

contents

  1. 1. 題目描述
  2. 2. 輸入格式
  3. 3. 輸出格式
  4. 4. 範例輸入
  5. 5. 範例輸出
  6. 6. Solution
    1. 6.1. 樸素平行
    2. 6.2. 負載平衡

題目描述

相信 n-Queen 問題對每個研究 backtracking 的人來講都不陌生，這個問題是要在一個 $n \times n$ 大小的棋盤上擺n個皇后，讓她們不會互相攻擊到。為了讓這個問題更難一點，我們設計了一些障礙物在棋盤上，在這些點上不能放皇后。請留意這些障礙物並不會防止皇后被攻擊。

在傳統的 8-Queen 問題中，旋轉與鏡射被視為不同解法，因此我們有 92 種可能的方式來放置皇后。

輸入格式

輸入的資料最多包含 10 筆測試個案，每個測試個案的第一行會有一個整數 $n$ ($3 < n < 20$)，接下來的 $n$ 行代表棋盤資料，點號 '.' 代表空的盤格，星號 '*' 代表放有障礙物的盤格。

輸出格式

對每筆測試個案，輸出這是第幾個 case 以及這個 case 有幾種可能的放置方式。

範例輸入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
8
........
........
........
........
........
........
........
........
4
.*..
....
....
....

範例輸出

1
2
Case 1: 92
Case 2: 1

Solution

首先，必須先認識最快的 N 皇后問題可以利用 bitmask 的技術，把過多的 memory access 的指令捨去而加速。

  • 樸素平行 Accepted (2766 ms, 512 KB)
  • 負載平衡 Accepted (1771 ms, 5248 KB)

樸素平行

在大多數的教科書上，平行只針對第一個列的位置平行，因此平行度最多 $N$，針對第一列每一個位置都分別開一個 thread 找解，這樣運算時間相當於跑最慢的那一個 thread。

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
#include <stdio.h>
int y_valid[32] = {};
int dfs(int lv, int row, int dia1, int dia2, int mask) {
    if (row == mask)
        return 1;
    int pos = mask & (~(row | dia1 | dia2)) & y_valid[lv], p;
    int ret = 0;
    while (pos) {
        p = pos & (-pos);
        pos -= p;
        ret += dfs(lv+1, row|p, (dia1|p)<<1, (dia2|p)>>1, mask);
    }
    return ret;
}
int totalNQueens(int n) {
    int sum = 0;
    int chunk = 1;
    int row = 0, dia1 = 0, dia2 = 0, mask = (1<<n)-1, lv = 0;
    int pos = mask & (~(row | dia1 | dia2)) & y_valid[0], p;
    #pragma omp parallel for schedule(dynamic, chunk) reduction(+:sum)
    for (int i = 0; i < n; i++) {
        if ((pos>>i)&1) {
            p = 1<<i;
            int t = dfs(lv+1, row|p, (dia1|p)<<1, (dia2|p)>>1, mask);
            sum += t;
        }
    }
    return sum;
}
int main() {
    int cases = 0, n;
    char s[32] = {};
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            y_valid[i] = (1<<n)-1;
            for (int j = 0; j < n; j++) {
                if (s[j] == '*')
                    y_valid[i] ^= (1<<j);
            }
        }
        int ret = totalNQueens(n);
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}

負載平衡

為了達到每一個 thread 盡可能分到相同的工作量，避免最慘的那一條有太多的解而很慢，做好細粒度 (fine-grain) 的分配，如此一來工作量就很高的機率會相同。

因此，一開始先進行廣度搜索，把前幾列的解展開，也許會獲得 $N^x$ 種盤面，這時候平均切給 $M$ 條 thread，分配的工作量平衡上就有比較好的展現。

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
#include <stdio.h>
#define MAXQ 16384
#define MAXN 32
int y_valid[32] = {};
typedef struct Board {
    int row, dia1, dia2;
} Board;
Board R[MAXQ*MAXN];
int dfs(int lv, int row, int dia1, int dia2, int mask) {
    if (row == mask)
        return 1;
    int pos = mask & (~(row | dia1 | dia2)) & y_valid[lv], p;
    int ret = 0;
    while (pos) {
        p = pos & (-pos);
        pos -= p;
        ret += dfs(lv+1, row|p, (dia1|p)<<1, (dia2|p)>>1, mask);
    }
    return ret;
}
int ida_dep, ida_cnt;
void IDA(int lv, int row, int dia1, int dia2, int mask) {
    if (lv == ida_dep) {
        Board b = {.row = row, .dia1 = dia1, .dia2 = dia2};
        R[ida_cnt++] = b;
        return ;
    }
    int pos = mask & (~(row | dia1 | dia2)) & y_valid[lv], p;
    while (pos) {
        p = pos & (-pos);
        pos -= p;
        IDA(lv+1, row|p, (dia1|p)<<1, (dia2|p)>>1, mask);
    }
}
int totalNQueens(int n) {
    int it = 0;
    int row = 0, dia1 = 0, dia2 = 0, mask = (1<<n)-1, lv = 0;
    for (it = 1; it <= n; it++) {
        ida_dep = it, ida_cnt = 0;
        IDA(0, row, dia1, dia2, mask);
        if (ida_cnt >= MAXQ) {
            int sum = 0;
            int chunk = 1024;
            #pragma omp parallel for schedule(static, chunk) reduction(+:sum)
            for (int i = 0; i < ida_cnt; i++)
                sum += dfs(it, R[i].row, R[i].dia1, R[i].dia2, mask);
            return sum;
        }
    }
    return ida_cnt;
}
int main() {
    int cases = 0, n;
    char s[32] = {};
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            y_valid[i] = (1<<n)-1;
            for (int j = 0; j < n; j++) {
                if (s[j] == '*')
                    y_valid[i] ^= (1<<j);
            }
        }
        int ret = totalNQueens(n);
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}