項(xiàng)目的源代碼在Github上托管，可以在這里查看不见。
PSP表格
| PSP2.1 | Personal Software Process Stages | 預(yù)估耗時(shí)（分鐘） | 實(shí)際耗時(shí)（分鐘） |
|---|---|---|---|
| Planning | 計(jì)劃 | 40 | 60 |
| Estimate | 估計(jì)這個(gè)任務(wù)需要多少時(shí)間 | -- | 1080 |
| Development | 開發(fā) | -- | -- |
| Analysis | 需求分析（包括學(xué)習(xí)新技術(shù)） | 150 | 180 |
| Design Spec | 生成設(shè)計(jì)文檔 | -- | -- |
| Design Review | 設(shè)計(jì)復(fù)審（和同事審核設(shè)計(jì)文檔） | -- | -- |
| Coding Standard | 代碼規(guī)范（為目前的開發(fā)制定合適的規(guī)范） | 40 | 60 |
| Design | 具體設(shè)計(jì) | 60 | 90 |
| Coding | 具體編碼 | 260 | 240 |
| Code Review | 代碼復(fù)審 | 30 | 90 |
| Test | 測試（自我測試，修改代碼崔步，提交修改） | 120 | 120 |
| Reporting | 報(bào)告 | 240 | 180 |
| Test Report | 測試報(bào)告 | 30 | 60 |
| Size Measurement | 計(jì)算工作量 | 30 | 60 |
| Postmortem & Process Improvement Plan | 事后總結(jié)稳吮，并提出過程改進(jìn)計(jì)劃 | 60 | 60 |
| 合計(jì) | 1020 | 1140 |
思路
項(xiàng)目要求的程序主要需要實(shí)現(xiàn)兩個(gè)功能：
- 求解數(shù)獨(dú)
- 生成數(shù)獨(dú)終局
在做這個(gè)項(xiàng)目之前本人也曾經(jīng)癡迷于數(shù)獨(dú)一段時(shí)間，因此對數(shù)獨(dú)游戲本身不需要花時(shí)間再做更多的了解井濒，就直接開始講解決這個(gè)問題的思路了灶似。
算法
求解數(shù)獨(dú)
數(shù)獨(dú)的求解過程中最重要的方法是排除法：由于每一行、每一列以及每一個(gè)九宮格中必須是不能重復(fù)的1到9的九個(gè)數(shù)字瑞你，因此對給出的任意一個(gè)數(shù)獨(dú)局面酪惭，許多空方格中的可選數(shù)字都是有限的，而在求解一個(gè)實(shí)際的數(shù)獨(dú)問題當(dāng)中者甲，許多空方格當(dāng)中可以填入的數(shù)字在運(yùn)用排除法之后往往只有兩三個(gè)——甚至只有一個(gè)春感，這種情況下自然就可以直接填入對應(yīng)的數(shù)字。
排除法的實(shí)現(xiàn)十分簡單虏缸，只要對一個(gè)空方格檢查其對應(yīng)的行鲫懒、列以及九宮格中其它已經(jīng)填入的數(shù)字即可，當(dāng)九個(gè)數(shù)字當(dāng)中的八個(gè)數(shù)字均被填入時(shí)就可以確定該方格中應(yīng)當(dāng)填入的數(shù)字刽辙，對簡單的數(shù)獨(dú)題而言窥岩，只要不斷地運(yùn)用排除法就可以最終解決它。遺憾的是宰缤，大部分?jǐn)?shù)獨(dú)題都沒有那么簡單颂翼，需要運(yùn)用許多更為復(fù)雜的技巧才能解決晃洒，如果要一一實(shí)現(xiàn)這些技巧不僅麻煩，而且并不能保證可以解決所有的數(shù)獨(dú)題疚鲤，因此在排除法之外還需要運(yùn)用別的方法锥累。
對數(shù)獨(dú)這類在解空間中進(jìn)行搜索的問題，回溯法是一個(gè)常用的方法集歇，只要不停地試探每個(gè)空方格中可以填入的數(shù)字，并在發(fā)現(xiàn)矛盾時(shí)進(jìn)行回溯语淘，就可以保證能找出一個(gè)數(shù)獨(dú)局面的所有解诲宇。問題是如果盲目地進(jìn)行搜索，則回溯法的效率會(huì)極低惶翻，最差的實(shí)現(xiàn)對每個(gè)空方格試探所有可能的數(shù)字姑蓝，將需要次搜索才能找到最終解，這是不可接受的吕粗，但只要結(jié)合排除法就可以簡單地解決這個(gè)問題纺荧。
通過運(yùn)用排除法，我們可以大大減少每個(gè)空方格中可能填入的數(shù)字颅筋，從而縮小了需要搜索的解空間宙暇，并且我們觀察到每個(gè)新填入的數(shù)字都可能讓其它方格中的可選數(shù)字減少，因此實(shí)際需要搜索的局面是很少的议泵。同時(shí)占贫，為了盡可能地減少填入錯(cuò)誤數(shù)字的概率，在每一步需要在空方格中填入不確定的數(shù)字時(shí)先口，我們選取可選數(shù)字最少的空方格填入數(shù)字型奥。
生成數(shù)獨(dú)終局
在完成求解數(shù)獨(dú)的程序之后，如何生成數(shù)獨(dú)終局的答案就變得十分顯然了碉京，只要在空的數(shù)獨(dú)局面上直接運(yùn)行已經(jīng)實(shí)現(xiàn)了的回溯法厢汹，則所返回的解都是有效的數(shù)獨(dú)終局。由于不需要從頭開始計(jì)算每一個(gè)終局谐宙，這個(gè)算法的效率十分高烫葬，且由于回溯法的一個(gè)特點(diǎn)就是可以找到所有的解，因此只要有足夠的時(shí)間我們完全可以生成所有的數(shù)獨(dú)終局卧惜，該算法的正確性也得到了保障厘灼。
使用語言
出于性能上的考慮，我們采用C++語言咽瓷，并使用Visual Studio 2017進(jìn)行項(xiàng)目的開發(fā)设凹，并且我們會(huì)使用許多C++17標(biāo)準(zhǔn)的特性，以使代碼更加現(xiàn)代茅姜、簡潔闪朱。
項(xiàng)目要求最后給出可以運(yùn)行的文件以及附帶的dll庫月匣，因此在開發(fā)的過程中我們將盡可能只使用標(biāo)準(zhǔn)庫，而不使用例如Boost的外部庫進(jìn)行開發(fā)奋姿。
附加題要求開發(fā)一個(gè)解數(shù)獨(dú)的GUI程序锄开，由于MFC、C++\CIR等Visual Studio自帶支持的GUI庫均需要運(yùn)行時(shí)支持（安裝附加程序）称诗，windows原生的圖形API又十分難用萍悴，因此決定使用Qt開發(fā)所要求的GUI。在windows上Qt開發(fā)的程序可以使用專用工具進(jìn)行deploy寓免，不需要運(yùn)行時(shí)支持癣诱，因此可以在任意電腦上運(yùn)行，符合項(xiàng)目的要求袜香。
設(shè)計(jì)實(shí)現(xiàn)
模塊
程序中將主要包含四個(gè)模塊：Main撕予，Generator，Solver蜈首，State实抡。每個(gè)模塊的功能如下述：
Main
主要包含程序的業(yè)務(wù)邏輯，負(fù)責(zé)處理程序的輸入欢策，并調(diào)用相應(yīng)的模塊進(jìn)行處理吆寨，最后對結(jié)果進(jìn)行輸出。
Main模塊包含程序的main()函數(shù)猬腰，其中涉及的功能有處理用戶的輸入鸟废，嘗試讀取/寫入相關(guān)的文件，調(diào)用相關(guān)的模塊姑荷，在發(fā)生錯(cuò)誤的時(shí)候結(jié)束程序并向用戶提供反饋盒延。
Main模塊中大部分的代碼都將與錯(cuò)誤處理有關(guān)，因?yàn)橛脩舻妮斎肟梢允侨我獾氖竺幔襂O操作也有相當(dāng)?shù)牟淮_定性添寺，這需要我們的程序擁有魯棒性，能正確地處理不同地輸入懈费，并在出現(xiàn)問題時(shí)正確地進(jìn)行錯(cuò)誤處理并退出程序计露，同時(shí)向用戶提供有用地信息。
Generator
包含生成數(shù)獨(dú)終局的算法憎乙，可以返回任意數(shù)量（不超過所有終局?jǐn)?shù)量）的數(shù)獨(dú)終局票罐。
Generator的功能與實(shí)現(xiàn)都相對簡單，它牽涉到的主要是調(diào)用Solver并返回對應(yīng)數(shù)量的解（數(shù)獨(dú)終局）泞边。
Generator模塊可以向Solver傳遞特定的參數(shù)以針對產(chǎn)生解的情況做出優(yōu)化该押。
Solver
包含回溯法的算法，使用回溯法解決一個(gè)數(shù)獨(dú)問題阵谚，并可以返回任意數(shù)量（不超過真值）的解蚕礼。
Solver在從傳遞過來的Board轉(zhuǎn)換為State之后就將只在State上進(jìn)行操作烟具。回溯法將在找到指定數(shù)量的解之后返回而非一直找到存在的所有解之后才返回（這個(gè)功能的必要性是因?yàn)槲覀冃枰?code>Solver產(chǎn)生不同的數(shù)獨(dú)終局奠蹬，這時(shí)提供的是一個(gè)空的局面朝聋，時(shí)間和空間都不允許我們找到所有的數(shù)獨(dú)終局再返回）。
State
表示一個(gè)數(shù)獨(dú)局面囤躁，可以在上面進(jìn)行操作冀痕、提取狀態(tài)。
一個(gè)State表示一個(gè)已經(jīng)使用排除法（或?qū)崿F(xiàn)了的其它方法）填入所有可以填入的數(shù)字的局面割以，而不能表示一個(gè)中間局面（即還存在可以使用排除法填入數(shù)字的局面）金度。這樣設(shè)計(jì)是因?yàn)槲覀冇^察到在使用回溯法求解的過程中，這樣的中間局面是沒有作用的严沥，只有在不能通過排除法（或?qū)崿F(xiàn)了的其它方法）再填入數(shù)字時(shí)才需要使用回溯法進(jìn)行操作，因此我們可以“跳過”中間的狀態(tài)中姜。這樣做簡化了程序的邏輯消玄，使模塊的責(zé)任更加明確。
State是immutable的丢胚，也就是說翩瓜，不能從外部改變一個(gè)State，每個(gè)State只能從一個(gè)已經(jīng)存在的State創(chuàng)建或者由構(gòu)建函數(shù)創(chuàng)建携龟。這樣設(shè)計(jì)的目的是為了使算法更加清晰兔跌，并且我們的算法沒有從外部改變一個(gè)State的必要。
測試
Visual Studio 2017 Community代碼分析程序沒有警告峡蟋。
我們對程序編寫了單元測試坟桅，單元測試使用的庫為Googel Test，簡稱GTest蕊蝗。使用Visual Studio檢查單元測試覆蓋率為98%仅乓。使用了30個(gè)很難的數(shù)獨(dú)題作為測試用例。
使用GTest的好處在于它提供了編寫好的Macro來供我們使用蓬戚，讓我們能很方便地編寫夸楣、組織對項(xiàng)目的單元測試，讓我們能將精力集中在程序邏輯的編寫上子漩，而不是對這些測試的組織豫喧、維護(hù)。
GTest的一個(gè)好處在于幢泼，當(dāng)測試失敗的時(shí)候它會(huì)自動(dòng)給出失敗的地方的詳細(xì)信息紧显，使我們能夠快速定位錯(cuò)誤，而不至于還要一個(gè)一個(gè)去試旭绒，且這些幾乎不需要編寫額外的代碼鸟妙，只需要使用它自帶的Macro編寫測試就可以享受它的便利性焦人。
最后我們對三個(gè)主要的模塊分別編寫了三個(gè)Test Suite，并在最后通過了所有測試重父。程序剛完成的時(shí)候是存在有Bug的花椭，單元測試幫助我們及時(shí)發(fā)現(xiàn)了Bug并定位到了它的位置，如果沒有單元測試的話在整個(gè)項(xiàng)目中尋找Bug將是一個(gè)十分困難的過程房午，而且也無法保證我們的模塊的可靠性矿辽。
在完成單元測試之后，我們還使用了從網(wǎng)上找到的20個(gè)非常難的數(shù)獨(dú)題來作為對性能的最終評(píng)定郭厌。最后程序在~140ms的時(shí)間內(nèi)解決了這20個(gè)問題袋倔，可以說是比較滿意的結(jié)果了。
性能分析
最終我們使用開啟O2優(yōu)化之后編譯產(chǎn)生的程序進(jìn)行測試折柠。
經(jīng)測試最初完成的程序要生成一百萬個(gè)不同的終局所需時(shí)間大致為~34s宾娜，這個(gè)性能已經(jīng)十分好了，主要得益于我們只用一個(gè)int表示一個(gè)格子中可以填入的數(shù)字扇售，并在State類的實(shí)現(xiàn)中使用了十分高效的比特運(yùn)算前塔，且對回溯法做了許多優(yōu)化，大大減少了錯(cuò)誤回溯的次數(shù)承冰。雖然已經(jīng)做的很好了华弓，但還有許多改進(jìn)的余地。
使用Visual Studio 2017自帶的性能探查器我們得到下列的結(jié)果：
可以看出困乒，程序運(yùn)行中在NumberOfSetBits函數(shù)上的運(yùn)行時(shí)間是一個(gè)瓶頸寂屏，本來我們使用的是最簡單的算法：
int NumberOfSetBits(int n) {
int count = 0;
while(n) {
if (n & 1) count++;
n >>= 1;
}
return count;
}
這個(gè)算法的效率是較低的，無論數(shù)值是1的比特位有多少個(gè)娜搂，都需要運(yùn)行大約9個(gè)循環(huán)迁霎，因此我們采用改進(jìn)的算法：
int NumberOfSetBits(int n) {
int count = 0;
while(n) {
n = (n - 1) & n;
count++;
}
return count;
}
改進(jìn)后的算法每次循環(huán)的次數(shù)與1的個(gè)數(shù)相同，可以看出效率是大大提升了的涌攻。再次運(yùn)行代碼分析得到的結(jié)果如下：
在改進(jìn)了NumberOfSetBits之后欧引，再次運(yùn)行測試，則發(fā)現(xiàn)現(xiàn)在生成一百萬個(gè)不同的終局只需要~21s恳谎，這是一個(gè)很大的進(jìn)步芝此。
可能的進(jìn)一步改進(jìn)
同時(shí)我們還可以看到程序的瓶頸在_AddConstraint函數(shù)上，這是在我們的預(yù)料之中的因痛，目前很難對函數(shù)本身再做優(yōu)化了婚苹，因此主要優(yōu)化的地方應(yīng)該是讓State更快地收斂，要做到這一點(diǎn)就需要在程序中運(yùn)用更多的數(shù)獨(dú)技巧鸵膏。
目前我們只使用了最簡單的對單個(gè)格子的排除法：當(dāng)一個(gè)格子中只有一個(gè)能填入的數(shù)字時(shí)膊升，將該數(shù)字填入它。而一個(gè)同樣常用的排除法是：當(dāng)某一行/某一列/某個(gè)九宮格中某個(gè)數(shù)字只在其中一個(gè)格子里可以填入時(shí)谭企，將該數(shù)字填入該格子廓译。實(shí)現(xiàn)該排除法可以使回溯法更快地收斂评肆，并減少需要搜索的解，很可能可以改進(jìn)算法非区。
還有一個(gè)可能的改進(jìn)是對多線程的優(yōu)化瓜挽，利用多核CPU的性能，和算法無關(guān)征绸。因?yàn)榛厮莘ㄊ菑囊粋€(gè)初局出發(fā)找到其所有的解久橙，那么我們可以在多個(gè)線程上對不同的初局同時(shí)運(yùn)行回溯法，并在最后將結(jié)果整合管怠。這可以顯著提高運(yùn)行速度淆衷，在4核CPU上速度提高四倍、8核CPU上速度提高八倍渤弛，不過這個(gè)方法只是提高了對硬件的使用祝拯，沒有真正提高運(yùn)算效率。
代碼說明
State
typedef std::array <std::array<int, 9>, 9> Board;
typedef std::array <std::array<int, 9>, 9> Grids;
class State
{
public:
State(const std::optional<Board> board = {}, bool puzzle_mode = true);
~State();
std::optional<State> AddConstraint(int row, int col, int n);
void Print();
bool IsComplete();
Grids GetGrids();
private:
Grids grids_;
bool puzzle_mode_;
void _AddConstraint(int row, int col, int n);
bool TryAddMoreConstraint();
bool valid();
};
State的關(guān)鍵代碼主要是我們對一個(gè)State的存儲(chǔ)形式與在其上面的操作她肯，出于效率的考慮鹿驼，我們使用一個(gè)9x9的int二維數(shù)組存儲(chǔ)數(shù)獨(dú)局面中每個(gè)格子的狀態(tài)，一個(gè)int對應(yīng)一個(gè)格子中可能填入的數(shù)字辕宏，最低的九個(gè)比特位代表九個(gè)數(shù)字是否可以填入。
比如說若一個(gè)格子中可能填入的數(shù)字為1砾莱、2瑞筐、5，則相對應(yīng)的int為0b10011腊瑟。我們用typedef定義Grids為State內(nèi)部表示狀態(tài)的數(shù)據(jù)聚假。
最關(guān)鍵的函數(shù)是AddConstraint，這表示將與行列對應(yīng)的數(shù)字限制為一個(gè)數(shù)字闰非，也可以理解為填入一個(gè)數(shù)字膘格，對應(yīng)的代碼如下：
void State::_AddConstraint(int row, int col, int n) {
assert(n >= 1 && n <= 9);
int flag = 1 << (n - 1);
assert(grids_[row][col] & flag);
grids_[row][col] = flag;
for (int i = 0; i < 9; i++) {
if (i == row) continue;
int prev = grids_[i][col];
grids_[i][col] &= ~(flag);
int after_bits = NumOfSetBits(grids_[i][col]);
if (prev != grids_[i][col] && after_bits == 1) {
_AddConstraint(i, col, MsgBitPos(grids_[i][col]));
}
}
for (int i = 0; i < 9; i++) {
if (i == col) continue;
int prev = grids_[row][i];
grids_[row][i] &= ~(flag);
int after_bits = NumOfSetBits(grids_[row][i]);
if (prev != grids_[row][i] && after_bits == 1) {
_AddConstraint(row, i, MsgBitPos(grids_[row][i]));
}
}
int row_start, col_start;
row_start = row - row % 3;
col_start = col - col % 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (row_start + i == row && col_start + j == col) continue;
int prev = grids_[row_start + i][col_start + j];
grids_[row_start + i][col_start + j] &= ~(flag);
int after_bits = NumOfSetBits(grids_[row_start + i][col_start + i]);
if (prev != grids_[row_start + i][col_start + j] && after_bits == 1) {
_AddConstraint(row_start + i, col_start + i, MsgBitPos(grids_[row_start + i][col_start + i]));
}
}
}
}
代碼中依次將要填入數(shù)字的格子對應(yīng)的行、列财松、九宮格中的其它格子中該數(shù)字的比特位置于零瘪贱，要注意的是，在這個(gè)過程中可能產(chǎn)生新的可以確定數(shù)字的格子辆毡，當(dāng)產(chǎn)生這樣的格子時(shí)我們必須對其調(diào)用對應(yīng)的AddConstraint_函數(shù)菜秦，以維持?jǐn)?shù)據(jù)的一致性（所有只有一個(gè)可能數(shù)字的格子都是已經(jīng)確定的）。
optional<State> State::AddConstraint(int row, int col, int n) {
if (!(grids_[row][col] & (1 << (n - 1)))) return {};
State new_state;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
new_state.grids_[i][j] = grids_[i][j];
}
}
new_state.puzzle_mode_ = puzzle_mode_;
new_state._AddConstraint(row, col, n);
if (puzzle_mode_) {
while(new_state.TryAddMoreConstraint());
}
if (!new_state.valid()) return {};
return new_state;
}
AddConstraint是AddConstraint_對應(yīng)的外部接口舶掖，它會(huì)創(chuàng)建一個(gè)新的State并在上面調(diào)用AddConstraint_函數(shù)球昨，注意的是當(dāng)新產(chǎn)生的State不合法時(shí)我們將返回一個(gè)空值，這里利用了std::optional這個(gè)C++17提供的新特性眨攘。
Solver
class Solver
{
public:
Solver(const std::optional<Board> board, int num = 1, bool puzzle_mode = true);
std::vector<Board> GetSolutions();
~Solver();
private:
std::vector<Board> solutions_;
void BackTrack(State s);
int target;
};
Solver的接口簡單明了主慰，只需要提供初始的Board嚣州、期望解的數(shù)量、解數(shù)獨(dú)的模式共螺，然后使用GetSolutions接受產(chǎn)生的數(shù)獨(dú)解就可以了该肴。
Solver中最關(guān)鍵的是實(shí)現(xiàn)回溯法的函數(shù)：
void Solver::BackTrack(State s) {
Grids grids = s.GetGrids();
if (s.IsComplete()) {
Board board;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
board[i][j] = MsgBitPos(grids[i][j]);
}
}
solutions_.push_back(board);
return;
}
int min_pos = -1, min_count = 10;
vector<int> a;
for (int i = 0; i < 9 * 9; i++) {
int count = NumOfSetBits(grids[i / 9][i % 9]);
if (count == 1) continue;
if (count < min_count) {
min_count = count;
min_pos = i;
}
if (count == 2) {
break;
}
}
for (int i = 0; i < 9; i++) {
if (grids[min_pos / 9][min_pos % 9] & (1 << i)) {
int row = min_pos / 9, col = min_pos % 9;
optional<State> new_state = s.AddConstraint(row, col, i + 1);
if (new_state.has_value()) {
BackTrack(*new_state);
if (solutions_.size() == target) {
return;
}
}
}
}
}
在BackTrack中我們首先判斷當(dāng)前的State是否已經(jīng)是一個(gè)完整的解，若是的話則將它添加到解集當(dāng)中并返回璃谨。然后我們尋找還沒有確定數(shù)的可選數(shù)字的數(shù)量最少的格子沙庐，在上面遞歸運(yùn)行回溯法。
找到格子之后我們在上面嘗試所有可能的數(shù)并遞歸調(diào)用回溯法佳吞，這是算法的部分拱雏，就不再贅述了。一個(gè)需要注意的是若產(chǎn)生合法的State則我們繼續(xù)嘗試下一個(gè)數(shù)底扳，而不需要回溯下去铸抑。
Generator
class Generator
{
public:
Generator(int n);
~Generator();
std::vector<Board> GetBoards();
private:
int n;
};
由于Generator實(shí)質(zhì)上只是Solver上的一層wrapper，因此接口與實(shí)現(xiàn)的代碼均十分簡單衷模。
vector<Board> Generator::GetBoards() {
Board b{};
b[0][0] = (4 + 1) % 9 + 1;
Solver s(b, n, false);
return s.GetSolutions();
}
按照題目要求我們將初始Board的第一個(gè)數(shù)設(shè)置為學(xué)號(hào)最后兩位進(jìn)行運(yùn)算的結(jié)果鹊汛，將其傳遞給Solver并返回得到的解。
SudokuSolver
這是我們的主函數(shù)阱冶，其中大部分的代碼都是輸入輸出與錯(cuò)誤處理刁憋，main函數(shù)的內(nèi)容如下：
int main(int argc, char *argv[]) {
if (argc != 3) {
PrintUsage();
return 0;
}
string option(argv[1]);
if (option == "-c") {
int n;
try {
n = stoi(argv[2]);
}
catch (invalid_argument e) {
cout << "'" << argv[2] << "' is not a valid number!";
return 0;
}
ofstream fout("sudoku.txt", ios::out | ios::trunc);
if (!fout) {
cout << "Failed opening file 'sudoku.txt' !" << endl;
return 0;
}
Generator g(n);
vector<Board> boards = g.GetBoards();
for (int i = 0; i < n; i++) {
OutputBoard(fout, boards[i]);
}
}
else if (option == "-s") {
ifstream fin(argv[2]);
if (!fin) {
cout << "Failed opening file '" << argv[2] << "' !" << endl;
return 0;
}
ofstream fout("sudoku.txt", ios::out | ios::trunc);
if (!fout) {
cout << "Failed opening file 'sudoku.txt' !" << endl;
return 0;
}
while (true) {
Board b;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
fin >> b[i][j];
if (fin.eof()) {
cout << "Solved all puzzles" << endl;
return 0;
}
if (b[i][j] < 0 || b[i][j] > 9 || fin.fail()) {
cout << "Invalid Sudoku problem!" << endl;
return 0;
}
}
}
Solver s(b);
if (s.GetSolutions().empty()) {
cout << "No solution exists!" << endl;
return 0;
}
Board solution = s.GetSolutions()[0];
OutputBoard(fout, solution);
}
}
else {
PrintUsage();
return 0;
}
}
可以看出來，我們需要檢查的主要有三個(gè)地方：
- 命令行參數(shù)
- 讀取/寫入文件
- 模塊的返回值
在這三個(gè)地方我們都需要檢查對應(yīng)的值木蹬，并在需要的時(shí)候中止程序運(yùn)行至耻，并向用戶提供錯(cuò)誤信息，這對保證程序的魯棒性十分重要镊叁。
總結(jié)
在本項(xiàng)目中我們使用C++實(shí)現(xiàn)了一個(gè)基于回溯法的可以生成數(shù)獨(dú)終局和求解數(shù)獨(dú)的程序尘颓，且在項(xiàng)目的過程中我們按照計(jì)劃、設(shè)計(jì)晦譬、編碼疤苹、測試、性能分析等一系列軟件工程中的標(biāo)準(zhǔn)步驟完成了項(xiàng)目敛腌。
從這個(gè)項(xiàng)目中我收獲了許多卧土，也掌握了許多之前只了解概念但并沒有實(shí)際接觸到的工具，對軟件工程有了更深的理解迎瞧。
