項目Github位址：https://github.com/JerryYouxin/sudoku.git
PSP表格
| PSP2.1 | Personal Software Process Stages | 預估耗時（分鐘） | 實際耗時（分鐘） |
|---|---|---|---|
| Planning | 計劃 | 30 | 10 |
| · Estimate | · 估計這個任務需要多少時間 | 400 | 720 |
| Development | 開發 | 380 | |
| · Analysis | · 需求分析 (包括學習新技術) | 40 | 20 |
| · Design Spec | · 生成設計文檔 | ||
| · Design Review | · 設計複審 (和同僚稽核設計文檔) | ||
| · Coding Standard | · 代碼規範 (為目前的開發制定合适的規範) | ||
| · Design | · 具體設計 | 60 | |
| · Coding | · 具體編碼 | 90 | 100 + 400(優化) |
| · Code Review | · 代碼複審 | ||
| · Test | · 測試（自我測試，修改代碼，送出修改） | ||
| Reporting | 報告 | ||
| · Test Report | · 測試報告 | ||
| · Size Measurement | · 計算工作量 | 15 | |
| · Postmortem & Process Improvement Plan | · 事後總結, 并提出過程改進計劃 |
|合計 | 400 | 720
實際開發
需求分析
軟體關鍵分為四個子產品：一個是輸入參數的解析；一個是數獨生成器，生成若幹數獨終局；一個是數獨求解器，根據輸入數獨求解一個可行解；一個是終端，在指令行程式中為檔案輸出，在附加題中為GUI界面顯示。
現在一個子產品一個子產品進行細化。首先輸入參數解析：有參數-c和-s，需要做到合法性檢驗，即參數必須是下面中的一個。
| 參數 | 類型/範圍 |
|---|---|
| -c | 整數N，1<=N<=10000000 |
| -s | 數獨題目的路徑path |
數獨生成器：需要輸入一個參數N，意義為生成數獨終局數量，其中1<=N<=1000000，且不重複。生成數獨矩陣時，左上角的第一個數為：（學号後兩位相加）%9 + 1。
數獨求解器：需要輸入一個9x9的數獨矩陣，并解出一個可行解。
終端：指令行程式終端有兩類功能，一是按格式輸出數獨檔案，二是按格式讀取數獨檔案。
設計子產品
指令行程式使用C++進行編寫。分為五個類：SudokuGame類，對應于上文中的終端；SudokuCreator，對應于上文中的數獨生成器；SudokuSolution，對應于上文中的數獨求解器；ArgumentParser，對應與上文中的參數解析器；Sudoku類對應于數獨存儲的矩陣資料結構。
其中Sudoku中有generate(int N)方法，可以生成不重複的N個數獨中盤矩陣，一個比較原始的生成算法為：
利用回溯法解出N個空數獨的解
但這種算法不可避免的在中間不可解的數獨狀态搜尋一段時間，比較耗時。還有一個感覺更好一些的生成算法為：
Step 0:
根據随機法初始化一個數獨A。
Step 1:
根據随機初始化的數獨A，由
1.同列網格中的列與列的互換（每列有三種互換方式 + 不變換）
2.同行網格中的行與行的互換（每行有三種互換方式 + 不變換）
是以每個數獨可以通過有限次1，2變換得到最多一共 44444*4 = 4096種不同的數獨。其中也包含了特例：如果互換兩列/行相同，則互換前後數獨是不變的，是以這種情況下會不計入生成的數獨當中。
Step 2:
然後對原始的數獨A進行下面兩種變換之一得到新的數獨A'：
1. 進行對角翻轉，即A'[i][j]=A[9-i][9-j]。
2. 進行數替換：将所有1變為2，2變為3，……，9變為1。
再将生成的所有數獨A'按照Step 1的方式進行擴增，這樣最終最多能達到 1024096 = 81920種不同的數獨。
其中Sudoku中有solve()方法，可以求解數獨，求解算法為：
1. 周遊一遍數獨，在行、列、塊的标記數組中标記已經填好的數，表示該數在所在行、列、塊中已經用過，不能再用。
2. 從第一個沒有填數字的空白開始，選擇一個還沒有在該行、列、塊中用過并還未嘗試過的數字，并标記在對應标記數組中。
3. 若沒有數字可以填入該空白，則回溯到上一個填上的空白，并回标（即反過程）對應的标記數組中。重複過程2.
也就是簡單的回溯算法。
設計實作過程
由于數獨本身并不複雜，主要有三個要點功能：存儲數獨，生成數獨，解數獨。這三個操作都是對數獨資料的操作，是以都可以歸到一個數獨類中，其中包括：
print -- 列印數獨資料
generate -- 生成數獨
solve -- 求解數獨
Sudoku(filename) -- 從檔案filename中讀取數獨資料
Sudoku(N) -- 初始化N個數獨
check() -- 數獨查重（檢測用）
其中輔助函數有：
parse(argc, argv, arg) -- 解析argv中的參數清單，并将解析出來的參數存到arg中
hash_code() -- 數獨查重用的哈希函數，用來初步檢測兩個數獨有沒有可能相等
-- 哈希函數選擇為：數獨中所有塊中第i項的和的乘積，i=1~9。
單元測試主要就測兩個功能即可：
1. 讀取不同大小的數獨，并求解輸出。大小、難度各異的測試資料5組。最大資料要有1000000個。
2. 生成不同數量的數獨終局，并輸出。大小要有兩個極限值（1，1000000），中間（1000），奇數（3，一個随手寫的大于10000的奇數）。
這樣初步的設計就完成了，就可以開始編碼了。
初步編碼&測試
首先編寫了數獨的生成部分的函數。上面通過生成随機模闆并進行等價變換的方法由于變換并不能保證每個變換出來的數獨都是不同的，也就是在生成較多數獨的時候會不可避免的産生大量的重複數獨，而為了消去重複數獨就需要在一個新的數獨生成後與生成好的其他數獨進行比較來進行去重操作，而這種查重操作是非常耗時的，即便用了哈希的方法（可能我選的哈希函數并不好）進行查重也是非常的耗費計算資源，使得使用這個方法優化起來感覺非常困難。由此我後來還是選擇了回溯算法進行批量生成。
生成部分的正确性檢驗正确後，開始開發數獨求解器部分。總體算法上跟數獨的生成是一樣的，都是回溯法進行可能解的搜尋。
性能分析及優化方案
終于來到了性能分析階段。在這個階段上我花費的時間比較長(雖然并沒有太大學質上的效果)。性能優化之前先得分析性能瓶頸在哪裡。我們先來測試數獨生成1000000個的時候的性能分析圖：
由分析圖可以看出主要有兩個熱點函數：generate函數和print函數。其中輸出是主要的瓶頸。為什麼呢，我們看一看原來寫的代碼（示意）：
for n = 0, N:
for i = 0, 9:
for j = 0,9:
fprintf a number
fprintf '\n'
fprintf '\n'
可以看到是一個一個數進行輸出的，一個一個寫磁盤是非常低效的，寫磁盤如果能夠批量塊存儲會快許多，那麼優化一下，讓這些資料緩存到一個buffer裡面，再統一輸出就會好多了：
for n = 0, N:
for i = 0, 9:
for j = 0,9:
sprintf a number to buffer
sprintf '\n' to buffer
sprintf '\n' to buffer
fwrite buffer
發現速度有些許提高，但用性能分析工具分析發現fwrite并不耗時，格式轉換到緩存卻耗時多了。那現在隻能想想改變資料存儲結構來減少中間的格式轉換過程了：數獨資料直接用字元進行存儲。
由于資料資料隻有0-9這十個數字就可以表示，而要求的輸出格式是很有規律的，是以用字元進行存儲完全不會影響算法的速度與實作，存儲空間也由原來的每個數字short變為一個數字字元和格式字元（空格或者換行符），是以空間消耗也完全不變——也就是跟原來相比基本沒有效率上的損失。是以原來的輸出就變為了：
for n = 0, N:
fwrite sudoku_data(n)
fwrite '\n'
實際測試後，寫1000000個數獨的時間從60多秒減到了大概2s，大概有30x的加速，應該是差不多了。如果還想加速的話，寫記憶體檔案也是一個好方法，從實體層面上能比寫磁盤快多了。但是windows的寫記憶體檔案比較麻煩，而現在的主要瓶頸在生成算法上，就沒有實作。
生成/求解算法上，可以用跳舞鍊進行優化。數獨可以解釋為精确覆寫問題，跳舞鍊是解決精确覆寫問題的有效算法，但是實作的時候出了點問題，由于時間限制就沒有實作。
數獨求解上，性能瓶頸跟數獨生成比較類似，也是算法和I/O比較耗時。輸出的解決方法已經說過了，輸入也是大同小異，就不深入說明了。
數獨求解的算法也是回溯，但是數獨求解有多個數獨需要求解，而這些數獨之間并沒有關聯，即可以并行處理多個數獨來提高求解速度。現在CPU一般都有多核，是以可以用openmp指導編譯語句進行多核多線程并行運算，進一步提高計算性能。即在程式中加入一句：
#pragma omp parallel for
for(int n=0; n<N; ++n) {
Solve n-th sudoku puzzle
...
}
這樣便可以利用現代處理器的多核架構，在我的計算機中，有四核并行，計算的時候使用率可以達到将近100%，與原來相比也有将近4倍的加速比。
這個項目的最主要的代碼就是回溯法求解的代碼了。回溯法求解思路上面也說過，主要有三個重要的緩存數組來加速回溯過程：
empty_value -- 第 i 行/列/塊 是否已經被使用。
trying_value -- 第 i 個數填了哪個數字。
fill -- 第 i 個空白是數獨中的第幾個數。（空白位置）由初始化得到後不再改變。
他們可以用來快速決定在哪裡、哪個數是可以填入的。在回溯過程中會随着搜尋進行不斷地更新這些數組。