零.github位址

GitHub位址：https://github.com/Liu-SD/SudoCmd （這個位址是指令行模式數獨的倉庫，包含了用作測試的BIN。DLL核心計算子產品位址是：https://github.com/Liu-SD/SudoCore ，UI界面項目位址是：https://github.com/Liu-SD/SudoUi 。）

一.PSP表格

PSP2.1	Personal Software Process Stages	預估耗時（分鐘）
Planning	計劃
· Estimate	· 估計這個任務需要多少時間	10
Development	開發
· Analysis	· 需求分析 (包括學習新技術)	100
· Design Spec	· 生成設計文檔
· Design Review	· 設計複審 (和同僚稽核設計文檔)
· Coding Standard	· 代碼規範 (為目前的開發制定合适的規範)
· Design	· 具體設計	30
· Coding	· 具體編碼	600
· Code Review	· 代碼複審
· Test	· 測試（自我測試，修改代碼，送出修改）	300
Reporting	報告
· Test Report	· 測試報告
· Size Measurement	· 計算工作量
· Postmortem & Process Improvement Plan	· 事後總結, 并提出過程改進計劃
合計	1980

二.說明你們在結對程式設計中是如何利用“Information Hiding, Interface Design, Loose Coupling”這些方法對接口進行設計的

一開始把指令行參數的處理過程和根據參數執行具體的功能耦合在一起，但是這一次需要實作的功能增加了，而且需要處理的參數的異常和錯誤情況也增加了很多，是以經過思考和讨論後，決定單獨寫一個子產品，輸入是指令行參數，把指令行參數中所包含的指令資訊儲存在自己預先設計好的結構體中，并處理可能出現的異常和錯誤情況。

typedef struct request
{
    //最後生成的數量
    int number;        
    //數獨問題的檔案路徑
    std::string *filepath;
    //存是哪種模式
    int mode;
    //對于挖空的情況，最大空的數量
    int upper;
    //最小
    int lower;
    //是不是要求唯一解
    bool unique;
    //是哪種類型（這裡預設有四種類型：1.生成終局-c 2.解決數獨 -s 3.生成不同模式 -m -n 4.生成不同挖空數 -r -n （-u））
    requests req;
} request;

（儲存資訊的結構體的定義）

之後根據結構體中的儲存好的資訊執行對應的接口。

request *req = new request();
    memset(req,0,sizeof(request));
    try {
        paraHandle(argc, args, req);
    }
    catch (format_err &e)
    {
        e.what();
    }
    catch(combination_conflict &e)
    {
        e.what();
    }
    catch (too_few_para &e)
    {
        e.what();
    }
    switch (req->req)
    {
    case End:
        //調用産生數獨終局的函數
        break;
    case Solve:
        //調用解決數獨的函數
        break;
    case Mode:
        //調用根據遊戲模式産生數獨遊戲的函數
        break;
    case Empty:
        //調用根據挖空數産生數獨遊戲的函數
        break;
    default:
        break;
    }
    return 0;

這樣，就把指令行參數的處理過程和具體功能的實作過程耦合性解開了。通過一個中間結構體request來實作從不同的指令行參數到不同的功能實作的資訊傳遞過程。我覺得設計很像在《Head First 設計模式》中所看到的指令模式，但感覺其實比書上的指令模式的實作還少了很多，例如這裡在實作時并沒有把不同的功能放在一個基類下面。

這裡我又想到了OO課之前所做的計程車排程以及電梯排程，當時也是通過設計require類，來實作控制台輸入--->資訊儲存在一個require對象裡--->根據這個require對象來實作電梯排程或者計程車排程。這裡通過設計這個request結構體，實作控制台輸入--->資訊儲存在request結構體裡--->根據這個結構體來實作具體的功能。

是以這個設計把指令的發出者（控制台）和指令的執行者（具體功能實作）解耦了。

三.關鍵函數的流程圖和算法解釋

0.這裡我沒有設計很多類，很多函數方法并沒有封裝到類中，是以這裡簡要說明一下重要的函數之間的關系吧：

1.指令行處理參數的邏輯解釋：

上面已經解釋了資訊的儲存，指令行參數的處理子產品除了需要儲存好相應指令的資訊外，還需要處理可能發生的各種異常錯誤。

