C++ 完美破解九宫格（数独）游戏

看到CSDN上有位大神用C#写了一个破解数独的程序（点击打开链接），不过我对C#也不懂，比较喜欢C++，就用标准C++也写了一个，希望各位喜欢。三纯程序，纯控制台程序，纯各人爱好，纯算法程序，无win API。基本思路与之前那个类似，采用brute force加剪枝，找到第一个符合条件的情况就立即退出不再查找。一般一个合格的数独只有唯一解，如果你的数独多解的话，那也就不叫数独了。

代码如下：

#include <iostream>#include <deque>using namespace std;const int MAX_SIZE = 9;// 九宫格struct Pos {Pos(int x, int y) : row(x), col(y) {};int row;int col;};typedef deque <Pos> qpos;qpos Q;// 记录要放置数字的位置// 九宫格数组，0表示玩家要放置数字的位置int sudoku[MAX_SIZE][MAX_SIZE] = {{0, 0, 3, 0, 5, 0, 0, 0, 9},{0, 0, 0, 1, 0, 0, 0, 2, 5},{0, 8, 0, 0, 3, 7, 0, 0, 0},{0, 0, 0, 0, 0, 8, 0, 9, 7},{2, 0, 0, 0, 6, 0, 0, 0, 4},{9, 4, 0, 0, 0, 0, 8, 0, 1},{0, 0, 0, 6, 9, 0, 4, 0, 0},{8, 0, 0, 0, 0, 5, 0, 0, 0},{6, 0, 0, 0, 1, 0, 9, 0, 0},};void printSudoku(){cout << "-------------------------" << endl;for (int i = 0; i < MAX_SIZE; i++) {for (int j = 0; j <MAX_SIZE; j++) {if (j % 3 == 0) {cout << "| ";}cout << sudoku[i][j] << " ";}cout << "| ";cout << endl;if ( (i+1) % 3 == 0 ) {cout << "-------------------------" << endl;}}}bool check(Pos p, int n){int cur_row = p.row;int cur_col = p.col;// 验证行列是否合格for (int i = 0; i < MAX_SIZE; i++) {if (n == sudoku[i][cur_col] || n == sudoku[cur_row][i]) {return false;}}// 验证九宫格内是无复生数字int grid_row = ( cur_row / 3 ) * 3;int grid_col = ( cur_col / 3 ) * 3;for (int i = 0; i < 3; i++) {if (n == sudoku[grid_row][i + grid_col] || n == sudoku[grid_row + i][grid_col]) {return false;}}return true;}bool place(qpos & Q){// 递归结束条件为没有要断续放置数字的位置if (Q.empty()) {printSudoku();return true;}Pos cur(Q.front().row, Q.front().col);// 当前需要放置的位置信息Q.pop_front();for (int i = 1; i <= 9; i++) {// 从1到9轮流尝试if ( check(cur, i) ) {sudoku[cur.row][cur.col] = i;// 放置数字i到当前位置if ( !place(Q) ) {// 放置下一位置// 下一位置放置失败，则在当前位置尝试放置下一个isudoku[cur.row][cur.col] = 0;// 将当前位置值重置} else {// 下一位置放置成功return true;}}}Q.push_front(cur);//当前位置不论怎么放置数字，下一位置都无法放置成功，// 重新插入该位置信息，返回上一级放置位置return false;}int main(){// Q中保存需要放置数字的位置for (int i = 0; i < MAX_SIZE; i++) {for (int j = 0; j < MAX_SIZE; j++) {if (0 == sudoku[i][j]) {Q.push_back(Pos(i, j));}}}place(Q);return 0;}

我也来个运行截图：

上面的程序只会打印出一种符合的数独，如果你想将所以可能的情况都打印出来怎么办，一般情况下，合格的数独都只有一种解，那万一有一个不合格的数独，你又想知道它的全部解，那么，你可以用下面的方法：

/*** 打印所有符合条件的情况*/void place2(qpos & Q){// 递归结束条件为没有要断续放置数字的位置if (Q.empty()) {printSudoku();return;}Pos cur(Q.front().row, Q.front().col);// 当前需要放置的位置信息Q.pop_front();for (int i = 1; i <= 9; i++) {// 从1到9轮流尝试if ( check(cur, i) ) {sudoku[cur.row][cur.col] = i;// 放置数字i到当前位置place2(Q);sudoku[cur.row][cur.col] = 0;// 将当前位置值重置}}Q.push_front(cur);// 重新插入该位置信息，返回上一级放置位置}