题意：解数独
分析：
完整的数独有四个充要条件：
1.每个格子都有填数字
2.每列都有1~9中的每个数字
3.每行都有1~9中的每个数字
4.每个9宫格都有1~9中的每个数字
可以转化成精确覆盖问题。每行表示一个格子的一种填法，1~81列表示这个格子的位置，82~162列表示这是哪一行的什么数字，163~243列表示这是哪一列的什么数字，244~324列表示这是哪一个九宫格里的什么数字。每行都把四个1填入这四个区间里的对应位置。最后求出这个01矩阵的精确覆盖就是解。
对于已经确定的点 我们就直接建一行 对于没有确定的点我们就 建k行(k<=9)，这样说如果在该行该列或者该3*3的矩阵中存在该数字 则对应的该数字所在的行就没有必要建立了
这样跑一次dlx精确覆盖就ok了
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <string.h>
using namespace std;
const int M=****; struct node{
int c,x,y,k;
};
struct DLX
{
int n,sz;
int S[**];
int row[M],col[M];
int L[M],R[M],U[M],D[M];
int ans[][];
int X[M],Y[M],Cnt[M];
void init(int n)
{
this->n=n;
for(int i=; i<=n; i++)
{
U[i]=i;D[i]=i;
L[i]=i-; R[i]=i+;
}
R[n]=;L[]=n;
sz=n+;
memset(S,,sizeof(S));
}
void addRow(int r,vector<node>columns)
{
int first=sz;
for(int i=; i<columns.size();i++)
{
int c=columns[i].c; X[sz]=columns[i].x; Y[sz]=columns[i].y; Cnt[sz]=columns[i].k;
L[sz]=sz-;
R[sz]=sz+;
D[sz]=c; U[sz]=U[c];
D[U[c]]=sz;U[c]=sz;
row[sz]=r;col[sz]=c;
S[c]++;sz++;
}
R[sz-]=first; L[first]=sz-;
}
#define FOR(i,A,s) for(int i=A[s]; i!=s; i=A[i])
void remove(int c)
{
L[R[c]]=L[c];
R[L[c]]=R[c];
FOR(i,D,c)
FOR(j,R,i)
{
U[D[j]]=U[j];D[U[j]]=D[j];--S[col[j]];
}
}
void restore(int c)
{
FOR(i,U,c)
FOR(j,L,i)
{
++S[col[j]];U[D[j]]=j;D[U[j]]=j;
}
L[R[c]]=c;
R[L[c]]=c;
}
bool dfs(int d)
{
if(R[]==)return true;
else
{
int num=R[];
FOR(i,R,)
{
if(S[i]==) return false;
if(S[num]>S[i])
{
num=i;
}
}
remove(num);
FOR(i,D,num)
{
ans[X[i]][Y[i]]=Cnt[i];
FOR(j,R,i)remove(col[j]);
if(dfs(i+))
{
return true;
}
FOR(j,L,i)restore(col[j]);
}
restore(num);
return false;
}
}
}Link;
bool hasr[][],hasc[][],hasp[][];
char str[];
vector<node> colum;
int main()
{
while(scanf("%s",str)==&&str[]!='e')
{
memset(hasr,false,sizeof(hasr));
memset(hasc,false,sizeof(hasc));
memset(hasp,false,sizeof(hasp));
for(int i=; i<; i++)
for(int j=; j<; j++)
{
if(str[i*+j]!='.')
{
int k=str[i*+j]-'';
hasr[i][k]=true;
hasc[j][k]=true;
hasp[i/ *+j/][k]=true;
}
}
int m=**;
int n=;
Link.init(m);
for(int i=; i<; i++)
for(int j=; j<; j++)
{
int k=;
if(str[i*+j]!='.')
k=str[i*+j]-'';
if(k!=)
{
n++;
colum.clear();
node dot;
dot.k=k;
dot.x=i;
dot.y=j;
dot.c=i*+j+;
colum.push_back(dot);
dot.c=+i*+k;
colum.push_back(dot);
dot.c=+j*+k;
colum.push_back(dot);
dot.c=+(i/*+j/)*+k;
colum.push_back(dot);
Link.addRow(n,colum);
}else {
node dot;
dot.x=i;dot.y=j;
for(int k=; k<=; k++)
{
if(hasr[i][k]==false &&hasc[j][k]==false && hasp[i/*+j/][k]==false)
{
dot.k=k;
colum.clear();
n++;
dot.c=i*+j+;
colum.push_back(dot);
dot.c=+i*+k;
colum.push_back(dot);
dot.c=+j*+k;
colum.push_back(dot);
dot.c=+(i/*+j/)*+k;
colum.push_back(dot);
Link.addRow(n,colum);
}
} } }
Link.dfs();
for(int i=; i<;i++)
for(int j=; j<; j++)
printf("%d",Link.ans[i][j]);
puts("");
}
return ;
}