思路：記錄每行每列每一個宮已經出現的數字就可以。數據比較弱

另外POJ 3074 3076 必須用剪枝策略。但實現較麻煩，還是以后學了DLX再來做吧

//Accepted 160K 0MS #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N =15; char sudo[N][N]; bool visr[N][N],visc[N][N],visg[N][N]; int pos[N][N]; bool flag; void print() {for(int i=1;i<=9;i++)printf("%s\n",sudo[i]+1); } void dfs(int x,int y) {if(y==10){dfs(x+1,1);return ;}if(x==10){print();flag=1;return ;}if(sudo[x][y]!='0'){dfs(x,y+1);return ;}for(int i=1;i<=9&&!flag;i++){if(visr[x][i]==0&&visc[y][i]==0&&visg[pos[x][y]][i]==0){sudo[x][y]='0'+i;visc[y][i]=visr[x][i]=visg[pos[x][y]][i]=1;dfs(x,y+1);sudo[x][y]='0';visc[y][i]=visr[x][i]=visg[pos[x][y]][i]=0;}} } void ini() {flag = false ;memset(visr,0,sizeof(visr));memset(visc,0,sizeof(visc));memset(visg,0,sizeof(visg)); } int main() {for(int i=1;i<=9;i++)for(int j=1;j<=9;j++)pos[i][j]=((j-1)/3+1)+3*((i-1)/3);int T;scanf("%d",&T);for(int cas=1;cas<=T;cas++){printf("Scenario #%d:\n",cas);ini();for(int i=1;i<=9;i++)scanf("%s",sudo[i]+1);for(int i=1;i<=9;i++)for(int j=1;j<=9;j++){int val=sudo[i][j]-'0';visr[i][val]=true;visc[j][val]=true;visg[pos[i][j]][val]=true;}dfs(1,1);puts("");}return 0; }

轉載于:https://www.cnblogs.com/bhlsheji/p/5137909.html

總結

以上是生活随笔為你收集整理的POJ 2676/2918 数独（dfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。