數(shù)獨(dú)是一個(gè)非常有名的游戲。整個(gè)是一個(gè)9X9的大宮格，其中又被劃分成9個(gè)3X3的小宮格。要求在每個(gè)小格中放入1-9中的某個(gè)數(shù)字。要求是：每行、每列、每個(gè)小宮格中數(shù)字不能重復(fù)。 現(xiàn)要求用計(jì)算機(jī)求解數(shù)獨(dú)。

輸入描述:

輸入9行，每行為空格隔開的9個(gè)數(shù)字，為0的地方就是需要填充的數(shù)字。

輸出描述:

輸出九行，每行九個(gè)空格隔開的數(shù)字，為解出的答案。

示例1

輸入 0 9 0 0 0 0 0 6 0 8 0 1 0 0 0 5 0 9 0 5 0 3 0 4 0 7 0 0 0 8 0 7 0 9 0 0 0 0 0 9 0 8 0 0 0 0 0 6 0 2 0 7 0 0 0 8 0 7 0 5 0 4 0 2 0 5 0 0 0 8 0 7 0 6 0 0 0 0 0 9 0 輸出 7 9 3 8 5 1 4 6 2 8 4 1 2 6 7 5 3 9 6 5 2 3 9 4 1 7 8 3 2 8 4 7 6 9 5 1 5 7 4 9 1 8 6 2 3 9 1 6 5 2 3 7 8 4 1 8 9 7 3 5 2 4 6 2 3 5 6 4 9 8 1 7 4 6 7 1 8 2 3 9 5

解法一：利用DFS進(jìn)行狀態(tài)搜索（搜到一種就輸出）

#include<bits/stdc++.h> using namespace std;int a[9][9]; int sum=0; bool sign=false;//只能輸出第一次搜索出的正確結(jié)果 bool check(int key,int n){//檢查行int j=n/9; for(int i=0;i<9;i++)if(a[j][i]==key) return false;//檢查列 j=n%9;for(int i=0;i<9;i++) {if(a[i][j]==key)return false;}//檢查九個(gè)小方塊int x=n/9;//n的行坐標(biāo)int y=n%9;//n的列坐標(biāo)//***最重要的技巧*** x=x/3*3;y=y/3*3; //x和y是n所在的小方塊最左上角的坐標(biāo) for(int i=x;i<x+3;i++)for(int j=y;j<y+3;j++)if(a[i][j]==key)return false; return true; } int DFS(int n){//把棋盤標(biāo)號(hào)，n是二維棋盤的一維序號(hào) if(n>80){//此時(shí)說明找到了 sign=true;//信號(hào)量 說明找到了 return 0;}if(a[n/9][n%9]!=0){DFS(n+1);}else{for(int i=1;i<=9;i++){if(check(i,n)){a[n/9][n%9]=i;if(n<=80) DFS(n+1);//這個(gè)if用于在找到一種解法之后的回溯過程中防止棋盤復(fù)原 /* if(sign){return 0; } *///只有沒找到的情況才回溯，如果不加下面的if語句，在遞歸回退的過程中填好的空又變回去了 if(sign==false) a[n/9][n%9]=0;//回溯 }} } return 0; } int main() {for(int i=0;i<9;i++)for(int j=0;j<9;j++) cin>>a[i][j];DFS(0); //不一定必有解，先按必有解的情況輸出 cout<<"******************"<<endl;for(int i=0;i<9;i++){for(int j=0;j<9;j++)cout<<a[i][j]<<' '; cout<<endl; }return 0;}

解法二：利用DFS搜索所有結(jié)果

#include<bits/stdc++.h> using namespace std;int a[9][9]; int sum=0; int s=0; int t=0;//輸出所有正確結(jié)果或無結(jié)果的情況 bool check(int key,int n){//行int j=n/9; for(int i=0;i<9;i++)if(a[j][i]==key) return false;//列 j=n%9;for(int i=0;i<9;i++) {if(a[i][j]==key)return false;}//九個(gè)小方塊int x=n/9;//n的行坐標(biāo)int y=n%9;//n的列坐標(biāo)//最重要的技巧 x=x/3*3;//n所在的小方塊最左上角的坐標(biāo) y=y/3*3; for(int i=x;i<x+3;i++)for(int j=y;j<y+3;j++)if(a[i][j]==key)return false; return true; } void shuchu(){t++; cout<<"******************"<<endl;for(int i=0;i<9;i++){for(int j=0;j<9;j++)cout<<a[i][j]<<' '; cout<<endl; } } int DFS(int n){s++;if(n>80){sum++;shuchu();cout<<sum<<endl; return 0;}if(a[n/9][n%9]!=0){DFS(n+1);}else{for(int i=1;i<=9;i++){if(check(i,n)){a[n/9][n%9]=i;DFS(n+1);//shuchu();a[n/9][n%9]=0;//回溯 }} } return 0; } int main() { // freopen("sample.out","w",stdout);for(int i=0;i<9;i++)for(int j=0;j<9;j++) cin>>a[i][j];DFS(0); //不一定必有解，先按必有解的情況輸出 cout<<"答案數(shù)："; cout<<sum<<endl;cout<<"進(jìn)入DFS次數(shù)："; cout<<s<<endl; cout<<"輸出次數(shù)：";cout<<t<<endl; // fclose(stdout);return 0;}

解法三：利用解法二找出所有數(shù)獨(dú)存在的結(jié)果，然后在結(jié)果中搜索符合給出的數(shù)獨(dú)空缺條件的。
在解法二中輸入

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

會(huì)搜索出 M種結(jié)果并保存起來，寫個(gè)程序在這些結(jié)果中搜索即可。在搜索時(shí)應(yīng)該注意優(yōu)化。
這個(gè)M看起來有點(diǎn)大啊，已經(jīng)跑到200w了還沒結(jié)束。

一個(gè)技巧：
假設(shè)搜索庫有M個(gè)數(shù)獨(dú)結(jié)果，待填數(shù)獨(dú)有N個(gè)數(shù)已知，即有N個(gè)條件（數(shù)獨(dú)中的非0數(shù)即為條件），那么有復(fù)雜度為O(M+N)和O(MN)的兩種算法。
O(M+N)的方法：
依次拿著N個(gè)條件在M個(gè)結(jié)果的結(jié)果庫中搜索，因?yàn)樗阉鞒鰜淼慕Y(jié)果在一定順序上是從小到大的，因此可以在第a個(gè)條件在結(jié)果庫中找到后，繼續(xù)用第a+1個(gè)條件在后面的結(jié)果庫中搜索。若所有條件都用光了，那么從最后一個(gè)條件搜索到的第一個(gè)結(jié)果到結(jié)果庫的最后一個(gè)結(jié)果都是符合條件的數(shù)獨(dú)。
O（MN）的方法：
遍歷結(jié)果庫然后在遍歷過程中匹配所有的條件，若符合所有的條件就輸出。

這個(gè)搜索的方法好像不大行啊！！！

總結(jié)

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

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