Github項目地址
https://github.com/JackManTvO/sudoku
PSP表格
| PSP2.1 | Personal Software Process Stages | 預估耗時（分鐘） | 實際耗時（分鐘） |
|---|---|---|---|
| Planning | 計劃 | 20 | 12 |
| Estimate | 估計這個任務需要多少時間 | 20 | 12 |
| Development | 開發(fā) | 520 | 890 |
| Analysis | 需求分析（包括學習新技術） | 120 | 170 |
| Design Spec | 生成設計文檔 | 30 | 55 |
| Design Review | 設計復審（和同時審核設計文檔） | 20 | 15 |
| Coding Standard | 代碼規(guī)范（為目前的開發(fā)制定合適的規(guī)范） | 20 | 10 |
| Design | 具體設計 | 60 | 80 |
| Coding | 具體編碼 | 180 | 400 |
| Code Review | 代碼復審 | 30 | 40 |
| Test | 測試（自我測試，修改代碼，提交修改） | 60 | 120 |
| Reporting | 報告 | 100 | 63 |
| Test Report | 測試報告 | 60 | 40 |
| Size Measurement | 計算工作量 | 10 | 10 |
| Postmortem & Process Improvement Plan | 事后總結，并提出過程改進計劃 | 30 | 13 |
| 合計 | 640 | 965 |
解題思路
生成數(shù)獨終局
??數(shù)獨的要求是在9×9的格子內，每一行和每一列和每一宮內都包含不重復的九個元素，但數(shù)獨終局的個數(shù)共有6,670,903,752,021,072,936,960（6.67×1021）種組合，盡管終局要求左上角第一個數(shù)字為固定值，其終局的種數(shù)也是巨大的。而程序設計對終局數(shù)量的需求僅在1,000,000個以內，因此，沒有必要窮舉找到前1,000,000種終局，而沒有合適的生成策略隨機生成則可能造成終局的重復。因此需制定合適的生成終局策略，而我的生成終局策略為對固定的終局模板進行數(shù)字交換以及行交換。這種策略共可以生成8!（除首數(shù)字外8個數(shù)字兩兩交換）×2（23行交換）×6（4～6行兩兩交換）×6（7～9行兩兩交換）=2,903,040種終局，大于要求的終局數(shù)。根據(jù)要求生成的終局個數(shù)對變換方式進行深度優(yōu)先搜索，第一層為數(shù)字交換，第二層為23行交換，第三層為4～6行交換，第四層為7～9行交換，以快速地遍歷第四層的葉子，以生成多個不重復的終局。
??具體步驟如下：
- 生成一固定的有效終局作為模板。
- 對模板進行數(shù)字交換。
- 對進行數(shù)字交換后的終局進行行交換（2～3行交換、4～6行交換、7～9行交換）保證宮內不重復。
- 若生成終局數(shù)滿足程序要求個數(shù)即返回，若不滿足，重復進行步驟2、步驟3。
求解數(shù)獨謎題
??對于給定的數(shù)獨謎題，按要求補充數(shù)獨的空缺，以完成數(shù)獨。因為填入的數(shù)需要滿足數(shù)獨的要求，所以每個固定位置的數(shù)值是有限制的，在剩余的可行值中選擇一個填入空白，接著填入下一個空白。若發(fā)現(xiàn)無可行解，則父節(jié)點選擇錯誤，采用回溯法，返回上一節(jié)點，填入另一可行解。直到生成樹的層數(shù)等于空缺數(shù)，則生成一可行的數(shù)獨終局，求解數(shù)獨謎題成功。
??具體步驟如下：
- 掃描題目，將空白值坐標取出存入數(shù)組A。
- 在數(shù)組A中選擇下一個坐標。
- 查詢其所在行、列、宮的數(shù)值，填入可行解數(shù)組，在可行解數(shù)組中選取下一可行解填入。
- 若填入成功，則返回步驟2，若無可行解，則在數(shù)組A中返回上一坐標，返回步驟3填入另一可行解。若A中無剩余，則返回，求解數(shù)獨成功。
設計實現(xiàn)過程
類
??我設計了三個類，分別為向量類、點類和數(shù)獨類（改進前）
Seed類（改進前）
| 變量名稱 | 類型 | 說明 |
|---|---|---|
| val | int[9] | 生成向量值 |
| 接口名稱 | 參數(shù)類型 | 返回類型 | 功能 |
|---|---|---|---|
| Seed | null | null | 根據(jù)宏定義的首數(shù)字生成生成向量 |
| swapi | int（腳標1），int（腳標2） | null | 根據(jù)腳標交換向量中兩數(shù)的位置 |
| getVal | int（腳標） | int（結果） | 根據(jù)腳標查詢向量中數(shù)值 |
Point類（改進前）
| 變量名稱 | 類型 | 說明 |
|---|---|---|
| x | int | 橫坐標 |
| y | int | 縱坐標 |
| pos | int[10] | 點的可行解標識 |
| 接口名稱 | 參數(shù)類型 | 返回類型 | 功能 |
|---|---|---|---|
| Point | null | null | 初始化類 |
| Point | Point*（實例） | null | 初始化類使其值與實例相同 |
Sudoku類（改進前）
| 變量名稱 | 類型 | 功能 |
|---|---|---|
| seed | Seed | 生成向量 |
| val | int[9][9] | 數(shù)獨 |
| zero | Point[60] | 空缺點集合 |
| 接口名稱 | 參數(shù)類型 | 返回類型 | 功能 |
|---|---|---|---|
| permuate | int（層數(shù)） | null | 根據(jù)層數(shù)dfs全排列 |
| mod | null | null | 根據(jù)生成向量生成模板 |
| generate | null | null | 全排列交換行生成終局 |
| cpy | const Sudoku*（模板) | null | 根據(jù)模板復制數(shù)獨 |
| swapRow | int（行數(shù)1），int（行數(shù)2） | null | 交換兩行數(shù)值 |
| write | FILE*（文件） | null | 將數(shù)獨寫入文件 |
| set | char*（字符串），int（行數(shù)） | null | 將文件讀出，按行給數(shù)獨賦值 |
| dfs | null | int（記號） | 深度優(yōu)先搜索，成功返回1，失敗返回0 |
類圖（改進后）
關鍵函數(shù)
元素交換函數(shù)
行交換函數(shù)
解數(shù)獨函數(shù)
單元測試設計
??使用了代碼走讀，并對三個關鍵函數(shù)使用路徑測試法進行了單元測試：
元素交換函數(shù)
| 路徑 | 輸入數(shù)據(jù) | 輸出數(shù)據(jù) |
|---|---|---|
| path1 | level=7 | 多個模板和終局 |
| path2 | level=10 | 無預期輸出 |
| path3 | level=6，nsudoku=0 | 無預期輸出 |
| path4 | level=6，nsudoku=1 | 1個終局 |
行交換函數(shù)
| 路徑 | 輸入數(shù)據(jù) | 輸出數(shù)據(jù) |
|---|---|---|
| path1 | nsudoku=72 | 72個模板和終局 |
解數(shù)獨函數(shù)
| 路徑 | 輸入數(shù)據(jù) | 輸出數(shù)據(jù) |
|---|---|---|
| path1 | 空點集 | 無預期輸出 |
| path2 | 包含3個點的點集 | 3個點值確定 |
改進
終局生成
??設置參數(shù)需要的棋盤數(shù)量為1,000,000，對該改進前代碼進行了10次性能分析，平均時間為138.251秒，最接近平均時間的一次為138.708秒。
??由性能分析可見，消耗最大的函數(shù)是Sudoku類的寫文件函數(shù)中的fputc函數(shù)，為了方便添加空格，我采用的是fputc函數(shù)逐個添加字符，且運行write函數(shù)后就關閉文件。這樣在1,000,000個終局生成中，會發(fā)生反復調用fputc函數(shù)和打開、關閉文件函數(shù)。因此我改動為在開始生成終局時打開文件，在寫入完成后關閉文件，將字符連接為字符串后，將一整個數(shù)獨終局以字符串寫入文件。且Point類的封裝性不強，我加強了Point類的封裝性（見類圖）。改進前在行交換時，回溯時需要置為交換前，浪費大量時間，我在行變換前，將數(shù)獨終局作為新變量保存以作為模板，方便進行二次行交換。
??改進后10次性能分析的平均時間為5.137秒，最接近平均時間的一次為5.368秒。
??由性能分析可見，改進后代碼平均時間減少為改進前的3.716%，大大縮短了生成時間。
數(shù)獨求解
??為了方便進行數(shù)獨求解，我添加了Pset類已保存空白點（見類圖），且封裝性良好。為了優(yōu)化性能，我采用了隨機的策略選取下一空白點的解，并記錄空白點處理的順序以方便回溯。這個算法的時間復雜度明顯優(yōu)于全圖遍歷。且為了減少數(shù)據(jù)的冗余，在讀入數(shù)獨時完成空白點集的添加。
代碼說明
元素交換函數(shù)
void Sudoku::permutate (int level) {
if (level == side - 2) { //全排列結束
mod (); //生成模板
generate (); //行交換
return;
}
for (int i = level; i < side; i++) {
if (i != level)
seed.swapi (level, i); //交換元素
permutate (level + 1); //遞歸
if (nsudoku == 0)
return;
if (i != level)
seed.swapi (level, i);
}
return;
}
行交換函數(shù)
void Sudoku::generate () { //生成終局
/*行變換*/
Sudoku ans;
for (int i = 0; i < 2 && nsudoku>0; i++) //第一階段
for (int j = 0; j < 6 && nsudoku>0; j++) //第二階段
for (int k = 0; k < 6 && nsudoku>0; k++) { //第三階段
ans.cpy(this);
switch (i) {
case 0:
break;
case 1:
ans.swapRow (1, 2); break;
}
switch (j) {
case 0:
break;
case 1:
ans.swapRow (4, 5); break;
case 2:
ans.swapRow (3, 4); break;
case 3:
ans.swapRow (3, 5); ans.swapRow (3, 4); break;
case 4:
ans.swapRow (3, 4); ans.swapRow (3, 5); break;
case 5:
ans.swapRow (3, 5); break;
}
switch (k) {
case 0:
break;
case 1:
ans.swapRow (7, 8); break;
case 2:
ans.swapRow (6, 7); break;
case 3:
ans.swapRow (6, 8); ans.swapRow (6, 7); break;
case 4:
ans.swapRow (6, 7); ans.swapRow (6, 8); break;
case 5:
ans.swapRow (6, 8); break;
}
ans.write (fpw);
nsudoku--; //生成數(shù)+1
if (nsudoku == 0) {
if (fpw != NULL)
fclose (fpw);
return;
}
if (fpw != NULL)
fprintf (fpw, "\n\n");
}
return;
}
解數(shù)獨函數(shù)
int Sudoku::dfs () {
int iz = pset.geti();
Point p (this->pset.getVal(iz));
/*初始化占有標識數(shù)組*/
for (int i = 0; i < 9; i++) {
if (val[p.getx ()][i] != 0 && p.getpos (val[p.getx ()][i]) == 0)
p.setpos (val[p.getx ()][i], 1);
if (val[i][p.gety ()] != 0 && p.getpos (val[p.getx ()][i]) == 0)
p.setpos (val[i][p.gety ()], 1);
}
for (int i = (p.getx () / 3) * 3; i < (p.getx () / 3) * 3 + 3; i++)
for (int j = (p.gety () / 3) * 3; j < (p.gety () / 3) * 3 + 3; j++)
if (val[i][j] != 0 && p.getpos (val[p.getx ()][i]) == 0)
p.setpos (val[i][j], 1);
/*尋找可行解*/
int found = 0;
for (int i = 1; i < 10; i++)
if (p.getpos(i) == 0) { //找到一可行解
found = 1;
val[p.getx ()][p.gety ()] = i;
p.setpos (i, 1);
pset.del (iz);
if (pset.isEmpty()) {
write (fpw);
return 1;
}
if (dfs ()) //找下一個空位的可行解
return 1;
p.setpos (i, 0);
}
return 0;
}
附加題
??附加題的解題關鍵有三，一是交互界面的設計，二是數(shù)獨題目的生成，三是解題結果的判定。
交互界面的設計
??我使用了C#開發(fā)Windows窗體應用（.Net Framework），窗體中包含9×9個TextBox以顯示數(shù)獨，以及四個Button分別用以開始新局、重新開始、提交答案以及重置題庫。數(shù)獨TextBox分別用兩種顯示風格以區(qū)分題目和解答（題目與解答不同風格的設計來源于網(wǎng)絡），在重置題庫題目完成后會有MessageBox提示以及判定題目時會以MessageBox告知答案的正確與否。交互界面美觀大方，簡約大氣。
??值得一提的是，設計TextBox的屬性使得數(shù)獨的交互方式可以是鼠標選擇或是Tab鍵選擇。
數(shù)獨題目的生成
??對于數(shù)獨題目的生成，共有兩種出題方法，分別為挖洞法和填數(shù)法。鑒于已經(jīng)完成的數(shù)獨生成器，我采用的是挖空法生成數(shù)獨題目。而我的第一方案是將數(shù)獨生成器為GUI提供接口Sudoku類及其成員函數(shù)，但由于C++與C#語法的不同，需要對其代碼進行大量修改，我放棄了這個方案。我采用的第二個方案是在GUI中創(chuàng)建Sudoku類及其終局生成函數(shù)和挖洞函數(shù)，并調用以創(chuàng)建數(shù)獨題目。終局生成函數(shù)與數(shù)度生成器中相同，而挖洞函數(shù)代碼如下：
public void puzzle() //生成謎題
{
int max = 60;
int min = 30;
int[] rand = new int[9];
Random rd = new Random();
for (int i = 0; i < 9; i++) //逐宮
{
int imax = max - (8 - i) * 2;
int imin = min - (8 - i) * 9;
if (imin < 2)
imin = 2;
if (imax > 9)
imax = 9;
rand[i] = rd.Next(imin, imax); //該宮內的數(shù)量
max -= rand[i];
min -= rand[i];
int[] arrNum = new int[rand[i]];
for (int ir = 0; ir < rand[i]; ir++)
{
Re:
int x = rd.Next(1, 9);
for (int ix = 0; ix < ir; ix++)
{
if (arrNum[ix] == x)
goto Re;
}
arrNum[ir] = x;
val[(i / 3) * 3 + (x - 1) / 3, (i % 3) * 3 + (x - 1) % 3] = 0;
}
}
}
??在這個函數(shù)中，我設計了隨機挖洞的算法。題目要求，挖洞數(shù)量要不少于30個，不大于60個，每個宮內的挖洞數(shù)量不小于2個。因此，每個宮內的隨機的挖洞數(shù)量為2～9個，但由于要使剩余的宮內洞數(shù)滿足要求，定義了imin和imax變量來保存當前宮可挖洞數(shù)的最小值和最大值。由此，可以得到當前宮挖洞數(shù)量的取值范圍，獲得rand[i]。接著隨機生成rand[i]個1～9之間不重復的隨機數(shù)，用以表示宮內位置。獲得了當前宮和宮內位置，即可生成滿足要求的數(shù)獨題目。
改進
??在黑盒測試過程中發(fā)現(xiàn)1,000,000個數(shù)獨題目用時時間長且沒有必要，我將題目數(shù)量改為100個，用時約為1秒，較為合適。且隨機挖洞函數(shù)勇士時間較長，我將挖洞函數(shù)的時機調整為一部分行交換之間，而不是每一個終局生成后，提高了題目生成的效率，但是卻增大了題目的相似性（題目之間行交換）。
解題結果的判定
??對于解題結果的判定，我的第一方案是使用數(shù)度生成器中檢驗數(shù)度正確性的函數(shù)。但是這是沒有必要的，因為其一隨機挖洞的題目，其解并非唯一，不能與解答后的終局進行對比，其二挖洞數(shù)較多，深度優(yōu)先搜索樹層數(shù)較大，回溯的步驟也增多，其三與題目生成原因相同，更改dll需要大量時間。我選擇的方案是直接判斷TextBox的值而不轉換為Sudoku類直接進行正確性判斷，至于要判斷每一行、每一列、每一宮元素填滿且無元素重復即可，因此，只需要9×9×9次循環(huán)即可。
private void button_submit_Click(object sender, EventArgs e)
{
if (begin == false)
{
MessageBox.Show("未開始游戲");
return;
}
int[,] map = new int[9, 9];
/*檢查是否完成*/
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
TextBox text_element = Game_table[i * 9 + j] as TextBox;
if (text_element.Text == "")
{
MessageBox.Show("未完成所有空白");
return;
}
else
map[i, j] = (text_element.Text.ToCharArray())[0] - '0';
}
}
/*沒有空白*/
int[] judge = new int[10];
for (int i = 0; i < 9; i++) //逐行
{
for (int j = 1; j <= 9; j++)
judge[i] = 0;
for (int j = 0; j < 9; j++)
{
int x = map[i, j];
judge[x] = 1;
}
for (int k = 1; k <= 9; k++)
{
if (judge[k] != 1)
{
MessageBox.Show("答案錯誤");
return;
}
}
}
for (int i = 0; i < 9; i++) //逐列
{
for (int j = 1; j <= 9; j++)
judge[i] = 0;
for (int j = 0; j < 9; j++)
{
int x = map[j, i];
judge[x] = 1;
}
for (int k = 1; k <= 9; k++)
{
if (judge[k] != 1)
{
MessageBox.Show("答案錯誤");
return;
}
}
}
for (int i = 0; i < 9; i += 3) //逐宮
for (int j = 0; j < 9; j += 3)
{
for (int k = 1; k <= 9; k++)
judge[k] = 0;
for (int a = 0; a < 3; a++)
for (int b = 0; b < 3; b++)
{
int x = map[i + a, j + b];
judge[x] = 1;
}
for (int k = 1; k <= 9; k++)
{
if (judge[k] != 1)
{
MessageBox.Show("答案錯誤");
return;
}
}
}
MessageBox.Show("回答正確");
}
??且為了保證其字符的有效性，我再設置TextBox的屬性時，使其KeyPress滿足CheckKey函數(shù)，代碼如下：
private void CheckKey(object sender, KeyPressEventArgs e)
{
if (begin == false)
return;
if (e.KeyChar != '\b' && (e.KeyChar < '1' || e.KeyChar > '9'))
e.Handled = true;
}
