| Time Limit: 2000MS | Memory Limit: 65536K | |||
| Total Submissions: 19638 | Accepted: 9408 | Special Judge | ||
Description
Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3x3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3x3 subsquare, all the digits from 1 to 9 to appear. Write a PRogram to solve a given Sudoku-task.
Input
The input data will start with the number of the test cases. For each test case, 9 lines follow, corresponding to the rows of the table. On each line a string of exactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0.Output
For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. If solutions is not unique, then the program may print any one of them.Sample Input
1103000509002109400000704000300502006060000050700803004000401000009205800804000107Sample Output
143628579572139468986754231391542786468917352725863914237481695619275843854396127Source
Southeastern Europe 2005題目意思：
數(shù)獨游戲，每行每列數(shù)字不同，9個3*3的方塊中數(shù)字不同，給出9*9的數(shù)字，0表示為空需要自己填入數(shù)字，求出一組解法。解題思路：
DFS暴搜…這題有毒，反著搜比正著搜快，估計是數(shù)據(jù)的緣故，有的大神正搜也妥妥的A了，我這個渣渣正搜TLE反搜32MS過的…先分別用結(jié)構(gòu)體和數(shù)組保存81個數(shù)的值及其坐標(biāo)，從80~0反搜來DFS，如果當(dāng)前位是0則依次嘗試填入1~9，每填一個就檢查一下是否當(dāng)前3*3的方塊和每行每列均不重復(fù)，如果不重復(fù)則能填入，繼續(xù)搜索下一位上的數(shù)；如果后面無法繼續(xù)填入，那么需要回溯，還原為0。直到搜索完81個位置上的數(shù)，僅輸出一組解，所以要做個標(biāo)記跳出。9個3*3的方塊我是直接根據(jù)行列范圍暴力確定的……#include<iostream>#include<cstdio>#include<iomanip>#include<cmath>#include<cstdlib>#include<cstring>#include<map>#include<algorithm>#include<vector>#include<queue>using namespace std;#define INF 0x3f3f3f3f#define MAXN 5050struct Node{ int x,y,v;} b[81];int a[9][9];bool flag;bool check(int m,int n){ if(m>=0&&m<=2&&n>=0&&n<=2)//0 for(int i=0; i<=2; ++i) for(int j=0; j<=2; ++j) if(i!=m&&j!=n) if(a[i][j]==a[m][n]) return false; if(m>=0&&m<=2&&n>=3&&n<=5)//1 for(int i=0; i<=2; ++i) for(int j=3; j<=5; ++j) if(i!=m&&j!=n) if(a[i][j]==a[m][n]) return false; if(m>=0&&m<=2&&n>=6&&n<=8)//2 for(int i=0; i<=2; ++i) for(int j=6; j<=8; ++j) if(i!=m&&j!=n) if(a[i][j]==a[m][n]) return false; if(m>=3&&m<=5&&n>=0&&n<=2)//3 for(int i=3; i<=5; ++i) for(int j=0; j<=2; ++j) if(i!=m&&j!=n) if(a[i][j]==a[m][n]) return false; if(m>=3&&m<=5&&n>=3&&n<=5)//4 for(int i=3; i<=5; ++i) for(int j=3; j<=5; ++j) if(i!=m&&j!=n) if(a[i][j]==a[m][n]) return false; if(m>=3&&m<=5&&n>=6&&n<=8)//5 for(int i=3; i<=5; ++i) for(int j=6; j<=8; ++j) if(i!=m&&j!=n) if(a[i][j]==a[m][n]) return false; if(m>=6&&m<=8&&n>=0&&n<=2)//6 for(int i=6; i<=8; ++i) for(int j=0; j<=2; ++j) if(i!=m&&j!=n) if(a[i][j]==a[m][n]) return false; if(m>=6&&m<=8&&n>=3&&n<=5)//7 for(int i=6; i<=8; ++i) for(int j=3; j<=5; ++j) if(i!=m&&j!=n) if(a[i][j]==a[m][n]) return false; if(m>=6&&m<=8&&n>=6&&n<=8)//8 for(int i=6; i<=8; ++i) for(int j=6; j<=8; ++j) if(i!=m&&j!=n) if(a[i][j]==a[m][n]) return false; for(int i=m+1; i<9; ++i) if(a[i][n]==a[m][n]) return false; for(int i=m-1; i>=0; --i) if(a[i][n]==a[m][n])return false; for(int i=n+1; i<9; ++i) if(a[m][i]==a[m][n])return false; for(int i=n-1; i>=0; --i) if(a[m][i]==a[m][n])return false; return true;}void dfs(int d){ if(flag) return;//保證只輸出一組 if(d<0) { for(int i=0; i<9; ++i) { for(int j=0; j<9; ++j) cout<<a[i][j]; cout<<endl; } flag=true; return; } if(b[d].v==0)//需要填入數(shù)字 for(int k=1; k<=9; ++k)//嘗試填入1~9 { b[d].v=k; a[b[d].x][b[d].y]=k; if(check(b[d].x,b[d].y))//可以填入 dfs(d-1); b[d].v=0;//還原為0 a[b[d].x][b[d].y]=0; } else dfs(d-1);//不需要填入數(shù)字}int main(){#ifdef ONLINE_JUDGE#else freopen("F:/cb/read.txt","r",stdin); //freopen("F:/cb/out.txt","w",stdout);#endif ios::sync_with_stdio(false); cin.tie(0); int t; cin>>t; while(t--) { flag=false; int cnt=0; string s; for(int i=0; i<9; ++i) { cin>>s; for(int j=0; j<9; ++j) { b[cnt].x=i,b[cnt].y=j; b[cnt++].v=s[j]-'0'; a[i][j]=s[j]-'0'; } } dfs(80);//反搜 } return 0;}/*1103000509002109400000704000300502006060000050700803004000401000009205800804000107*/
新聞熱點
疑難解答