我覺得這裡可能産錯誤可以分為①功能性參數（-c -m -n等）的組合錯誤②内容型參數（-n後面的數字，-m後面的123等）的内容錯誤

對于①，采用的檢查錯誤的辦法是，每個功能性參數對應一個flag，

1.可以檢測是否重複輸入了這個功能性參數，具體辦法就是在檢測到是這個參數比如-c後，在設定c_flag之前，檢查一下c_flag是不是已經被設定了

2.可以檢測是否組合錯誤，具體辦法是：目前僅有四種功能性組合①-c代表的産生終局②-s代表的解決③-m和-n代表的産生不同模式的遊戲④-r-n（和-u）代表的

不同挖空數遊戲，那麼我在周遊完所有指令行參數後，檢測這四種組合是否出現，如果都沒出現，那麼說明這個組合有問題，具體實作下面詳細說。

對于②，就是定義各種具體的異常，比如字元串中含數字，數字範圍不符合要求等等，一旦檢測到了，那麼抛出異常就好

上面的邏輯圖保證了大部分的錯誤都可以被檢測出來，根據之前分好的錯誤類型，目前還有一類錯誤沒有檢測，就是參數的組合還需要檢測是不是有問題。

參數的組合錯誤中，重複性在之前的邏輯也能被檢測出來，這裡簡要說一下如何保證參數的組合沒問題：

bool c_flag = false;
bool s_flag = false;
bool n_flag = false;
bool m_flag = false;
bool r_flag = false;
bool u_flag = false;

一開始有6個标志位，都先設定為false，每次檢測到一個參數的輸入，就把對應的标志位設定為true

是以這樣在一開始周遊參數清單時就可以檢測重複性：如果在設定一個參數比如-c的标志位發現已經為true了，那麼就意味着這個參數-c重複出現了，這時就會抛出異常，輸出錯誤資訊，并結束程式。

是以如果能運作到周遊結束，就說明：之前的每個參數都隻出現了一次。此時如何用這些标志位檢測參數的組合是否有問題呢？這裡我又想起計組裡的一個小思想，計組裡控制器首先需要确定一條32位指令是哪個指令，怎麼确定？通過指令的“标志位”即前6位和後6位或者其他的标志位來唯一确定它。即每條不同的計組指令和它的這些标志位的編碼是一一對應的。而這裡我可以确定四種正确的組合情況：

①僅有-c

②僅有-s

③有-m和-n

④有-r和-n，可能還有-u

上面這四種情況是互相獨立的事件，是以我們可以将它們分别用上面說的6個标志位表示好：

bool c_func = c_flag && !(s_flag || m_flag || r_flag || u_flag || n_flag);
bool s_func = s_flag && !(c_flag || m_flag || r_flag || u_flag || n_flag);
bool m_func = m_flag&&n_flag && !(c_flag || s_flag || r_flag || u_flag);
bool r_func = r_flag&&n_flag && !(c_flag || s_flag || m_flag);

最後這四個标志位因為四個事件是互相獨立的，是以最多僅可能有一個是真的，但是如果最後這四個沒有一個是真的，那麼就意味着出現了這四個組合以外的其他的參數組合，此時報錯就好。而且這樣也不需要考慮參數之間的順序。

是以以上就是我的整個指令行參數處理子產品的邏輯描述。

2.根據輸入的挖空數來産生數獨遊戲的generate邏輯

void generate(int number, int lower, int upper, bool unique, int[][] result)

這裡挖空其實很簡單，每行适當的挖幾個空就好，但是如果還要求唯一解，那就需要思考如何挖空才能哇足夠多的空還能保證唯一解。

關于挖空算法我也查了很多資料，但是僅僅隻能找到“一邊挖，一邊判斷是否唯一解”的随機性的算法。是以之後也是用這樣的随機挖空然後判斷的算法。

一開始我犯了錯誤，我總是在全部挖完後才判斷是否滿足唯一解，如果不滿足，我又重新挖完然後重新判斷。然而這樣挖完空才判斷會導緻往往挖完的數獨無法滿足唯一解，而且很浪費時間，導緻我的算法一開始的時候速度及其的慢！而且對于很多的數獨終局，往往無論怎麼挖都得不到唯一解的遊戲。

