連連看演算法要解決的問題，是把棋盤上的圖塊轉成電腦可以搜尋的資料結構，再判斷兩個相同圖形能不能在兩次轉彎以內連線消除。這篇筆記從演算法的基本定義開始，整理時間複雜度、空間複雜度、圖形資料結構、深度優先搜尋（Depth-first Search，DFS）與廣度優先搜尋（Breadth-first Search，BFS），最後回到連連看遊戲的路徑設計方向。
演算法是什麼？
演算法可以先理解成「輸入 + 處理規則 = 輸出」。在遊戲或後端邏輯裡，演算法的價值不只在算出答案，也在於答案是否能用可預期的時間與記憶體算出來。
演算法的簡單定義：
輸入 + 演算法 = 輸出
一般判斷演算法的好壞，會使用「時間複雜度」和「空間複雜度」評估。時間複雜度關心運算步驟會怎麼隨輸入變大，空間複雜度則關心程式完全執行時需要多少記憶體。
若想先看更完整的入門說明，可以參考 AppWorks School 的〈初學者學演算法：談什麼是演算法和時間複雜度〉。
時間複雜度怎麼判斷？
時間複雜度不是拿碼表量實際秒數，而是估算演算法會執行多少步驟。輸入資料越大，步驟增加越快的演算法，通常越需要小心效能。
所謂時間複雜度，指的是執行一段演算法、跑完整個運算邏輯所要花的時間。雖然這個複雜度名為「時間複雜度」，但真正衡量某個演算法時，通常是以步驟次數來看。
如果一個演算法執行的步驟是固定的，不會因為輸入值而改變，可以記成 `O(1)`：
```text
function(int n) {
print(n);
}
```
如果演算法會依照輸入 `n` 的數量跑 `n` 次，時間複雜度就是 `O(n)`：
```text
function(int n) {
for (i = 0; i < n; i++) {
print(i);
}
}
```
有時候跑的次數不是單純的 `n`。例如下面這個例子會跑 `n * (n - 1) = n^2 - n` 次，但 Big O 表示法會保留最高次方，並拿掉係數與較低次方，所以記成 `O(n^2)`：
```text
function(int n) {
for (i = 0; i < n; i++) {
for (j = 0; j < n - 1; j++) {
print(i * j);
}
}
}
```
| 常見記法 | 步驟成長方式 | 直覺例子 |
|---|---|---|
| `O(1)` | 固定次數 | 印出一個值 |
| `O(n)` | 隨輸入線性增加 | 掃過一排資料 |
| `O(n^2)` | 雙層迴圈式增加 | 比對每一組資料 |
空間複雜度怎麼判斷？
空間複雜度衡量程式執行時需要的記憶體量。判斷空間複雜度時，要看變數、陣列、遞迴呼叫堆疊是否會隨輸入規模變大。
一個程式的空間複雜度，是指完整執行程式所需的記憶體量。例如下面這個函式，不管程式跑了幾遍，都不會影響使用的變數數量，所以空間複雜度記做 `O(1)`：
```text
function(int n) {
for (int i = 0; i < n; i++) {
print(i);
}
}
```
但下面這個函式會隨著丟進去的數字而影響變數的量，因為 `c[n]` 需要跟著 `n` 變大，所以空間複雜度是 `O(n)`：
```text
function(int n) {
int c[n];
for (int i = 0; i < n; i++) {
c[i] = i;
}
}
```
遞迴的空間複雜度一般與最深的呼叫深度成正比。若遞迴中還有局部變數或參數，所需的空間複雜度會更高。
哪些問題是經典的演算法例子？
旅行推銷員問題與一筆畫問題都是經典演算法議題。兩個問題都能讓人看到：演算法不只是寫程式，而是先把真實問題抽象成資料、限制條件與搜尋目標。
人工智慧也是演算法的一種。著名的旅行推銷員問題（Travelling Salesman Problem，TSP）假定已知每個城市間的距離，要求在不重複訪問同一個城市的情況下，找出最快速的行程組合。旅行推銷員問題是電腦科學中著名的難解問題。
Source：Saurabh.harsh，引用自 TechNews〈從演算法到人工智慧，淺談計算機的真正威力〉。
一筆畫問題也是很經典的演算法議題。一筆畫問題是柯尼斯堡七橋問題經抽象化後的推廣，也是圖遍歷問題的一種。
Source：維基百科〈柯尼斯堡七橋問題〉。
在柯尼斯堡問題中，如果將橋所連接的地區視為點，將每座橋視為一條邊，問題會變成：對於一個有四個頂點和七條邊的連通圖 `G(S, E)`，能否找到一條恰好包含所有邊、且沒有重複的路徑？
歐拉將柯尼斯堡七橋問題推廣成：對於一個給定的圖，怎樣判斷是否存在一條恰好包含所有邊、且沒有重複的路徑？一筆畫問題的解答是：如果一個圖能一筆畫成，奇頂點的數目必須是 `0` 或 `2`。
連連看遊戲需要解決哪些演算法問題？
連連看遊戲至少要處理初始盤面、可消除判斷、最短路徑搜尋與僵局解除。這些問題背後都能轉成圖形資料結構與搜尋演算法。
《程式之美：微軟技術面試心得》裡給了許多經典演算法題目，例如構造數獨遊戲、一疊蔥油餅的排序、一排石頭的遊戲、俄羅斯方塊遊戲、踩地雷遊戲的機率、連連看遊戲。因為我小時候很喜歡玩 kawai 連連看，所以選擇連連看作為這次鐵人賽的題目。
若要設計一個連連看遊戲的演算法，可以從這幾個問題開始：
- 如何用簡單的電腦模型描述連連看盤面？
- 如何判斷兩個圖形能否相消？
- 如何求出兩個相同圖形間的最短路徑，也就是轉彎數最少、路徑經過的格子數目最少？
- 如何確定目前處於僵局狀態，並設計演算法解除僵局？
在經典最短路徑問題中，目標通常是求出經過格子數目最少的路徑。連連看還多了一個限制：為了確保轉彎次數最少，需要把最短路徑問題的目標函數改成「轉彎數優先」。雖然目標函數修改了，演算法框架仍然可以保持不變；廣度優先搜尋就是解決經典最短路徑問題的一個思考方向。
連連看的消除條件怎麼拆成程式邏輯？
連連看的消除條件可以拆成三件事：圖形相同、路徑沒有被阻擋、轉彎次數少於三次。只要其中一項不成立，兩個圖塊就不能消除。
根據上面的說明，若想要做一個連連看遊戲，需要先處理下列問題：
| 問題 | 程式設計方向 |
|---|---|
| 產生遊戲初始局面 | 用電腦資料格式儲存每一格圖形資料 |
| 判斷是否可相消 | 使用者選擇兩個圖形後，確認兩個圖形相同，且兩者之間存在少於三個轉彎的路徑 |
| 判斷僵局 | 搜尋全部現有圖案，判斷是否還有任何可消除組合 |
| 解除僵局 | 當玩家無法再消除任意兩個圖像時，隨機打亂局面 |
因此，連連看至少會需要用到圖形（Graph）演算法，以及搜尋演算法，包含深度優先搜尋與廣度優先搜尋。
Graph 資料結構可以怎麼表示？
圖形資料結構由頂點與邊組成。程式實作時，常見表示法包含相鄰矩陣、相鄰串列與邊集合；選擇哪一種表示法，會影響記憶體使用量與搜尋效率。
一張圖由數個點（vertex）以及數條邊（edge）構成。點與點之間可以用邊連接，表示這兩點有關聯。若要用程式語言表示一張圖，常見方法如下：
| 表示法 | 儲存方式 | 優點 | 注意事項 |
|---|---|---|---|
| 相鄰矩陣（Adjacency Matrix） | 將節點當作矩陣的行和列索引；若頂點間有連接，`array[i][j] = 1`，反之為 `0` | 查詢兩點是否相連很直觀 | 遇到稀疏圖會浪費空間，頂點數量改變時較不彈性 |
| 相鄰串列（Adjacency List） | 每個點後方串連所有相鄰點 | 比相鄰矩陣節省空間 | 查詢任兩點是否相連時，需要掃描串列 |
| 邊集合（Edge List） | 用陣列記錄所有點與點之間的邊 | 直觀且節省空間 | 不適合頻繁查詢相鄰點 |
上面幾種圖形表示法整理自〈演算法筆記：Graph〉。
搜尋演算法在圖裡扮演什麼角色？
搜尋演算法負責決定圖要從哪裡開始讀、依照什麼順序讀、讀到哪裡停止。連連看要找兩個圖塊之間是否存在合法路徑，本質上就是在棋盤圖裡做搜尋。
圖的遍歷，就是通盤讀取圖的資訊：決定好從哪裡開始讀，依照什麼順序讀，要讀到哪裡為止。流程設計得好，在解決圖的問題時，還可以一邊讀取圖的資訊，一邊順手解決問題。
利用最簡單的資料結構 `queue` 和 `stack`，就能製造不同的遍歷順序，得到兩種遍歷演算法：
- Breadth-first Search（廣度優先搜尋，BFS）：通常用 `queue` 處理，先走訪同一層的節點，再往下一層。
- Depth-first Search（深度優先搜尋，DFS）：通常用 `stack` 或遞迴處理，沿著一條路盡量往深處走，再回溯找其他路。
深度優先搜尋 DFS 怎麼運作？
深度優先搜尋會從起點一路往尚未拜訪的節點深入，直到不能再前進才回溯。深度優先搜尋適合遍歷整張圖，也常用遞迴或堆疊實作。
深度優先搜尋法是一種用來遍尋樹（tree）或圖（graph）的演算法。搜尋從樹的根，或圖中的某一點開始，先探尋邊上尚未搜尋的節點，並盡可能往深處搜尋；直到該節點的所有邊上節點都已探尋，就回溯到前一個節點，重複探尋尚未搜尋的節點，直到找到目的節點或遍尋全部節點。
深度優先搜尋屬於盲目搜索（uninformed search），常用堆疊（Stack）處理，也常以遞迴呈現。假設起始點為 `A`，且每一節點由左至右搜尋下個節點，結果會是：`A, B, E, F, D, C, G`。
廣度優先搜尋 BFS 怎麼運作？
廣度優先搜尋會先走訪起點周圍所有相鄰節點，再一層一層往外擴張。當每條邊權重相同時，廣度優先搜尋常用來找最短路徑。
廣度優先搜尋法是一種圖形（graph）搜索演算法。搜尋從圖的某一節點開始，接著走訪此節點所有相鄰且未拜訪過的節點，再由走訪過的節點繼續進行先廣後深的搜尋。以樹（tree）來說，就是先把同一深度（level）的節點走訪完，再繼續向下一個深度搜尋，直到找到目的節點或遍尋全部節點。
廣度優先搜尋屬於盲目搜索，常用佇列（Queue）處理，也常以迴圈呈現。假設起始點為 `A`，且每一節點由左至右搜尋下個節點，結果會是：`A, B, C, D, E, F, G`。
連連看棋盤要怎麼儲存？
連連看棋盤可以用二維陣列儲存，每個索引位置代表一個格子。這種表示法容易判斷兩個點是否在同一列或同一行，也方便後續搜尋可連線路徑。
以連連看來說，因為棋盤裡任意兩個同一排或同一列的點都可以做直線相連，若用二維陣列直接儲存棋盤內容，就可以用該陣列第一個索引值或第二個索引值是否相同，判斷兩點是否在同一條線上。
若圖形為 `10 x 10` 的棋盤，陣列可以設計如下：
使用這樣的陣列儲存方式時，要注意上圖的 `x`、`y` 軸位置，和一般做遊戲時的 `x`、`y` 軸方向剛好相反。計算點與點之間的位置時，如果座標方向沒先統一，很容易在路徑判斷時出錯。
路徑則可以使用圖演算法中的關聯矩陣概念記錄。例如 `[[0, 0], [-1, 0], [-1, 8], [0, 8]]` 表示一條由多個轉折點構成的路徑。在連連看遊戲裡，每一個合法路徑都應由四個或以內的點組成，且每兩個相鄰點之間必定要有相同的 `x` 或相同的 `y`。
連連看路線搜尋為什麼適合用 BFS 思考？
連連看路線搜尋適合用 BFS 思考，因為 BFS 會由近到遠擴張路徑。只要把搜尋成本改成「轉彎數優先，再看格子數」，就能貼近連連看的消除規則。
在一般最短路徑搜尋中，常會以廣度優先搜尋為主。連連看的特殊限制是：連線的線條不可大於兩個轉彎處。兩個轉彎處代表連接兩個圖塊的線，最多只能由三條直線組成。
可以把直線當成搜尋單元，先搜尋 `A` 點上、下、左、右最遠能到達的點，再對比 `B` 點上、下、左、右最遠可以到達的點，判斷是否有可能形成一條連線。若有可能，再繼續尋找中間是否存在可能的第二條線。
這裡的實作判斷可以濃縮成三層：
- 先判斷 `A` 到 `B` 是否能直線相連。
- 若不能直線相連，判斷是否存在一個轉折點，讓 `A` 到轉折點、轉折點到 `B` 都可直線通過。
- 若一次轉折也不成立，再判斷是否存在兩個轉折點，讓路徑由三段直線組成。
延伸閱讀
- PixiJS 如何實作連連看盤面與消除邏輯
- PixiJS 提示與重整按鈕教學：連連看遊戲功能實作
- 圖形資料庫的概念入門
- LeetCode 2218 Maximum Value of K Coins From Piles 解題筆記
常見問題
演算法和資料結構有什麼關係？
演算法是解決問題的步驟，資料結構是資料在程式裡的存放方式。連連看若用二維陣列存棋盤，路徑搜尋就能直接利用列與行的索引判斷直線是否可通過。
連連看為什麼需要圖形演算法？
連連看棋盤上的格子可以視為頂點，格子之間可通過的直線可以視為邊。判斷兩個圖塊能否消除，其實就是判斷兩個頂點之間是否存在符合轉彎限制的路徑。
連連看消除一定要用 BFS 嗎？
連連看消除不一定只能用 BFS。BFS 適合拿來思考最短路徑與逐層擴張，但實作時也可以針對直線、一次轉折、兩次轉折分別寫判斷函式。
DFS 和 BFS 在連連看裡差在哪？
DFS 會沿著一條可能路徑一路深入，適合完整遍歷或回溯搜尋。BFS 會先檢查距離較近或層級較淺的候選路徑，比較貼近「先找最少轉彎數」的需求。
連連看的僵局要怎麼判斷？
連連看的僵局可以用全盤搜尋判斷：掃過目前棋盤上的圖塊，找出每一對相同圖形，逐一檢查是否存在合法路徑。若沒有任何一組可以消除，就代表進入僵局，可以重新洗牌打亂盤面。
參考資料
- AppWorks School，〈初學者學演算法：談什麼是演算法和時間複雜度〉。
- 維基百科，〈一筆畫問題〉。
- 維基百科，〈柯尼斯堡七橋問題〉。
- TechNews，〈從演算法到人工智慧，淺談計算機的真正威力〉。
- Noob's Space，〈資料結構筆記：演算法、時間複雜度、空間複雜度〉。
- 演算法筆記，〈Graph〉。
- Simon Says，〈深度優先搜尋〉。
- Simon Says，〈廣度優先搜尋法〉。
最後更新
2018-10-17（本文保留 2018 年連連看演算法筆記內容，並補上 GEO 結構、FAQ 與站內延伸閱讀。）
關於作者 {#author}
Claire Chang ｜ 企業 AI 導入與流程轉型顧問。專注於 AI Agent 架構設計、ERP 系統整合與企業 AI 治理。
首次發布：2018-10-17