剛剛看到很多人都用DFS+剪枝做數(shù)獨(dú)。。 頓時(shí)不爽了， 我家DLX 何在。。。

不過想想確實(shí)這個(gè)搜索剪枝真的很多，不過怎么說還是DLX 快...

#include <stdio.h> #include <string.h> #include <iostream> using namespace std; #define N 300000 #define INF 0x3fffffffchar g[10][10]; int ans[1000]; int u[5000],d[5000],r[5000],l[5000],num[5000],H[1000],save[5000],save1[5000]; int flag,head; const int n=729; const int m=324; int id;void prepare() {for(int i=0;i<=m;i++){num[i]=0;d[i]=i;u[i]=i;r[i]=i+1;l[i+1]=i;}r[m]=0;memset(H,-1,sizeof(H)); // 記錄每一行的第一個(gè)點(diǎn) }void link(int tn,int tm) {id++;save1[id]=tn; // 記錄行++num[save[id]=tm]; // 記錄列d[id]=d[tm];u[ d[tm] ]=id;u[id]=tm;d[tm]=id;if(H[tn]<0) H[tn]=l[id]=r[id]=id;else{r[id]=r[H[tn]];l[ r[H[tn]] ]=id;r[ H[tn] ]=id;l[id]=H[tn];} }void build() {id=m;int sum;prepare();int tn=0;for(int i=1;i<=81;i++){for(int j=1;j<=9;j++){++tn;link(tn,i);}}sum=81;/////for(int i=1;i<=9;i++) // 每一行 {tn=(i-1)*81;for(int k=1;k<=9;k++){int tk=tn+k;for(int j=1;j<=9;j++){link(tk,sum+(i-1)*9+k);tk+=9;}}}sum+=81;///for(int i=1;i<=9;i++){tn=(i-1)*9;for(int k=1;k<=9;k++){int tk=tn+k;for(int j=1;j<=9;j++){link(tk,sum+(i-1)*9+k);tk+=81;}}}sum+=81;/int tt=0;for(int i1=1;i1<=3;i1++){for(int j1=1;j1<=3;j1++){tn=(i1-1)*81*3+9*3*(j1-1);for(int k=1;k<=9;k++){++tt;int tk;for(int i=1;i<=3;i++){for(int j=1;j<=3;j++){tk=tn+(i-1)*81+9*(j-1)+k;link(tk,sum+tt);}}}}} }void remove(int s) {l[ r[s] ]=l[s];r[ l[s] ]=r[s];for(int i=d[s];i!=s;i=d[i])for(int j=r[i];j!=i;j=r[j]){u[d[j]]=u[j];d[u[j]]=d[j];num[save[j]]--;} }void resume(int s) {r[l[s]]=s;l[r[s]]=s;for(int i=u[s];i!=s;i=u[i])for(int j=l[i];j!=i;j=l[j]){u[d[j]]=j;d[u[j]]=j;num[save[j]]++;} }void dfs(int s) {if(flag) return ;if(r[head]==head){flag=1;for(int i=0;i<s;i++){int ti,tj,tk;int tans=save1[ans[i]]-1;ti= (tans)/81+1;tj= (tans%81)/9+1;;tk= (tans%81)%9+1;//printf("<%d %d> ",ti,tj);g[ti][tj]=tk+'0';}return ;}int mi=INF,tu;for(int i=r[head];i!=head;i=r[i])if(mi>num[i]){mi=num[i];tu=i;}remove(tu);for(int i=d[tu];i!=tu;i=d[i]){for(int j=r[i];j!=i;j=r[j])remove(save[j]);ans[s]=i;dfs(s+1);for(int j=l[i];j!=i;j=l[j])resume(save[j]);}resume(tu); }int main() {int fflag=0;char tt;while(cin>>tt){if(fflag==1){printf("\n");}fflag=1;build();int tu=0;for(int i=1;i<=9;i++){for(int j=1;j<=9;j++){if(i==1&&j==1)g[i][j]=tt;elsecin>>g[i][j];if(g[i][j]!='?'){int kk=g[i][j]-'0';remove( save[ H[tu+kk] ] );for(int i1=r[ H[tu+kk] ];i1 != H[tu+kk];i1=r[i1]){remove( save[i1] );}}tu+=9;}}flag=0;dfs(0);for(int i=1;i<=9;i++){for(int j=1;j<9;j++)printf("%c ",g[i][j]);printf("%c",g[i][9]);printf("\n");}}return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/chenhuan001/archive/2013/04/10/3012094.html

總結(jié)

以上是生活随笔為你收集整理的HDU 1426(数独)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。