天天看點
傳回

結對項目-數獨程式擴充

項目位址

https://github.com/si1entic/Sudoku-2.git

需求分析

  • 指令行

    合法參數有六種： -c 、 -s 、 -n -m 、 -n -r 、 -n -u 、 -n -r -u (支援多參數的順序任意)

    -c 1~1000000 -n 1~10000 -m 1~3 -r 20~55

  • GUI程式

    難度選擇、計時、提示、最佳記錄

開發過程

  • 看教科書和其它資料中關于Information Hiding, Interface Design, Loose Coupling的章節，說明你們在結對程式設計中是如何利用這些方法對接口進行設計的。（5'）

      在OO課程中，我們學習面向對象程式的需求分析和設計原則時，提到過5個經典的設計原則檢查(SOLID)。其中的SRP(Single Responsibility Principle)要求每個子產品都隻有一個明确的職責。因為子產品職責多，就意味着邏輯難以封閉，容易受到外部因素變化而變化，導緻該子產品不穩定。在本項目中，我們把涉及到計算資料的生成和求解數獨功能提出來，形成一個獨立的子產品。其他的控制輸入、資料可視化等功能也形成各自的子產品，再通過接口把它們聯系起來，這樣各子產品間就做到了松耦合（即修改一個子產品時不需要更改其他的子產品），同時也實作了不同子產品間的資訊隐藏（即每個子產品隻通路自己感興趣的資料來實作自己負責的功能）。

      例如本項目中的Core子產品，功能就是生成和求解數獨，是以提供generate和solve兩個接口函數供外部調用。當需求發生變化時（生成符合要求的數獨），我們遵從OCP原則，不修改已有實作(close)，而是通過擴充來增加新功能(open)。是以我們重載了generate函數，通過接收不同參數，來滿足不同的需求。

  • 計算子產品接口的設計與實作過程。設計包括代碼如何組織，比如會有幾個類，幾個函數，他們之間關系如何，關鍵函數是否需要畫出流程圖？說明你的算法的關鍵（不必列出源代碼），以及獨到之處。（7'）

      Core子產品主要可分為三部分，一是随機生成終盤，二是按要求挖空，三是求解數獨題目。是以主要分為三個類，其中FinalMaker類的make函數采用每行随機填數的方法生成一個終盤（為了可玩性犧牲了絕對不重複性，雖然理論上可能生成等效數獨但機率極低），PuzzleSovlver類的求解函數采用效率極高的DLX算法，而Core類通過調用這兩類的函數來實作随機生成終盤、求解數獨、保證唯一解挖空功能。最後一個功能應該是最難實作的，這裡我們采取的辦法是：先生成終盤，再随機挖空，然後求解看有沒有多解，有則重新挖。流程圖如下：

    結對項目-數獨程式擴充
    此外，影響數獨難度的因素較多，評定起來也比較複雜，比賽一般采取人工求解評定難度，而軟體中普遍認可的是SE值(求解該數獨用到最難解法難度)。但這對于我們的程式來說顯然有些難了，是以采用比較簡單的以挖空數來劃分：Easy 20~30空 Normal 31~45空 Hard 46~55空。
  • 畫出UML圖顯示計算子產品部分各個實體之間的關系(畫一個圖即可)。（2’）
    結對項目-數獨程式擴充

  • 計算子產品接口部分的性能改進。記錄在改進計算子產品性能上所花費的時間，描述你改進的思路，并展示一張性能分析圖（由VS 2015/2017的性能分析工具自動生成），并展示你程式中消耗最大的函數。（3'）

      主要分析最複雜的生成唯一解數獨的功能。生成數量少時還好，個數大于1000就明顯慢到無法接受的地步。分析發現findSolutions()函數耗時極長，于是針對它做了修改，在發現有第二個解時就抛出一個int，在最外面通過try catch來接收這個抛出，進而跳出了多重的遞歸，大大減少了判斷是否有唯一解的時間。下面是在-n 10000 -r 40~50 -u參數下的性能分析圖：

    結對項目-數獨程式擴充
    消耗最大的函數時Input類的handle函數，負責調用其他函數實作功能。而各功能函數中，耗時較多的是生成随機數獨的make()和檢查唯一解的checkUnique()。但需要說明的是，當挖空數在50以上時，程式耗時會大大加長，原因在于挖較多空時需要大量地調用checkUnique函數，導緻消耗激增，暫時沒有更好的解決方法。

  • 看Design by Contract, Code Contract的内容：

    http://en.wikipedia.org/wiki/Design_by_contract

    http://msdn.microsoft.com/en-us/devlabs/dd491992.aspx

    描述這些做法的優缺點, 說明你是如何把它們融入結對作業中的。（5'）

    契約式設計(OO老師非常推崇的模式，讓我們寫了不少)

    設計人員為軟體元件定義了形式化、精确和可驗證的接口規範。使用者和被調用者地位平等，雙方必須彼此履行義務，才可以行駛權利。

    這樣做的優點是提倡程式員對程式設計進行規範化操作，有了語言級别的前置後置條件和不變式的明确定義，程式的結構變得更加便于閱讀和交流；各部件職責獨立且僅為自己的功能負責，産生錯誤時定位較容易；保證了調用與被調用雙方代碼的品質，提高了軟體工程的效率和品質。

    缺點是對于程式語言有一定的要求，需要斷言機制。

    我們在Core子產品接口的設計中運用了DbC，規定了generate()、solve()傳入參數的前置條件(例如0<mode<4)，後置條件(result為合法的數獨)，不變式(None)。

  • 計算子產品部分單元測試展示。展示出項目部分單元測試代碼，并說明測試的函數，構造測試資料的思路。并将單元測試得到的測試覆寫率截圖，發表在部落格中。要求總體覆寫率到90%以上，否則單元測試部分視作無效。（6'）

      Core單元的功能為生成和求解數獨，對于生成的測試主要分三個方面：一是生成的題目是否合法（比如某行是否會出現兩個"1"之類的），二是挖空數是否在規定範圍之内。可通過下面的函數檢測：

    bool checkValid(int final[9][9], int row, int col, int& blanks)
{
	int value = final[row][col];
	if (value == 0)
	{
		blanks++;
		return true;
	}
	for (int i = row / 3 * 3; i < row / 3 * 3 + 3; i++) // 檢測該塊是否已有該數字
		for (int j = col / 3 * 3; j < col / 3 * 3 + 3; j++)
			if (final[i][j] == value)
				if (!(i == row&&j == col))
					return false;
	for (int i = 0; i < 9; i++) // 檢測該行該列是否已有該數字
		if ((i != col&&final[row][i] == value) || (final[i][col] == value&&i != row))
			return false;
	return true;
}

