?網上看到一則新聞，江蘇69歲農民3天破解“世界最難數獨”，我也寫了個程序破解該數獨。

原報道截圖如下：

原題如下：

?

運行結果：

?

?

#include<iostream> #include<ctime> using namespace std;int p[9][9]; //存放九宮格數據 int z[][9] = { //分為九小宮{0,0,0,1,1,1,2,2,2},{0,0,0,1,1,1,2,2,2},{0,0,0,1,1,1,2,2,2},{3,3,3,4,4,4,5,5,5},{3,3,3,4,4,4,5,5,5},{3,3,3,4,4,4,5,5,5},{6,6,6,7,7,7,8,8,8},{6,6,6,7,7,7,8,8,8},{6,6,6,7,7,7,8,8,8}, }; int r[9][10]; //r[i][j]為1時，第i行數字j(1~9)已放置 int c[9][10]; //c[m][n]為1時，第m列數字n(1~9)已放置 int d[9][10]; //d[x][y]為1時，第x宮數字y(1~9)已放置 int count; //解的個數void input(); void output(); void init(); void search(int); int main() {clock_t clockBegin, clockEnd; //用clock()來計時 毫秒 cout<<"輸入:"<<endl;input(); cout<<"輸出:"<<endl;clockBegin = clock(); //計時開始 init();search(0); clockEnd = clock(); //計時結束 cout<<"計算用時"<< clockEnd - clockBegin<<"ms"<<endl; return 0; }void output(){int i,j;for(i = 0; i < 9; i++){for(j = 0; j < 9; j++){cout<<p[i][j]<<' ';}cout<<endl;}count++; } void init(){ int i,j,x;for(i = 0; i < 9; i++){for(j = 0; j < 9; j++){x = p[i][j];if(x == 0)continue;else{r[i][x] = 1;c[j][x] = 1;d[z[i][j]][x] = 1;}}} }void search(int cur) {if(count == 1) return;else if(cur == 81) //遞歸邊界output();else{int i,j,k,l;i = cur / 9; //行號j = cur % 9; //列號if(p[i][j] != 0)search(cur + 1);else{l = z[i][j];for(k = 1; k <= 9; k++){if(r[i][k]||c[j][k]||d[l][k]) //檢查行、列和宮內是否沖突continue;p[i][j] = k;r[i][k] = c[j][k] = d[l][k] = 1; //修改全局變量search(cur + 1); p[i][j] = r[i][k] = c[j][k] = d[l][k] =0;}}} }void input(){int i,j;for(i = 0; i < 9; i++)for(j = 0; j < 9;j++)cin>>p[i][j]; }

總結

以上是生活随笔為你收集整理的一秒内破解“最难数独”的全部內容，希望文章能夠幫你解決所遇到的問題。

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