題目描述?Description

“芬蘭數(shù)學家因卡拉，花費3個月時間設計出了世界上迄今難度最大的數(shù)獨游戲，而且它只有一個答案。因卡拉說只有思考能力最快、頭腦最聰明的人才能破解這個游戲。”這是英國《每日郵報》2012年6月30日的一篇報道。這個號稱“世界最難數(shù)獨”的“超級游戲”，卻被揚州一位69歲的農(nóng)民花三天時間解了出來。

看到這個新聞后，我激動不已，證明我們OI的實力的機會來了，我們雖然不是思考能力最快、頭腦最聰明的人，但是我們可以保證在1s之內(nèi)解題。

好了廢話不多說了……

數(shù)獨是一種填數(shù)字游戲，英文名叫Sudoku，起源于瑞士，上世紀70年代由美國一家數(shù)學邏輯游戲雜志首先發(fā)表，名為Number?Place，后在日本流行，1984年將Sudoku命名為數(shù)獨，即“獨立的數(shù)字”的省略，解釋為每個方格都填上一個個位數(shù)。2004年，曾任中國香港高等法院法官的高樂德(Wayne?Gould)把這款游戲帶到英國，成為英國流行的數(shù)學智力拼圖游戲。

　　玩家需要根據(jù)9×9盤面上的已知數(shù)字，推理出所有剩余位置（數(shù)據(jù)表示為數(shù)字0）的數(shù)字，并滿足每一行、每一列、每一個粗線宮內(nèi)的數(shù)字均含1-9，不重復。

現(xiàn)在給你一個數(shù)獨，請你解答出來。每個數(shù)獨保證有解且只有一個。

輸入描述?Input Description

9行9列。

每個數(shù)字用空格隔開。0代表要填的數(shù)

行末沒有空格，末尾沒有回車。

輸出描述?Output Description

輸出答案。

排成9行9列。

行末沒有空格，結尾可以有回車。

樣例輸入?Sample Input

2 0 0 0 1 0 8 9 0
0 0 7 0 0 0 0 0 0
0 0 0 9 0 0 0 0 7
0 6 0 0 0 1 3 0 0
0 9 0 7 3 4 0 8 0
0 0 3 6 0 0 0 5 0
6 0 0 0 0 2 0 0 0
0 0 0 0 0 0 1 0 0
0 5 9 0 8 0 0 0 3

樣例輸出?Sample Output

2 4 5 3 1 7 8 9 6
9 1 7 2 6 8 5 3 4
3 8 6 9 4 5 2 1 7
4 6 2 8 5 1 3 7 9
5 9 1 7 3 4 6 8 2
8 7 3 6 2 9 4 5 1
6 3 8 1 7 2 9 4 5
7 2 4 5 9 3 1 6 8
1 5 9 4 8 6 7 2 3

數(shù)據(jù)范圍及提示?Data Size & Hint

保證有解，每個數(shù)獨都由<a href="http://oubk.com/">http://oubk.com</a>數(shù)獨網(wǎng)提供。

其中數(shù)據(jù)hard1.in為芬蘭數(shù)學家提供。

思路：我先說一下，做完這個題后，我終于會填數(shù)獨了233。 思路也是比較簡單的吧，只不過我沒有想到具體的實現(xiàn)方法，于是就老老實實的看題解，然后總結了一個比較簡潔的寫法。 首先，我們令bool數(shù)組row[x][v]表示第x行是否存在v這個數(shù),col[y][v]表示第y列是否存在v這個數(shù)，由于題目要求，同一個3*3的小格子里不能出現(xiàn)相同的數(shù)，所以我們又令gz[i][j][v]表示第i大行的格子第j大列的格子是否存在v這個數(shù)，然后就很簡單了，枚舉每一行，有空位就枚舉1到9所有數(shù)字，看看當前狀態(tài)可不可行，可行就dfs下一層。當當前行格子已被放滿，那么就去下一行。如果所有格子都被填滿，那么直接輸出答案，并直接退出程序（因為題目保證，一定存且僅存一組解）。 代碼如下： #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> using namespace std; const int maxn=12; int read() {int ret=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}return ret*f; } int n,mmp[maxn][maxn]; bool row[maxn][maxn],col[maxn][maxn],gz[4][4][maxn]; inline void place(int x,int y,int v,bool t) {row[x][v]=t,col[y][v]=t;gz[(x-1)/3][(y-1)/3][v]=t; } int res=81; void dfs(int x,int y,int step) {if(step==res){for(int i=1;i<=9;i++){ for(int j=1;j<=9;j++)printf("%d ",mmp[i][j]);printf("\n");}exit(0);}int flag=0;for(int i=y;i<=9;i++)if(!mmp[x][i]) {y=i;flag=1;break;}if(flag){for(int i=1;i<=9;i++){if(row[x][i]||col[y][i]||gz[(x-1)/3][(y-1)/3][i]) continue;mmp[x][y]=i;place(x,y,i,1);dfs(x,y,step+1);mmp[x][y]=0;place(x,y,i,0);}}else dfs(x+1,1,step); } int main() {for(int i=1;i<=9;i++)for(int j=1;j<=9;j++){mmp[i][j]=read();if(mmp[i][j]){place(i,j,mmp[i][j],1);res--;}}dfs(1,1,0);return 0; }

?

轉載于:https://www.cnblogs.com/loi-frank/p/7727006.html

總結

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

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