三是判斷是否有唯一解，這裡直接調用PuzzleSolve::checkUnique()進行檢查。

測試代碼：

```

[TestMethod]

void TestGenerate1()

{

srand((unsigned)time(NULL));

Core c;

const int number = 100;

for (int mode = 1; mode <= 3; mode++) // 周遊三個難度

int result[number][81];

c.generate(number, mode, result);

int game[9][9];

int blanks;

for (int i = 0; i < number; i++) // 周遊生成的題目

memcpy(game, result[i], sizeof(game));

blanks = 0;

for (int j = 0; j < 81; j++)

Assert::IsTrue(checkValid(game, j / 9, j % 9, blanks), L"合法性出錯");

switch (mode)

case 1:

Assert::IsTrue(blanks >= 20 && blanks <= 30, L"難度1挖空範圍出錯");

break;

case 2:

Assert::IsTrue(blanks >= 31 && blanks <= 45, L"難度2挖空範圍出錯");

case 3:

Assert::IsTrue(blanks >= 46 && blanks <= 55, L"難度3挖空範圍出錯");

default:

}

};

[TestMethod]
void TestGenerate2()
{
	Core c;
	const int number = 100, lower = 20, upper = 30;
	int result[number][81];
	c.generate(number, lower, upper, false, result);
	int game[9][9];
	int blanks;
	for (int i = 0; i < number; i++)    // 周遊生成的題目
	{
		memcpy(game, result[i], sizeof(game));
		blanks = 0;
		for (int j = 0; j < 81; j++)
			Assert::IsTrue(checkValid(game, j / 9, j % 9, blanks), L"合法性出錯");
		Assert::IsTrue(blanks >= lower && blanks <= upper, L"挖空範圍出錯");
	}
};

[TestMethod]
void TestGenerate3()
{
	Core c;
	PuzzleSovlver ps;
	const int number = 100, lower = 40, upper = 55;
	int result[number][81];
	c.generate(number, lower, upper, true, result);
	int game[9][9];
	int blanks;
	for (int i = 0; i < number; i++)    // 周遊生成的題目
	{
		memcpy(game, result[i], sizeof(game));
		blanks = 0;
		for (int j = 0; j < 81; j++)
			Assert::IsTrue(checkValid(game, j / 9, j % 9, blanks), L"合法性出錯");
		Assert::IsTrue(blanks >= lower && blanks <= upper, L"挖空範圍出錯");
		Assert::IsTrue(ps.checkUnique(game), L"唯一性出錯");
	}
};

[TestMethod]
void TestSolve()
{
	Core c;
	int puzzle[1][81];
	int final[9][9];
	int blanks = 0;

	c.generate(1, 1, puzzle);
	Assert::IsTrue(c.solve(puzzle[0], puzzle[0]), L"求解失敗");
	memcpy(final, puzzle, sizeof(final));
	for (int j = 0; j < 81; j++)
		Assert::IsTrue(checkValid(final, j / 9, j % 9, blanks), L"合法性出錯");

	c.generate(1, 2, puzzle);
	Assert::IsTrue(c.solve(puzzle[0], puzzle[0]), L"求解失敗");
	memcpy(final, puzzle, sizeof(final));
	for (int j = 0; j < 81; j++)
		Assert::IsTrue(checkValid(final, j / 9, j % 9, blanks), L"合法性出錯");

	c.generate(1, 3, puzzle);
	Assert::IsTrue(c.solve(puzzle[0], puzzle[0]), L"求解失敗");
	memcpy(final, puzzle, sizeof(final));
	for (int j = 0; j < 81; j++)
		Assert::IsTrue(checkValid(final, j / 9, j % 9, blanks), L"合法性出錯");

	c.generate(1, 20, 55, false, puzzle);
	Assert::IsTrue(c.solve(puzzle[0], puzzle[0]), L"求解失敗");
	memcpy(final, puzzle, sizeof(final));
	for (int j = 0; j < 81; j++)
		Assert::IsTrue(checkValid(final, j / 9, j % 9, blanks), L"合法性出錯");

	c.generate(1, 50, 55, true, puzzle);
	Assert::IsTrue(c.solve(puzzle[0], puzzle[0]), L"求解失敗");
	memcpy(final, puzzle, sizeof(final));
	for (int j = 0; j < 81; j++)
		Assert::IsTrue(checkValid(final, j / 9, j % 9, blanks), L"合法性出錯");

	puzzle[0][0] = puzzle[0][1] = 1;
    Assert::IsFalse(c.solve(puzzle[0], puzzle[0]), L"解出非法數獨");
};
```

