Github項目地址：https://github.com/CarloFz/OOOOOLD

一、PSP表格

PSP2.1Personal Software Process Stages預估耗時(分鐘)

Planning	計劃	60
Estimate	估計這個任務需要多少時間	10
Development	開發	600
Analysis	需求分析（包括學習新技術）	60
Design Spec	生成設計文檔	60
Design Review	設計復審（和同事審核設計文檔）	20
Coding Standard	代碼規范（為目前的開發制定合適的規范）	20
Design	具體設計	60
Coding	具體編碼	600
Code Review	代碼復審	20
Test	測試（自我測試，修改代碼，提交修改）	120
Reporting	報告	60
Test Report	測試報告	30
Size Measurement	計算工作量	20
Postmortem & Process Improvement Plan	事后總結，并提出過程改進計劃	20
	合計	1760

二、解題思路

終局生成
???????題目要求最多生成100w個不重復數獨終局，其中左上角的數字不能改變
經過查閱資料，我決定使用一個已經寫好的數獨模板，然后對這個模板的第一行進行全排列（除第一個數字）。但是顯然這樣做還不能達到100w的復雜度，于是我們可以通過對于模板進行行列的交換，再配合上每個交換后的模板的第一行的全排列，就能夠達到100w的復雜度。

數獨求解
???????這部分計劃使用回溯法求數獨的解，并且通過對題目進行預處理減少回溯法的時間復雜度

三、設計實現過程

???????這個項目的代碼文件主要分成四部分
第一部分為header.h：主要負責相關庫的引入和所有函數的聲明

#pragma once #include <stdio.h> #include <iostream> #include <string.h> #include <string> #include <fstream> #include <ctime> #include <vector> using namespace std; #define MAX_CREATE 1000000 #define MAX_BUFLEN 10000 #define CREATE_FILENAME "./createSudoku.txt" #define SOLVE_FILENAME "./solveSudoku.txt"int inputProcess(int argc, char** argv); int create(int count); int solve(char *path);void swapChar(char* a, char* b);//交換某兩個字符的位置 void write(char* buf[], int buflen, bool fin);//將緩沖的內容寫入文件void initPossibleSet(int matrix[9][9], vector<int> possibleSet[9][9]);//初始化所有位置的可能的答案的集合 void updatePossibleSet(int matrix[9][9], vector<int> possibleSet[9][9], int row, int col);//更新某一個位置的可能的答案的集合 void checkPossibleSet(int matrix[9][9], vector<int> possibleSet[9][9]);//檢查是否有能夠唯一確定的空位 bool checkTrue(int matrix[9][9]);//檢查數獨解是否正確（DEBUG用） bool backTrace(int row, int col, int matrix[9][9], vector<int> possibleSet[9][9], int nextPos[9][9][2]);//回溯法求解數獨

第二部分為main.cpp：是程序的主要框架，負責調用各個部分的函數

第三部分為input.cpp：這個文件中包含檢測輸入的合法性的相關函數的實現

第四部分為create.cpp: 這個文件中包含生成數獨終局所需要的相關函數的實現

下圖為我使用的數獨終局模板

第五部分為solve.cpp：這個文件中包含解決數獨問題所需要的相關函數的實現

四、性能分析

創建數獨：sudoku.exe -c num

-c 1-c 1000-c 10000-c 1000000

0.001s	0.031s	0.105s	10.255s

???????關于創建數獨的部分，主要的時間花費在通過多級循環遍歷所有模板的交換可能，但是在寫入文件的部分應該還有提升空間。
???????寫入文件時，我設計了一個比較大的緩沖區，每次生成一個終局之后就把這個終局添加到緩沖區中，當緩沖區滿之后，再把緩沖區的內容一次性寫入文件中。
???????因此緩沖區的大小是IO部分的時間復雜度的關鍵

求解數獨：sudoku.exe -s path

-s 1-s 1000-s 10000-s 1000000

0.001s	0.095s	0.733s	73.216s

