1. Github 位址
https://github.com/hanayashiki/Sudoku
2. PSP
| PSP2.1 | Personal Software Process Stages | 預估耗時 | 實際耗時 |
|---|---|---|---|
| Planning | 計劃 | 5min | |
| · Estimate | · 估計這個任務需要多少時間 | ||
| Development | 開發 | 22h | 42h |
| · Analysis | · 需求分析 (包括學習新技術) | 8h | 12h |
| · Design Spec | · 生成設計文檔 | 2h | 2h |
| · Design Review | · 設計複審 (和同僚稽核設計文檔) | 0h | |
| · Coding Standard | · 代碼規範 (為目前的開發制定合适的規範) | 0.5h | |
| · Design | · 具體設計 | 0.5h | 1h |
| · Coding | · 具體編碼 | 3h | 6h |
| · Code Review | · 代碼複審 | 6h | |
| · Test | · 測試（自我測試，修改代碼，送出修改） | 30h | |
| Reporting | 報告 | 3.5h | 3.5h |
| · Test Report | · 測試報告 | ||
| · Size Measurement | · 計算工作量 | ||
| · Postmortem & Process Improvement Plan | · 事後總結, 并提出過程改進計劃 | 1h | 15min |
| 合計 | 25.5h |
3. 解題思路：
1. 解數獨（舊思路）
首先查閱資料，得知：
數獨問題可以轉化為圖着色問題：把每個空格當做一個個的結點P(i,j)，則每個宮、每個行、每個列的結點都内部互相連接配接在一起，相鄰的結點不可以是同樣的顔色。然而，圖着色問題是一個NPC問題，也就是說對于數獨來講，我們不一定能找到時間複雜度很低的算法。（輸入的量是不變的，為81個0-9的數，然而由于圖着色問題時間複雜度會很大，數獨問題的複雜度也可能很大）。[1][2]
是以放棄了尋找動态規劃等多項式時間複雜度算法的努力。
但是我們可以用比較暴力但是盡量減少無用嘗試的算法盡快得出數獨的一個解，下面給出僞代碼：
class point:
int number
int candidates = []
int x, y
point mat[9][9] = input(some_file) // or failure, stop.
// Initialize a point map
def get_candidates(point p):
清空p的candidates
若number是0，周遊p所在列的每一行、每一列和每一個宮
傳回p的candidates數量
若number不是0，傳回0。
def get_min_point():
周遊mat分别運作 get_candidates ，找到傳回值最小的一個point（減少分支）
傳回這個point
def solve():
point p
stack changes // Records augments of trials
stack rollback // Records used augments of trials, for recovery from failures
p = get_min_point()
do:
将所有p的candidates的 push 到 changes 中
change = changes.pop()
rollback.push(change)
将 change 寫入 mat 中
p = get_min_point()
change.set_trials(len(p.candidates))
if p == 0:
rollback.top.decre_trials()
根據rollback彈棧并復原，對目前rollback棧頂進行decre_trials()，直到目前rollback.top.trials不是0
while not changes.is_empty() 難點在于維護嘗試，我們需要進行一個嘗試，即進行它的子嘗試，然後當所有子嘗試都走不通時，復原。概念上，我們需要維護一棵樹來記錄決策，然而如果我們有順序的進行嘗試，即符合先序周遊的規則，那麼可以用棧來實作，這樣避免了建立樹的動态配置設定等問題，提高了逼格和效率。
2.解數獨（新思路）
花了一天的時間熟悉VS和c++後，我用樸素的思維寫了一些輪子，把程式封裝起來。比如說Matrix類用來記錄點的填值和候選值，Change類用來記錄工作樹，等等。終于把算法實作好了的時候，發現舊思路處理一些數獨題目奇慢無比，比如說：
4 7 0 9 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 8 0 1
0 0 6 0 0 0 0 0 0
8 0 1 0 0 2 5 0 0
0 0 0 7 0 0 0 4 0
0 0 0 0 5 1 0 0 0
6 0 0 0 0 0 0 7 0
0 0 0 0 0 8 0 0 0
由于分叉較多，程式漫無目的地擴充工作樹，導緻空間複雜度和時間複雜度都超過預期，解該題需要約0.5s，不能滿足60s解1000道題的需求。
最後一天交作業，聽ACM大佬和助教提到了DLX算法[3]，就上網查找并且學習了DLX算法，然後親自進行了實作，發現效果很好。DLX算法處理數獨問題的思路如下：
1. 對于一個01矩陣，DLX可以在近似線性時間範圍内求出一組行，使得這些行(a_i,j, a_i,j+1,...a_i,n)滿足它們的和是(1,...,1)，如果存在。
2. 對于數獨，我們要求每一行、每一列、每一宮都有1...9這9個數字，對于數獨的一次填寫，我們可以這樣表示它的性質：
feature = (fill, row, column, group)，
fill是81維的01向量，表示填寫的位置編号；row是9*9維向量，它每9位表示一行中已經填入的數；column和group也類似row。
通過合适的辦法具體表示feature, 則數獨正确填寫完成等價于所有填寫feature的向量和為(1,....,1)。
DLX算法：
是一種回溯的算法，但是可以排除掉較少不成功的嘗試，是以比暴力回溯數獨矩陣要快很多。
步驟：
對于矩陣A，有行r1, r2...r_n。假設所求向量集合叫S
1. 選擇一個非零的行向量r，假定它屬于S。
2. r有一些分量為1，删去其它包含同維非零分量的行向量。删去這些分量所在的列向量。得到新的矩陣A'。
3. 假如A`為空，那麼算法結束，把所有選擇過的r加入S。如果A'有零列向量，回溯并在上一步選擇其它的嘗試，同時這表明r不正确，它将不再被嘗試。否則，把A'當做A，回到1。
利用雙向連結清單，可以在較低的空間複雜度下實作DLX算法。
3. 生成終局：
雖然回溯算法很慢，但是我們可以讓它在填滿以後不結束自己，而是進行回溯，這樣隻要有足夠的空間就可以生成1000,000甚至所有的數獨終局。
4. 設計實作過程
1. 解數獨：
類：DLX類，用于存一些執行DLX算法的函數和資料結構。struct Node用于存儲結點，包括它的right, left, up, down四個雙向連結清單指針。
函數：DLX的核心算法在于遞歸嘗試算法search以及子過程recover和cover，cover用來實作算法的步驟2，recover用于回溯上一步。
2. 生成數獨：
繼承了舊思路，主要用到Matrix類來管理數獨矩陣，用Change來記錄工作樹，用修改過的solve來實作填滿回溯。
5. 改進思路：
主要難題在解數獨不逾時的問題上，實際上經曆了五步：
1. 使用棧來存儲工作步驟（由于沒想清楚，失敗了）
2. 改用樹存儲工作步驟（第一個能work的版本）
3. 改用位運算來節約計算時間（節約了2/3的時間，但仍然很慢）
4. 嘗試剪枝的算法，但發現剪枝本身也很耗費時間，得不償失。
5. 徹底重構，采用數獨轉換的DLX算法，快得飛起。
生成數獨終局的時間分析：
一半是IO，1/4用來回溯(create，修改自舊思路解數獨的solve)，1/4運作剪枝算法(corner)。
解數獨的時間分析：
主要還是DLX算法比較耗費時間，其中一半時間用來把數獨轉化為矩陣這一中間過程。
6. 關鍵代碼：
1. 生成數獨：
void create(int gene_count) {
matrix.fill_in_figure(1, 1, (7 + 7) % 9 + 1);
int level = 0;
int x, y, count;
bool first = true;
char candi_buf[10] = "";
//
//cout << x << ", " << y << ", " << count << endl;
//1. build up root
//2. get a min point, if failed, rollback root's change,
// try root.next (if null, rollback) or root.base (not null, otherwise quit)
//3. build possible changes, linking them to the root, mark root as expanded
//4. set now to be root's fchild
//5. implement change
//6. go to 2
//
Change* now = root;
while (true) {
Point* p = matrix.get_min_point_fast();
Change* cut_trial = NULL;
if ((p && (p->get_candi_count() > 1))) {
cut_trial = corner();
}
if (cut_trial) {
//cout << "----------used cut-----------" << endl;
cut_trial->set_base(now);
cut_trial->set_next(NULL);
now->set_fchild(cut_trial);
//matrix.display();
//cout << "------" << endl;
matrix.fill_in(cut_trial);
now = cut_trial;
//matrix.display();
// back to while head
}
else {
//Point* p = matrix.get_min_point_fast();
if (p) {
Change* new_change = NULL;
Change* last_change = NULL;
p->show_candidates(candi_buf);
//cout << candi_buf << " => ";
//shuffle(candi_buf);
//cout << candi_buf << endl;
if (DEBUG2) cout << "candi_buf:" << candi_buf;
int x, y;
p->get_pos(&x, &y);
for (int i = 0; candi_buf[i] != 0; i++) {
new_change = new Change(x, y, candi_buf[i] - '0');
new_change->set_next(last_change);
new_change->set_base(now);
last_change = new_change;
}
now->set_fchild(new_change);
if (now == NULL) {
matrix.display();
exit(1);
}
now = now->get_fchild();
matrix.fill_in(now);
if (DEBUG2) now->display("fill in:");
if (DEBUG2) matrix.display();
if (matrix.get_zeroes() == 0) {
matrix.dump(output);
fprintf(output, "\n");
if (--gene_count == 0) {
return;
}
}
}
else {
//...todo: rollback｝
//now->display("roll back:");
matrix.roll_back(now);
if (now->get_next() != NULL) {
now = now->get_next();
}
else {
while (now->get_base()) {
//now->get_base()->display("roll back:");
Change* base = now->get_base();
matrix.roll_back(now->get_base());
if (now->get_base()->get_next() != NULL) {
now = now->get_base()->get_next();
// base->clean_desc(base);
// delete base;
break;
}
now = now->get_base();
}
}
matrix.fill_in(now);
//now->display("fill in:");
}
}
}
} 2. 解數獨：
bool DLX::search(int k)
{
///cout << "search: " << k << endl;
if (head->right == head) {
return true;
}
int min_size = INT_MAX;
Node *c = head->right;
Node *c_root = c;
while (c != head) {
//find the row of smallest size
if (c->size < min_size) {
min_size = c->size;
c_root = c;
if (min_size == 1) {
break;
}
if (min_size == 0) {
return false;
}
}
c = c->right;
}
cover(c_root); //close the colomn and relevant rows
Node *current_row, *current;
for (current_row = c_root->down; current_row != c_root;
current_row = current_row->down) // try adding each row
{
result.push_back(current_row->row_root->num); // try regarding it as an answer
//cout << "result_push: " << current_row->row_root->num << "; " << endl;
for (current = current_row->right; current != current_row;
current = current->right)
{
//cout << "second cover" << endl;
cover(current->col_root);
}
if (search(k + 1)) {
return true;
}
for (current = current_row->left; current != current_row;
current = current->left)
{
//cout << "second recover" << endl;
recover(current->col_root);
}
result.pop_back();
}
recover(c_root);
return false;
}
參考資料：
[1] https://baike.baidu.com/item/%E5%9B%BE%E7%9D%80%E8%89%B2%E9%97%AE%E9%A2%98/8928655?fr=aladdin
[2] http://www.cnblogs.com/grenet/archive/2013/06/19/3138654.html
[3] http://www.jianshu.com/p/93b52c37cc65