單元測試覆寫率：

結對項目-數獨程式擴充
結對項目-數獨程式擴充

  • 計算子產品部分異常處理說明。在部落格中詳細介紹每種異常的設計目标。每種異常都要選擇一個單元測試樣例釋出在部落格中，并指明錯誤對應的場景。（5'）

    針對generate和solve接口的參數，異常可分為以下四類。

  1. NumberException：-n/-c參數的number範圍出錯 
    [TestMethod]
void TestNumberException()
{
    Core c;
    int result[1][81];
    try
    {
        c.generate(-1, 1, result);  // 	number傳入-1        
        Assert::Fail(L"number範圍出錯");
    }
    catch (NumberException& e)
    {
        cout << e.what() << endl;
    }
    try
    {
        c.generate(INT_MAX, 20, 30, true, result); // 	number傳入最大int值
        Assert::Fail(L"number範圍出錯");
    }
    catch (NumberException& e)
    {
        cout << e.what() << endl;
    }
};
  2. ModeException ：-m參數的mode範圍出錯 
    [TestMethod]
void TestModeException()
{
    Core c;
    int result[1][81];
    try
    {
        c.generate(1, 0, result); // 	mode傳入0
        Assert::Fail(L"mode範圍出錯");
    }
    catch (ModeException& e)
    {
        cout << e.what() << endl;
    }
    try
    {
        c.generate(1, 4, result); // 	mode傳入4
        Assert::Fail(L"mode範圍出錯");
    }
    catch (ModeException& e)
    {
        cout << e.what() << endl;
    }
};
  3. RangeException ：-r參數的range範圍出錯 
    [TestMethod]
