---
# System prepended metadata

title: 2020q3 Homework4 (quiz4)
tags: [進階電腦系統理論與實作]

---

# 2020q3 Homework4 (quiz4)
contributed by < `JimmyLiu0530` >

###### tags: `進階電腦系統理論與實作`

## 測驗1: LeetCode [461. Hamming Distance](https://leetcode.com/problems/hamming-distance/)

兩個整數間的 Hamming distance 為其二進位的每個位元的差。請計算輸入參數兩整數 x 與 y 的 Hamming distance，例如整數 1 的二進位為 0 0 0 1，而整數 4 的二進位為 0 1 0 0，則 1 與 4 的 Hamming distance 為 2。
```c=
int hammingDistance(int x, int y) {
    return __builtin_popcount(x OP y);
}
```

### 程式說明
唯有兩數的某一位元相異，他們的 hamming distance 才會加1，因此先對兩數 x, y 作 `^`，再利用 `__builtin_popcount`計算有幾個位元為1，即為 hamming distance，所以`OP = ^`。

### 延伸問題
#### 1. 舉出不使用 gcc extension 的 C99 實作程式碼。
```c=
int hammingDistance_v2(int x, int y) {
    int total = 0;
    for (int i = 0; i < 31; i++) {
        int oneCount = 0;
        if (((1 << i) & x) != 0)
            oneCount++;
        if (((1 << i) & y) != 0)
            oneCount++;
        total += oneCount * (2 - oneCount);
    }   
    return total;
}
```
仿照延伸問題2的做法，詳細的原理見下方。