???????關于求解數獨的部分，我通過網上查閱資料，發現使用c++的ifstream和ofstream可以直接把文件全部讀入內存或把緩沖區的內容全部寫入文件，于是讀寫文件的時間幾乎可以不考慮優化。
???????這部分最占用時間的是對每個數獨進行遞歸的回溯法求解。使用比較簡單的回溯法處理1e6的數據大概需要140多秒，顯然還有很大優化空間。
???????于是我采用對數獨題目進行預處理的方式，在每個題目中，都會有很多的空白是可以通過同行、同列、同九宮格的已有數字推斷出唯一解的，我們可以在使用回溯法求解時把這些空先解答出來，這樣就能很大程度上減少遞歸的層數，能有效地減少回溯法的時間復雜度。
???????具體的實現方法是我通過possibleSet來存放每一個空格的所有可能解，當某個空格的可能解只有一個時，我們就可以把這個空格填上這個數字，然后對于這個空格所有同行、同列、同九宮格的空格更新他們的possibleSet，再重復檢查每個空的解空間大小，當沒有空格能求出唯一解時，我們進入回溯法進行求解。
???????同樣的，在回溯法中我也考慮過使用這樣的方法減少回溯的復雜度，即在每次嘗試對一個空填入可行解時都更新其他空格的可行解，并對有唯一解的空格進行解答。但是這樣以來就使得回溯法每一次都需要大量的計算來對possibleSet進行更新，也使得回溯法對于數獨矩陣的還原過程變得很困難，因為我額外對數獨矩陣做了很大的修改。這些問題使得我在這樣實現代碼時讓處理1e6的數據的時間增加到190多秒，于是這個方法被棄用。
???????但是我們仍然可以使用possibleSet對回溯法進行一些優化。在回溯法中，我們對于每個空都要用9個數字分別嘗試填入，這意味這有很多次重復查詢。于是我們在嘗試填入之前先更新這個空格的possibleSet，然后將possibleSet中的解嘗試填入空格中，這樣能很顯著的減少回溯時間。
???????除此之外，原始的回溯法中，每一此遞歸調用都是調用當前處理的元素的下一個元素，也就是說并不是空格的元素也會使用一層遞歸調用，于是我想通過只對于空格使用回溯法減少遞歸層數。最終我通過nextPos[9][9][2]的數組存放每個數獨矩陣元素的下一個空格的位置，這個數組在取出一個數獨題目并進行過預處理后就可以得出，然后在回溯法時每次遞歸調用只需要通過查表調用當前數組元素的下一個空格位置即可。
???????經過預處理、減少查詢時間、減少遞歸層數的方式進行優化過后，對于1e6的數獨題目只需要70多秒的時間即可解答。但是需要注意的是，我這這里使用的1e6的測試數據都是我通過對終局進行隨機挖空得到的，空格的個數都在60-30之間，可能與實際的數獨題目有一些差距。而且當之前使用比較簡單的數獨題目時，解題時間會有很大的縮短，只需要10多秒就能解決1e6的數據。所以說實際的運行效率與題目的難易程度有很大關系，這主要是因為簡單的題目空格較少，回溯法層數很小，而且很多空格都可以通過預處理解決，而困難的題目會導致預處理效果不明顯，回溯法搜索時很費時間。

五、代碼說明

main.cpp

