（有点类似于 N 皇后，就是通过递归找可能的解法）

题目：
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

题解：
保存三个状态数组
flag1：每一行，已经选取的数
flag2：每一列，已经选取的数
flag3：每 3 * 3 的块，已经选取的数

可以通过状态压缩来保存状态（已经选取的数）
例，二进制 110010，即选了数组1，4，5

依次考虑每一个空白格的可能填入的数字
如果在对应的 行，列，块 中都没有选过对应的数字
则选取对应的数字，进行递归，判断下一个空白格

直到为所有的空白格找到填法

（官方题解里有一个优化思路是，先判断空白格取值只有一种的，相当于将可以确定的空白格先全部填入对应的数）

代码如下

class Solution {
public:int flag[9][9] = { 0 };int flag1[9] = { 0 };int flag2[9] = { 0 };int flag3[3][3] = { 0 };int res[9][9];bool solve(int f, int flag[9][9], int flag1[9], int flag2[9], int flag3[3][3]) {if(f == 81) {for(int i = 0; i < 9; i++) {for(int j = 0; j < 9; j++) {res[i][j] = flag[i][j] + '0';}}return true;}int ff = f + 1;while(ff < 81 && flag[ff / 9][ff % 9] != 0) ff++;int fflag[9][9];int fflag1[9];int fflag2[9];int fflag3[3][3];for(int i = 0; i < 9; i++) {fflag1[i] = flag1[i];fflag2[i] = flag2[i];fflag3[i / 3][i % 3] = flag3[i / 3][i % 3];for(int j = 0; j < 9; j++) {fflag[i][j] = flag[i][j];}}for(int i = 1; i <= 9; i++) {if(!((flag1[f / 9] >> i) & 1) && !((flag2[f % 9] >> i) & 1) && !((flag3[(f / 9) / 3][(f % 9) / 3] >> i) & 1)) {fflag[f / 9][f % 9] = i;fflag1[f / 9] += (1 << i);fflag2[f % 9] += (1 << i);fflag3[(f / 9) / 3][(f % 9) / 3] += (1 << i);if(solve(ff, fflag, fflag1, fflag2, fflag3)) {return true;}fflag[f / 9][f % 9] = 0;fflag1[f / 9] -= (1 << i);fflag2[f % 9] -= (1 << i);fflag3[(f / 9) / 3][(f % 9) / 3] -= (1 << i);}}return false;}void solveSudoku(vector>& board) {for(int i = 0; i < 9; i++) {for(int j = 0; j < 9; j++) {if(board[i][j] == '.') flag[i][j] = 0;else {flag[i][j] = board[i][j] - '0';flag1[i] += (1 << flag[i][j]);flag2[j] += (1 << flag[i][j]);flag3[i / 3][j / 3] += (1 << flag[i][j]);}   }}int f = 0;while(f < 81 && flag[f / 9][f % 9] != 0) f++;solve(f, flag, flag1, flag2, flag3);for(int i = 0; i < 9; i++) {for(int j = 0; j < 9; j++) {board[i][j] = res[i][j];}}}
};