個人項目作業-數獨生成與求解
項目位址
https://github.com/FelixCaae/SudokuGen
解題思路
一開始打算自己設計一個算法，因為之前也做過數獨題目，對解題思路有一定的了解，打算用排除法加搜尋來做，初步的思路是這樣的，首先初始化一個空數獨表格，給每個格子内填入可能的解，在沒有任何限制條件的情況下就是1-9。然後将題目上的數字依次填入，每填入一個數字就依據限制條件對可能性做一些修改，比如(0,0)的位置填入了1，那麼就從第一個宮内的其他數字單元和該行該列的其他數字單元中移除可能解1.如此反複，将題目填入完畢後，依次周遊可能解最少的單元來進行解的搜尋，每次确定一個解就進一步壓縮限制條件直到所有數字都被填完。
這個算法沒有來得及實施，因為感覺很可能會性能不足，是以就上百度搜尋了一下數獨的算法求解，了解到一種以宮為機關進行填寫的算法而不是以格為機關進行填寫的回溯法和一種以數獨的同質性為基礎的交換算法(用于生成而不是求解）。Wiki上列舉的各種方法更為詳細，但是沒有細看，決定先試試回溯法，并且用python寫了一個版本用于驗證。
數獨入門解題技巧 http://ask.kedo.gov.cn/resource/stars/823575.shtml
回溯法介紹 http://blog.sina.com.cn/s/blog_a28e3dd90101e1i2.html
設計過程
這部分參考了之前OO的經驗，把功能分給了4個類，參數處理類(ArgumentHandler)用于處理輸入的參數，檔案處理類(FileHandler)用于打開關閉檔案和讀寫數獨，表類(Table)用于記錄數獨資料并且提供生成和求解的方法，數獨緩沖類(SdkBuffer)用于臨時存儲生成的數獨。
類确定後，首先是設計公有方法，确定類的協同關系以及確定覆寫全部功能，其中比較重要的Table類試着使用了形式化的方法
1 class Table
2
3 {
4
5 private:
6
7 int cells[9][9];
8
9 int total;
10
11 int top;
12
13 SdkBuffer* pCurrentBuffer;
14
15 public:
16
17 Table();
18
19 /*@Modifies:this
20
21 Set all elements to zero ,which stands for not being filled.
22
23 */
24
25 void SetZero();
26
27
28
29 /*@Requires:0<=row,col<9 and 1<=num<=9
30
31 ＠Modifies:this
32
33 Set one element to the value given
34
35 */
36
37 void Set(int row, int col, int num);
38
39
40
41 /*@Requires:length(num)>=9 and any element i in num[][] ==> 1<=i<=9
42
43 @Modifies:this
44
45 Set the table with the two-dimension array given.
46
47 */
48
49 void Set(int num[][9]);
50
51
52
53 /*@Requires:total>0 and total <=100000 and sdb!=null and total<sdb->GetCapacity()
54
55 @Modifies:sdb
56
57 Generate sudoku solution and write to a file.
58
59 */
60
61 void Generate(unsigned int total, FileHandler* fh);
62
63
64
65 /*@Requires:sdb!=nulls
66
67 @Effects:/result==true <==> We can find at least one solution
68
69 @Effects:/result==false <==> We can`t find any solution
70
71 Solve the problem in the table
72
73 */
74
75 bool Solve(SdkBuffer* sdb);
76
77
78
79 /*Solve the problems in src buffer and write the answers to the dst buffer
80
81 Notice:it will clear the dst buffer firtst and clear src buffer as an effect
82
83 */
84
85 void Solve(SdkBuffer * sdbSrc, SdkBuffer * sdbDst);
86
87
88
89 /*@Requires:total>0 and total <=100000 and sdb!=null
90
91 @Modifies:sdb
92
93 Generate sudoku solution to the sdb
94
95 */
96
97 void Generate(unsigned int total, SdkBuffer* sdb);
98
99
100
101 /*@Requires:src!=null,dst!=null
102
103 @Modifies:src,dst
104
105 Solve the problem set given by the src and output the result to dst.
106
107 */
108
109 void Solve(FileHandler* src, FileHandler*dst);
110
111 ~Table();
112
113 private:
114
115 /*@Requires : 0<rst, cst<3 1 <= num <= 9
116
117 @Effects : / result == null <= = > there is one number in Palace(rst, cst) equals to num
118
119 @Effects : / result == {-1 } <= = > there is no suitable place for num in Palace(rst, cst)
120
121 @Effects : len(/ result) >= 1 && / result != {-1} <= = > there is one or more suitable place for num in Palace(rst, cst)*/
122
123 int* lookUp(int rst, int cst, int num);
124
125
126
127 void solve(int subt, int num);
128
129 } 其他類的方法設計比較簡單，緩沖區采用了棧的設計，參數處理器使用一個方法接受輸入參數，并傳回一個枚舉型變量，檔案讀寫類是對檔案操作做了一個簡單的封裝。
單元測試及性能優化
這部分沒有來得及做，确實時間沒有安排好，直到周六才開始編碼，而且周末組隊的事情耽誤了一些時間，這個作業其實還是很勉強完成的，之後得補上測試，優化的話可能得結對程式設計的時候再說了。
代碼展示
關鍵算法
int* Table::lookUp(int rst, int cst, int num)
{
int *result=new int[10];
int index=0;
int ron=0,con=0;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
ron = i + rst * 3;
con = j + cst * 3;
if (cells[ron][con] == num)
{
return NULL;
}
if (cells[ron][con] != 0)
continue;
bool pass=true;
for (int t = 0; t < 9; t++)
{
if (cells[ron][t] == num || cells[t][con] == num)
{
pass = false;
break;
}
}
if (pass)
{
result[index++] = ron*9+con;
}
}
}
// printf("%d", index);
result[index] = -1;
return result;
}
void Table::solve(int subt, int num)
{
//this function works recursively to fill number 1-9 one by one to all the 9 sub tables
//subt index subtable ,which is a 3x3 palace. It`s index starts from 0 to 8
//num (1-9) is the current number we try to fiil in
// printf("%d %d\n", subt, num);
//if we get enough solutions ,just exit
if (total == top)
return;
//It signals that all numbers are filled.
else if (num == 10)
{
total += 1;
pCurrentBuffer->Fill(cells);
return;
}
//we should try the next number while that all palaces are reached
else if (subt == 9)
{
solve(0, num + 1);
return;
}
//Row or Column of SubTable
int rst = subt / 3;
int cst = subt % 3;
//suitable cells
int * suitcells = lookUp(rst, cst, num);
if (suitcells == NULL)
{
solve(subt + 1, num);
return;
}
int index = 0;
//Row or Column of Number
int ron = 0;
int con = 0;
while (suitcells[index] != -1 && total!=top)
{
ron = suitcells[index] / 9;
con = suitcells[index] % 9;
cells[ron][con] = num;
solve(subt + 1, num);
cells[ron][con] = 0;
index++;
}
delete[] suitcells;
} lookUp()函數用于在某一個宮内為一指定的數尋找合适的位置，傳回NULL代表該數已存在，空數組代表沒有合适的位置等等。
solve()函數遞歸調用自己，依次填入1-9到九個宮裡，直到發現無解或解的個數達到設定值為止。
| PSP2.1 | Personal Software Process Stages | 預估耗時（分鐘） | 實際耗時（分鐘） |
| Planning | 計劃 | 20 | 15 |
| · Estimate | · 估計這個任務需要多少時間 | ||
| Development | 開發 | 665 | 570 |
| · Analysis | · 需求分析 (包括學習新技術) | 200 | 120 |
| · Design Spec | · 生成設計文檔 | 60 | 90 |
| · Design Review | · 設計複審 (和同僚稽核設計文檔) | 30 | |
| · Coding Standard | · 代碼規範 (為目前的開發制定合适的規範) | 5 | |
| · Design | · 具體設計 | 100 | |
| · Coding | · 具體編碼 | 300 | |
| · Code Review | · 代碼複審 | ||
| · Test | · 測試（自我測試，修改代碼，送出修改） | 45 | |
| Reporting | 報告 | 80 | |
| · Test Report | · 測試報告 | 10 | |
| · Size Measurement | · 計算工作量 | ||
| · Postmortem & Process Improvement Plan | · 事後總結, 并提出過程改進計劃 | 40 | |
| 合計 | 765 |
總結:
這次作業完成的比較失敗吧，自己感覺，沒有一開始就認真着手這些工作導緻時間不充裕，容錯率低是一個很大的原因。
其次是查詢資料的環節，由于偷懶沒有仔細比較各種算法的優劣，而是快速地憑印象選擇，如果不是看到其他人的交流很可能不知道那些比較有效率的算法。
設計階段沒有很到位，隻是花了幾分鐘畫了一個草圖，可能之後會表現出來一些問題吧。
代碼複審，嫌麻煩，時間短，沒有做，結果在調試上浪費了很多時間在一些小細節上.. 主要的算法明明先用python實作了一遍，幾乎一模一樣的寫到VS裡，本以為這塊會是出錯率最低的地方，實際上花了最多的時間來調。如果仔細審查一遍會好很多吧。
單元測試..沒有做，是以可能還有很多潛在的漏洞。設計的時候就沒有設計單元測試，真是一團糟..