求解数独问题的基本方法是在(dfs)的过程中剪枝，下面这几种方法的剪枝强度递增
朴素方法
通过数组记录每行、每列、每个九宫格中已经填过的数字，从左上角的空格开始(dfs)，填入所在行、列和九宫格中都没有出现过的数字
相关题目：hdu1426 Sudoku Killer
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<ctime>
#include<algorithm>
#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
const int N=9;
int R[N+5][N+5],C[N+5][N+5],S[N][N][N+5];
int b[N+5][N+5];
char a[N];
bool dfs(int x,int y){
if(y==N){
y=0;
x++;
}
if(x==N) return true;
if(b[x][y]){
if(dfs(x,y+1)) return true;
}
else{
for(int num=1;num<=N;num++){
if(!R[x][num] && !C[y][num] && !S[x/3][y/3][num]){
R[x][num]=1;
C[y][num]=1;
S[x/3][y/3][num]=1;
b[x][y]=num;
if(dfs(x,y+1)) return true;
b[x][y]=0;
R[x][num]=0;
C[y][num]=0;
S[x/3][y/3][num]=0;
}
}
}
return false;
}
int main(void){
bool first=true;
while(scanf("%s",a)!=EOF){
memset(R,0,sizeof(R));
memset(C,0,sizeof(C));
memset(S,0,sizeof(S));
if(a[0]=='?') b[0][0]=0;
else{
b[0][0]=a[0]-'0';
R[0][b[0][0]]=1;
C[0][b[0][0]]=1;
S[0][0][b[0][0]]=1;
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(i==0 && j==0) continue;
scanf("%s",a);
if(a[0]=='?'){
b[i][j]=0;
}
else{
b[i][j]=a[0]-'0';
R[i][b[i][j]]=1;
C[j][b[i][j]]=1;
S[i/3][j/3][b[i][j]]=1;
}
}
}
if(dfs(0,0)){
if(first) first=false;
else printf("
");
for(int i=0;i<N;i++){
printf("%d",b[i][0]);
for(int j=1;j<N;j++){
printf(" %d",b[i][j]);
}
printf("
");
}
}
}
return 0;
}
二进制压缩优化
1.通过二进制压缩记录出现过的数字，数位上为(1)表示这个数字还没有使用过，通过(lowbit)操作得到二进制表示的状态下所有可填的数字
2.每次(dfs)时遍历所有格子，选择候选数字数目最小的空格（二进制中(1)的个数最少）填数字
相关题目：hdu3111 Sudoku
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<ctime>
#include<algorithm>
#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
const int N=9,maxx=1<<N;
int T,R[15],C[15],S[5][5];
int ones[maxx+10],number[maxx+10];
char a[N+5][N+5],b[N];
void init(){
for(int i=0;i<maxx;i++){
int s=0;
for(int j=i;j;j-=lowbit(j)){
s++;
}
ones[i]=s;
}
for(int i=0;i<N;i++) number[1<<i]=i;
}
void init2(){
for(int i=0;i<N;i++){
R[i]=C[i]=maxx-1;
for(int j=0;j<N;j++){
S[i/3][j/3]=maxx-1;
}
}
}
int sum(int x,int y){
return R[x]&C[y]&S[x/3][y/3];
}
bool dfs(int rest){
if(rest==0) return true;
int x,y,mini=10;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(a[i][j]=='?'){
int t=ones[sum(i,j)];
if(mini>t){
x=i;
y=j;
mini=t;
}
}
}
}
int X=sum(x,y);
for(int i=X;i;i-=lowbit(i)){
R[x]-=lowbit(i);
C[y]-=lowbit(i);
S[x/3][y/3]-=lowbit(i);
a[x][y]='1'+number[lowbit(i)];
if(dfs(rest-1)) return true;
a[x][y]='?';
R[x]+=lowbit(i);
C[y]+=lowbit(i);
S[x/3][y/3]+=lowbit(i);
}
return false;
}
int main(void){
init();
scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
if(cas!=1) scanf("%s",b);
int cnt=0;
init2();
for(int i=0;i<N;i++){
scanf("%s",a[i]);
for(int j=0;j<N;j++){
if(a[i][j]=='?'){
cnt++;
}
else{
int bit=a[i][j]-'1';
R[i]-=1<<bit;
C[j]-=1<<bit;
S[i/3][j/3]-=1<<bit;
}
}
}
if(cas!=1) printf("---
");
if(dfs(cnt)){
for(int i=0;i<N;i++){
printf("%s
",a[i]);
}
}
else{
printf("impossible
");
}
}
return 0;
}
从分支最少的部分开始搜索（16*16数独）
1.如果一个位置只能填一个数字，那么就填上这个数字
2.枚举每一个数字，判断在每行、每列、每个十六宫格中有没有可以填的地方。如果只有一个地方可以填，就填上这个数字，如果没有位置可以填，直接回溯
3.选取可能填的数字最少的格子，枚举所有情况进行(dfs)
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<ctime>
#include<algorithm>
#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
const int N=16;
int num,a[N+5][N+5],table[N+5][N+5];
char s[N+5];
//在某个位置填入数字，同时更新填入这个数字之后的影响
void put_in(int x,int y,int k){
num++;
a[x][y]=k;
table[x][y]|=1<<k;
for(int i=0;i<N;i++){
table[x][i]|=1<<k;
table[i][y]|=1<<k;
}
int r=x/4*4;
int c=y/4*4;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
table[r+i][c+j]|=1<<k;
}
}
}
int _count(int x){
for(int i=0;x;i++){
if(x&1){
if(x>>1==0) return i;
return -1;
}
x>>=1;
}
return -1;
}
int row(int x,int k){
int t=-1;
for(int y=0;y<N;y++){
if(a[x][y]==k) return -1;
if(a[x][y]>=0) continue;
if((table[x][y]&1<<k)==0){
if(t!=-1) return -1;
t=y;
}
}
if(t!=-1) return t;
return -2;
}
int col(int y,int k){
int t=-1;
for(int x=0;x<N;x++){
if(a[x][y]==k) return -1;
if(a[x][y]>=0) continue;
if((table[x][y]&1<<k)==0){
if(t!=-1) return -1;
t=x;
}
}
if(t!=-1) return t;
return -2;
}
void cube(int r,int c,int k,int& x,int& y){
x=-2;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(a[r+i][c+j]==k){
x=-1;
return;
}
if(a[r+i][c+j]>=0) continue;
if((table[r+i][c+j]&1<<k)==0){
if(x!=-2){
x=-1;
return;
}
x=i;
y=j;
}
}
}
}
//计算一个位置中已经填入的数字个数
int cal(int x){
int cnt=0;
while(x){
if(x&1) cnt++;
x>>=1;
}
return cnt;
}
bool dfs(){
if(num==256) return true;
//判断是否存在一个位置，只能填一个数字
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(a[i][j]>=0) continue;
int k=_count(table[i][j]);
if(k!=-1) put_in(i,j,k);
}
}
//判断某行是否只能填一个数字
for(int i=0;i<N;i++){
for(int k=0;k<N;k++){
int j=row(i,k);
if(j==-2) return false;
if(j!=-1) put_in(i,j,k);
}
}
//判断某列是否只能填一个数字
for(int j=0;j<N;j++){
for(int k=0;k<N;k++){
int i=col(j,k);
if(i==-2) return false;
if(i!=-1) put_in(i,j,k);
}
}
//判断某个十六宫格是否只能填一个数字
for(int i=0;i<N;i+=4){
for(int j=0;j<N;j+=4){
for(int k=0;k<N;k++){
int x,y;
cube(i,j,k,x,y);
if(x==-2) return false;
if(x!=-1) put_in(i+x,j+y,k);
}
}
}
if(num==256) return true;
//寻找可以填的数字最少的格子开始搜索
int t_num,t_table[N+5][N+5],t_a[N+5][N+5];
t_num=num;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
t_table[i][j]=table[i][j];
t_a[i][j]=a[i][j];
}
}
int mx,my,mn=16;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(a[i][j]>=0) continue;
int r=16-cal(table[i][j]);
if(r<mn){
mn=r;
mx=i;
my=j;
}
}
}
for(int k=0;k<N;k++){
if((table[mx][my]&1<<k)==0){
put_in(mx,my,k);
if(dfs()) return true;
num=t_num;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
a[i][j]=t_a[i][j];
table[i][j]=t_table[i][j];
}
}
}
}
return false;
}
int main(void){
while(scanf("%s",s)!=EOF){
num=0;
memset(table,0,sizeof(table));
for(int j=0;j<N;j++){
if(s[j]!='-'){
put_in(0,j,s[j]-'A');
}
else a[0][j]=-1;
}
for(int i=1;i<N;i++){
scanf("%s",s);
for(int j=0;j<N;j++){
if(s[j]!='-'){
put_in(i,j,s[j]-'A');
}
else a[i][j]=-1;
}
}
if(dfs()){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
printf("%c",a[i][j]+'A');
}
printf("
");
}
}
}
return 0;
}