首页 > 代码库 > 51nod 1211 数独
51nod 1211 数独
数独游戏规则如下：在9 * 9的盘面上有些已知的数字及未知的数字，推理出所有未知的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。 
有些局面存在多个解或无解，这属于不标准的数独。对于不标准的局面，输出No Solution。
Input
第1 - 9行，每行9个数中间用空格分隔，0表示该格子的数未知。Output
如果局面是不标准的，输出No Solution，否则数据具体的解。转化为精确覆盖问题用dlx算法求解
共324列表示每行、列、3x3区域中有且只有每种数字一个，每个位置只能填一个数
共729行表示81个格子，填1~9的所有可能
#include<bits/stdc++.h>const int N=10007;int l[N],r[N],u[N],d[N],rid[N],cid[N],idp=325,n0=325;int stk[1007],stp=0,ed=0;int ds[753][329];int vs[11][11],cs[1007];void del(int mw){ l[r[mw]]=l[mw]; r[l[mw]]=r[mw]; for(int w=d[mw];w!=mw;w=d[w]){ for(int v=r[w];v!=w;v=r[v]){ u[d[v]]=u[v]; d[u[v]]=d[v]; --cs[cid[v]]; } }}void ins(int mw){ l[r[mw]]=r[l[mw]]=mw; for(int w=d[mw];w!=mw;w=d[w]){ for(int v=r[w];v!=w;v=r[v]){ u[d[v]]=d[u[v]]=v; ++cs[cid[v]]; } }}bool dfs(){ if(r[n0]==n0){ if(ed)puts("No Solution"),exit(0); ed=1; for(int i=0;i<stp;++i){ int x=stk[i]-1; vs[x/81+1][x/9%9+1]=x%9+1; } } int mn=100000,mw=0; for(int w=r[n0];w!=n0;w=r[w])if(cs[w]<mn)mn=cs[mw=w]; del(mw); for(int w=d[mw];w!=mw;w=d[w]){ stk[stp++]=rid[w]; for(int v=r[w];v!=w;v=r[v])del(cid[v]); dfs(); for(int v=r[w];v!=w;v=r[v])ins(cid[v]); --stp; } ins(mw); return 0;}int main(){ for(int i=1;i<=9;++i)for(int j=1;j<=9;++j)scanf("%d",vs[i]+j); for(int i=1;i<=9;++i)for(int j=1;j<=9;++j)for(int k=1;k<=9;++k)if(!vs[i][j]||vs[i][j]==k){ int a=(i-1)*81+(j-1)*9+k; ds[a][(i-1)*9+k]=++idp; ds[a][81+(j-1)*9+k]=++idp; ds[a][162+((i-1)/3*3+(j-1)/3)*9+k]=++idp; ds[a][243+(i-1)*9+j]=++idp; } for(int i=1;i<=324;++i){ l[i+1]=i,r[i]=i+1; int p=i; for(int j=1;j<=729;++j)if(int w=ds[j][i]){ d[p]=w,u[w]=p; p=w; ++cs[i]; } u[i]=p,d[p]=i; if(!cs[i])return puts("No Solution"),0; } l[1]=n0,r[n0]=1; for(int i=1;i<=729;++i){ int p=0,p0; for(int j=1;j<=324;++j)if(int w=ds[i][j]){ if(p)r[p]=w,l[w]=p; else p0=w; p=w; rid[w]=i; cid[w]=j; } if(p)r[p]=p0,l[p0]=p; } dfs(); if(!ed)return puts("No Solution"),0; for(int i=1;i<=9;++i){ for(int j=1;j<=9;++j)printf("%d ",vs[i][j]); putchar(10); } return 0;}
51nod 1211 数独
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。