題意：標準的一道數獨題

DFS做法：

將橫縱九宮格里的數字用位運算狀態壓縮，且可以通過邏輯或來確定總共有哪些數字被選擇了，很方便也很快，代碼如下

#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <ctime> #include <algorithm> #include <iostream> #include <sstream> #include <string> #define oo 0x13131313 using namespace std; char MAP[30][30]; int ANS[30][30]; int x[30],y[30],z[30]; int nx[30]={0,1,1,1,4,4,4,7,7,7}; int ny[30]={0,1,4,7,1,4,7,1,4,7}; int nn[20][20]; void init() {freopen("a.in","r",stdin);freopen("a.out","w",stdout); } void input() {memset(x,0,sizeof(x));memset(y,0,sizeof(y));memset(z,0,sizeof(z));memset(ANS,0,sizeof(ANS));for(int i=2;i<=9;i++)gets(MAP[i]);gets(MAP[10]);for(int i=1;i<=9;i++)for(int j=0;j<=16;j=j+2)if(MAP[i][j]!='?') x[i]=(x[i]|(1<<MAP[i][j]-'0')),ANS[i][((j/2)+1)]=MAP[i][j]-'0',y[((j/2)+1)]=(y[((j/2)+1)]|(1<<(MAP[i][j]-'0')));for(int k=1;k<=9;k++)for(int i=nx[k];i<=nx[k]+2;i++)for(int j=ny[k];j<=ny[k]+2;j++){if(MAP[i][((j-1)*2)]!='?') z[k]=(z[k]|(1<<(MAP[i][((j-1)*2)]-'0')));nn[i][j]=k;} } int dfs(int X,int Y) {int XX=X,YY=Y;if(YY+1<=9) YY++;else XX++,YY=1;if(X==10) return 1;else{if(ANS[X][Y]!=0) {if(dfs(XX,YY)) return 1;}else{int xxx=x[X],yyy=y[Y],zzz=z[nn[X][Y]];int t=x[X]|y[Y]|z[nn[X][Y]];for(int i=1;i<=9;i++){if((1&(t>>i))==0){ANS[X][Y]=i;x[X]=(x[X]|(1<<i));y[Y]=(y[Y]|(1<<i));z[nn[X][Y]]=(z[nn[X][Y]]|(1<<i));if(dfs(XX,YY)) return 1;ANS[X][Y]=0;x[X]=xxx;y[Y]=yyy;z[nn[X][Y]]=zzz;}}}}return 0; } void solve() {dfs(1,1);for(int i=1;i<=9;i++){for(int j=1;j<=9;j++){printf("%d",ANS[i][j]);if(j!=9) printf(" ");}printf("\n");} } int main() {// init();int Case=0;while(gets(MAP[1])){if(Case++) printf("\n");input();solve();} }
DLX 做法待研究

轉載于:https://www.cnblogs.com/zy691357966/p/5480402.html

總結

以上是生活随笔為你收集整理的【位运算DFS/DLX】【HDU1426】【数独】的全部內容，希望文章能夠幫你解決所遇到的問題。

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