1.項目的Github位址
https://github.com/crvz6182/sudoku
2.開發預估耗時：
| PSP2.1 | Personal Software Process Stages | 預估耗時（分鐘） | 實際耗時（分鐘） |
| Planning | 計劃 | 10 | |
| · Estimate | · 估計這個任務需要多少時間 | ||
| Development | 開發 | 890 | |
| · Analysis | · 需求分析 (包括學習新技術) | 30 | |
| · Design Spec | · 生成設計文檔 | 5 | |
| · Design Review | · 設計複審 (和同僚稽核設計文檔) | ||
| · Coding Standard | · 代碼規範 (為目前的開發制定合适的規範) | ||
| · Design | · 具體設計 | 20 | |
| · Coding | · 具體編碼 | 500 | |
| · Code Review | · 代碼複審 | ||
| · Test | · 測試（自我測試，修改代碼，送出修改） | 300 | |
| Reporting | 報告 | 95 | |
| · Test Report | · 測試報告 | 60 | |
| · Size Measurement | · 計算工作量 | ||
| · Postmortem & Process Improvement Plan | · 事後總結, 并提出過程改進計劃 | ||
| 合計 | 995 |
3.解題思路
這次的項目要求既能生成不重複的數獨又能解數獨。
生成數獨算法的靈感來源于《程式設計之美》中有關數獨的一部分論述，書中提到可以通過生成好的3x3矩陣擴充成合法的9x9數獨。由于不能重複，随機生成再查重要消耗相當多的時間，而且當時也不知道其他順序生成的方法，就覺得這個主意不錯。
書中的算法雖然不能滿足1000000個的需求，但是給出了如何增加變化的提示。可以通過部分行列的對換生成更多種類的數獨。在這次題目限制的左上角數字不變的情況下，隻要确定了一個3x3矩陣，就可以生成2*6*6*2*6*6=5184個數獨。3x3矩陣可以視為生成數獨的一個“種子”。接下來就要確定不同的種子生成的數獨中沒有重複了。
種子和最後生成的數獨中的每個3x3區域都是一一對應的。将最後生成的數獨中左上角的3x3區域中的格子編号：（左上角固定為6）
| 6 | X | Y |
| x | a | b |
| y | c | d |
由于6不能變換位置，是以行列變換隻會涉及第2,3行和2,3列。剩下的數字隻能從1,2,3,4,5,7,8,9裡選。
以如下順序填充這個區域：先取一組數X,Y，再取一組數x,y，然後把剩下的數字由大到小填入abcd。隻要兩個數獨中X,Y,x,y這四個位置的數字不完全相同就不會重複。假如數字相同但位置不同，進行行列變換後雖然可以使位置相同，但會影響abcd四個數的位置，是以還是不同情況。在這個規則下生成的種子可以有8*7*6*5=1680個。總共可以生成1680*5184=8709120個，滿足1000000個的需求。
解數獨采用了比較簡單的回溯法，依次往未填入數字的格子中填數，如果無法繼續進行則回溯到上一次填數的位置。直到全部填完，或是回溯到開頭後發現無解。
4.設計思路
沒有使用類，在main函數中判斷要解還是生成，以及生成種子。
關于生成的函數：
void transform(int sudoku[][9], int x, int y, int X, int Y, int* others, int num, char *result, int &r_tag)
用于将種子擴充為數獨并進行變換，變換後結果輸出到result
關于求解的函數：
bool in_area(int sudoku[][9], int x, int y, int i)
判斷某個數是否已經在一個3x3區域内
void solve(int sudoku_s[][9], char* result, int &r_tag)
求解一個數獨并将結果輸出到result
調用關系：
main調用solve，transform
solve調用in_area
關于單元測試：
單元測試針對上述三個函數，給定不同輸入情況并判斷是否正常輸出
（教程中給的單元測試操作方法沒有生成.exe，但是覆寫率分析插件隻能針對.exe，我嘗試了很久也沒能一起使用）
5.程式改進
這次的項目可以說有一半的時間都花在了改進上。改進過程中沒有改動算法，主要是針對細節問題進行優化。
在第一版完成後，生成的運作速度特别慢。後來通過性能分析發現字元串的“+=”拼接操作占用了大量時間，于是改用字元數組存儲最後結果，性能得到了顯著提升。在自己的電腦上測試時生成1000000個的所需時間從一分多鐘降到了6s左右。
在求解算法中我一開始使用多位數儲存所有可能選擇，性能分析後發現由于需要多次除法和取餘數運算導緻效率很低，後來改用了數組進行儲存，用時減少了近6/7。
時間還是主要花在對字元的操作上
6.代碼展示
for (x = 1; x <= 7; x++)
for (y = x + 1; y <= 8; y++)
for (X = 1; X <= 7; X++)
for (Y = X + 1; Y <= 8; Y++)
if (X != x&&X != y&&Y != x&&Y != y) {
for (int i = 1; i < 9; i++) {
if (X != i&&x != i&&Y != i&&y != i) {
if (i == 6)
others[j++] = 9;
else
others[j++] = i;
}
if (j == 4) {
j = 0;
break;
}
}
if (X == 6)X = 9; if (Y == 6)Y = 9; if (x == 6)x = 9; if (y == 6)y = 9; 周遊所有種子，用x,y,X,Y儲存關鍵區分元素，others數組儲存其他元素
for (x1 = 0; x1 < 2; x1++) {
for (x2 = 0; x2 < 6; x2++) {
for (x3 = 0; x3 < 6; x3++) {
for (y1 = 0; y1 < 2; y1++) {
for (y2 = 0; y2 < 6; y2++) {
for (y3 = 0; y3 < 6; y3++) {
......
} 周遊所有行列變換的情況，循環内部為根據相應情況進行變換
int x = 0, y = 0, i = 0, j = 0, m = 0, n = 0;
for (int p = 0; p < 9; p++)
for (int q = 0; q < 9; q++) {
if (sudoku[p][q] == 0)
list_tag[p][q] = -1;
else
list_tag[p][q] = -2;
for (int r = 0; r < 9; r++) {
list[p][q][r] = 0;
}
}
while (x != 9 && y != -1) {//周遊
if (0 <= x&&x <= 8 && 0 <= y&&y <= 8 && sudoku[x][y] == 0) {
for (i = 1; i <= 9; i++) {
if (in_area(sudoku, x, y, i))continue;
for (j = 0; j < 9; j++) {
if (sudoku[x][j] == i) break;
if (sudoku[j][y] == i) break;
}
if (j != 9)continue;
list[x][y][++list_tag[x][y]] = i;
}
if (list_tag[x][y] == -1) {
st = 1;
y--;
if (y == -1) {
x--; y = 8;
}
}
else {
sudoku[x][y] = list[x][y][list_tag[x][y]];
st = 0;
y++;
if (y == 9) {
x++; y = 0;
}
}
}
else {
if (list_tag[x][y] == -2) {
switch (st) {
case 0:
y++;
if (y == 9) {
x++; y = 0;
}break;
case 1:
y--;
if (y == -1) {
x--; y = 8;
}
break;
}
}
else {
if (list_tag[x][y] == 0) {
sudoku[x][y] = 0;
list[x][y][0] = 0;
list_tag[x][y] = -1;
st = 1;
y--;
if (y == -1) {
x--; y = 8;
}
}
else {
list[x][y][list_tag[x][y]] = 0;
sudoku[x][y] = list[x][y][--list_tag[x][y]];
st = 0;
y++;
if (y == 9) {
x++; y = 0;
}
}
}
}
if (y == -1) {
cout << "無解\n"; exit(1);
}
}
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
result[r_tag++] = char(sudoku[i][j] + '0');
if (j == 8)
result[r_tag++] = '\n';
else
result[r_tag++] = ' ';
}
}
result[r_tag++] = '\n'; 求解數獨時的回溯過程，用數組儲存每個位置可以填的所有數字
7.完成後的PSP
| 10 | |||
| 20 | |||
| 1400 | |||
| 80 | |||
| 5 | |||
| 500 | |||
| 30 | |||
| 600 | |||
| 120 | |||
| 100 | |||
| 1470 |
對我來說，這次作業的壓力不亞于當初讓我忙了好幾天的OO計程車作業。要想在時限内盡量完美的完成任務對我來說很難，光是在Debug上我就花了好幾個小時，這幾天幾乎一直都在做相關的事情。是以我最後沒有寫附加題，沒有用DLX算法，編碼品質也很差……就個人能力上來說我還很弱，可能選擇這門課的目的就是為了鍛煉一下自己吧……