項目相關要求
Github 項目位址：https://github.com/zjwml4581792/Software-engineering
第一次的真軟工實踐作業就是這種題目，想想還有點小激動，終于又要敲代碼啦。看着自己現在的程式設計的“紙飛機階段”，想完成，還是等待~并心懷希望吧！
先看題目。
我是題目
度娘說：數獨（百度百科）
數獨（Sudoku，Crosswords）是源自18世紀瑞士的一種數學遊戲。是一種運用紙、筆進行演算的邏輯遊戲。玩家需要根據9×9盤面上的已知數字，推理出所有剩餘空格的數字，并滿足每一行、每一列、每一個粗線宮（3*3）内的數字均含1-9，不重複。
數獨盤面是個九宮，每一宮又分為九個小格。在這八十一格中給出一定的已知數字和解題條件，利用邏輯和推理，在其他的空格上填入1-9的數字。使1-9每個數字在每一行、每一列和每一宮中都隻出現一次，是以又稱“九宮格”。
工具清單
- 程式設計語言： C/C++
- 程式設計IDE：Visual Studio 2017 社群版
- 效能分析工具：Visual Studio Profiling Tools
- 源代碼管理平台：Github
- markdown 編輯器：有道雲筆記
解題思路
遇到的困難及解決方法
- 困難描述
看到的第一眼就是，這個題目跟程式語言綜合設計的那個馬踏棋盤和N皇後問題好像啊，一百度，果然三個題目經常綁定出現，用的很多都是回溯。
然而自己并不是很懂回溯，于是自己找了找不是回溯算法的大神寫的部落格。可惜大神寫的算法我基本看不懂。
各種各樣的問題顯示了自己的功力不足，函數什麼時候開始回溯啊，調用函數自己的那行到底寫在哪裡啊，比較好的想法到底是哪一種啊……
- 做過哪些嘗試
自己什麼都不懂，直接開始寫是不現實的，于是開始問學長。
先問了個直系老鄉研究所學生谷歌（還是微軟）大佬，說“數獨問題用 dancing links 算法來寫”，，一百度好像dancing links 真的很厲害的樣子，但是好像這麼複雜的雙向連結清單我真的寫不出來。
自己百度“數獨生成算法”吧，看看前輩們都用的是什麼算法，用的思想是不是太超前自己能不能接受。
找到的比較看得懂自己印象比較深有啟發的：
- 【算法研究】數獨高效完全解生成算法的研究和實作
- JavaScript九宮格數獨生成算法
- 五大常用算法之四：回溯法
于是自己嘗試了生成 9 個随機數組一行一行填進矩陣，一個一個數字地填，一個九宮填一個九宮地填等等各種方法。
- 是否解決
最後采用了 0~9 輪流逐行地填的方法，即從1開始填，從第0行填到第8行，1填完了填2，直到9。
事實證明采用了某種方法如果理論沒問題一定要堅持到底，如果不斷地嘗試别的方法真的沒有效率，就跟《建構之法》裡的畫扇面一樣，過早想着優化，都還沒完成必要功能和需求就不要考慮太多。先寫出來了再說。
- 有何收獲
從 【1】 中汲取了“按九宮格從左到右從上到下，從 1-9 輪流填，填完了再填下一個數”的思想并改造；
從 【2】 中得到了先把無依賴的主對角線上的三個小九宮填滿，再填其他九宮的思想（但是最終并沒有用到這方法）
從 【3】 中了解了怎麼寫回溯算法。
自己的搜尋能力暴漲，code能力小幅升，熬夜能力MAX，泡面技巧infinite
。拖延症已病入膏肓
關鍵代碼
習慣看到題目就先建立個類，這個數獨類至少需要有構造函數、析構函數、建立矩陣、列印矩陣四個函數，數獨矩陣二維數組，然後根據需要添加了初始化函數，判斷函數，檔案變量等，詳見代碼注釋。
class Sudo
{
public:
Sudo(int id); //構造函數
~Sudo(); //析構函數
void createSudoku(int id);//建立數獨矩陣
void print(); //列印
void init(); //初始化
private:
ofstream outfile; //輸出檔案
int arr[9][9]; //數獨矩陣數組
int flag; //是否把每一行的該數都填好的标志
int firstNumber; //題目要求的跟學号有關的數
bool isRight(int row, int column, int num);//判斷row行column列是否可以填num
vector<int> randVector(); //生成随機數組
void fillNumber(int num, int row); //從row開始每一行開始填充num
void clean(int i); //填充失敗，把i數清除，重新填過
};
看到題目想到要寫的第一個函數就是判斷函數，在寫的時候先分别寫了行判斷、列判斷、九宮判斷三個函數，以及調用三個函數的isRight原始版，後來整合到一起了就成了下面的新生版。由于是逐行填充的，隻需要檢查列和九宮符不符合要求即可。
後來思考如果按照每個九宮來填數，隻需要判斷行和列會不會更快，但是按九宮來填數，填數就麻煩了，根據第一個部落格裡的來看，應該按九宮來會快些。
bool Sudo::isRight(int row, int column, int num)
{//判斷所在位置是否可行
for (int i = 0; i < 9; i++)
{//檢查列可不可以
if (arr[i][column] == num)
return false;
}
int northwestX = row / 3 * 3;//算小九宮的第一個位置
int northwestY = column / 3 * 3;
//檢查九宮
for (int i = 0; i < 3; i++)//橫向檢查
{
for (int j = 0; j < 3; j++)//豎向檢查
{
if (arr[i + northwestX][j + northwestY] == num)
return false;
}
}
return true;
}
如果是普通的随機數的生成的話，一定會生成重複的随機數，于是生成一個0-8的随機數組，需要用的時候周遊數組。
如何生成随機數組的方法是網上找的，C++下數組随機shuffle的方法解
vector<int> Sudo::randVector()//生成随機數組
{
vector<int> result;
result.clear();
for (int i = 0; i < 9; i++)
result.push_back(i);
random_shuffle(result.begin(), result.end());
return result;
}
建立數獨，先填要求的數，再從1-9填，沒法填了就退回上一個數重新填過。
void Sudo::createSudoku(int hhhhhh)//建立數獨
{
fillNumber(firstNumber, 1); //先把要求的那個數填進去
for (int i = 1; i < 9; i++) //從1到9開始填充
{
if (i == firstNumber)//如果是要求的那個數
continue; //則跳過
fillNumber(i, 0); //逐行填充數i
if (flag) //如果填充好了
flag = false; //将flag置false，準備下一個數
else //如果沒填好
{
clean(i);//把上一個數清掉，重填
i -= 2; //先-2，待會+1，從上一個數重新開始
}
}
for (int i = 0; i < 9; i++)//發現上面填完了之後9是空的
{
for (int j = 0; j < 9; j++)//就寫一個循環把9補上
{
if (arr[i][j] == 0)
arr[i][j] = 9;
}
}
}
最重要的填數，不過這個回溯挺最簡單，從第0行開始填num。
void Sudo::fillNumber(int num, int row)//從row行開始填充num
{
if (row > 8) //如果0-8行都填完了
{
flag = true; //将填好的标志flag置true
return; //傳回
}
vector<int>temp = randVector(); //生成随機數組，
for (int i = 0; i < 9; i++) //從數組第一個數開始測試第row行temp[i]列行不行
{
if (arr[row][temp.at(i)] != 0)//如果這個位置填過了
continue; //跳過這列
if (isRight(row, temp.at(i), num))//如果這個位置可以
{
arr[row][temp.at(i)] = num; //填上去
fillNumber(num, row + 1); //填下一個行
if (flag) //如果填好了
return; //傳回
arr[row][temp.at(i)] = 0;//如果這個數這行填不成，把上一行該數置0，換temp下一個數試試
}
}
}
程式運作截圖
圖中的運作時間是測試用的，暴露了自己這個算法有待改進，很大的改進。
效能分析
摘要
調用關系樹
從中可以看出，主要是填充數函數占了最多時間，是以算法本身有很大的改進空間，比如判斷函數，從周同學的作業中，可以看出自己和TA的差距；也可以把fillNumber函數的傳回值設為Bool,也能少個變量flag。另外vector系列也是比較耗時的，用的不多的話，自己寫個随機生成數組的函數，借助庫函數是比較耗時。
關于執行力、泛泛而談的了解
百毒百科說
執行力是指有效利用資源、保質保量達成目标的能力，指的是貫徹戰略意圖，完成預定目标的操作能力。是把企業戰略、規劃、目标轉化成為效益、成果的關鍵。
執行力包含完成任務的意願，完成任務的能力，完成任務的程度。對個人而言執行力就是辦事能力；對團隊而言執行力就是戰鬥力；對企業而言執行力就是經營能力。
簡單來說就是行動力。
我的了解就是，在拿到任務之後，用自己最專注的熱情去完成這件事，最及時地完成，對待任務當機立斷、雷厲風行,以秋風掃落葉之勢，腳踏實地、貫徹始終,知行合一。
其實上面的這段話就是泛泛而談，沒有什麼針對性，就比如創新創業比賽上，上台的很多學生都是侃侃而談，對于自己的産品本身的介紹并不多，就算是客觀的場面話，也沒有講到針對于自身産品最大的痛點。
PSP
| PSP2.1 | Personal Software Process Stages | 預估耗時（分鐘） | 實際耗時（分鐘） |
|---|---|---|---|
| Planning | 計劃 | 20 | 10 |
| · Estimate | · 估計這個任務需要多少時間 | ||
| Development | 開發 | 1775 | 1820 |
| · Analysis | · 需求分析 (包括學習新技術) | 60 | 73 |
| · Design Spec | · 生成設計文檔 | 30 | 沒有做 |
| · Design Review | · 設計複審 (和同僚稽核設計文檔) | 單幹，不需要 | |
| · Coding Standard | · 代碼規範 (為目前的開發制定合适的規範) | 15 | 7 |
| · Design | · 具體設計 | 120 | |
| · Coding | · 具體編碼 | 1440 | 1560 |
| · Code Review | · 代碼複審 | ||
| · Test | · 測試（自我測試，修改代碼，送出修改） | 40 | |
| Reporting | 報告 | 155 | 78 |
| · Test Report | · 測試報告 | ||
| · Size Measurement | · 計算工作量 | ||
| · Postmortem & Process Improvement Plan | · 事後總結, 并提出過程改進計劃 | 33 | |
| 合計 | 1960 | 1908 |
學習進度條
| 第 N 周 | 新增代碼（行） | 累計代碼（行） | 學習耗時(小時) | 累計學習耗時（小時） | 重要成長 |
|---|---|---|---|---|---|
| 第 0 周 | 192 | 31 | 複習C++文法、學習VS2017操作、了解回溯 |
參考資料
- 1、JavaScript九宮格數獨生成算法
- 2、C++檔案操作詳解
- 3、C++下數組随機shuffle的方法解
- 4、【算法研究】數獨高效完全解生成算法的研究和實作
- 5、五大常用算法之四：回溯法
- 6、帶你玩轉Visual Studio——性能分析與優化