之後我改正了這個錯誤，改為每一行每一行挖空，起初我還在想是不是要一個空一個空挖，挖完判斷，但是這樣做不但不好控制空的“均勻分布”，而且判斷次數過多還可能導緻時間過長。是以我還是選擇了每行選擇幾個空挖，挖完判斷，如果目前仍然滿足唯一解就繼續挖下一行，如果不滿足那麼重新挖這一行。

但是這樣做又出現了新問題，就是發現很多時候對于很多數獨終局，你在确定上面幾行的挖空情況後，對于将要挖的這一行無論怎麼挖可能都無法滿足唯一解了，或者說很難滿足唯一解。導緻了死循環或者說挖空循環次數太多的問題。

然後我就加入了“棧”，用來儲存之前幾行的挖空情況，包括挖了幾個空和挖了哪些空，如果發現這一行在重新挖空超過一定數量後仍然無法滿足唯一解，那麼可能我們需要重新随機挖上一行才能更快的解決問題。是以我加入了一個記錄變量，記錄目前這一行重新挖空的次數，如果超過了給定次數，就重新挖上一行的空，這樣通過不斷的随機挖空調整，每個數獨終局總能“挖”出唯一解的遊戲。

但是在測試挖空數為55，即最大挖空數時，發現還是會有挖空一直挖不出唯一解的情況，一直在循環。而且我還發現，對于一些數獨終局，很輕易的就能把唯一解的數獨給挖出來，而對于一些數獨終局，往往需要循環挖空很多次才能挖出一個唯一解的數獨，甚至等了很長時間也沒有結果。是以我又采取了一個措施：我設定了另一個記錄變量，這個記錄變量記錄了在挖空過程中每一行挖空次數超過最大次數失敗然後回溯的次數，如果發現這個次數大于了自己設定的最大值，那麼說明這個數獨很難生成唯一解終局，直接放棄這個終局，接受下一個終局挖。

在經曆了上面的一系列改進後，終于我的算法可以以還不錯的速度随機生成唯一解的數獨初局。但是我覺得還有改進的地方，注意到我之前設定了兩個記錄變量，第一個記錄變量不如就記為trycount，記錄了目前這一行挖空失敗的次數，如果trycount大于了設定值k_maxtry，那麼就會恢複上一行重新挖上一行，另一個記錄變量記為backcount，每一次恢複上一行，這個變量就加1，然後當backcount大于設定值k_maxback後，這個數獨終局停止挖空，放棄，選擇下一個數獨終局來進行挖空。是以說上面所說的k_maxtry決定了你會給某一行多少次挖空機會，而k_maxback決定了你給這個數獨幾次回溯重挖的機會。這兩者共同決定了你在這個數獨終局上願意花多長時間嘗試挖出一個唯一解的空。如果這兩個數字設定過大，那麼你可能會在一些很難挖出唯一解的終局上浪費時間，如果設定過小，那麼你可能會錯過一些再試一試就可以挖出唯一解的終局。

是以這兩個數字的調整是很重要的，下面性能改進上詳細說明。

四.UML圖：

我們這次的設計感覺還是沒有過多涉及繼承多态什麼的，是以UML圖沒有繼承關系，是以這裡簡單畫一下本次實作的uml圖：

五.計算子產品接口部分的性能改進

之前對于dlx的性能提升已經做了很多工作了，是以這裡沒有在這個上面花太多時間。

之前說過k_maxtry和k_maxback決定了你會在每個數獨終局上嘗試挖空的次數，如果這兩個數字設定的過大，那麼可能會在一些很難挖出唯一解的數獨上浪費時間，如果這兩個數字設定過小，那麼可能會造成生成數獨的次數過多。是以我嘗試了很多組參數來測試其生成1000個唯一解挖空數為55的數獨需要多長時間。下面是一些資料：

k_maxtry

k_maxback

耗時

1:32

1:19

1:13

1:17

1:16

1:24

1:22

1:14

1:09

1:18

從測試的結果看，(k_maxtry=7,k_maxback=3)組合的耗時最小，原來的組合是(5,5)是以性能提升了一點，但是并不多。

六.契約式程式設計的優缺點

在看了Design by Contract的相關資料後，我覺得這個“契約式程式設計”就和之前OO課上所講的“規格”有很大的關系。

