Parallel N-Queens

title: N-Queens
class: center, middle

## Parallel N-Queens Problem

### 平行 N 皇后問題

R04922067 楊翔雲, Morris

NTU CSIE

---

## N 皇后問題 ##

* 在一個 `\(N \times N\)` 大小的棋盤上擺 `\(N\)` 個皇后，求有多少種解法

* 下圖為 `\(8 \times 8\)` 棋盤上，放置一皇后的攻擊範圍

.center[![](./images/p10074-board.PNG)]

---

## 回溯找解 ##

* 依序放入可行的位置

* 第一行放置一個 `\(N\)` 種

* 第二行放置一個 `\(N-1\)` 種

* ...

* 運行次數 `\(N \cdot (N-1) \cdot (N-2) \cdots 1 = N!\)`

* 當 `\(N = 20\)` 時，`\(20! = 2432902008176640000\)`

---

## 回溯找解 + 剪枝 ##

* 三個基本要求不可同行、同列、同對角

* 根據窮舉行的順序，故可保證不同行

* 只需要檢查同列、同對角

## 合法放置的檢查效能 ##

* 嚴重影響效能

* 演算法的操作常數

---

## 檢查操作 - 按部就班 ##

### 對角檢查 - `\(O(n)\)` ###

```c
int isValid(int x, int y, int pos[][2], int n) {
    for (int i = 0; i < n; i++) {
        if (abs(pos[i][0]-x) == abs(pos[i][1]-y))
          return 0;
    }
    return 1;
}
```

### 同列檢查 - `\(O(1)\)` ###

```c
int place[MAX_COLUMN];
if (place[c] == 0) {
    // recursion
}
```

---

## 檢查操作 - 精簡 ##

* 如果同列檢查都能 `\(O(1)\)`，對角檢查也可以 `\(O(1)\)`

* 將正反對角線依序編號

```c
#define MAXN 20
int dia1[MAXN*2], dia2[MAXN*2];

int isValid(int x, int y) {
    return (dia1[x+y] || dia2[x-y+MAXN]);
}
```

---

## 窮舉操作 ##

* 在每一層搜索時，必須對每一個位置檢查是否合法

* 使得確切運行次數為 `\(N\)`

* 如何降低常數，並非運行 `\(O(N \cdot N!)\)`，而是真正的 `\(O(N!)\)`

```c
int dfs(int level, State state) {
    ...
    for (int i = 0; i < n; i++) {
        if (!isValid(level+1, transfer(state, i)))
            continue;
        ...
    }
    ...
}
```

---

## 窮舉操作 - 精簡 ##

* 使用鏈結串列維護候選名單

* 每次加深搜索將減少一個候選選項

* 這只是一種概念，實作方法很重要

```c
int dfs(int level, State state, list cand) {
    ...
    for (auto e: cand) {
        if (!isValid(level+1, transfer(state, i)))
            continue;
        cand.erase(e);
        ...
        cand.insert(e);
    }
    ...
}
```

---

## 窮舉操作 - 極致 ##

* Bit-level parallelism： `\(O(1)\)` 找到所有合法的解

* 將放置資訊壓成 0/1 bit，則 1 表示放置、0 表示尚未放置。

* 在皇后問題中，剩餘的合法位置   
`all & (~(row | dia1 | dia2))`，其中 `all = (1<<n)-1`

```c
int dfs(int row, int dia1, int dia2, ...) {
    int pos = all & (~(row | dia1 | dia2));
    while (pos) {
        int lowbit = pos&(-pos);
        pos ^= lowbit;
        dfs(row|lowbit, (dia1|lowbit)<<1, (dia2|lowbit)>>1, ...);
        ...
    }
    ...
}
```

---

class: center, middle

## 今天還要來點平行嗎 ##

---

## 平行設計 - 搜索 ##

* 搜索次數無法估計

* 搭配剪枝更難計算

* 平行工作分配不均

---

## 平行設計 - 第一步 ##

* 第一行放置有 `\(N\)` 種方法

* 分別平行統計後，合併整體的解個數

```c
#pragma omp parallel for
for (int i = 0; i < n; i++) {
    place_first_row(i);
    dfs(...)
}
```

分兩種問題討論：

* 當處理器個數遠小於 `\(N\)`，scheduling policy 影響效能

* 當處理器個數遠大於 `\(N\)`，平行度不足以使用所有處理器

---

## 平行設計 - 第二步 ##

* 為拓展平行度，將子問題展開，藉以得到足夠的平行度

* 如果展開到第二行以上，子問題個數接近 `\(N^2\)` 種

```c
all_state = bfs(init_state, #limit_state);

#pragma omp parallel schedule(???)
for (auto s: all_state) {
    dfs(s)
}
```

代價

* 不易平行的 Breadth-First-Search

* 額外的記憶體空間

---

## 平行設計 - 等價交換 ##

* 展開前三行的所有可能

* 利用 `OpenMP` 的語法 `collapse()`

* 將好幾層 for 迴圈壓平後平行

```c
#pragma omp parallel
{
    #pragma omp for schedule(???) collapse(3)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                dfs_config(i, j, k, n);
            }
        }
    }
}
```

---

## 所追求的目標 ##

* 轉換成精準覆蓋問題，使用 Dancing Links 解決皇后問題

* 以增強中途剪枝的能力

* 以位元運算實作 Dancing Links + Algorithm X 算法