Su-Su-Sudoku
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 402 Accepted Submission(s):
191
Problem Description
By now, everyone has played Sudoku: you're given a
9-by-9 grid of boxes which you are to fill in with the digits 1 through 9 so
that 1) every row has all nine digits, 2) every column has all nine digits, and
3) all nine 3-by-3 subgrids have all nine digits. To start the game you are
given a partially completed grid and are asked to fill in the remainder of the
boxes. One such puzzle is shown below.
In this problem, you will be given Sudoku grids which you have nearly completed; indeed you've filled in every box except five. You are asked to complete the grid, or determine that it's impossible. (You might have already made an error!)
In this problem, you will be given Sudoku grids which you have nearly completed; indeed you've filled in every box except five. You are asked to complete the grid, or determine that it's impossible. (You might have already made an error!)
Input
The first line of input will contain a positive integer
indicating the number of test cases to follow. Each test case will be a nearly
completed Sudoku grid consisting of 9 lines, each containing 9 characters from
the set of digits 0 through 9. There will be exactly five 0's in each test case,
indicating the five unfilled boxes.
Output
Output for each test case should be either
Could not complete this grid.
if it is impossible to complete the grid according to the rules of the game, or the completed grid, in the form given below. (There are no blank spaces in the output.) If there is a way to complete the grid, it will be unique. Separate test cases with a blank line.
Could not complete this grid.
if it is impossible to complete the grid according to the rules of the game, or the completed grid, in the form given below. (There are no blank spaces in the output.) If there is a way to complete the grid, it will be unique. Separate test cases with a blank line.
Sample Input
2
481253697
267948105
539671204
654389712
908704563
173562849
702136958
315897426
896425371
481253697
267948105
539671284
654289710
908704562
173562849
702136958
315897426
896425371
Sample Output
481253697
267948135
539671284
654389712
928714563
173562849
742136958
315897426
896425371
Could not complete this grid.
Source
Recommend
lcy
思路：简单DFS，坑爹的输出格式，我害PE了六次
代码：
#include <iostream> #include <cstring> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> using namespace std; int map[12][12]; char str[12]; int soso[110][3]; int the_search_number; int the_last_flag; int the_time; int the_search_flag[110]; int ans; bool the_last_can() { int bool_number[12]; for(int i = 1;i <= 9;i ++) { memset(bool_number,0,sizeof(bool_number)); for(int j = 1;j <= 9;j ++) { if(bool_number[map[i][j]] == 1) return false; bool_number[map[i][j]] = 1; } } for(int i = 1;i <= 9;i ++) { memset(bool_number,0,sizeof(bool_number)); for(int j = 1;j <= 9;j ++) { if(bool_number[map[j][i]] == 1) return false; bool_number[map[j][i]] = 1; } } for(int i = 1;i < 7;i += 3) { for(int j = 1;j < 7;j += 3) { memset(bool_number,0,sizeof(bool_number)); for(int k = i;k <= i + 3;k ++) { for(int h = j;h <= j + 3;h ++) { if(bool_number[map[k][h]] == 1) return false; bool_number[map[k][h]] == 1; } } } } return true; } bool yes_you_can(int x,int y,int k) { for(int i = 1;i <= 9;i ++) if(k == map[i][y]) return false; for(int i = 1;i <= 9;i ++) if(k == map[x][i]) return false; if(x <= 3) { if(y <= 3) { for(int i = 1;i <= 3;i ++) for(int j = 1;j <= 3;j ++) if(map[i][j] == k) return false; } if(y <= 6 && y > 3) { for(int i = 1;i <= 3;i ++) for(int j = 4;j <= 6;j ++) if(map[i][j] == k) return false; } if(y <= 9 && y > 6) { for(int i = 1;i <= 3;i ++) for(int j = 7;j <= 9;j ++) if(map[i][j] == k) return false; } } if(x > 3 && x <= 6) { if(y <= 3) { for(int i = 4;i <= 6;i ++) for(int j = 1;j <= 3;j ++) if(map[i][j] == k) return false; } if(y <= 6 && y > 3) { for(int i = 4;i <= 6;i ++) for(int j = 4;j <= 6;j ++) if(map[i][j] == k) return false; } if(y <= 9 && y > 6) { for(int i = 4;i <= 6;i ++) for(int j = 7;j <= 9;j ++) if(map[i][j] == k) return false; } } if(x > 6 && x <= 9) { if(y <= 3) { for(int i = 7;i <= 9;i ++) for(int j = 1;j <= 3;j ++) if(map[i][j] == k) return false; } if(y <= 6 && y > 3) { for(int i = 7;i <= 9;i ++) for(int j = 4;j <= 6;j ++) if(map[i][j] == k) return false; } if(y <= 9 && y > 6) { for(int i = 7;i <= 9;i ++) for(int j = 7;j <= 9;j ++) if(map[i][j] == k) return false; } } return true; } void DFS(int now) { if(the_last_flag != -1) return ; if(now == the_search_number + 1) { //for(int i = 1;i <= 9;i ++) //{ //for(int j = 1;j <= 9;j ++) //printf("%d",map[i][j]); //printf(" "); //} if(the_last_can() == 0) { the_last_flag = 0; return ; } else { the_last_flag = 1; return ; } } for(int p = 1;p <= 9;p ++) { if(yes_you_can(soso[now][0],soso[now][1],p) == 1) { map[soso[now][0]][soso[now][1]] = p; the_search_flag[now] = 1; DFS(now + 1); if(the_last_flag != -1) return ; } } if(the_search_flag[now] == 0) { the_last_flag = 0; return ; } if(the_last_flag != -1) return ; } int main() { while(~scanf("%d",&the_time)) { for(int t = 1;t <= the_time;t ++) { memset(map,0,sizeof(map)); memset(soso,0,sizeof(soso)); memset(the_search_flag,0,sizeof(the_search_flag)); ans = 0; for(int i = 1;i <= 9;i ++) { memset(str,0,sizeof(str)); scanf("%s",str); for(int j = 0;j < 9;j ++) { map[i][j + 1] = str[j] - '0'; if(map[i][j + 1] == 0) { soso[++ ans][0] = i; soso[ans][1] = j + 1; } } } the_search_number = ans; the_last_flag = -1; DFS(1); if(the_last_flag == 0 || the_last_flag == -1) { printf("Could not complete this grid. "); } if(the_last_flag == 1) { for(int i = 1;i <= 9;i ++) { for(int j = 1;j <= 9;j ++) printf("%d",map[i][j]); printf(" "); } } if(t != the_time) printf(" "); } } return 0; }