在OO課上一開始我是很反感寫那麼多規格的，但是随着學習的深入，我愈發覺得提前寫好這些規格無論是對整體設計還是程式的完備性都是有很大的改善和幫助的。契約式程式設計講究“前置條件”，“後置條件”和“不變性”。對于每個方法，我們先檢驗輸入是否符合我們提前定義好的“前置條件”，然後保證這個方法對于符合前置條件的輸入可以做到我們之前定義好的結果，那麼這種規定可以有效的保證程式設計的規範性和正确性。

對于結對程式設計來講，這個規範是特别有用的。因為在結對程式設計時，兩人合作經常會出現一方需要調用另一方的方法，但是因為這個方法不是自己親手寫的，調用方不知道調用後會不會傳回正确的結果，而被調用方又會擔心調用方傳入的參數可能不合法然後導緻崩潰，是以這時就需要一種“契約”來提前規定好每一個方法的合法輸入和具體效果，這樣不僅雙方在調用時可以放心的使用對方的方法，而且提前規定好輸入和方法效果有利于更好的設計。

是以總的來說我覺得優點有：

1.提高合作變成的效率

2.提高代碼的準确性

我覺得缺點可能就是需要提前規定好規則，可能需要花費很多時間。而且因為目前程式設計經驗的不足，可能提前做好的設計在實際程式設計時又需要改動，造成很多時間浪費。

但是我覺得在大量程式設計經驗和時間允許的條件下，“契約式程式設計”對提高程式設計效率和程式設計的準确性來說是特别有幫助的。

七.單元測試代碼及覆寫率展示：

可以看到測試程式的覆寫率都達到了90%以上。

測試資料思路：

這裡主要說一下我所測試的子產品：

void generate(int number, int lower, int upper, bool unique, int[][] result)

這個子產品輸入參數是：number，lower，upper，unique，需要往result數組中寫入結果，據此我構造了如下的測試代碼：

int uppers[10] = { 20,55,55,55,55,55,20,20,46,50 };
    int lowers[10] = { 20,55,20,20,46,46,20,20,40,40 };
　　這裡根據upper和lower的不同取值選擇了10組upper和lower
    for (int j = 0; j<10; j++) {
        bool unique = true;
        int upper = uppers[j];
        int lower = lowers[j];
        int number = 1000
        //這裡可以把數字調小點，如果時間慢的話
        int **result = new int*[number] {0};
        for (int i = 0; i < number; i++)
        {
            result[i] = new int[81]{ 0 };
        }
        
        generate(number, lower, upper, unique, result);
        for (int i = 0; i < number; i++) {
            int rstr[81][3] = { 0 };
            int rstr_p = 0;
            for (int j = 0; j < 81; j++) {
                if (result[i][j])
                {
                    rstr[rstr_p][0] = result[i][j];
                    //bug 2 下标都寫錯為了0
                    rstr[rstr_p][1] = j / 9 + 1;
                    rstr[rstr_p][2] = j % 9 + 1;
                    ++rstr_p;
                }
            }
　　　　　　這裡需要測試兩項：
            DLX.addRestrict(rstr_p, rstr);
            //1.挖空數量是否足夠
            assert(rstr_p >= (81 - upper) && rstr_p <= (81 - lower));
            //2.是否滿足唯一解要求
            if (!unique)
            {
                assert(DLX.find(1, false, NULL));
            }
            else {
                assert(!DLX.find(2, false, NULL));
            }
            DLX.clearRestrict();
        }
    }

根據upper和lower的不同情況選擇了10組資料，覆寫了最大挖空數，最小挖空數，正常範圍，最大範圍和最小範圍一緻等10種情況，unique也測試了要求唯一解和不要求唯一解兩種情況。

最後生成的數獨每一個都先檢查挖空數是不是在範圍内，然後檢查是不是滿足之前規定的唯一解條件。

八.計算子產品部分異常處理說明

在這次異常進行中，除了極少部分的異常，其他的異常我都專門寫在了指令行參數的處理子產品中，下面我詳細的分析一下異常部分的處理。

這次的外部輸入，可能就是指令行參數的輸入了，而我們這次根據指令行要實作的具體功能就是四個：

