问题描述：给定一个由3*3的方块分割而成的9*9的格子。其中一些格子中填有1~9的数字，其余格子则是空白的。请在空白的的格子填入1~9的数字，使得在每行、每列和每个3*3的方块中，1~9的每个数字都恰好出现一次。
row[i]的二进制代表当前行的状态，如果当前位为1说明该行还没放该数，比如当前row是4，说明数字3还没放，3说明数字1,2还没放。
col[i]，grid[i][j] 同理。
Sudoku POJ - 2676 37. 解数独
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define oo cout<<"!!!"<<endl;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
// headconst int maxn = 1e3+11;char str[maxn][maxn];
int row[maxn],col[maxn],grid[maxn],cnt[maxn],num[maxn],tot;int g(int x,int y)
{return (x/3)*3 + y/3;
}void flip(int x,int y,int z)
{row[x] ^= 1<<z;col[y] ^= 1<<z;grid[g(x,y)] ^= 1<<z;
}bool dfs(int now)
{ if(now == 0)return 1;int tmp = 10,x,y;for(int i = 0;i<9;i++)for(int j = 0;j<9;j++){if(str[i][j] != '0')continue;int val = row[i] & col[j] & grid[g(i,j)];if(!val)return 0;if(cnt[val] < tmp){tmp = cnt[val];x = i, y = j;}}int val = row[x] & col[y] & grid[g(x,y)];for (; val; val -= val&-val) {int z = num[val&-val];str[x][y] = '1' + z;flip(x, y, z);if (dfs(now - 1)) return 1;flip(x, y, z);str[x][y] = '0';} return 0;
}int main()
{int T;cin>>T;for(int i = 0;i < 1<<9; i++)for(int j = i;j;j -= j&-j)cnt[i]++;//记录i的二进制中有多少1for(int i = 0;i<9;i++)num[1<<i] = i;//记录1<<i是移动i位while(T--){for(int i = 0;i<9;i++) scanf("%s",str[i]);for(int i = 0;i<9;i++)row[i] = col[i] = grid[i] = (1<<9)-1;//二进制中位1代表当前位没放该数字tot = 0;for(int i = 0;i<9;i++)for(int j = 0;j<9;j++)if(str[i][j] != '0')flip(i,j,str[i][j] - '1');else tot++;dfs(tot);for(int i = 0;i<9;i++)puts(str[i]);}
}