BIT软件工程个人项目——数独sudoku
BIT軟件工程個人項目——數獨sudoku
目錄：
(點擊可頁內跳轉)
1. 項目地址
2. PSP表格
3. 解題思路描述
——3.1初期思考
——3.2數獨終局生成
——3.3求解數獨
4. 設計實現
——4.1 類的組織
——4.2 類中主要成員、方法的調用關系
——4.3 單元測試的設計及代碼覆蓋率測試
5. 程序優化
6. 代碼說明
7. 心得感悟
1. 項目地址
根據要求所有代碼在更新過程中托管在github上，一有文件更改就簽入。為了方便各位閱讀代碼，在編程過程中，我給每個文件，每個成員，每個函數方法，都做了極其詳細的注釋。
交上項目地址：https://github.com/EasonGuo666/MySudoku
2. PSP表格
| PLANNING | 計劃 | - | - |
| ----estimate | 估計這個任務需要多長時間 | 10 | 10 |
| DEVELOPMENT | 開發 | - | - |
| ----analysis | 需求分析(包括學習新技術) | 120 | 200 |
| ----design spec | 生成設計文檔 | 60 | 80 |
| ----design review | 設計復審(和同事審核設計文檔) | 30 | 20 |
| ----coding standard | 代碼規范(為目前的開發制定合適的規范) | 10 | 10 |
| ----design | 具體設計 | 20 | 60 |
| ----coding | 具體編碼 | 1200 | 1800 |
| ----code review | 代碼復審 | 300 | 300 |
| ----test | 測試(自我測試，修改代碼，提交修改) | 120 | 200 |
| REPORTING | 報告 | ||
| test report | 測試報告 | 20 | 60 |
| size measurement | 計算工作量 | 10 | 10 |
| postmortem & process improvement plan | 事后總結，并提出過程改進計劃 | 180 | 100 |
| 合計 | 2080 | 2850 |
3. 解題思路描述
------3.1初期思考
最初拿到這個題的時候，心里一陣翻騰。老師讓用github托管代碼，這個我之前學過一些，應該問題不大。難點就在于如何設計完成題目中很多細碎的功能。其實在老師給的文檔里題目中的主要功能已經被分解成了兩個大的部分：“數獨終局生成”和“求解數獨”。剩下的就是一些性能上的優化以及命令處理時候的程序容錯性要求了，例如：如果輸入錯誤命令的話會提示錯誤輸入；如果輸入sudoku.exe -c 20和sudoku 20 -c應該都可以完成生成20個不同數獨終局的功能。下面就來討論如何生成終局和求解數獨。
------3.2數獨終局生成
要求是：生成規定數量的各不相同的終局。在思考過程中，我有過兩個想法。
（1）最開始的想法是：對一個給定的數獨終局，交換兩個數的位置，這樣生成的終局跟原來的終局肯定不一樣。用這種方法：給定一個終局，我們可以生成45個不同的終局。但是呢，，這種方法有個弊端，有時候兩個不同的終局交換數字后生成的終局可能是重復的，而且難以找到一個方法來避免這種重復。所以這種想法在我看來不是很可行。
比如：a交換1,9之后，b交換4,5之后，下面兩個終局產生的新終局是一樣的。
a：······························b:
1 2 3 4 5 6 7 8 9············9 2 3 5 4 6 7 8 1
4 5 6 7 8 9 1 2 3············5 4 6 7 8 1 9 2 3
7 8 9 1 2 3 4 5 6············7 8 1 9 2 3 5 4 6
2 3 4 5 6 7 8 9 1············2 3 5 4 6 7 8 1 9
5 6 7 8 9 1 2 3 4············4 6 7 8 1 9 2 3 5
8 9 1 2 3 4 5 6 7············8 1 9 2 3 5 4 6 7
3 4 5 6 7 8 9 1 2············3 5 4 6 7 8 1 9 2
6 7 8 9 1 2 3 4 5············6 7 8 1 9 2 3 5 4
9 1 2 3 4 5 6 7 8············1 9 2 3 5 4 6 7 8
（2）后來在看到一篇博客的時候，吸取到了別人思想的精華。
原來一個數獨終局的生成可以用第一行的平移來形成( ? ?ω?? )?！！！！！真的好巧妙，平移的時候只要滿足一定規律，就可以使新生成的數獨終局滿足數獨三原則：橫行無重復，縱行無重復，3×3方格內無重復。
規格是這樣：
①下面的幾行由第一行平移得到，先給定第一行的一個排列，只要第一行的排列是1到9這9個不重復的數，就可以滿足每一橫行內無重復。
②滿足上一條前提下，只要下面幾行在平移的時候每一行平移錯開的位數不同，就可以保證9個列都是不包含重復數字。
③為了讓3×3方格也滿足規則，平移時，每三行一組，組內每行間平移錯開的位數相差3。比如：用{0，3，6}表示前三行的情況，意思是：給定一個排列第一行可以看做是向前平移了0個長度。第二行相當于第一行向前平移3個長度。第三行相當于第一行向前平移6個長度。用這種方法中間三行是{1，4，7}，后三行是{2，5，8}。
如果還不明白的話，舉個例子：給定第一行排列123456789，根據這三個平移規則可以得到上文提到的終局a。平移序列 { {0，3，6}，{1，4，7}，{2，5，8} }
第一行平移位數只能是0，第二行的3和第三行的6可以互換（有2種組合）。第四五六行的1，4，7之間可以任意組合（有6種組合）。第七八九行的2，5，8也可以任意組合（有6種組合）。這樣給定一個第一行的排列，可以有2×6×6=72種不同終局的生成。而第一行的排列數總共有8！=40320個（因為老師規定了第一個數是學號后兩位算出來的不能變，就只有8個數的排列） 。這樣總共可以生成的不同數獨的數量有8！×72=2903040種，遠遠滿足1000000的要求了。
------3.3求解數獨
這里看了這篇博客的思想有了啟發：https://www.cnblogs.com/dancer16/p/6916795.html
這位老兄的博客里代碼寫地還算比較優雅。
我在設計求解數獨的算法的時候，想起了dfs搜索，速度貌似還可以。思想是：對于每一個空位都檢查一下從1到9這九個數哪個可以被放在當前的空位，找到一個暫時行的數先放進去，就挪到下一個空位繼續進行嘗試。如果遇到一個空位1到9都填不進去數，說明前面有問題了，返回上一層dfs的遞歸，從上一次填進去的那個數的位置再次繼續嘗試。直到所有的位置都填滿了數，遞歸結束。
4. 設計實現
-
在編碼過程中嚴格遵守Google C++規范，（除了大括號位置）
-
程序流程圖如下：
------4.1 類的組織
因為題目中給的功能劃分已經明確，其實就兩大部分：終局生成和求解數獨。
但是當程序從控制臺接受輸入的時候，我們并不知道輸入的參數到底是“-c 整數”類型的，還是“-s 文件名”類型的，而且題目中也提到了對于異常輸入的容錯性處理，所以我專門建立一個Input類用來處理輸入數據。
程序的核心功能有兩個：終局生成和求解數獨，所以我建立一個SudokuOperation類專門處理數獨操作。當控制臺輸入“-c 整數”命令的時候，調用某個成員函數來生成終局；當控制臺輸入“-s 文件名”命令的時候，調用另外一個成員函數來求解數獨。
總共就建立了這兩個類。
------4.2 類中成員、方法的調用關系
以下是我的Input類和SudokuOperation類的核心成員和主要方法及其調用關系。1）Input類：
members：
①int argc; //表示命令行參數的數量
②char **argv; //命令行參數二維數組
③int num; //表示命令行參數的數量,比argc語義更明確所以引入
④char type; //命令行輸入的是“-c”，type就等于‘c’，如果是“-s”type就是‘s’。
⑤char filename; //文件名字符串
methods：
void input_type_analyse();//命令行輸入之后，調用此函數做分析處理
2）SudokuOperation：
methods：
①void generate_ending(int num);//生成終局調用的函數。它執行時會調用②
②void move_step_generate(); //每一行平移時候的步長生成函數
③void solve_sudoku(char *filename);//解數獨調用的函數，它執行時會調用④
④void search_solution(int i, int j, int (&matrix)[9][9]); //dfs的過程，它會調用⑤
⑤bool check(int i, int j, int n, int matrix[9][9]); //判斷在matrix[i][j]的位置填上n是否可行
具體代碼執行時的調用情況以及每個方法內部的組織，請查詢博客開頭項目github連接，我已經對代碼做了極其詳盡的注釋。
------4.3 單元測試的設計及代碼覆蓋率測試
以前寫代碼從來沒有過單元測試，所幸的是這學期老師上課講了概念。but如何進行仍然是個不小的問題，我在這里找到了答案：
https://docs.microsoft.com/zh-cn/visualstudio/test/getting-started-with-unit-testing?view=vs-2017
微軟Visual Studio團隊的的官方描述可謂是十分詳盡了，基本上屬于手把手教學，我看了十分高興，對自己的項目進行了單元測試
我設計了10個測試，每個測試用例都對應著程序中可能出錯的地方，其中前8個測試（TestMethod1-8）是針對于輸入出現的各種情況，包括正常輸入，參數換位輸入，待求解文件不存在的異常輸入等等；后2個測試（TestMethod9-10）是根據數獨操作類SudokuOperation進行測試，檢查平移位數矩陣的正確性和生成數獨結果的正確性等等。
詳細測試代碼見博文頭部的github鏈接，里面sudoku_unit_test文件夾中的sudoku_unit_test.cpp文件就是哦~
關于代碼覆蓋性分析，是衡量測試好壞的一種標準，代碼覆蓋率越大，說明被我們測試到的代碼片段所占整個代碼的比重也就越大，理論上測試效果就越成功。Visual Studio enterprise版本上自帶了代碼測試，但是，，，，，，我的VS是professional版本的，并不能進行代碼覆蓋率測試。所以只能自行下載插件解決。在VS marketplace里有一個名叫OpenCppCoverage的插件可以檢查C++代碼的測試覆蓋率。于是我下載了這個插件作為對欠缺功能的補充。
但是這個插件只能對單個樣例進行覆蓋率測試，無法查看全部用例的覆蓋率，所以顯示的結果會比單元測試全部用例對于項目的覆蓋率實際要低很多
可以看到仍然達到了55%的覆蓋率，而這只是一個用例的結果，再加上其他測試用例，應該遠不止55%。但是由于實在找不到一款插件對全部的用例進行測試，就只好作罷
5. 程序優化
生成數獨終局優化：
下圖是輸出1000000個數獨終局的CPU占用情況：
這個結果還是令人滿意的 \ ^_ ^ /。
下面是改進后的最終版生成數獨CPU占用情況：
在平移每行的時候，不要用模運算(%)來補一行后面的空位啦。
I mean，如果你的數獨
第一行是1 2 3 4 5 6 7 8 9
第二行是4 5 6 7 8 9 1 2 3
那么第二行的后三個數（打了刪除線的三個數，不要用模運算來求）
我想了一種方法可以提高生成數獨的計算速度 (/ ￣▽￣)/*
用一個joint_line數組表示兩個第一行的拼接，
比如第一行如果是1 2 3 5 6 7 8 9的話，
joint_line就是1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9，如果想要生成第二行，就直接從joint_line[3]所在的位置開始往后面用memcpy_s()函數截取9個整型數，cpy到第二行中去。這種方法很快，基本不消耗什么時間。
解數獨優化：
在求解數獨時：在搜索可行解的過程中，并不是不管三七二十一，先把一個一個數填進去到最后檢查是否為一個合格的數獨。而是采用了在填一個數之前就檢查這個數是否滿足當前的結果，如果不滿足就回退的方法。（用這種方法相當于剪掉了一些不必要的搜索路徑，即：如果1填在某一個位置不合適就不繼續往下找，而是檢查2，3，4，···放在這個位置合不合適。）
6. 代碼說明
生成數獨代碼：
那么joint_line[18] = {9,1,2,3,4,5,6,7,8, 9,1,2,3,4,5,6,7,8};
這樣在做平移的時候，就不用膜來膜去的，直接memory copy 9個整數的長度就可以得到一行，非常方便（上文已經提到了）
生成數獨的代碼如下：
void SudokuOperation::generate_ending(int num) {errno_t err;FILE *file;err = fopen_s(&file, "C:\\Users\\Administrator\\Desktop\\MySudoku\\MySudoku\\Debug\\sudoku.txt", "w");if (err != 0)printf("file doesn't exist\n");move_step_generate();int first_line[9] = { 9,1,2,3,4,5,6,7,8 };//for the convenience of operation, joint_line is double first_lineint joint_line[18];while (next_permutation(&first_line[1], &first_line[9])){//If we have already generated enough game ending, breakif (num_now >= num)break;//use the same permutation for 72 timesint circle = 72;while (circle--){//If we have already generated enough game ending, breakif (num_now >= num)break;else{//joint_line is double first_line connected with each othermemcpy(joint_line, first_line, sizeof(first_line));memcpy(&joint_line[9], first_line, sizeof(first_line));int i = num_now % 72;for (int j = 0; j < 9; j++){int step = move_step_matrix[i][j];memcpy(&result_matrix[j], &joint_line[step], 9 * sizeof(int));}for (int j = 0; j < 9; j++){fprintf(file, "%d %d %d %d %d %d %d %d %d\n", result_matrix[j][0], result_matrix[j][1], result_matrix[j][2], result_matrix[j][3], result_matrix[j][4], result_matrix[j][5], result_matrix[j][5], result_matrix[j][6], result_matrix[j][7], result_matrix[j][8]);}fprintf(file,"\n");num_now++;}}}fclose(file); }這是generate_ending()所調用的“每行移動步數生成函數”——move_step_generate()的代碼，執行結果保存在move_step_matrix[72][9]數組中。表示72種移動方式。
move_step_generate()代碼如下：
void SudokuOperation::move_step_generate() {int move_dictionary1[2][3] = { { 0,3,6 },{ 0,6,3 } };int move_dictionary2[6][3] = { { 1,4,7 },{ 1,7,4 },{ 4,1,7 },{ 4,7,1 },{ 7,4,1 },{ 7,1,4 } };int move_dictionary3[6][3] = { { 2,5,8 },{ 2,8,5 },{ 5,2,8 },{ 5,8,2 },{ 8,2,5 },{ 8,5,2 } };int i, j, k, count = 0;int step[9];for (i = 0; i < 2; i++){for (j = 0; j < 6; j++){for (k = 0; k < 6; k++){memcpy(step, move_dictionary1[i], 3*sizeof(int));memcpy(&step[3], move_dictionary2[j], 3*sizeof(int));memcpy(&step[6], move_dictionary3[k], 3*sizeof(int));memcpy(&move_step_matrix[count], step, 9*sizeof(int));count++;}}} }求解數獨：
求解數獨部分的代碼相對復雜，solve_sudoku()調用函數search_solution()，其中solve_sudoku()從文件中讀入一個待求解的矩陣，就調用search_solution()求解一次，一直讀到文件尾為止。search_solution()在每次執行的過程中需要檢查當前位置能否放下某個數字，這時候調用check()函數.
solve_sudoku()函數代碼如下：
void SudokuOperation::solve_sudoku(char *filename) {errno_t err, erw;FILE *rfile, *wfile;err = fopen_s(&rfile, filename, "r");erw = fopen_s(&wfile, "C:\\Users\\Administrator\\Desktop\\MySudoku\\MySudoku\\Debug\\sudoku.txt", "w");if (err != 0 || erw != 0)printf("the input or output file doesn't exist\n");else{//Read the file, and get the puzzle matrix in the fileint puzzle_matrix[9][9];//*blank_or_enter is used for engulfing two kinds of characters, ' ' and '\n'char blank_or_enter;int i, j;do{for (i = 0; i < 9; i++){for (j = 0; j < 9; j++){fscanf_s(rfile, "%d%c", &puzzle_matrix[i][j], &blank_or_enter, sizeof(int) + sizeof(char));}}//search for one solution in puzzle_matrix[][], fill the puzzle_matrix from puzzle_matrix[0][0]search_solution(0, 0, puzzle_matrix);success_sign = false;for (i = 0; i < 9; i++){fprintf(wfile, "%d %d %d %d %d %d %d %d %d\n", puzzle_matrix[i][0], puzzle_matrix[i][1], puzzle_matrix[i][2], puzzle_matrix[i][3], puzzle_matrix[i][4], puzzle_matrix[i][5], puzzle_matrix[i][6], puzzle_matrix[i][7], puzzle_matrix[i][8]);}fprintf(wfile, "\n");} while (fscanf_s(rfile, "%c", &blank_or_enter, sizeof(char))!=EOF);//engulf the '\n' between two sudoku matrixs}fclose(rfile);fclose(wfile); }search_solution()函數代碼如下：
void SudokuOperation::search_solution(int i, int j, int (&matrix)[9][9]) {//if search has come to an end, return.if (success_sign == true)return;else{//if we have finished searching the last line, return if (i > 8){success_sign = true;return;}//if j > 8, which means current line is done, we have two options.if (j > 8){//if the current line isn't the last line, search for the next lineif (i < 8)search_solution(i + 1, 0, matrix);//If the current line is the last line, returnif (i == 8){success_sign = true;return;}}//if current position is not vacant, jump itif (matrix[i][j] != 0)search_solution(i, j + 1, matrix);else{//if i <= 8 && j <= 8, search in the current line.if (i <= 8 && j <= 8){//try each number from 1~9 at current position(i,j).for (int n = 1; n <= 9; n++){if (check(i, j, n, matrix)){matrix[i][j] = n;search_solution(i, j + 1, matrix);//If we successfully find a solution at the end of searching, returnif (success_sign == true)return;elsematrix[i][j] = 0;}}}}} }check()函數代碼如下：
bool SudokuOperation::check(int i, int j, int n, int matrix[9][9]) {int col, row;//check the numbers in the same horizontal column before we put n at matrix[i][j]for (col = 0; col < 9; col++){if (matrix[i][col] == n)return false;}//check the numbers in the same vertical row before we put n at matrix[i][j]for (row = 0; row < 9; row++){if (matrix[row][j] == n)return false;}//check the numbers in the same 3*3 squareint base_row = (i / 3) * 3;int base_col = (j / 3) * 3;for (row = base_row; row < base_row + 3; row++){for (col = base_col; col < base_col + 3; col++){if (matrix[row][col] == n)return false;}}//If obey the sudoku rules, return truereturn true; }7. 心得感悟
努力擁有良好的代碼風格： 之前做過一些github上開源項目的代碼注釋的統計工作，所以我對一些開源項目中的代碼風格有所了解。很多時候在C++項目中，開發者會把：類的定義、成員變量以及成員函數的接口放在.h文件中，把成員函數的具體實現放在.cpp文件中。而且每個成員函數前面和函數體內部都有大量注釋，這方便后來的程序猿能夠讀懂代碼，是一種良好的習慣。在本項目中，我也努力使自己的代碼風格向這些著名的項目靠攏，因此我加了很多行注釋。我的幾乎全部代碼都采用了Google C++規范，但是因為自己實在不太習慣把大括號放在與for循環同一行的寫法，所以在實際編程寫大括號的時候有所變通。
for(······){//這是標準的谷歌寫法 } for(······) {//我的寫法 }再次讓我深切體會到：軟件工程不僅僅是編程。軟件開發過程是一個綜合的過程，從前期的需求分析開始，到后來的設計，再到實現，性能優化，每一步都需要投入很多精力和時間。
總結
以上是生活随笔為你收集整理的BIT软件工程个人项目——数独sudoku的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 七、ref引用与数组的常用方法
- 下一篇： teamviewer14 去商用途提示