-c 生成數獨終局
-s生解決數獨檔案中的數獨遊戲
-m和-n根據難易程度生成數獨遊戲
-r和-n(-u)根據挖空數生成數獨遊戲

同時根據我之前所定義的錯誤的兩種分類①功能性參數（-c -m -n等）的組合錯誤②内容型參數（-n後面的數字，-m後面的123等）的内容錯誤，我們可以從這兩個角度很容易的總結出所有可能的異常，思路如下：

1.如果參數的數量不符合規定，那麼會報出參數太少的錯誤。

2.參數的格式需要符合要求，即除了-u以外，其他的在功能性參數後必須要有内容型參數，如果不符合要求，那麼抛出參數格式不對的錯誤

3.參數格式都對了以後，就看參數的内容是不是有問題，這裡就要一個功能一個功能分析：

對于-c，我們規定它後面的數字字元串轉化為數字後必須要在1~100*10000，是以我們需要檢驗這個數字字元串是不是符合要求，注意這裡不僅要保證數字範圍不能過大，尤其需要注意的是需要保證這個數字範圍不能超過int，這個在OO中已經很熟練了。是以這裡可能抛出數字超出範圍的錯誤
對于-s，我們規定後面的字元串必須要是有效的檔案名，即檔案必須存在。這個我并沒有在指令行參數的處理子產品中規定，因為結對夥伴已經告訴我他在solve接口中判斷了，是以這裡沒有檢查檔案名是否存在
對于-r，我們規定後面必須是“x~y”的格式，是以不符合這個格式的會抛出參數格式不對的錯誤，而對于x和y不僅需要判斷是不是有數字範圍超出的錯誤，還要保證lower必須要小于等于upper，如果不滿足需要抛出lower大于upper的錯誤
對于-n，我們需要規定判斷後面的數字字元串是不是滿足1~10000的範圍限制，具體的錯誤定義和之前的-c一緻
對于-m，我們同樣需要規定後面的數字字元串是不是滿足在1~3的範圍内
對于-u，其實查不出什麼錯

4.功能性參數都檢測好後，接下來需要做的就是檢查參數的組合問題，組合不正确需要抛出參數組合錯誤。

綜上，我們可以定義出5種錯誤：

1.參數太少

指令行輸入: sudoku.exe -c
 try{
    paraHandle(argc,argv,req);
}catch(too_few_para &e){e.what();}
會捕獲到對應的異常

2.參數格式不對

指令行輸入: sudoku.exe aaa
 try{
    paraHandle(argc,argv,req);
}catch(format_err &e){e.what();}

3.數字超出範圍

指令行輸入: sudoku.exe -c 100000000000000
 try{
    paraHandle(argc,argv,req);
}catch(out_of_range &e){e.what();}

4.lower大于upper

指令行輸入: sudoku.exe -r 55~54 -n 100
 try{
    paraHandle(argc,argv,req);
}catch(lower_biggerthan_upper &e){e.what();}

5.參數組合錯誤

指令行輸入: sudoku.exe -c 100 -s puzzle.txt
 try{
    paraHandle(argc,argv,req);
}catch(combination_err &e){e.what();}

九.界面子產品的詳細設計過程

界面子產品的重點在于數獨棋盤的設計。我們設計的棋盤由81個pushButton組成。每個按鈕使用styleSheet做不同的變形。在相應函數中，使用正則比對和修改styleSheet進而實作按鈕式樣的動态變化。這裡貼幾個按鈕的stylesheet：

border-style:solid;
border-color:black;
border-width:1px;
border-top-width:2px;
border-top-left-radius:10px;
border-left-width:2px;

下面是一個動态修改stylesheet的代碼示例：

const std::regex bg("(background-color:).+?;\\n");
QPushButton *pb = board_[i];

std::string styleSheet = pb->styleSheet().toStdString();
styleSheet = std::regex_replace(styleSheet, bg, "$1" + none_rstrColor+ ";\n");
pb->setStyleSheet(styleSheet.c_str());

十.界面子產品與計算子產品的對接

将計算子產品封裝到DLL中，然後在界面子產品動态調用DLL。以下是調用DLL中函數的過程：

typedef void(*GENERATE_M) (int, int, int**);
typedef void(*GENERATE_R) (int, int, int, bool, int**);
typedef bool(*SOLVE_S) (int *, int *);

