题目描述：
问题描述：数独（Sudoku）是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个3X3粗线宫内的数字均含1-9，并且不重复。
例如：
输入
输出
输入描述：
包含已知数字的9X9盘面数组[空缺位以数字0表示]
输出描述：
完整的9X9盘面数组
示例：
输入：
0 9 2 4 8 1 7 6 3 4 1 3 7 6 2 9 8 5 8 6 7 3 5 9 4 1 2 6 2 4 1 9 5 3 7 8 7 5 9 8 4 3 1 2 6 1 3 8 6 2 7 5 9 4 2 7 1 5 3 8 6 4 9 3 8 6 9 1 4 2 5 7 0 4 5 2 7 6 8 3 1
输出：
5 9 2 4 8 1 7 6 3 4 1 3 7 6 2 9 8 5 8 6 7 3 5 9 4 1 2 6 2 4 1 9 5 3 7 8 7 5 9 8 4 3 1 2 6 1 3 8 6 2 7 5 9 4 2 7 1 5 3 8 6 4 9 3 8 6 9 1 4 2 5 7 9 4 5 2 7 6 8 3 1
解题思路：
本题是数独问题，采用深度优先遍历法，一个个输入，若某个点没有合适数值，则返回到上个点重新找合适点，直到所有点都完美填充。
VaildExist函数用来判断该位置是否能放置数值m，数独中某行某列某个3*3的方针不能有重复数字；Find函数找寻数独表中的下一个0点位置，将row和col刷新，若没0点了，则说明填充完毕了；DFS是深度优先遍历法的主函数，用flag表示当前数据填充是否合适，col满9则row进1，即进入下一行，用Find判断还有0点没，若还有，则将row和col刷新到最近的0点位置，然后1-9依次填充，若有合适值填充进去，则继续执行DFS，DFS如果返回的是错误结果，那之前填充的数值要换掉，继续找下一个合适的，若找完都没有合适的，就再返回到上一个填充数的位置并进行数值更换，以此类推，直到某次DFS返回的是true，则表示完成数独表的填充。
测试代码：
#include<iostream> #include<vector> #include<string> using namespace std; // 判断该位置是否能放置m，即同行同列同3*3方阵是否存在m bool ValidExist(vector<vector<int>> sudoku, int i, int j, int m) { //判断所在行 for (int k = 0; k < 9; ++k) { if (sudoku[i][k] == m) return false; } //判断所在列 for (int k = 0; k < 9; ++k) { if (sudoku[k][j] == m) return false; } //判断所在3*3方阵 int Lrow = i / 3 * 3; int Lcol = j / 3 * 3; for (int row = Lrow; row < Lrow + 3; ++row) for (int col = Lcol; col < Lcol + 3; ++col) { if (sudoku[row][col] == m) return false; } return true; } // 找寻数独表的0点 bool Find(vector<vector<int>> sudoku, int &row, int &col) { int i, j; while (row < 9 && col < 9) { if (sudoku[row][col] == 0) return true; else { col++; if (col == 9) { col = 0; row++; } } } return false; } // 深度优先遍历法 bool DFS(vector<vector<int>> &sudoku, int row, int col) { bool flag = false; if (col > 8) { col = col % 9; row++; } // 如果没有0点了，则表示完成了填充 if (!Find(sudoku, row, col)) return true; // 从1开始赋值，若填写某个数值后，其他0点位置无法找到合适值，则数值递进再次尝试 for (int m = 1; m <= 9; m++) { if (ValidExist(sudoku, row, col, m)) { sudoku[row][col] = m; flag= DFS(sudoku, row, col+1); if (flag == false) continue; else return true; } } // 若没有合适值，将当前位置置0，返回false，使上个填充数据再更换其他数值尝试 if (flag == false) { sudoku[row][col] = 0; return false; } } int main() { vector<vector<int>> sudoku(9, vector<int>(9, 0)); for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) cin >> sudoku[i][j]; DFS(sudoku, 0, 0); for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) cout << sudoku[i][j] << " "; cout << endl; } return 0; }
