LINK:数独

这道题好难 比DXL模板题要难上不少.

首先 还是考虑将行当做决策 那么 一共有\(9*9*9=729\) 个决策.

考虑列用来填充 需要有的条件为 某个位置能能放一次\(9*9\) 某行放一个x 某列放一个x 某九宫放一个.

那么列数为\(4*9*9=324\)。

考虑1的个数 每一行都有这4种形式 所以一共存在\(4*9*9*9=2916\)个1.

图非常容易建出来 注意答案的输出。(每一次写都相当于学了一遍 什么时候才能学会呢

const int MAXN=3510,maxn=10;
int W=9,n,m,cnt;
int a[maxn][maxn],b[maxn][maxn];
int l[MAXN],r[MAXN],col[MAXN],row[MAXN],u[MAXN],d[MAXN],h[MAXN],s[MAXN],ans[MAXN];
inline void prepare()
{
rep(0,m,i)
{
l[i]=i-1;
r[i]=i+1;
u[i]=d[i]=i;
}
r[m]=0;l[0]=m;
memset(h,-1,sizeof(h));
cnt=m;
}
inline void Link(int x,int y)
{
++s[y];
row[++cnt]=x;col[cnt]=y; u[cnt]=y;d[cnt]=d[y];
u[d[y]]=cnt;d[y]=cnt;
if(h[x]==-1)h[x]=r[cnt]=l[cnt]=cnt;
else
{
r[cnt]=h[x];
l[cnt]=l[h[x]];
r[l[h[x]]]=cnt;
l[h[x]]=cnt;
}
}
inline void remove(int y)
{
r[l[y]]=r[y];l[r[y]]=l[y];
for(int i=d[y];i!=y;i=d[i])//枚举行
{
for(int j=r[i];j!=i;j=r[j])//删除列
{
u[d[j]]=u[j];
d[u[j]]=d[j];
--s[col[j]];
}
}
}
inline void resume(int y)
{
for(int i=u[y];i!=y;i=u[i])
{
for(int j=l[i];j!=i;j=l[j])
{
u[d[j]]=j;
d[u[j]]=j;
++s[col[j]];
}
}
r[l[y]]=y;l[r[y]]=y;
}
inline void dance(int dep)
{
if(!r[0])
{
rep(1,dep-1,i)
{
int cc=(ans[i]-1)%9+1;
int y=(ans[i]-1)/9%9+1;
int x=(ans[i]-1)/9/9+1;
b[x][y]=cc;
}
rep(1,W,i)
{
rep(1,W,j)put_(b[i][j]);
puts("");
}
exit(0);
}
int y=r[0];
for(int i=r[0];i;i=r[i])if(s[i]<s[y])y=i;
remove(y);
for(int i=d[y];i!=y;i=d[i])
{
ans[dep]=row[i];
for(int j=r[i];j!=i;j=r[j])remove(col[j]);
dance(dep+1);
for(int j=l[i];j!=i;j=l[j])resume(col[j]);
}
resume(y);
}
int main()
{
freopen("1.in","r",stdin);
m=324;n=729;prepare();
rep(1,W,i)rep(1,W,j)
{
get(a[i][j]);
rep(1,W,k)
{
if(a[i][j]&&a[i][j]!=k)continue;
int id=(W*(i-1)+(j-1))*W+k;
int w1=(j-1)*W+k;//某一列要有k.
int w2=W*W+(i-1)*W+k;//某一行要有k.
int w3=W*W*2+(i-1)*W+j;//某个位置只能放一次.
int w4=W*W*3+((i-1)/3*3+(j-1)/3)*9+k;
Link(id,w1);Link(id,w2);Link(id,w3);Link(id,w4);
}
}
dance(1);return 0;
}
05-26 19:18