void TestRangeException()
{
    Core c;
    int result[1][81];
    try
    {
        c.generate(1, -1, 20, false, result); // 	lower傳入-1
        Assert::Fail(L"range範圍出錯");
    }
    catch (RangeException& e)
    {
        cout << e.what() << endl;
    }
    try
    {
        c.generate(1, 50, 40, false, result); // 傳入的lower比upper大
        Assert::Fail(L"range範圍出錯");
    }
    catch (RangeException& e)
    {
        cout << e.what() << endl;
    }
    try
    {
        c.generate(1, 20, 56, false, result); // upper傳入56
        Assert::Fail(L"range範圍出錯");
    }
    catch (RangeException& e)
    {
        cout << e.what() << endl;
    }
};
  4. ValidException ：傳入非法數獨報錯 
    [TestMethod]
void TestValidException()
{
    Core c;
    int result[1][81];
    c.generate(1, 3, result);
    result[0][0] = result[0][1] = 1;
    try
    {
        c.solve(result[0], result[0]); // 傳入非法數獨
        Assert::Fail(L"解出非法數獨");
    }
    catch (ValidException& e)
    {
        cout << e.what() << endl;
    };
};
    結對項目-數獨程式擴充
  • 界面子產品的詳細設計過程。在部落格中詳細介紹界面子產品是如何設計的，并寫一些必要的代碼說明解釋實作過程。(5')

    • Sudoku.cpp/h 界面部分

      界面分為菜單欄、主界面，最佳紀錄界面和說明界面四部分。

      菜單欄中有New和Help兩個界面，New中提供選擇難度以及最佳紀錄檢視功能，Help對應于說明界面。通過QAction實作動作的，并用connect進行綁定

      例：

    Sudoku.cpp

private:
QAction *easyOpenAction;
QMenu *menuNew;
void easyOpen();
…………

menuNew = menuBar()->addMenu(tr("&New"));
menuNew->addAction(easyOpenAction);
easyOpenAction = new QAction(tr("Easy"), this);
connect(easyOpenAction, &QAction::triggered, this, &QtGuiApplication2::easyOpen);
    主界面劃分為上下兩個部分。上部分是一些目前狀态及重置按鈕的顯示，下部分為遊戲主界面，其中又分九個小格，通過對Margin參數的設定，實作小九宮格之間的空隙。 
    QGridLayout *mainLayout;    // 主界面
QGridLayout *topLayout;    // 上部分
QGridLayout *midLayout;    // 遊戲部分
QGridLayout *midLayoutIn[3][3];    // 小九宮格
…………

for (int i = 0; i < 3; i++)     // 将小九宮格加入遊戲部分
{
	for (int j = 0; j < 3; j++) 
	{
		midLayoutIn[i][j] = new QGridLayout();
		midLayoutIn[i][j]->setMargin(2);        // 空隙
		midLayout->addLayout(midLayoutIn[i][j], i, j, 0);
	}
}
for (int i = 0; i < 81; i++)     // 向小九宮格中加入小格子
{
	midLayoutIn[i / 9 / 3][i % 9 / 3]->addWidget(sudo[i], i / 9, i % 9, 0);
	connect(sudo[i], SIGNAL(tip_clicked()), this, SLOT(tipClick()));
	connect(sudo[i], SIGNAL(textChanged(const QString& )), this, SLOT(sudoTableEdit()));    
	// 如果檢測到參數改變，則調用相應方法，方法中會對填入的數進行一個簡單判斷，并檢查該數獨是否完全正确
}

    最佳紀錄界面中為最佳紀錄的展示以及重置功能，實作基本同上，使用 recordLayout->show();彈出新視窗

    說明界面中則用一個标簽對程式進行簡單介紹

    • MineEditLine.cpp/h 重寫的單行輸入框控件

      對于提示功能，由于需要具體确定格子位置，最終選擇了在格子上右鍵，會彈出一個菜單欄，其中有tip選項，點選tip獲得該格子的提示的方式。為此，我通過MineEdlitLine繼承了QEditLine類，重寫了其中的contextMenuEvent方法，并在選中tip時放出一個tip_click()的信号，主視窗通過接收到這個信号，來執行相關操作。

    MineEditLine.cpp

void MineLineEdit::contextMenuEvent(QContextMenuEvent *event)
{
//清除原有菜單
pop_menu->clear();
if (this->isReadOnly()) {    // 如果不可填，就不彈出菜單
	return;
}
pop_menu->addAction(tipAction);
pop_menu->exec(QCursor::pos());
event->accept();
}

…………
connect(tipAction, &QAction::triggered, this, &MineLineEdit::tip);

…………
emit tip_clicked();

    ps: 由于是文本框模式，需要限制輸入，具體實作大緻如下

    QRegExp rx("[1-9]");

    sudo[i]->setMaxLength(1);

    sudo[i]->setValidator(new QRegExpValidator(rx, sudo[i]));

  • 界面子產品與計算子產品的對接。詳細地描述UI子產品的設計與兩個子產品的對接，并在部落格中截圖實作的功能。(4')

    由于對Core子產品接口作了明确的規定，是以在雙方都遵守這一契約進行編碼的情況下，對接起來沒有什麼難度，花時間最多的反而是在VS上安裝Qt以及一些配置問題。

    • 計算子產品執行個體 
    Sudoku.cpp
private:    // Core中對應的子產品
    Core sudoku;

    • UI子產品設計與對接

      UI中在數獨生成、提示生成的部分使用到了計算子產品。

    • 數獨生成

      點選start/restart按鈕後，通過 sudoku.generate(1, model, result); 調用計算子產品中的數獨生成，再通過一一将數以對應方式呈現到界面上，實作初始遊戲界面的生成。

    • 提示生成

      在檢查到tip_click()信号後，調用相關方法，通過數獨求解方法生成tip，并以藍色顯示在對應位置上。如果目前數獨不合法或不可解，則彈出對應提示。

    void Sudoku::tipClick() 
{
	MineLineEdit *mle = qobject_cast<MineLineEdit*>(sender());
	int i = mle->accessibleName().toInt();
	int solution[81];
	bool f = false;
	try {
		f = sudoku.solve(result[0], solution);
	}
	catch (const std::exception&) {
		QMessageBox::information(this, tr("tip"), tr("Already Wrong"));
		return;
	}
	if (f) 
	{
		mle->setText(QString::number(solution[i]));
		result[0][i] = solution[i];
		sudoTable[i / 9][i % 9] = solution[i];
		mle->setStyleSheet("color: blue;");
	}
	else 
		QMessageBox::information(this, tr("tip"), tr("Already Wrong"));
}
    功能截圖見下面附加題部分。

  • 描述結對的過程，提供非擺拍的兩人在讨論的結對照片。（1'）

    由于行動得比較慢，當時剩的人已經不多了，于是選了和我同班的女生 😃

    考慮到上次個人項目我的算法稍快一些，于是決定我做Core她寫GUI。

    當然這隻是大緻分工，很多細節還是一起讨論商量出來的共同成果。

    結對項目-數獨程式擴充

  • 看教科書和其它參考書，網站中關于結對程式設計的章節，例如：

    http://www.cnblogs.com/xinz/archive/2011/08/07/2130332.html

    說明結對程式設計的優點和缺點。結對的每一個人的優點和缺點在哪裡 (要列出至少三個優點和一個缺點)。(5')

    結對程式設計

    優點：交流更加友善，能更加高效地解決開發問題；可以互相學習，快速提升程式設計水準(尤其是水準較低一方的)；互相監督能提高工作效率，還可以提高代碼品質，減少一些過失性bug。

    缺點：有些情況下成員各持己見，加大内耗；老手對于新手可能耐心不夠，産生團隊沖突，影響工作氣氛。

    她

    優點：代碼注釋多，擅長交流，有耐心

    缺點：有點拖延症233

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

附加題

  1. 子產品的松耦合測試

    合作小組：15061132 15061151

    遇到的問題

    • 他們的Core子產品+我們的GUI子產品：

      在向solve傳入非法數獨後，我們的子產品希望catch到一個我們定義的異常類型，而他們的子產品裡顯然沒有，故編譯錯誤。

      改進辦法：由于我們的自定義異常繼承自标準庫的exception類，故可以改為

      catch (const std::exception&)

       。

    • 他們的Core子產品+我們的Test子產品：

      這部分處理比較麻煩，因為當時為了友善，我們的測試子產品裡調用了Core子產品的非接口函數來進行檢測生成的數獨是否有唯一解，但他們的子產品裡顯然沒有開這個接口。

      改進辦法：在測試子產品裡重新實作檢測函數。

      其次，由于我們對于mode的劃分不同，是以我們對-m參數的測試不能應用在他們的Core上。

      最後我們有兩個測試對方無法通過：一個是generate(100,40,55,true,result)程式抛出異常，另一個是向solve傳入錯誤的數獨時沒有抛出異常。經确認，第一點的确是對方的代碼出了bug，第二點是由于他們對于傳入錯誤數獨的處理方式是傳回false而不抛異常。

    • 我們的Core子產品+他們的子產品

      根據對方回報，他們的GUI和TEST都能正常對接我們的Core子產品，是以沒有發現問題。具體内容請移步他們的部落格檢視。😃

  2. 軟體釋出

    加入了使用說明，并添加了應用圖示，軟體截圖如下：

    結對項目-數獨程式擴充

    根據使用者回報，做出了以下改進：

    1.玩家A覺得遊戲界面太醜。是以我們對界面的設計、配色等進行了一些修改，比初版好了不少。

    2.玩家B希望在某格填入不符規則的數字時給予提醒。故我們将不合法數字設為紅色，并将提示的數字設為藍色。

    3.玩家C認為提示應該有次數限制。但我們考慮到某些玩家可能在有限的提示裡解不出題目，是以仍不做限制。

    4.玩家D的評價是界面還是太醜。我們非常感謝這條建議 然後選擇了無視，并表示等招募到美工再給大爺您做美化吼不吼啊。(面帶微笑)

上一篇: 個人作業Week3-案例分析
下一篇: 【暑假】[深入動态規劃]UVa 12170 Easy Climb