#### 2. 練習 LeetCode [477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)，你應當提交你的實作，並確保執行結果正確且不超時
- (第一次提交)用最直覺的方法兩層 for 迴圈，結果超時
- (第二次提交)此方法採 bit-by-bit 的觀點來實作
```c=
int totalHammingDistance(int* nums, int numsSize){
    int total = 0;
    for (int i = 0; i < 31; i++) {
        int oneCount = 0;
        for (int j = 0; j < numsSize; j++) {
            if (((1 << i) & nums[j]) != 0)
                oneCount++;
        }
        total += oneCount * (numsSize - oneCount);
    }
    return total;
}
```
![](https://i.imgur.com/utnf6Mc.png)

假設在某一位元共有 `oneCount` 個數字為1，那麼就有 `(n - oneCount)` 個數字為0，因為陣列中的每個數字皆會與其他數字計算過一次 hamming distance，所以就會使 hamming distance 總和增加 `oneCount * (n - oneCount)`。如此一來，遍歷所有位元的總和即為最後的答案。

#### 3. 研讀[錯誤更正碼簡介](https://w3.math.sinica.edu.tw/math_media/d184/18404.pdf)及[抽象代數的實務應用](https://www.math.sinica.edu.tw/www/file_upload/summer/crypt2017/data/2017/%E4%B8%8A%E8%AA%B2%E8%AC%9B%E7%BE%A9/[20170710][%E6%8A%BD%E8%B1%A1%E4%BB%A3%E6%95%B8%E7%9A%84%E5%AF%A6%E5%8B%99%E6%87%89%E7%94%A8].pdf)，摘錄其中 Hamming Distance 和 Hamming Weight 的描述並重新闡述，舉出實際的 C 程式碼來解說
> - 搭配閱讀 [Hamming codes, Part I](https://www.youtube.com/watch?v=X8jsijhllIA&feature=youtu.be) 及 [Hamming codes, Part II](https://www.youtube.com/watch?v=b3NxrZOu_CE&feature=youtu.be)，你可適度摘錄影片中的素材，但應當清楚標註來源

Hamming weight, 記作 $w_H(x)$, 表示 x 向量有幾個位元為1; 而 Hamming distance, 記作 $d_H(x,x')$, 表示兩個向量有幾個不同的位元，又可透過相加兩向量再取其 hamming weight 得到，因此可以寫成 $w_H(x+x')$ (即 $d_H(x,x')$ = $w_H(x+x')$)。

假設模擬從 sender 取得的16個位元，其中11個 data bits，4個 parity bits:
```c=
char bits[16];
for (int i = 0; i < 16; i++) {
    bits[i] = rand()%2;
}

/*output:{1,0,0,0,1,0,1,0,0,1,1,1,0,1,1,0}*/
```

接著針對所有位元為1的作 XOR，會得到:
```c=
int res = 0;
for (int i = 0; i < 16; i++) {
    if (bits[i])
        res ^= bits[i];
}

/*output: 9*/
```
為了讓上述的 XOR 結果為0，9的二進位為`1001`，因此對第 1 及第 8 個進行位元反轉:
```c=
bits[1] = !bits[1];
bits[8] = !bits[8];

int res = 0;
for (int i = 0; i < 16; i++) {
    if (bits[i])
        res ^= bits[i];
}

/*output: 0*/
```
接下來我們就可以模擬資料傳送過程中受干擾的情況，例如假設第 10 個位元在傳送中受到干擾，XOR 結果就會得到 10，也就是錯誤的位元，因此可以馬上找到錯誤的位元加以修正:
```c=
bits[10] = !bits[10];

int res = 0;
for (int i = 0; i < 16; i++) {
    if (bits[i])
        res ^= bits[i];
}

/*output: 10*/
```


#### 4. 研讀 [Reed–Solomon error correction](https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction)，再閱讀 Linux 核心原始程式碼的 [lib/reed_solomon 目錄](https://github.com/torvalds/linux/tree/master/lib/reed_solomon)，抽離後者程式碼為單獨可執行的程式，作為 ECC 的示範
--------------------------------------

## 測驗2: LeetCode [1483. Kth Ancestor of a Tree Node](https://leetcode.com/problems/kth-ancestor-of-a-tree-node/)

給定一棵樹，樹上有 n 個節點，編號自 0 到 n−1。樹以父節點陣列的形式提供，其中 parent[i] 是節點 i 的父節點。樹的根節點是編號為 0 的節點。請設計 treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k) 函式，回傳節點 node 的第 k 個祖先節點。若不存在這樣的祖先節點，回傳 -1。樹節點的第 k 個祖先節點是從該節點到根節點路徑上的第 k 個節點

```c=
#include <stdlib.h>

typedef struct {
    AAA;
    int max_level;
} TreeAncestor;

TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)
{
    TreeAncestor *obj = malloc(sizeof(TreeAncestor));
    obj->parent = malloc(n * sizeof(int *));

    int max_level = 32 - __builtin_clz(n) + 1;
    for (int i = 0; i < n; i++) {
        obj->parent[i] = malloc(max_level * sizeof(int));
        for (int j = 0; j < max_level; j++)
            obj->parent[i][j] = -1;
    }
    for (int i = 0; i < parentSize; i++)
        obj->parent[i][0] = parent[i];

    for (int j = 1;; j++) {
        int quit = 1;
        for (int i = 0; i < parentSize; i++) {
            obj->parent[i][j] = obj->parent[i][j + BBB] == -1
                                    ? -1
                                    : obj->parent[obj->parent[i][j - 1]][j - 1];
            if (obj->parent[i][j] != -1) quit = 0;
        }
        if (quit) break;
    }
    obj->max_level = max_level - 1;
    return obj;
}

int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)
{
    int max_level = obj->max_level;
    for (int i = 0; i < max_level && node != -1; ++i)
        if (k & (CCC))
            node = obj->parent[node][i];
    return node;
}

void treeAncestorFree(TreeAncestor *obj)
{
    for (int i = 0; i < obj->n; i++)
        free(obj->parent[i]);
    free(obj->parent);
    free(obj);
}
```

### 程式說明
首先，根據 line 10-11及15得知 `obj->parent` 是一個指標的指標，因此 `AAA = int **parent`。

此題的原理: 假設要找某節點的第 k 個祖先，k = 3 (= $2^0+2^1$) 為例，那麼意同於找此節點的第 $2^0$ 個祖先的第 $2^1$ 個祖先。
> **為甚麼要這樣做?**
> 因為 n 個點的樹在最差的情況下有 n-1 個祖先，若將每個節點從第 0 到第 n-1 個祖先記錄下來，則需要 O($n^2$) 的空間，但取得第 k 個祖先只需要 O(1) 的時間。
> 
> 相反的，若不額外記錄各節點的祖先，時間複雜度就會提高。因此本方法能在時間與空間取一個平衡 - 僅記錄第 $2^0$、$2^1$、...、$2^n$ 個祖先。

obj->parent[i][j] 的意義就是第 i 個節點的第 $2^j$ 個祖先是誰，所以 line 14-20 就在對此二維陣列初始化及設定每個節點的第一個祖先。

接著，line 22-31 建立每個節點 i 的第 $2^j$ 個祖先，會先看此節點是否存在第 $2^{j-1}$ 個祖先，
- 若不存在，則此節點必不存在第 $2^j$ 個祖先; 
- 若存在，則此節點的第 $2^j$ 個祖先 = 此節點的第 $2^{j-1}$ 個祖先的第 $2^{j-1}$ 個祖先，因此 `BBB = -1`。

最後呼叫 `treeAncestorGetKthAncestor` 時，根據上述第二段的原理去拆解 k ，因此 `CCC = 1 << i`。


### 延伸問題
#### 1. 指出可改進的地方，並實作對應的程式碼
- Compile error
在 `TreeAncestor` struct 中，新增 `int n;`
```c=
typedef struct {
    ...
    int n;
} TreeAncestor;
```
並在 `treeAncestorCreate` 中，新增 `obj->n = n;`
```c=
TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize) 
{
    TreeAncestor *obj = malloc(sizeof(TreeAncestor));
    obj->parent = malloc(n * sizeof(int *));
    obj->n = n;
}
```

- 減少使用的記憶體
在原本的程式碼中，之所以 `max_level = 32 - __builtin_clz(n) + 1;` 需要 `+1` ，為的就是多額外配置空間給 obj->parent[i] ，好讓底下 line 22 的 `for` 不會越界存取。(因為這裡 `for` 是靠 `quit` 來離開迴圈的)

    也就是說若新增 for 的中止條件，就不用擔心越界，也不需要配置額外空間，來達到節省記憶體的目的。
    
    因此，修改後的部分程式碼如下:
```c=
TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)
{
    ...
    int max_level = 32 - __builtin_clz(n); // remove +1
    ...
    for (int j = 1; j < max_level; j++) { // add j < max_level
        int quit = 1;
        for (int i = 0; i < parentSize; i++) {
            obj->parent[i][j] = obj->parent[i][j - 1] == -1
                                    ? -1
                                    : obj->parent[obj->parent[i][j - 1]][j - 1];
            if (obj->parent[i][j] != -1) quit = 0;
        }
        if (quit) break;
    }
    obj->max_level = max_level; // remove +1
    return obj;
}
```


![](https://i.imgur.com/FOmJocN.png)
修改前的程式碼需要 70.3 MB 的記憶體空間，而修改過後只需 68.5 MB，減少了 1.8 MB。


#### 3. 在 LeetCode [1483. Kth Ancestor of a Tree Node](https://leetcode.com/problems/kth-ancestor-of-a-tree-node/) 提交你的實作，你應該要在 C 語言項目中，執行時間領先 75% 的提交者
--------------------------------------
![](https://i.imgur.com/s6Ckfns.png)


## 測驗3: [FizzBuzz](https://en.wikipedia.org/wiki/Fizz_buzz)

考慮貌似簡單卻蘊含實作深度的 FizzBuzz 題目:
- 從 1 數到 n，如果是 3的倍數，印出 “Fizz”
- 如果是 5 的倍數，印出 “Buzz”
- 如果是 15 的倍數，印出 “FizzBuzz”
- 如果都不是，就印出數字本身

直覺的實作程式碼如下: (`naive.c`)
```c=
#include <stdio.h>
int main() {
    for (unsigned int i = 1; i < 100; i++) {
        if (i % 3 == 0) printf("Fizz");
        if (i % 5 == 0) printf("Buzz");
        if (i % 15 == 0) printf("FizzBuzz");
        if ((i % 3) && (i % 5)) printf("%u", i);
        printf("\n");
    }
    return 0;
}
```
觀察 `printf` 的(格式)字串，可分類為以下三種:

1. 整數格式字串 ``"%d"`` : 長度為 2 B
2. “Fizz” 或 “Buzz” : 長度為 4 B
3. “FizzBuzz” : 長度為 8 B

考慮下方程式碼:
```c=
#define MSG_LEN 8
char fmt[MSG_LEN + 1];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
```
我們若能精準從給定輸入 `i` 的規律去控制 `start` 及 `length`，即可符合 FizzBuzz 題意:
```c=
string literal: "fizzbuzz%u"
         offset:  0   4   8
```
以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: (`bitwise.c`)
```c=
#define MSG_LEN 8

static inline bool is_divisible(uint32_t n, uint64_t M) {
    return n * M <= M - 1;
}

static uint64_t M3 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1;
static uint64_t M5 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 5 + 1;

int main(int argc, char *argv[]) {
    for (size_t i = 1; i <= 100; i++) {
        uint8_t div3 = is_divisible(i, M3);
        uint8_t div5 = is_divisible(i, M5);
        unsigned int length = (2 << div3) << div5;

        char fmt[MSG_LEN + 1];
        strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> KK1) >> (KK2 << KK3)], length);
        fmt[length] = '\0';

        printf(fmt, i);
        printf("\n");
    }
    return 0;
}
```
gcc-9 還內建了 [FizzBuzz optimization](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82853) (Bug 82853 - Optimize x % 3 == 0 without modulo)。

### 程式說明
首先，回顧一下 quiz 2 所學的[快速 mod 運算](https://hackmd.io/JMzU3vDsRYuavmBRvpPjDA#%E6%B8%AC%E9%A9%973-%E5%BF%AB%E9%80%9Fmod%E9%81%8B%E7%AE%97)即可了解 line 3-4, 7-8 及 12-13 的原理，在此不贅述。

根據題目給的提示可以整理成下列四種可能:
| 被n整除 | start | length |
| ------ | ----- | ------ |
| n = 3 | 0 | 4 |
| n = 5 | 4 | 4 |
| n = 15 | 0 | 8 |
| X | 8 | 2 |
(X:不被3或5整除)

再回頭看程式碼，在 line 12-13，`div3` 及 `div5` 若為 1，代表 `i` 分別被 3 跟 5 整除，否則為0，於是根據上面表格可以推算出 `length = (2 << div3) << div5`。

處理完 `length` 接著換 `start`。在 line 17，此處`(MSG_LEN >> KK1) >> (KK2 << KK3)`即為 `start`，一樣根據上表，即可推得 `KK1 = div5`, `KK2 = div3`, `KK3 = 2`。


### 延伸問題
#### 1. 評估 `naive.c` 和 `bitwise.c` 效能落差
> - 避免 stream I/O 帶來的影響，可將 `printf` 更換為 `sprintf`

#### 2. 分析 [Faster remainders when the divisor is a constant: beating compilers and libdivide](https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/) 一文的想法 (可參照同一篇網誌下方的評論)，並設計另一種 bitmask，如「可被 3 整除則末位設為 1」「可被 5 整除則倒數第二位設定為 1」，然後再改寫 `bitwise.c` 程式碼，試圖運用更少的指令來實作出 branchless;
> - 參照 [fastmod: A header file for fast 32-bit division remainders on 64-bit hardware](https://github.com/lemire/fastmod)

--------------------------------------
## 測驗4: 已知除數範圍，加速除法運算

考慮到整數 `PAGE_QUEUES` 可能有以下數值:
- (1 or 2 or 3 or 4)
- (5 or 6 or 7 or 8) x $2^n$, n from 1 to 14

給定 `size_t offset`，試著改善原本運算:
```c=
#include <stdint.h>
size_t blockidx = offset / PAGE_QUEUES;
```
由於 `PAGE_QUEUES` 的數值分佈已知，在整數除法時，可思考加速運算的機制。需要注意，某些硬體平台缺乏整數除法指令 (如 Arm Cortex-A8)，即使 Intel 公司出品的 Core 處裡器 [Sandy Bridge 微架構](https://en.wikipedia.org/wiki/Sandy_Bridge)中，針對 64 位元整數的除法運算，會佔用 40 到 103 個處理器週期，運算成本仍屬沉重。
> 來源: [Agner Fog’s instruction tables](https://www.agner.org/optimize/instruction_tables.pdf)，第 180 頁

於是我們可預先進行計算，從而避免整數除法指令的使用: (假設在 x86_64 硬體執行 GNU/Linux 並透過 gcc/clang 編譯)
```c=
#include <stdint.h>
#define ffs32(x)  ((__builtin_ffs(x)) - 1)
size_t blockidx;
size_t divident = PAGE_QUEUES;
blockidx = offset >> ffs32(divident);
divident >>= ffs32(divident);
switch (divident) {
    CASES
}
```
其中 CASES 可能形如:
```c=
case 2: blockidx /= 2; 
    break;
```
這樣的組合，請用最少的 case-break 敘述做出同等`size_t blockidx = offset / PAGE_QUEUES;` 效果的程式碼。

### 程式說明

此方法原理就是先對被除數以及除數同時右移     `ffs32(divident)`位元，剩下的運算再交給 case 處理。

| divident(dec) | divident(binary) | divident >> ffs(divident) |
| -------- | ------------------------- | ----- |
| 1*$2^n$ | 00010...0 | 0001=1 |
| 2*$2^n$ | 00100...0 | 0001=1 |
| 3*$2^n$ | 00110...0 | 0011=3 |
| 4*$2^n$ | 01000...0 | 0001=1 |
| 5*$2^n$ | 01010...0 | 0101=5 |
| 6*$2^n$ | 01100...0 | 0011=3 |
| 7*$2^n$ | 01110...0 | 0111=7 |
| 8*$2^n$ | 10000...0 | 0001=1 |

根據上面張表可得知 CASES 至少需要包含 1, 3, 5, 7 這四個數字，但又因為任何數除以 1 還是原數，所以只需 3, 5, 7 三數即可。

### 延伸問題
#### 1. 練習 LeetCode [51. N-Queens](https://leetcode.com/problems/n-queens/)，應選擇 C 語言並善用上述的 `__builtin_ffs`，大幅降低記憶體開銷
```c=
int ways[] = {1, 1, 0, 0, 2, 10, 4, 40, 92, 352,
    724, 2680, 14200, 73712, 365596, 2279184, 14772512, 
    95815104, 666090624};

int *QueenPos;
int ***res;
int count = 0;

void StoreAnswer(int n)
{
    char* queen = malloc((n + 1) * sizeof(char));
    queen[n] = '\0';
    for (int i = 0; i< n; i++){
        for(int j = 0; j< n; j++){
            queen[j] = (QueenPos[i] == j) ? 'Q' : '.';
        }
        memcpy(res[count][i], queen, n + 1);        
    }
    free(queen);
    count++;
}

bool checkQueen(int row, int col)
{
    for (int i = 0; i < row; i++) {
        if (col == QueenPos[i] || abs(col - QueenPos[i]) == abs(row - i))
            return false;
    }
    return true;
}

void NQueens(int row, int n)
{
    if (count == ways[n])
        return;
    
    for (int j = 0; j < n; j++) {
        if (checkQueen(row, j)) {
            QueenPos[row] = j;
            if (row == n - 1)
                StoreAnswer(n);
            else
                NQueens(row + 1, n);
        }
    }   
}

char ***solveNQueens(int n, int *returnSize, int **returnColumnSizes)
{
    *returnSize = ways[n];
    *returnColumnSizes = malloc(ways[n] * sizeof(int));
    for (int i = 0; i < ways[n]; i++) {
        (*returnColumnSizes)[i] = n;
    }
    
    QueenPos = malloc(n * sizeof(int));
    
    res = malloc(ways[n] * sizeof(char **));
    for (int i = 0; i < ways[n]; i++) {
        res[i] = malloc(n * sizeof(char *));
    }
    for (int i = 0; i < ways[n]; i++) {
        for (int j = 0; j < n; j++) {
            res[i][j] = malloc((n + 1) * sizeof(char));
        }
    } 
    
    NQueens(0, n);
    count=0;
    return res;
}
```

程式說明:
- 大致流程(可搭配下面的圖來看): 
    - 從第0列開始，一列一列往下看。
    - 每一列中，由左至右一行一行看，透過呼叫 `CheckQueen` 檢查是否 Queen 可以放在此位置
        - 若可以，則遞迴的往下一列去看(即`NQueens(row+1)`)
        - 這裡還要檢查是否為最後一列，若是，則以找到其中一種棋盤擺放方式，呼叫 `PushAnswer` 將結果存入 `res`
    - 若已找到全部的擺放方式，則 return
```graphviz
digraph{
    node [shape = record]
    
    n1[label="{Q|x|x|x}|{x|x||}|{x||x|}|{x|||x}"]
    n2[label="{x|Q|x|x}|{x|x|x|}|{|x||x}|{|x||}"]
    n3[label="{x|x|Q|x}|{|x|x|x}|{x||x|}|{||x|}"]
    n4[label="{x|x|x|Q}|{||x|x}|{|x||x}|{x|||x}"]
    
    n1302[label="{Q|x|x|x}|{x|x|x|Q}|{x|Q|x|x}|{x|x|x|x}" color = gray]
    n14[label="{Q|x|x|x}|{x|x||x}|{x|x|x|}|{x|Q|x|x}"]
    n24[label="{x|x||}|{Q|x|x|x}|{x|x|x|}|{x|Q|x|x}"]
    n31[label="{x|Q|x|x}|{x|x|x|}|{Q|x|x|x}|{x|x||}"]
    n41[label="{x|Q|x|x}|{x|x|x|}|{x|x||x}|{Q|x|x|x}"]
    n4203[label="{x|x|x|x}|{x|Q|x|x}|{x|x|x|Q}|{Q|x|x|x}" color = gray]
    
    n1420[label="{Q|x|x|x}|{x|x|Q|x}|{x|x|x|x}|{x|Q|x|x}" color = gray]
    n1403[label="{Q|x|x|x}|{x|x|x|x}|{x|x|x|Q}|{x|Q|x|x}" color = gray]
    n2413[label="{x|x|Q|x}|{Q|x|x|x}|{x|x|x|Q}|{x|Q|x|x}" color= red]
    n2401[label="{x|x|x|Q}|{Q|x|x|x}|{x|x|x|x}|{x|Q|x|x}" color = gray]
    n3142[label="{x|Q|x|x}|{x|x|x|Q}|{Q|x|x|x}|{x|x|Q|x}" color= red]
    n3104[label="{x|Q|x|x}|{x|x|x|x}|{Q|x|x|x}|{x|x|x|Q}" color = gray]
    n4130[label="{x|Q|x|x}|{x|x|x|x}|{x|x|Q|x}|{Q|x|x|x}" color = gray]
    n4102[label="{x|Q|x|x}|{x|x|x|Q}|{x|x|x|x}|{Q|x|x|x}" color = gray]
    
    root->n1->n1302
          n1->n14->n1420
              n14->n1403
    root->n2->n24->n2413
              n24->n2401
    root->n3->n31->n3142
              n31->n3104
    root->n4->n41->n4130
              n41->n4102
          n4->n4203
    
    
}
```


- `***solveNQueens(int n, int *returnSize, int **returnColumnSizes)`
    - `*returnSize`: 記錄 `res` 的 2D array 數量(即 `ways[n]`)
    - `**returnColumnSizes`: 記錄每個 2D array 的行數(即 `n`)
    - `QueenPos`: 記錄各列 Queen 所在的行數(即 QueenPos[1]=3 代表 Queen在第一列第三行)
    - `***res`: 記錄每個答案的棋盤擺放方式
    
- `NQueens(int row, int n)`
    - 主要就是**遞迴**的去找可能的擺放方式
    - line 34-35 用來判斷是否已找到全部擺放方式

- `checkQueen(int row, int col)`
    - 檢查該 `row` 以上的所有格子看是否已存在 Queen 使得
        1. 與 `col` 同一行 或
        2. 在 `(row, col)` 的右上或左上
    - 若都沒有，代表 `(row, col)` 可以放 Queen，反之，則不行放

- `StoreAnswer(int n)` 
    - 根據 `QueenPos` 將一種擺放方式存到 `res` 中
        - 看過所有 n x n 個格子，若該格有擺放 Queen，則為 `'Q'`，否則為 `'.'`