# 2019-pd Project #1 Sudoku
###### tags: `2019pd2`

這次的作業分成 `generate`, `transform`與`solve` 三個部分，其中`transform`跟`generate`可以視為是同一個東西 ~~（除非你真的很想從零開始生一個數獨的題目出來）~~ ，所以我會比較著重在`solve`的方法上
## 前置作業（Preparing）
在做solve之前，我們必須先決定作為基底的 class 的底層資料要用什麼資料型態，最常見的資料可以是一維的 int 陣列、二維的 int 陣列、一維的 vector 或是二維的 vector（也就是 vector 套 vector 的概念），不過因為本次作業有牽扯到運算速度的問題，再加上屬於 STL 容器的 vector 有著非常多身為高階程式語言才具備的方便特性，所以執行的效能將大大地受到後台維護的影響，並且使用二維陣列的話在思考上可以更加直觀、快速，並省去多餘的乘法、取餘等計算 ~~（以及思考人生的機會）~~。所以，在做數獨之前，請先深吸一口氣，然後暫時忘掉 vector 這種好用東西的存在 ~~（開心地走入segmentation fault的懷抱）~~
## 數獨演算法（Sudoku Solving Algorithms）
數獨有許多不同的演算法可以做解題的演算，像是最基本的 backtracking, stochastic, 以及最為抽象的 exact cover（也是目前可以最快解出答案的演算法），但因為本次作業需要解出多解的問題，所以大部分在網路上看到現成的程式碼都不能直接照抄（網路上現成的程式大多數都是假設題目為唯一解，並且解出答案即停止），但經過實驗測試，不需要透過特別抽象的演算法以及多餘的輔助規律即可達到作業要求，所以我們就以最常見也是最易懂的 backtracking 解釋：
## 回溯法（Backtracking）
Backtracking 其實是一種 DFS(Depth First Search) 的演算法，但因為 DFS 在不同的問題差異性其實還蠻大的所以用一張圖來簡單說明：
<br>
<center> <img src = "https://upload.wikimedia.org/wikipedia/commons/8/8c/Sudoku_solved_by_bactracking.gif"> </center>
<br>

從這張圖可以看的出來傳統的 backtracking 就是從左上方的空格開始，依序填入 1 ~ 9 的數字，並不斷做規則符合的測試，如果填入的數無法符合數獨的規則的話，就透過遞迴到前一個所填的數，並換另一個數來測試，直到試出答案為止。但這樣做其實真的很沒有效率，因為其實可能有格子可以填入的數只有一個，但 backtracking 會把其他不可能的8個數全部試過一遍，大大的拖累了執行的速度，所以我們要稍微的改進一下這支演算法

## 想法
如果是我們自己在解數獨的時候，我們通常是將該空格可以填入的數字以鉛筆註記（像是下面這張圖這樣），而通過這樣的過程，我們可以大幅度的減少 backtracking 進入錯誤節點的機率。所以我們可以利用另外一些變數來記錄這些格子可以填入的數字，而這個資料可以是 $9 \times 9$ 的整數陣列搭配位元運算來在記錄（ex： `110010100` 代表該格可以填入的數字為 $3, 5, 8, 9$）也可以使用 $9 \times 9 \times 9$ 的的陣列來記錄可填入的數字（像是 $[0][2][0] = 1, [0][2][1] = 1$ 表示 $1, 2$ 可以填之類的）。不管最後你選擇的方法如何，反正就是要將空格可以填入的數字利用另外的變數記錄下來，並將可填入的數字只有一個的空格填入，而做到這個階段，最簡單的數獨題目也就差不多大功告成了。
<center><img src='https://upload.wikimedia.org/wikipedia/commons/d/db/Sudoku2.gif'></center><br>

## 暴力求解法（bruteforce）
接著我們再想想，如果現在數獨的題目上還存在著許多未填入的空格，而且這些空格都有至少兩個的可填入數字，那我們會怎麼做？

最簡單的做法是把題目影印一份之後開始試不同的數字組合，並且我們合理的情況應該是從可填入數字數最少的那格開始填起，接著再將 backtracking 的方法應用進來，就可以解出數獨的題目了

## 關於效能
關於如何減少運算時間的問題，大家可以去網路上 google 有許多文章談論到如何優化效能，但就這個作業而言，最直接的做法就是減少迴圈的運算，能不要跑的迴圈就盡可能的跳過，不得已一定得跑的迴圈就看能不能少跑一點，像是初始化二維陣列最簡單的方法可能是用雙層迴圈來進行初始化，但這樣的做法會需要跑N * N次的迴圈，但是透過定義在 `cstring` 這個header裡的 `memset` 可以少去跑迴圈的時間，直接將對應的位元清成指定的值（但如果是使用`memset`的話只能初始化為 `0` 或是 `-1` ）或是利用 `memcpy` 複製陣列都可以減少多餘的迴圈運算時間，當然你也可以考慮用 exact cover 的觀點來解題， ~~但是光是要了解 dancing links 到底是怎麼運作跟實作的可就會花上兩、三天或是一整個禮拜的時間。~~ 而且經由實驗證實，使用特殊的數獨規則並不會大幅加速運算的時間，只會增加多餘的迴圈運算，所以只要專注在減少，避免迴圈的使用，就可以完成作業囉～加油吧！