Github 位址：https://github.com/JerryYouxin/sudoku
PSP表格
| PSP2.1 | Personal Software Process Stages | 預估耗時（分鐘） | 實際耗時（分鐘） |
|---|---|---|---|
| Planning | 計劃 | 30 | 10 |
| · Estimate | · 估計這個任務需要多少時間 | 1200 | 1600 |
| Development | 開發 | 800 | |
| · Analysis | · 需求分析 (包括學習新技術) | 40 | 20 |
| · Design Spec | · 生成設計文檔 | 60 | |
| · Design Review | · 設計複審 (和同僚稽核設計文檔) | ||
| · Coding Standard | · 代碼規範 (為目前的開發制定合适的規範) | ||
| · Design | · 具體設計 | 300 | 400 |
| · Coding | · 具體編碼 | 500 | |
| · Code Review | · 代碼複審 | ||
| · Test | · 測試（自我測試，修改代碼，送出修改） | ||
| Reporting | 報告 | 70 | |
| · Test Report | · 測試報告 | ||
| · Size Measurement | · 計算工作量 | 15 | |
| · Postmortem & Process Improvement Plan | · 事後總結, 并提出過程改進計劃 |
|合計 | 1200 | 1600
看教科書和其它資料中關于Information Hiding, Interface Design, Loose Coupling的章節，說明你們在結對程式設計中是如何利用這些方法對接口進行設計的
在實作中，我們通過接口設計，将不同子產品之間用同一個接口進行互動，使得接口的實作方法等與上層調用無關，上層調用并不用關心接口的具體實作而不影響使用。而資訊隐藏可以讓上層不用關心也不能介入底層的實作，使得程式間的獨立性有了保障。
在我的解題函數solve中，原來使用的方法是回溯法，後來改為DLX重新定義了一個DLX_Solver進行解題，而接口還是用solve進行互動，隻是裡面的實作改為了調用DLX_Solver進行解題。而這些實作上的改變并沒有影響上層GUI，這是有效的資訊隐藏(實作方法以及相關資料結構的隐藏)、接口設計的結果，讓我們的子產品間具有了松耦合性。
計算子產品接口的設計與實作過程
計算子產品接口如下(Core類中的成員函數)：
void generate(int number,int mode,int result[][81]);
void generate(int number,int lower,int upper,bool unique,int result[][81]);
void generate(int number,int result[][81]); // generate final states
bool solve(int puzzle[],int solution[]);
void solve(int number,int *puzzle,int *solution);
int read_sudoku(int **puzzle,const char* filename);
int write_sudoku(int number,int *puzzle,const char* filename);
bool check_valid(int *solution);
int check_valid(int number,int *solution);
bool check_same(int number,int *solution);
其中generate(int number, int result)用回溯法進行終局的搜尋(可以參考我的個人項目的部落格)。在實作生成隻有唯一解的數獨時，先用上述終局生成函數生成數獨終局，再進行挖空，每次挖空後用解數獨函數來求解數獨，該函數可以傳回數獨解的數量，由此可以判斷是否為唯一解。如果不是唯一解的數獨則回溯不挖空，并再檢視下一個空是否可以挖（這是一個遞歸）。代碼如下：
bool Core::__generate_unique(int num, int maxNum, int index, int result[]) {
if(index>=81||maxNum<=num) return maxNum<=num;
int x = result[index];
result[index] = 0;
if(isUniqueSolve(result)) {
return __generate_unique(num+1,maxNum,index+1,result);
}
else {
result[index] = x;
return __generate_unique(num,maxNum,index+1,result);
}
}
void Core::generate(int number,int lower,int upper,bool unique,int result[][81]) {
if(number<1||number>10000) throw NumException();
if(lower>upper||lower<0||upper>64) throw RangeException();
if(unique) {
generate(number,result);
#pragma omp parallel for
for(int n=0;n<number;++n) {
int num = lower;//rand()%(upper-lower+1)+lower;
__generate_unique(0,num,0,result[n]);
}
} else {
generate(number,result);
for(int n=0;n<number;++n) {
int num = rand()%(upper-lower+1)+lower;
for(int i=0;i<81;++i) {
if(81-i+1<=num) {
result[n][i] = 0;
--num;
}
else {
double r = rand()/(double)RAND_MAX;
if(r<0.5) {
result[n][i] = 0;
--num;
}
}
}
}
}
}
在檢查函數上，Core類提供了三個接口以供檢查數獨合法性等資訊：
// check functions
bool check_valid(int *solution);
int check_valid(int number,int *solution);
bool check_same(int number,int *solution);
其中check_valid為檢查輸入數獨是否為合法數獨，即每個數字都是0~9之間的整數且符合數獨的規則要求。如果是合法的bool check_valid(int)會傳回true，int check_valid(int,int)會傳回0，否則為非法數獨。其中bool類型的需要保證輸入的數獨是隻有一個的，且所有的函數輸入都至少配置設定好足夠的記憶體空間。
check_same函數是檢查數獨是否有重的，使用字元串表示+STL map實作，查重效率較高。這三個函數的代碼如下。
typedef std::map<std::string,int> hashMap;
// same is false
bool Core::check_same(int number,int *solution) {
if(solution==0||number<=0) return false;
hashMap hmap;
char ph[82];
for(int i=0;i<number;++i) {
int* ptr = solution+i*81;
memset(ph,0,82);
for(int j=0;j<81;++j) {
ph[j] = ptr[j]+'0';
}
ph[81] = '\0';
std::string x(ph);
// search if the number is already exist
hashMap::iterator it= hmap.find(x);
if(it == hmap.end()) {
hmap[x] = 1;
}
else {
return false;
}
}
return true;
}
// valid is true
bool Core::check_valid(int *solution) {
if(solution==0) return false;
bool empty_value[9][9][3]={ 0 }; // (value, r/c/b number, row/col/block)
for(int r=0;r<9;++r) {
for(int c=0;c<9;++c) {
int b = 3*(r/3)+(c/3);
int i = r*9+c;
int v = solution[i]-1;
if(solution[i]>9||solution[i]<0) return false;
if(solution[i]==0) continue;
if(empty_value[v][r][0]||empty_value[v][c][1]||empty_value[v][b][2]) {
return false;
}
empty_value[v][r][0] = true;
empty_value[v][c][1] = true;
empty_value[v][b][2] = true;
}
}
return true;
}
int Core::check_valid(int number,int *solution) {
if(solution==0) return -1;
for(int i=0;i<number;++i) {
if(!check_valid(solution+i*81)) {
return i+1;
}
}
return 0;
}
-m生成難度的是基于挖的空的數量和空間自由度兩個方面決定。
一般而言，肯定是挖空越多總體趨勢上難度越大。
難度等級的增加，空格數總體趨勢遞增，不同難度等級的題目空格數也一樣的情況。我們得出初步結論，簡單按照空格的數目多少來劃分數獨題目的難易程度是不全面的。同樣空格數的數獨題目，空格數分布位置的不同對難度等級也造成影響。
在這種思維下，我們提出自由度的概念：，數獨的難度等級與行、列、宮格内的空格數存在着聯系。提出以空格自由度衡量數獨的難度等級。數獨的空格自由度，指除掉空格本身，空格所在行、列、九宮内的空格數總和。
我們通過這兩個方面的思維，将空格從20到55分為3個區間，自由度從700到1300分為三個區間，難度的劃分是隻要一個條件達到了相應區間就可以認為達到了要求。
這樣我們可以在第一次個人項目的基礎上，随即進行挖空，直至滿足了條件。
可以參考
http://www.cnblogs.com/candyhuang/archive/2011/12/21/2153668.html
Solve函數跟個人項目相比，改為用DLX算法求解數獨。
UML圖
計算子產品接口部分的性能改進
原來的回溯算法性能很低，是以在求解上，由個人項目時的回溯法改為了快速求解精确覆寫問題的DLX算法。但是在實作後卻發現加速并不明顯，甚至還有些慢。在最耗時間的生成唯一解的情況下，用VS性能分析後得到如下圖：
[1]!(http://images2017.cnblogs.com/blog/1224149/201710/1224149-20171015145603137-289738865.png)
由于我截圖的時候代碼有些改動導緻函數名并不能正常顯示。圖中最耗時間的是DLXSolver中的solve函數，由于查找唯一解時挖空是遞歸搜尋，是以這是很正常的現象。但是注意到第二位的那個new函數，是配置設定空間的函數，這個耗時也很長，這是為什麼？看看代碼，發現在将數獨問題轉換為精準覆寫問題時會申請記憶體空間來建立雙向十字連結清單來存儲稀疏矩陣。由于原來的實作為一個節點一個節點進行記憶體配置設定，是以隻要改為剛開始統一配置設定好一批節點後，後面按需所配即可。改進後速度有了大大提高，如圖。
優缺點
通過合同設計（DbC），也稱為合同程式設計，按合同程式設計和按合同程式設計設計，是設計軟體的一種方法。它規定軟體設計人員應該為軟體元件定義正式，精确和可驗證的接口規範，這些規範擴充了具有前提條件，後置條件和不變量的抽象資料類型的普通定義。這些規範根據概念隐喻被稱為“合同” 具有商業合同的條件和義務。
這段翻譯自wiki。Design by Contract可以讓多人合作通過嚴格規定的接口規範來簡化多人合作時的溝通、合并成本，大大提高了合作效率。并且這樣也使得内部實作方法跟上層使用接口相獨立，使得軟體結構松耦合，使得擴充、修改更容易，維護更友善。
我們在進行結對程式設計時規定了Core和GUI子產品部分的接口規範，使得我們兩個開發的兩個子產品可以迅速對接，具有松耦合性。
計算子產品部分單元測試展示
單元測試思路為每個主要的函數都進行測試。I/O操作的單元測試，其中refRes是一個合法的數獨數組：
TEST_METHOD(TestRead)
{
Core core;
int refRes[]={
...
};
int* result;
core.read_sudoku(&result,"sudokuexp.txt");
for(int i=0;i<162;++i)
Assert::AreEqual(refRes[i],result[i]);
delete[] result;
}
TEST_METHOD(TestWrite)
{
Core core;
int refRes[]={
...
};
int* result;
core.write_sudoku(2,refRes,"sudoku.txt");
core.read_sudoku(&result,"sudoku.txt");
for(int i=0;i<162;++i)
Assert::AreEqual(refRes[i],result[i]);
delete[] result;
}
對于generate，對于每個不同大小的輸入、不同類型的接口進行測試，并在最後調用檢查函數check_valid和check_same來驗證正确性。
TEST_METHOD(TestGen...)
{
Core core;
const int N = ...; // MAXIMUM
//int result[N][81];
int* result = new int[N*81];
core.generate(N,(int(*)[81])result);
Assert::AreEqual(core.check_valid(N,(int*)result),0);
Assert::IsTrue(core.check_same(N,(int*)result));
delete[] result;
}
Solve函數同樣，讀入測試資料後調用solve接口進行解題，然後用check_valid進行正确性檢查。
TEST_METHOD(TestSolveExp)
{
Core core;
const int N = 2; // MAXIMUM
int* result = new int[N*81];
//int result[N][81];
int* puzzle;
core.read_sudoku(&puzzle,"sudokuexp.txt");
core.solve(N,puzzle,(int*)result);
Assert::AreEqual(core.check_valid(N,(int*)result),0);
Assert::IsTrue(core.check_same(N,(int*)result));
delete[] result;
delete[] puzzle;
}
單元測試結果如下：
計算子產品部分異常處理說明
計算子產品異常有四類：RangeException，NumException，ModeException，InvalidSudokuException。每個異常都在函數剛開始進行參數檢查時，如果參數異常則抛出相關異常。單元測試如下：
TEST_METHOD(TestInvalidSudokuException)
{
Core core;
const int N = 1; // MAXIMUM
int puzzle[] ={
9, 9, 8, 0, 6, 0, 1, 2, 4,
2, 3, 7, 4, 5, 1, 9, 6, 8,
1, 4, 6, 0, 2, 0, 3, 5, 7,
0, 1, 2, 0, 7, 0, 5, 9, 3,
0, 7, 3, 0, 1, 0, 4, 8, 2,
4, 8, 0, 0, 0, 5, 6, 0, 1,
7, 0, 4, 5, 9, 0, 8, 1, 6,
8, 1, 0, 7, 4, 6, 2, 0, 0,
3, 0, 5, 0, 8, 0, 7, 0, 9,
};
int result[81]={ 0 };
try {
Assert::IsFalse(core.check_valid(puzzle));
Assert::AreEqual(core.check_valid(1,puzzle),1);
core.solve(puzzle,(int*)result);
Assert::Fail();
}
catch(InvalidSudokuException e) {
}
}
TEST_METHOD(TestRangeException)
{
Core core;
const int N = 1000; // MAXIMUM
//int result[N][81];
int* result = new int[N*81];
try {
core.generate(N,-1,55,false,(int(*)[81])result);
Assert::Fail();
}
catch(RangeException e) {
}
delete[] result;
}
TEST_METHOD(TestNumException_R)
{
Core core;
const int N = 1000; // MAXIMUM
//int result[N][81];
int* result = new int[N*81];
try {
core.generate(-1,20,55,false,(int(*)[81])result);
Assert::Fail();
}
catch(NumException e) {
}
delete[] result;
}
TEST_METHOD(TestNumException_M)
{
Core core;
const int N = 1000; // MAXIMUM
//int result[N][81];
int* result = new int[N*81];
try {
core.generate(-1,1,(int(*)[81])result);
Assert::Fail();
}
catch(NumException e) {
}
delete[] result;
}
TEST_METHOD(TestModeException)
{
Core core;
const int N = 1000; // MAXIMUM
//int result[N][81];
int* result = new int[N*81];
try {
core.generate(N,0,(int(*)[81])result);
Assert::Fail();
}
catch(ModeException e) {
}
delete[] result;
}
結果如下：
界面子產品的詳細設計過程
首先是一個計時的工具，通過Qlabel來實作，在時間能夠走得情況下（通過全局變量changable來控制），将time_show增長，并且将其的分鐘數和秒數set到兩個label的txt上面，就是先了記時的功能。
void MainWindow::time_change()
{
if(time_changable==true)
{
time_show++;
int minute=time_show/60;
int second=time_show%60;
char str1[3];
char str2[3];
sprintf(str1,"%02d",minute);
sprintf(str2,"%02d",second);
minute_->setText(str1);
second_->setText(str2);
}
接下來是各個控制按鈕，它們的類型都是QPushButton，它們之間有一定的邏輯關系，比如在剛剛按下new_game按鈕的時候，除了restart和new_game之外的按鈕都是不能按下的，而一旦選擇了數獨中的按鈕，那麼根據選擇的是原先就有的，新填上的還是現在為止還沒有填上的，不同的按鈕會分别轉換為可選中和不可選中的狀态，以下面的代碼為例
void MainWindow::pause()
{
if(Pause->text().compare("Pause")==0)
{
time_changable=false;
for(int i=0;i<81;i++)
{
follow[i]->setEnabled(false);
}
for(int j=0;j<9;j++)
{
fillin[j]->setEnabled(false);
}
Remind_Me->setEnabled(false);
Check->setEnabled(false);
Wipe->setEnabled(false);
Pause->setText("Continue");
}
else
{
if(Pause->text().compare("Continue")==0)
{
time_changable=true;
for(int i=0;i<81;i++)
{
follow[i]->setEnabled(true);
}
Remind_Me->setEnabled(true);
Check->setEnabled(true);
Wipe->setEnabled(true);
Pause->setText("Pause");
}
}
for(int j=0;j<9;j++)
{
fillin[j]->setEnabled(false);
}
}
void MainWindow::wipe()
{
QString str1=last_button->objectName();
Wipe->setEnabled(false);
QString tmp;
for(int j = 0; j < str1.length(); j++)
{
if(str1[j] >= '0' && str1[j] <= '9')
tmp.append(str1[j]);
}
bool ok;
int index=tmp.toInt(&ok,10);
if((last_button->text().compare("")!=0)&&sudukuinto[index]==0)
{
follow[index]->setText("");
nowsuduku[index]=0;
}
for(int j=0;j<9;j++)
{
fillin[j]->setEnabled(false);
}
}
最後的成品大概是這樣的，可以計時、選擇難度、開新局，重新此局，删除填過的空。
界面子產品與計算子產品的對接
void Core::generate(int number,int mode,int result[][81]) {
if(number<1||number>10000) throw NumException();
if(mode!=1&&mode!=2&&mode!=3) throw ModeException();
int i = 0;
int free_degree = 0;
int sudoku_num = 0;
int num = 0;
int the_time = 0;
int hollow_num = 0;
for (sudoku_num = 0; sudoku_num < number; sudoku_num++)
{
generate(1,(int(*)[81])result[sudoku_num]);
free_degree = 0;
num = 0;
if (mode == 1)
{
hollow_num=rand() % 9 + 40;
if (the_time == 0)
{
for (int ii = 0;; ii = ii + 2)
{
上面這部分是實作難度生成的代碼，而這部分的代碼通過什麼樣的方式與UI的工程相聯系起來呢，主要是通過動态連結庫所生成的代碼庫，UI通過調用來實作的。在UI的顯示類中将core定義為其中的一個屬性，然後通過調用生成和求解的方法将相應的結果傳回到UI子產品的一個變量result中，再通過UI的settext将其顯示在圖形界面上。
具體代碼思想大概是這樣：
private:
QPushButton *follow[81];
QPushButton *fillin[10];
QPushButton *Remind_Me;
QPushButton *Restart;
QPushButton *New_Game;
QPushButton *Check;
QPushButton *Pause;
QPushButton *Wipe;
QComboBox *choose_;
QLabel *minute_;
QLabel *second_;
Core core;
core.generate(1,diff,result[i]);
QString mode=ui->centralWidget->findChild<QComboBox*>("choose")->currentText();
bool a=false;
switch( QMessageBox::question(this, "begin a new game?",
"you choose "+mode+" ,are you sure"),
QMessageBox::Ok | QMessageBox::Cancel,QMessageBox::Ok )
描述結對的過程
結對程式設計的優點和缺點
優點：
- 互相學習，互相提高
- 減少代碼出錯率
- 代碼可讀性會高
缺點：
- 如果兩個人合作不默契可能會大大降低效率