int main(int argc, char** argv) {clock_t start = clock();//輸入處理int type = inputProcess(argc, argv);if (type == -1){cout << "參數錯誤，請重新輸入" << endl;return 0;}//任務處理if (type == 1){int count = atoi(argv[2]);create(count);}else if (type == 2){solve(argv[2]);}clock_t end = clock();cout << "time : " << ((double)end - start) / CLOCKS_PER_SEC << "s\n" << endl;return 0; }

input.cpp

int inputProcess(int argc, char** argv) {//驗證參數個數if (argc != 3){return -1;}//驗證第一個參數-c/-sint type = 0; //-c = 1; -s = 2;if (strcmp(argv[1],"-c") == 0) {type = 1;}else if (strcmp(argv[1], "-s") == 0){type = 2;}else {type = -1;//錯誤參數}if (type == -1){return -1;}//驗證第二個參數if (type == 1)//-c{string countS = argv[2];for (unsigned int i = 0; i < countS.length(); i++){if (countS[i] > '9' || countS[i] < '0'){return -1;}}}else if (type == 2) {//-sFILE* p = NULL;fopen_s(&p, argv[2], "r");if (p == NULL){return -1;}fclose(p);}return type; }

create.cpp

int create(int count) {//覆蓋之前的文件FILE* p = NULL;fopen_s(&p, CREATE_FILENAME, "w");if (p != 0) {fclose(p);}char** buf;buf = (char**)malloc(sizeof(char*) * MAX_BUFLEN);int buflen = 0;int countRes = 0;if (count > MAX_CREATE){cout << "請求生成的數獨終局過多" << endl;return 0;}//數獨終局的原始模板，其他的終局在此基礎上變化而成char sudoTemplate[10][10] = { "abcghidef","defabcghi","ghidefabc","bcahigefd","efdbcahig","higefdbca","cabighfde","fdecabigh","ighfdecab" };char matrix[9][9];for (int i = 0; i < 9; i++){for (int j = 0; j < 9; j++){matrix[i][j] = sudoTemplate[i][j];}}//六層循環遍歷每一種模板的交換情況//行for(int row1 = 0; row1 < 2; row1++){//12行交換for (int i = 0; i < 9; i++){swapChar(&matrix[1][i], &matrix[2][i]);}for (int row2 = 0; row2 < 6; row2++){if (row2 % 2 == 0){//34行交換for (int i = 0; i < 9; i++){swapChar(&matrix[3][i], &matrix[4][i]);}}else {//45行交換for (int i = 0; i < 9; i++){swapChar(&matrix[5][i], &matrix[4][i]);}}for (int row3 = 0; row3 < 6; row3++){if (row3 % 2 == 0){//67行交換for (int i = 0; i < 9; i++){swapChar(&matrix[6][i], &matrix[7][i]);}}else {//78行交換for (int i = 0; i < 9; i++){swapChar(&matrix[7][i], &matrix[8][i]);}}//列for (int col1 = 0; col1 < 2; col1++){//12列交換for (int i = 0; i < 9; i++){swapChar(&matrix[i][1], &matrix[i][2]);}for (int col2 = 0; col2 < 6; col2++){if (col2 % 2 == 0){//34列交換for (int i = 0; i < 9; i++){swapChar(&matrix[i][3], &matrix[i][4]);}}else {//45列交換for (int i = 0; i < 9; i++){swapChar(&matrix[i][4], &matrix[i][5]);}}for (int col3 = 0; col3 < 6; col3++){if (col2 % 2 == 0){//67列交換for (int i = 0; i < 9; i++){swapChar(&matrix[i][6], &matrix[i][7]);}}else {//78列交換for (int i = 0; i < 9; i++){swapChar(&matrix[i][7], &matrix[i][8]);}}//開始生成全排列int index[8] = { -1,-1,-1,-1,-1,-1,-1,-1 };int pos[9];for (pos[1] = 0; pos[1] < 8; pos[1]++){for (pos[2] = 0; pos[2] < 7; pos[2]++){for (pos[3] = 0; pos[3] < 6; pos[3]++){for (pos[4] = 0; pos[4] < 5; pos[4]++){for (pos[5] = 0; pos[5] < 4; pos[5]++){for (pos[6] = 0; pos[6] < 3; pos[6]++){for (pos[7] = 0; pos[7] < 2; pos[7]++){for (pos[8] = 0; pos[8] < 1; pos[8]++){//計算排列//映射信息存在index中index[pos[1]] = 1;for (int i = 2; i <= 8; i++) {int countPos = 0;for (int j = 0; j < 8; j++){if (index[j] == -1){countPos++;}if (countPos - 1 == pos[i]) {index[j] = i + 1;break;}}}//生成一個終局endchar* end = (char*)malloc(sizeof(char) * 81);for (int i = 0; i < 9; i++){for (int j = 0; j < 9; j++) {if (matrix[i][j] == 'a') {if (end != 0) {end[i * 9 + j] = '2';}}else {if (end != 0) {end[i * 9 + j] = index[matrix[i][j] - 'a' - 1] + '1' - 1;}}}}//將終局存在IO緩沖中if (buf != 0) {buf[buflen++] = end;}countRes++;if (countRes == count) {if (buflen != 0) {write(buf, buflen, true);buflen = 0;}return 0;}if (buflen >= MAX_BUFLEN) {write(buf, buflen, false);buflen = 0;}for (int i = 0; i < 8; i++){index[i] = -1;}}}}}}}}}//}}}}}}return 0; } void swapChar(char* a, char* b) {char temp = *a;*a = *b;*b = temp; } void write(char* buf[], int bufLen, bool fin) {FILE* p = NULL;fopen_s(&p, CREATE_FILENAME, "a+");for (int i = 0; i < bufLen; i++){for (int j = 0; j < 9; j++){for (int k = 0; k < 9; k++){if (p != 0) {fwrite(&buf[i][j * 9 + k], sizeof(char), 1, p);if (k != 8) {fprintf(p, " ");}}}if (!(j == 8 && fin && i == bufLen - 1)) {if (p != 0) {fprintf(p, "\n");}}}if (!fin || i != bufLen - 1) {if (p != 0) {fprintf(p, "\n");}}free(buf[i]);}if (p != 0) {fclose(p);} }

solve.cpp

int solve(char* path) {//讀文件ifstream fin(path, std::ios::binary);int bufLen = static_cast<unsigned int>(fin.seekg(0, std::ios::end).tellg());vector<char> buf(bufLen);fin.seekg(0, std::ios::beg).read(&buf[0], static_cast<std::streamsize>(buf.size()));fin.close();int bufPoint = 0;while (bufPoint < bufLen){int bufPointStart = bufPoint;//取出一個數獨題目int matrix[9][9];vector<int> possibleSet[9][9];for (int i = 0; i < 9; i++){for (int j = 0; j < 9; j++){matrix[i][j] = buf[bufPoint] - '0';bufPoint += 2;possibleSet[i][j].clear();}}//先把答案唯一的空位填上，降低遞歸的復雜度initPossibleSet(matrix, possibleSet);checkPossibleSet(matrix, possibleSet);//將空位的位置存成表，加快查詢速度int nextPos[9][9][2];int startPos[2] = { -1, -1 };for (int i = 8; i >= 0; i--){for (int j = 8; j >= 0; j--){nextPos[i][j][0] = startPos[0];nextPos[i][j][1] = startPos[1];if (matrix[i][j] == 0) {startPos[0] = i;startPos[1] = j;}}}//回溯法求解backTrace(startPos[0], startPos[1], matrix, possibleSet, nextPos);if (bufPoint != bufLen - 1) {bufPoint++;}//存儲解for (int i = 0; i < 9; i++){for (int j = 0; j < 9; j++){buf[bufPointStart] = matrix[i][j] + '0';bufPointStart += 2;}}}//寫文件ofstream fout(SOLVE_FILENAME, std::ios::binary);fout.seekp(0).write(&buf[0], bufLen);fout.close();return 0; } //初始化所有位置的可能的答案的集合 void initPossibleSet(int matrix[9][9], vector<int> possibleSet[9][9]) {for (int i = 0; i < 9; i++){for (int j = 0; j < 9; j++) {updatePossibleSet(matrix, possibleSet, i, j);}} } //更新某一個位置的可能的答案的集合 void updatePossibleSet(int matrix[9][9], vector<int> possibleSet[9][9], int row, int col) {possibleSet[row][col].clear();if (matrix[row][col] == 0){int exist[9];memset(exist, 0, sizeof(exist));for (int k = 0; k < 9; k++){if (matrix[row][k] != 0) {exist[matrix[row][k] - 1] = 1;}if (matrix[k][col] != 0) {exist[matrix[k][col] - 1] = 1;}if (matrix[row / 3 * 3 + k / 3][col / 3 * 3 + k % 3] != 0){exist[matrix[row / 3 * 3 + k / 3][col / 3 * 3 + k % 3] - 1] = 1;}}for (int k = 0; k < 9; k++) {if (exist[k] == 0) {possibleSet[row][col].push_back(k + 1);}}} } //檢查是否有能夠唯一確定的空位 void checkPossibleSet(int matrix[9][9], vector<int> possibleSet[9][9]) {bool stepOut = true;while (stepOut){stepOut = false;for (int i = 0; i < 9; i++){for (int j = 0; j < 9; j++) {if (possibleSet[i][j].size() == 1) {stepOut = true;matrix[i][j] = possibleSet[i][j][0];possibleSet[i][j].clear();for (int k = 0; k < 9; k++){updatePossibleSet(matrix, possibleSet, i, k);updatePossibleSet(matrix, possibleSet, k, j);updatePossibleSet(matrix, possibleSet, i/3*3+k/3, j/3*3+k%3);}}}}} } //檢查數獨解是否正確（DEBUG用） bool checkTrue(int matrix[9][9]) {for (int i = 0; i < 9; i++) {int existR[9];int existC[9];int existB[9];memset(existR, 0, sizeof(existR));memset(existC, 0, sizeof(existC));memset(existB, 0, sizeof(existB));int baseR = 0, baseC = 0;switch (i){case 0:baseR = 0; baseC = 0;break;case 1:baseR = 0; baseC = 3;break;case 2:baseR = 0; baseC = 6;break;case 3:baseR = 3; baseC = 0;break;case 4:baseR = 3; baseC = 3;break;case 5:baseR = 3; baseC = 6;break;case 6:baseR = 6; baseC = 0;break;case 7:baseR = 6; baseC = 3;break;case 8:baseR = 6; baseC = 6;break;default:break;}for (int j = 0; j < 9; j++) {if (matrix[i][j] <= 0 || matrix[i][j] >= 10 ||matrix[j][i] <= 0 || matrix[j][i] >= 10 ||matrix[baseR + j / 3][baseC + j % 3] <= 0 || matrix[baseR + j / 3][baseC + j % 3] >= 10){return false;}if (existC[matrix[j][i] - 1] == 1 || existR[matrix[i][j] - 1] == 1 || existB[matrix[baseR + j / 3][baseC + j % 3] - 1] == 1) {return false;}else {existC[matrix[j][i] - 1] = 1;existR[matrix[i][j] - 1] = 1;existB[matrix[baseR + j / 3][baseC + j % 3] - 1] = 1;}}}return true; } //回溯法求解數獨 bool backTrace(int row, int col, int matrix[9][9], vector<int> possibleSet[9][9], int nextPos[9][9][2]) {if (row == -1 && col == -1) {//已經成功了，打印數組即可return true;}updatePossibleSet(matrix, possibleSet, row, col);for (int k = 0; k < possibleSet[row][col].size(); k++) {//判斷給i行j列放1-9中的任意一個數是否能滿足規則//將該值賦給該空格，然后進入下一個空格matrix[row][col] = possibleSet[row][col][k];if (backTrace(nextPos[row][col][0], nextPos[row][col][1], matrix, possibleSet, nextPos)){return true;}//初始化該空格matrix[row][col] = 0;}return false; }

以上代碼都在visual stdio 2019自帶的代碼分析器中消除了所有警告

六、實際花費的時間

PSP2.1Personal Software Process Stages實際耗時(分鐘)

Planning	計劃	60
Estimate	估計這個任務需要多少時間	10
Development	開發	1200
Analysis	需求分析（包括學習新技術）	60
Design Spec	生成設計文檔	60
Design Review	設計復審（和同事審核設計文檔）	20
Coding Standard	代碼規范（為目前的開發制定合適的規范）	20
Design	具體設計	60
Coding	具體編碼	1800
Code Review	代碼復審	20
Test	測試（自我測試，修改代碼，提交修改）	180
Reporting	報告	80
Test Report	測試報告	30
Size Measurement	計算工作量	20
Postmortem & Process Improvement Plan	事后總結，并提出過程改進計劃	20
	合計	3640

七、總結

???????這此的數獨項目中我印象最深的時解數獨的優化過程，有很多的優化想法，但是因為設計時考慮不周，導致出現了很多次的負優化。程序效率的優化部分我還有很多需要改進的地方。

總結

以上是生活随笔為你收集整理的软件工程基础-个人项目-数独的生成与求解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。