（有点类似于 N 皇后，就是通过递归找可能的解法）
题目：
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
题解：
保存三个状态数组
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<vector<char>>& 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];
}
}
}
};