--- tags: 成大高階競技程式設計 2020, ys --- :+1: [2020 競技程設教材 HackMD Book](https://hackmd.io/@nckuacm/ryLIV6BYI) :+1: 2020 Week 5: Graph Structures = 本週要繼續介紹些基本的資料結構 並且接下來將使用這些資料結構構造(解釋)一些演算法 > 底下的術語挺多的,各位不需馬上就得記起來,等到未來碰到再回來多複習幾遍 # Graph 圖 (Graph),是一個由邊 (Edge) 集合與點 (Vertex) 集合所組成的資料結構 ![](https://i.imgur.com/Z5A39X3.png) 圖的術語: * 點 (vertex): 組成圖的最基本的元素 * 邊 (edge): 點與點的關係 * $u$ 的鄰點 (neighbors): $u$ 透過一個邊連到的所有點 * 有向圖 (directed graph): 邊帶有**方向**性 * 無向圖 (undirected graph): 每條邊都是**雙向**的 * 道路 (walk[^7]): 點邊相間的序列, e.g. $v_0e_1v_1e_2v_2..e_nv_n$ * 行跡 (trail): **邊不重複**的道路 * 路徑 (path): **點不重複**的道路[^8] * 環 (cycle): 路徑的**起**點與**終**點連接後形成環 * 度 (degree): 與該點連接的邊數量 (無向性) * 入度 (in-degree): 連到該點的邊數量 (方向性) * 出度 (out-degree): 該點往外連的邊數量 (方向性) * 走訪/遍歷 (traversal/search): 走完全部的點或邊 > 口語上常會把路徑表示成道路,但根據多數的圖論書籍,這兩者定義是不同的 在討論圖的邊,常會有 $u$ 是邊起點與 $v$ 是邊終點的慣例用符 ```graphviz digraph { rankdir="LR"; u -> v; } ``` > 上面這就是一種有向圖 ## 圖的儲存 通常圖用鄰接表 (adjacency list) 或鄰接矩陣 (adjacency matrix) 儲存資料 ### 鄰接表 ```cpp struct edge { int u, v, w; }; // 兩個相鄰點與邊權重 vector<edge> E; int main() { : . while(M--) { scanf("%d%d%d", &u, &v, &w); E.push_back({u, v, w}); } } ``` 直接紀錄所有邊(兩點與權重) 或是 ```cpp struct vertex { int v, w; }; // 鄰點與邊權重 vector<vertex> E[MAXN]; int main() { : . while(M--) { scanf("%d%d%d", &u, &v, &w); E[u].push_back({v, w}); } } ``` 為每個點紀錄其所有鄰點與之間的權重 ### 鄰接矩陣 ```cpp int E[MAXN][MAXN]; int main() { : . while(M--) { scanf("%d%d%d", &u, &v, &w); E[u][v] = w; } } ``` 為每對點紀錄邊的關係 (有無權重可代表是否有邊) > 使用鄰接矩陣要注意空間成本 --- # Tree 樹 (Tree),這個資料結構在圖像化看起來像顆倒掛的[樹](https://zh.wikipedia.org/wiki/%E6%A0%91),根在上,而葉子在下。 ![](https://i.imgur.com/j8BGaid.png) 樹的術語及特點: * 樹是種**有向無環連通圖** * 節點 (node): 樹上的點不使用圖的術語:點 (vertex) * 父 (parent): 節點能**反向**拜訪的**第一個**節點 * 子 (child): 節點能**正向**拜訪的**第一個**節點 * 祖先 (ancestor): 節點能反向拜訪的所有節點 * 孫子 (descendant): 節點能正向拜訪的所有節點 * 根 (root): 沒有父節點的節點 * 葉 (leaf): 沒有子節點的節點 * 深度 (depth): 節點的深度為從根到該節點所經過的邊數 * 森林 (forest): 一個集合 包含所有不相交的樹 * ==**每個非根節點只有一個父節點**== > 在數學上的圖論領域,通常樹是種**無向**無環的連通圖 ## 樹的儲存 將節點本身的資料,以及連接的其他節點位置以 `node` 結構保存下來 ```cpp struct node { int val; // value node *ch1, *ch2, *ch3, *ch4; // vector<node*> ch; } ``` --- # Union-Find Forest (併查森林) 考慮設計一個結構, 它要能存放一些集合,且這些集合之間**沒有相同元素** 這樣的集合族稱作 **Disjoint sets** > Disjoint sets 通常應用在"**分類**"問題中 直觀的想法是將每個**集合有哪些元素**,用陣列或連結串列紀錄起來 而常見的集合操作有,新增、刪除、(取)聯集、取交集(?)、取集合大小 >可以思考一下這些操作的複雜度要多少 但併查森林則是將紀錄方式從 "集合有哪些元素" 改為 "**元素屬於哪個集合**" ## Initialization ```cpp for (int v = 1; v <= N; v++) group[v] = v; ``` ```graphviz graph { 1; 2; 3; 4; "..."; "N-1"; N; } ``` ## Find Find 會尋找某個元素屬於哪個集合 ```cpp int Find(int v) { if (v == group[v]) return v; return Find(group[v]); } ``` 假設有元素 $1$ ~ $5$,其中 $1,2$ 一組,$3,4,5$ 一組。 ```graphviz digraph { 1 -> 2; 3 -> 4; 4 -> 5; } ``` 下 `Find(5)` 指令,會回傳 $3$ ### Path Compression 稍微想像一下可發現,若樹長這樣: ```graphviz digraph { rankdir="LR"; p[label = "..."]; 3 -> 4 -> 5 -> "..." -> i -> p -> N; } ``` 那麼明顯 `Find(i)` 的複雜度為 $O(N)$ 直覺的,如果樹不是長得這麼長,而是**一個個節點**都直接接在 $3$ 底下 那麼 `Find(i)` 的複雜度似乎就能下降了。 所以每當回溯時就順便把最上層 group 的標號[^10](也就是 $3$) 給所有拜訪完的節點 $i$ 也就是改寫為: ```cpp int Find(int v) { if (v == group[v]) return v; return group[v] = Find(group[v]); // Path Compression } ``` 於是原本的森林下 `Find(5)` 指令 ```graphviz digraph { 1 -> 2; 3 -> 4; 4 -> 5; } ``` 森林會變成: ```graphviz digraph { 1 -> 2; 3 -> 4; 3 -> 5; } ``` ## Union Union 會將兩個集合合併起來 > 再次提醒:此集合族是 disjoint 的 ```cpp void Union(int u, int v) { group[Find(u)] = Find(v); } ``` 若對下圖這樣的情況,做 `Union(4, 2);` 也就是將 $4$ 的 root $3$ 合併到 $2$ 的 root $1$ ```graphviz digraph { 1 -> 2; 3 -> 4; 3 -> 5; } ``` 則上圖會變為下圖這樣: ```graphviz digraph { 1 -> 2; 1 -> 3 -> 4; 3 -> 5; } ``` 還有種方式稱作 [Union by rank/size](https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Union),將 rank/size 小的樹併到 rank/size 大的樹下,可以加快許多。 #### 範例 [UVa OJ 879 Circuit Net](https://uva.onlinejudge.org/external/8/879.pdf): ```cpp int u, v; cin.ignore(); // for getline while (getline(cin, pins)) { if (pins.empty()) break; // for getline stringstream sin(pins); while (sin >> a >> b) Union(a, b); } int cnt = 0; for (int i = 1; i <= N; i++) if (group[i] == i) cnt++; ``` >`std::stringstream` 是很方便的東西,不過據說效率不夠優。 #### 練習: [UVa OJ 10583 Ubiquitous Religions](https://uva.onlinejudge.org/external/105/10583.pdf) [UVa OJ 11987 Almost Union-Find](https://uva.onlinejudge.org/external/119/11987.pdf) [TIOJ 1192 鑰匙設計](https://tioj.ck.tp.edu.tw/problems/1192) [CODEFORCES 1253D Harmonious Graph](https://codeforces.com/contest/1253/problem/D) # 搜尋 有了圖,有了樹,可以開始討論這回事了 不彷將搜尋所能觸及到的 可能性/目標 稱為**狀態** 每當狀態改變後,前個狀態到下個狀態的過程稱**狀態轉移**。 若把狀態看作**點**,而狀態轉移看作**邊**,包含這些點與邊的**圖**稱作**狀態空間** 回憶一下上面曾介紹的術語: * 走訪/遍歷 (traversal/search): 走完全部的點或邊 遍歷也是種搜尋,但"走完"可能得付出龐大的時間成本,或是空間成本 根據狀態空間規模,須用一些手段使得能更快速的找到所想要的東西。 本章使用的圖論符號慣例: - $V$ (Vertex) 表節點集合,表達單一點常用 $u$, $v$ - $E$ (Edge) 表邊集合,通常起點用 $u$、終點用 $v$ 作為點符號 > $u \to v$ 邊可寫成 $(u, v) \in E$ # 深度優先搜尋 (Depth-first Search) 顧名思義,要盡量以深層的方式搜尋,以下簡稱 DFS ```graphviz graph { node[label=""]; a -- e; a -- b; b -- c; c -- d -- b; c -- e; c -- f; b -- g; b -- h -- a; h -- i -- b; h -- j; a -- k; k -- l; a -- m; m -- n; m -- o -- a; } ``` 走訪方式:每拜訪一點就往其一鄰點拜訪下去。 >這裡的走訪為走遍所有**點** (而非邊) >若中途碰到曾走過的點不往下繼續走。[^dfs-1] ```graphviz graph { edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 1 -- 2; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=black] 1 -- 6; 6 -- 3; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 3 -- 5 -- 6; 3 -- 2; 3 -- 4; 6 -- 7; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=black] 6 -- 9; 9 -- 1; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 9 -- 8 -- 6; 9 -- 10; 1 -- 11; 11 -- 12; 1 -- 13; 13 -- 14; 13 -- 15; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=black] 15 -- 1; } ``` 按照上圖,走訪**順序**為 $1$ 依照自然數列開始走訪到 $15$。 DFS 走過的道路為**樹**,稱此樹為 DFS 樹: ```graphviz digraph { edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 1[ xlabel = <0> ]; 2[ xlabel = <1> ]; 11[ xlabel = <1> ]; 13[ xlabel = <1> ]; 3[ xlabel = <2> ]; 12[ xlabel = <2> ]; 14[ xlabel = <2> ]; 15[ xlabel = <2> ]; 4[ xlabel = <3> ]; 5[ xlabel = <3> ]; 6[ xlabel = <4> ]; 7[ xlabel = <5> ]; 8[ xlabel = <5> ]; 9[ xlabel = <6> ]; 10[ xlabel = <7> ]; 1 -> 2; 2 -> 3; 3 -> 4; 3 -> 5; 5 -> 6; 6 -> 7; 6 -> 8; 8 -> 9; 9 -> 10; 1 -> 11; 11 -> 12; 1 -> 13; 13 -> 14; 13 -> 15; } ``` (圖上節點左上角的數字代表深度) ```cpp void dfs(int u, int dep) { // dep := depth for (int v: E[u]) { if (vis[v]) continue; vis[v] = true; dfs(v, dep+1); } } ``` > 這裡 for 迴圈採用 [Range-based](https://en.cppreference.com/w/cpp/language/range-for) 寫法 其中 `vis[i]`[^convention] 為 `true` 代表此點已**拜訪完**,下次遇到此點直接略過。 所以在開始進行走訪前,將起點設為**拜訪完**: ```cpp vis[root] = true; // root 代表走訪此圖的起點 dfs(root, 0); ``` DFS 除了能夠以上述遞迴方式呈現,也可以採用 **stack** 來實作: ```cpp stack<tuple<int, int, int>> S; S.emplace(root, 0, 0); vis[root] = true; while (!S.empty()) { auto [u, cur, dep] = S.top(); S.pop(); // cur := current index for (int i = cur; i < E[u].size(); i++) { int v = E[u][i]; if (vis[v]) continue; vis[v] = true; S.emplace(u, i, dep); S.emplace(v, 0, dep+1); break; } } ``` ## 狀態空間搜尋[^dfs-2] 搜尋某個**狀態**,可以利用**函式**與**參數**表示,例如會把 `f(1, 2, 3)` 和 `f(3, 4, 5)` 這樣的函式呼叫,當作不同的狀態去接觸(求解)它。 #### 範例 [UVa OJ 572 Oil Deposits](https://uva.onlinejudge.org/external/5/572.pdf): 題目要求一個區域中有幾個**連通**圖 所謂的連通,就是圖中任意兩點間至少有一條路徑 當接觸到 `dfs(r, c)` 狀態時,代表這裡有包含座標 $(r, c)$ 的 oil deposit (前提 `plot[r][c]` 為 `'@'`) 而 DFS 走訪時,只需確保不再重複走到走過的點,所以走過就設 `'*'` ```cpp void dfs(int r, int c) { if (plot[r][c] == '*') return; plot[r][c] = '*'; for (int dr = -1; dr <= 1; dr++) for (int dc = -1; dc <= 1; dc++) //雙重迴圈讓八個方位都走 if (r+dr >= 0 && r+dr < m && c+dc >= 0 && c+dc < n) dfs(r+dr, c+dc); } ``` *只要是連通圖,DFS 都能把此圖走訪完* 這裡簡單算走進幾次連通圖就好 ```cpp int count = 0; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (plot[i][j] == '@') { dfs(i, j); count++; } ``` # 廣度優先搜尋 (Breadth-first Search) 顧名思義,要盡量以寬廣的方式搜尋,以下簡稱 BFS ```graphviz graph { node[label=""]; a -- e; a -- b; b -- c; c -- d -- b; c -- e; c -- f; b -- g; b -- h -- a; h -- i -- b; h -- j; a -- k; k -- l; a -- m; m -- n; m -- o -- a; } ``` 走訪方式:每拜訪一節點就將其全部鄰點拜訪過。 >同 DFS,碰到曾走過的點則不往下繼續走 ```graphviz graph { edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 1 -- 2; 1 -- 3; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=black] 3 -- 8; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=black] 8 -- 10; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 10 -- 3; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 8 -- 2; 8 -- 15; 3 -- 9; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=black] 3 -- 4; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 4 -- 1; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=black] 4 -- 11; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 11 -- 3; 4 -- 12; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 1 -- 5; 5 -- 13; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 1 -- 6; 6 -- 14; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=black] 6 -- 7; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 7 -- 1; } ``` 按照上圖,走訪**順序**為 $1$ 依照自然數列開始走訪到 $15$。 對於一個**點**,會經歷以下階段: 1. 未拜訪:不曾進入隊列 2. 拜訪中:進入隊列 3. 拜訪完:離開隊列 則 BFS 的流程為: 1. 將起點(root)加入隊列中 2. 每次將一個拜訪中的點 $u$ 的所有**未拜訪鄰點**加進隊列,而 $u$ 就此拜訪完畢 3. 重複動作 2. 直至隊列為空 > 若圖是連通圖,則 BFS 會將所有點都拜訪過 ```cpp queue<int> Q; Q.push(root); //root 代表走訪此圖的起點 vis[root] = true; while (!Q.empty()) { int u = Q.front(); Q.pop(); for (auto& v: E[u]) { if (vis[v]) continue; vis[v] = true; Q.push(v); } } ``` > 根據條件應將不合法的走法濾掉,在 `Q.push()` 之前可判斷一下。 >BFS 跟 DFS 結構只差在 stack 和 queue,除此之外兩者是非常相似的 與 DFS 同樣,由於不會走訪曾走過的點,所以 BFS 走完後也會有個 BFS 樹: ```graphviz digraph { 1[ xlabel = <0> ]; 2[ xlabel = <1> ]; 3[ xlabel = <1> ]; 4[ xlabel = <1> ]; 5[ xlabel = <1> ]; 6[ xlabel = <1> ]; 7[ xlabel = <1> ]; 8[ xlabel = <2> ]; 9[ xlabel = <2> ]; 10[ xlabel = <2> ]; 11[ xlabel = <2> ]; 12[ xlabel = <2> ]; 13[ xlabel = <2> ]; 14[ xlabel = <2> ]; 15[ xlabel = <3> ]; edge[arrowhead=vee, arrowtail=inv, arrowsize=.87, color=maroon] 1 -> 2; 2 -> 8; 8 -> 15; 1 -> 3; 3 -> 9; 3 -> 10; 3 -> 11; 1 -> 4; 4 -> 12; 1 -> 5; 5 -> 13; 1 -> 6; 6 -> 14; 1 -> 7; } ``` ## 最短步數 搜索地圖**起點到任意點**的最短步數/路徑, 例如地圖上 `*` 代表牆(不能走),`$` 代表路,`%` 是起點,`@`是終點 且每一步只走上下左右一格: ``` * * * * * * * * * * * * * * $ % $ $ * * * $ $ $ $ * * $ * * * $ * $ * * * $ * * * $ * $ $ $ * $ * * * $ * $ * $ $ $ * * * $ $ * * $ * $ $ * * * $ $ $ * * * $ * * @ * * $ * $ $ $ * * $ * * $ * $ * $ * * $ $ $ $ $ $ * * * * * * * * * * * * * ``` BFS 可以應用在這[^bfs-1]: ```haskell * * * * * * * * * * * * * * 1 0 1 2 * * * 5 4 3 2 * * 3 * * * 6 * 4 * * * 4 * * * 7 * 5 6 7 * 5 * * * 8 * 6 * 8 7 6 * * * 9 10 * * 9 * 7 8 * * * 11 12 13 * * * 9 * * 21 * * 14 * 12 11 10 * * 20 * * 15 * 13 * 11 * * 19 18 17 16 15 14 * * * * * * * * * * * * * ``` 其中上面數字代表**深度**。 這個走法就跟[粘菌走迷宮](https://www.youtube.com/watch?v=czk4xgdhdY4)同樣 #### 範例 [UVa OJ 11624 Fire!](https://uva.onlinejudge.org/external/116/11624.pdf): 最開始先將 Joe 與各火點放進 queue 中,以便讓 BFS 以此為起點走訪: ```cpp for (int r = 0; r < R; r++) { scanf("%s", input); for (int c = 0; c < C; c++) { if (input[c] == '#') maze[r][c] = 0; if (input[c] == '.') maze[r][c] = INF; if (input[c] == 'J') J.push({r, c, 0}), maze[r][c] = INF, vis[r][c] = true; if (input[c] == 'F') F.push({r, c, 0}), maze[r][c] = 0; } } ``` (其中 `INF`[^convention] 為一個非常大的數字,例如 `int` 的上限) Joe 不能被火燒到,所以 Joe 一定要**走得比火快** 由此,算出各點何時火會燒過來就能判斷 Joe 是否能比火先到 搜尋火到各點的**最短路**: ```cpp while (!F.empty()) { point f = F.front(); F.pop(); for (int d = 0; d < 4; d++) { int nr = f.r+dr[d], nc = f.c+dc[d]; if (nr == R || nc == C || nr < 0 || nc < 0 || maze[nr][nc] != INF || maze[nr][nc] == 0) continue; maze[nr][nc] = f.t + 1; F.push({nr, nc, f.t+1}); } } ``` 其中 `point` 結構三個變數為 **r**ow, **c**olumn 與 **t**ime (火抵達的時間) 並利用 dr 與 dc 以當前所在點走遍四個方向: ```cpp /* 左, 右, 下, 上 */ int const dr[] = {0, 0, -1, 1}; int const dc[] = {-1, 1, 0, 0}; ``` 現在 maze (也就是地圖) 上有紀錄火到的時間了。 接下來讓 Joe 去尋找最短路: ```cpp int escape = -1; while (!J.empty()) { point j = J.front(); J.pop(); if ((j.r == R-1 || j.c == C-1) || (j.r == 0 || j.c == 0)) { escape = j.t + 1; break; } for (int d = 0; d < 4; d++) { int nr = j.r+dr[d], nc = j.c+dc[d]; if (vis[nr][nc] || j.t + 1 >= maze[nr][nc]) continue; vis[nr][nc] = true; J.push({nr, nc, j.t+1}); } } ``` `j.t + 1 >= maze[nr][nc]` 就能看 Joe 走這點是不是會被火燒 最後判斷走到邊界,就成功逃脫了! #### 練習: [UVa OJ 532 Dungeon Master](https://uva.onlinejudge.org/external/5/532.pdf) [STEP5 0127 攻略妹妹](http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0127) [UVa OJ 11234 Expressions](https://uva.onlinejudge.org/external/112/11234.pdf) [UVa OJ 1599 Ideal Path](https://uva.onlinejudge.org/external/15/1599.pdf) \* [CODEFORCES 1307D Cow and Fields](https://codeforces.com/problemset/problem/1307/D) # Backtracking >利用各種可得的限制來做搜尋目標中的偷吃步 八皇后問題[^bt-1]:西洋棋盤上任意擺放八個皇后彼此都不互攻的情況有幾種? 如下圖是其中一種合法的擺法 ![](https://i.imgur.com/c6rMMbY.png) [^bt-1] 若想著把每一種任意擺放可能性列出來,再來挑選可行的盤面, 將有 $\binom{64}{8} = 4426165368$[^combination] 種盤面要產,明顯的程式會跑很久 而兩個皇后放在同個 row 或 column 上一定會互攻,所以只需在每個 row 或 column 擺放一個皇后就好: ```cpp int dfs(int row) { if (row == 8) return 1; int sum = 0; for (int col = 0; col < 8; col++) if (check(row, col)) { board[row] = col; // 在 (row, col) 放置一個皇后 sum += dfs(row + 1); } return sum; } ``` 這邊的 `check(r, c)` 就是本節的主題了, 在轉移狀態(盤面)前,若能預感(?)這狀態不是想要的,就中斷轉移,然後 backtrack 到原狀態,繼續進行別的狀態轉移 用 `check(r, c)` 檢查將皇后放置在 $(r, c)$ 後是否能繼續再放置其他皇后。 用點幾何概念的話,會發現 `check()` 只需要 $O(N = 8)$ 就能做到: ```cpp bool check(r2, c2) { for (int r1 = 0; r1 < r2; r1++) { int c1 = board[r1]; if (c1 == c2 || c1-c2 == r1-r2 || c1-c2 == r2-r1) return false; } return true; } ``` 枚舉的盤面會少於 $N!$ 很多,因為 `check()` 剪掉了許多不必再繼續遞迴下去的 DFS 樹枝。 ![](https://blogs.mathworks.com/steve/files/queen-solver-animation-6.gif)[^bt-2] #### 練習: [UVa OJ 524 Prime Ring Problem](https://uva.onlinejudge.org/external/5/524.pdf) [UVa OJ 211 The Domino Effect](https://uva.onlinejudge.org/external/2/211.pdf) [^7]: 看英文 walk 這字,帶有一種隨意的感覺,是種無限制的路 [^8]: 很多人無法很好的區分道路與路徑,甚至行跡,通常得仔細讀上下文 [^10]: 這邊容易誤會,因為 disjoint sets tree 的"根",是我們進行遞迴下探走到的"葉"。 [^convention]: 這個變數將成為以後的慣例 [^dfs-1]: 注意,這裡的圖剛好是連通的。 [^dfs-2]: [State space search](https://en.wikipedia.org/wiki/State_space_search) [^bfs-1]: 有時間可以玩玩看 [pipes](https://github.com/ccns/105-club-fair-game-problems/tree/master/1/2),裡頭有附上 source code [^bt-1]: [Wikipedia/ Eight queens puzzle](https://en.wikipedia.org/wiki/Eight_queens_puzzle) [^bt-2]: [Mathworks/ The Eight Queens Problem](https://blogs.mathworks.com/steve/2017/04/20/the-eight-queens-problem/) [^CE]: 不過實驗證明,提交上 Codeforces 會拿到 Compilation error [^combination]: 就是組合 $C$ $64$ 取 $8$ 的意思