????? 大學時，對數獨比較有一點興趣，后來參加了一次學校組織的數獨比賽，可惜結果不佳。最后本程序猿不服，突發奇想，準備自己寫一個程序，解決數獨問題。

?????? 思路也很簡單，遍歷，每碰到一個空位，則從1到9逐個試探，填完之后先判定所填數字是否有效，然后判斷新填完后的數獨是否可解。

????? 先來一個函數，判斷數獨是否有效。代碼如下

/* 檢測一個數獨是否有效，即在行，列，或小九宮格中出現重復數字，空位用-1代替 */ //bool used[9] 用于記錄數字是否出現過 //輔助函數，檢測一個數字是否出現過 bool ChechNum(const int num, bool used[9]) { //沒出現過返回true，否則返回falseif (num == -1) return true;if (used[num - 1]) return false;else {used[num - 1] = true;return true;} }bool IsSudoValid(vector<vector<int>>& board) {bool used[9];for (int i = 0; i < 9; ++i) {fill(used, used + 9, false); //初始化輔助數組for (int j = 0; j < 9; ++j) { //檢查行if (!ChechNum(board[i][j], used))return false;}fill(used, used + 9, false);for (int j = 0; j < 9; ++j) { //檢測列if (!ChechNum(board[j][i], used))return false;}}for(int r=0;r<3;++r) //檢查九個小九宮格for (int c = 0; c < 3; ++c) { //c,j，代表數列；r,i代表行fill(used, used + 9, false);for (int i = 3 * r; i < r * 3+3; ++i)for (int j = 3 * c; j < c * 3+3; ++j)if (!ChechNum(board[i][j], used))return false;}return true; }

?????? 再來一個函數，判斷位置(x,y)所填的數，是否合法

//檢測位置（x,y）是否合法 bool isVliad(vector<vector<int>>& board, int x, int y) {for (int row = 0; row < 9; ++row) { //檢查y列if (row != x && board[row][y] == board[x][y])return false;}for (int col = 0; col < 9; ++col) { //檢查x行if (col != y && board[x][col] == board[x][y])return false;}for (int row = 3 * (x / 3); row < 3 * (x / 3 + 1); ++row)for (int col = 3 * (y / 3); col < 3 * (y / 3 + 1); ++col)if ((row != x || col != y) && board[row][col] == board[x][y])return false;return true; }

?????? 最后一個函數，求解數獨

bool solveSudoKu(vector<vector<int>>& sudo) {for (int row = 0;row < 9; ++row) for (int col = 0; col < 9; ++col) {if (sudo[row][col] == -1) {for (int i = 1; i < 10; ++i) {sudo[row][col] = i;if (isVliad(sudo,row,col) && solveSudoKu(sudo))return true;sudo[row][col] = -1;}return false;}}return true; }

??????? 驗證函數

void test() {vector<vector<int>> suDoKu;suDoKu.push_back({ 5, 3,-1, -1, 7,-1, -1,-1,-1 });suDoKu.push_back({ 6,-1,-1, 1,-1, 5, -1,-1,-1 });suDoKu.push_back({ -1, 9, 8, -1,-1,-1, -1, 6,-1 });suDoKu.push_back({ 8,-1,-1, -1, 6,-1, -1,-1, 3 });suDoKu.push_back({ 4,-1,-1, 8,-1, 3, -1,-1, 1 });suDoKu.push_back({ 7,-1,-1, -1, 2,-1, -1,-1, 6 });suDoKu.push_back({ -1, 6,-1, -1,-1,-1, 2, 8,-1 });suDoKu.push_back({ -1,-1,-1, 4, 1, 9, -1,-1, 5 });suDoKu.push_back({ -1,-1,-1, -1, 8,-1, -1, 7, 9 });if(IsSudoValid(suDoKu)){cout << "數獨有效！" << endl;}else {cout << "數獨無效！" << endl;}solveSudoKu(suDoKu);for (auto vec : suDoKu) {for (auto value : vec)printf("%2d\t", value);printf("\n");} }

??????? 最終執行test()函數即可得出結果。如圖所示

總結

以上是生活随笔為你收集整理的c/c++ 求解数独的全部內容，希望文章能夠幫你解決所遇到的問題。

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