HMODULE coreDLL;
GENERATE_M generate_m = NULL;
GENERATE_R generate_r = NULL;
SOLVE_S solve_s = NULL;

coreDLL = LoadLibrary(TEXT("Core/SoduCore.dll"));
generate_m = (GENERATE_M)GetProcAddress(coreDLL, "generate_m");
generate_r = (GENERATE_R)GetProcAddress(coreDLL, "generate_r");
solve_s = (SOLVE_S)GetProcAddress(coreDLL, "solve_s");

FreeLibrary(CoreDLL);

在響應函數中使用三個接口函數實作功能。

void MainWindow::initBoard(int mode, bool unique){
    ...
    if(unique){
        int difficultyDivide[4] = {20, 32, 44, 56};
        generate_r(1, difficultyDivide[mode - 1], difficultyDivide[mode] - 1, true, &originBoard);
    }
    else{
        generate_m(1, mode, &originBoard);
    }
    ...
}
void MainWindow::newGame(){
    ...
    if(currentindex<3){
        int difficultyDivide[4] = {20, 32, 44, 56};
        generate_r(1, difficultyDivide[currentindex ], difficultyDivide[currentindex+1] - 1, true, &originBoard);
    }
    else{
        generate_m(1, (currentindex%3)+1, &originBoard);
    }
    ...
}

十一.描述結對的過程

話不多說，直接發我們讨論的照片。

十二.結對程式設計的優缺點和結對夥伴的評價

優點：

大大提高效率。結對程式設計看似是兩人寫一段程式，但其實寫程式的速度大大提高，因為思路斷了後可以有人幫助提醒
提高代碼的準确率，因為結對程式設計兩個人都在思考，是以可以很快的發現錯誤并改正
兩個人互相督促，大大改善了拖延症

缺點：

可能需要一段磨合時間吧，一開始的效率肯定沒有那麼高的

結對夥伴劉的優點：

審美好，設計的GUI大家都說好看；積極主動，學習能力強，善于解決問題

寫的代碼注釋太少。。

我的優點：

比較細緻認真，

總是想得多，做的少。。

十三.PSP表格





			120




			800
			630
			200

			60


		2000

十四.界面子產品，測試子產品和核心子產品的松耦合

github位址：https://github.com/Liu-SD/SudoUi

合作小組兩位同學學号：15061119 15061104

代碼合并的過程有些曲折...我們本想在qt creator上修改相應的代碼引入他們的lib，但是因為至今仍然不明的原因，qt一直不能争取的引入這個lib，是以不得已我們把我們的代碼轉移到VS上，使用VS的qt插件，修改相應代碼就可以正确的使用他們的lib了。

經過測試，他們的子產品沒有大的問題，但是有兩點不足：

1.根據數獨的生成情況可以看出他們的數獨遊戲的終局生成沒有加入随機的因素，即生成數獨的順序是按照固定的順序回溯得到的，這樣導緻可玩性有些下降。

2.他們的生成唯一解的數獨算法最後生成的數獨空的分布不均勻，它們的挖空總是集中在上半部分。

十五.通過增量修改的方式，改程序式，釋出一個真正的軟體

我們把我們的數獨程式介紹給周圍人玩，收到了如下回報：

“沒有支援鍵盤輸入很不爽”。關于這一點，因為截止時間快到了，是以在上交的版本還沒有時間鍵盤輸入，不過之後一定會實作鍵盤的輸入的。
“提示錯誤時把一整行都變紅了，感覺很不舒服”。這裡我們把這部分改了，原來是把錯誤的行/列/九宮格變紅，現在是僅僅把錯誤重複的兩個數字變紅，這樣能舒服很多
“沒有新手引導”。新手引導目前隻能加上一個help按鈕，給你說如何操作，更詳細的引導之後再加。
“太難了，不玩了不玩了”。這位同學連easy模式都覺得難，我覺得這是他自己的問題：)
“remind me次數是不是需要加個限制”，這個限制之後會加。
“有個bug，gui剛打開就可以點選數獨格子了”。這确實是個bug，在使用者設定好模式之前，不能讓填數獨的格子Enable。

[2017BUAA軟工]結對項目-數獨程式擴充