Description
Sudoku is a placement puzzle. The goal is to enter a symbol in each cell of a grid, most frequently a 9 x 9 grid made up of 3 x 3subgrids. Each row, column and subgrid must contain only one instance of each symbol. Sudoku initially became popular in Japan in 1986 and attained international popularity in 2005.
The word Sudoku means ``single number" in Japanese. The symbols in Sudoku puzzles are often numerals, but arithmetic relationships between numerals are irrelevant.
According to wikipedia:
The number of valid Sudoku solution grids for the standard 9 x 9 grid was calculated by Bertram Felgenhauer in 2005 to be 6,670,903,752,021,072,936,960, which is roughly the number of micrometers to the nearest star. This number is equal to 9! * 722 * 2
Write a program to find a solution to a 9 x 9 Sudoku puzzle given a starting configuration.
Input
The first line will contain an integer specifying the number of puzzles to be solved. The remaining lines will specify the starting configuration for each of the puzzles. Each line in a starting configuration will have nine characters selected from the numerals 1-9 and the underscore which indicates an empty cell.
Output
For each puzzle, the output should specify the puzzle number (starting at one) and describe the solution characteristics. If there is a single solution, it should be printed. Otherwise, a message indicating whether there are no solutions or multiple solutions should be printed. The output should be similar to that shown below. All input cases have less than 10,000 solutions.
Sample Input
3 ________4 1____9_7_ __37_28__ ____7_26_ 4_______8 _91_6____ __42_36__ _3_14___9 9________ 7_9__2___ 3_____891 ___39___4 48__6____ __5___6__ ____4__23 2___57___ 568_____7 ___8__4_2 82_______ ___5__2__ __6_4_7__ _5___1_7_ 9_2_5_4_1 _3_8_6_9_ __3_6_1__ __5__2___ _______34
Sample Output
Puzzle 1 has 6 solutions Puzzle 2 solution is 719482365 324675891 856391274 482563719 135729648 697148523 243957186 568214937 971836452 Puzzle 3 has no solution
分析：
本题较为复杂，虽然能够看出明显应该用深度搜索方法，但是即使时间限制有10s使用暴力算法仍然会超时，需要一定的优化和剪枝。按照做数独的一般思路，先对数独空格进行可能性分析将所有格子的可能答案数做记录（已有的记为1），然后每次搜索之前先进行筛选，从前向后找答案数最少的进行深搜，一旦搜完再整理结果。剪枝的方案是，搜索时遇到有格子无法填入数字（即答案数为0）就返回0值。同时，注意因为深搜是反复进行的，输入数组会被反复还原，可能的答案要另行保存不能使用原有输入的数组。本题能很好的考察搜索的特点，值得反复研究，而且数独也是很有趣的数学谜题。
PS：注意输出数据的格式调整。
代码：
1 // Problem#: 1317 2 // Submission#: 1877449 3 // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License 4 // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/ 5 // All Copyright reserved by Informatic Lab of Sun Yat-sen University 6 #include <iostream> 7 #include <cstring> 8 #include <fstream> 9 using namespace std; 10 11 int sudoku[9][9],recnt,ans[9][9],p[82]; 12 bool isvalid[9][9][10],flag; 13 14 int dfs(){ 15 int n = 81; 16 int x,y; 17 for( int i=0 ; i<81 ; i++ ){ 18 x = i/9; 19 y = i%9; 20 if( sudoku[x][y] ) continue; 21 if( !p[i] ) return 0; 22 if( p[i]>0 && p[i]<p[n] ) n = i; 23 } 24 if(n==81){ 25 if( flag ){ 26 flag = false; 27 memcpy(ans,sudoku,sizeof(ans)); 28 } 29 return 1; 30 } 31 x = n/9; 32 y = n%9; 33 int trow[81],tcol[81],c; 34 int re = 0; 35 for( int t=1 ; t<10 ; t++ ){ 36 if( isvalid[x][y][t] ){ 37 int tp[82]; 38 memcpy(tp,p,sizeof(tp)); 39 sudoku[x][y] = t; 40 c = 0; 41 p[n] = 0; 42 for( int k=0 ; k<9 ; k++ ){ 43 if( isvalid[k][y][t] ){ 44 isvalid[k][y][t] = false; 45 trow[c] = k; 46 tcol[c++] = y; 47 p[k*9+y]--; 48 } 49 if( isvalid[x][k][t] ){ 50 isvalid[x][k][t] = false; 51 trow[c] = x; 52 tcol[c++] = k; 53 p[x*9+k]--; 54 } 55 } 56 for( int r=x/3*3 ; r < (x/3+1)*3 ; r++ ) 57 for( int s=y/3*3 ; s < (y/3+1)*3 ; s++ ) 58 if( isvalid[r][s][t] ){ 59 isvalid[r][s][t] = false; 60 trow[c] = r; 61 tcol[c++] = s; 62 p[r*9+s]--; 63 } 64 re += dfs(); 65 for( int i=0 ; i<c ; i++ ) 66 isvalid[trow[i]][tcol[i]][t] = true; 67 memcpy(p,tp,sizeof(p)); 68 sudoku[x][y] = 0; 69 } 70 } 71 return re; 72 } 73 74 int main(){ 75 int n; 76 char c; 77 cin >> n; 78 for(int count=1 ; count <= n ; count++){ 79 recnt = 0; 80 flag = true; 81 memset(sudoku,0,sizeof(sudoku)); 82 memset(isvalid,true,sizeof(isvalid)); 83 memset(p,0,sizeof(p)); 84 p[81] = 1000; 85 for( int i=0 ; i<9 ; i++ ){ 86 for( int j=0 ; j<9 ; j++ ){ 87 cin >> c; 88 if( c!='_' ){ 89 sudoku[i][j] = c - '0'; 90 int t = sudoku[i][j]; 91 for( int k=0 ; k<9 ; k++ ){ 92 isvalid[k][j][t] = k==i; 93 isvalid[i][k][t] = k==j; 94 isvalid[i][j][k+1] = k+1==t; 95 } 96 for( int r=i/3*3 ; r < (i/3+1)*3 ; r++ ) 97 for( int s=j/3*3 ; s < (j/3+1)*3 ; s++ ) 98 if( r!=i&&s!=j ) isvalid[r][s][t] = false; 99 } 100 } 101 } 102 for( int i=0 ; i<9 ; i++ ) 103 for( int j=0 ; j<9 ; j++ ) 104 for( int k=1 ; k<10 ; k++ ) 105 if( isvalid[i][j][k] ) p[i*9+j]++; 106 recnt += dfs(); 107 cout << "Puzzle " << count; 108 if(recnt){ 109 if( recnt>1 ) cout << " has " << recnt << " solutions" << endl; 110 else{ 111 cout << " solution is" << endl; 112 for( int i=0 ; i<9 ; i++ ){ 113 for( int j=0 ; j<9 ; j++ ) 114 cout << ans[i][j]; 115 cout << endl; 116 } 117 } 118 }else{ 119 cout << " has no solution" << endl; 120 } 121 if( count<n ) cout << endl; 122 } 123 return 0; 124 }