题目如下所示：
编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。

Note:

给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。

---

代码如下所示：

#include <iostream>
#include <algorithm>
#include <vector>using namespace std;class Solution {
public: void solveSudoku(vector<vector<char>>& board) {Dfs(board, 0);}private:bool flag = false;void Dfs(vector<vector<char>>& board, int n)  // 深搜思想{// 判断上一个数据是否满足条件（ 横、竖、九宫格 ）if (n > 0 && n <= 81) if (!JudgeIsNoWant(board, n - 1)) return;if (n >= 81) 	//　到最后则返回{flag = true;return;}int x = n / 9;  // 定位当前数的位置int y = n % 9;if (board[x][y] != '.')		// 只对 数字为 0 的元素进行搜索Dfs(board, n + 1);else {// 每一个空位有 10 种可能性for (int i = 1; i < 10; i++) {board[x][y] = i + 48;	// 当前的数字放入到数组之中，Dfs(board, n + 1);		// 进行下一个位置的搜索if (flag == true) return;board[x][y] = '.';	// 不满足条件，重新清 0}}}bool JudgeIsNoWant(vector<vector<char>>& board, int n)	// n 表示是当前的第几个数{int x = n / 9;  		// 定位当前数的位置（数据在二维数组中的位置）int y = n % 9;for (size_t i = 0; i < 9; i++)  // 横竖 搜索{if (board[x][i] == board[x][y] && i != y) return false;if (board[i][y] == board[x][y] && i != x) return false;}// 九宫格 搜索	这里需要一个小小的算法，确定九宫格的位置for (int i = x / 3 * 3; i < x / 3 * 3 + 3; i++)for (int j = y / 3 * 3; j < y / 3 * 3 + 3; j++)if (board[i][j] == board[x][y] && (i != x || j != y))return false;return true;}
};int main() {/*世界上最难的数独:0 0 5 3 0 0 0 0 08 0 0 0 0 0 0 2 00 7 0 0 1 0 5 0 04 0 0 0 0 5 3 0 00 1 0 0 7 0 0 0 60 0 3 2 0 0 0 8 00 6 0 5 0 0 0 0 90 0 4 0 0 0 0 3 00 0 0 0 0 9 7 0 0*/vector<vector<char>> vec(9);vec[0] = { '.', '.', '5', '3', '.', '.', '.','.', '.' };vec[1] = { '8', '.', '.', '.', '.' ,'.', '.','2', '.' };vec[2] = { '.', '7', '.', '.', '1' ,'.', '5','.', '.' };vec[3] = { '4', '.', '.', '.', '.' ,'5', '3','.', '.' };vec[4] = { '.', '1', '.', '.', '7' ,'.', '.','.', '6' };vec[5] = { '.', '.', '3', '2', '.' ,'.', '.','8', '.' };vec[6] = { '.', '6', '.', '5', '.' ,'.', '.','.', '9' };vec[7] = { '.', '.', '4', '.', '.' ,'.', '.','3', '.' };vec[8] = { '.', '.', '.', '.', '.' ,'9', '7','.', '.' };(new Solution)->solveSudoku(vec);return 0;
}