2014
02-14

Su-Su-Sudoku

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!)

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.

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.

2
481253697
267948105
539671204
654389712
908704563
173562849
702136958
315897426
896425371
481253697
267948105
539671284
654289710
908704562
173562849
702136958
315897426
896425371

481253697
267948135
539671284
654389712
928714563
173562849
742136958
315897426
896425371

Could not complete this grid.

#include<stdio.h>
#include<string.h>
#include<queue>
#include<math.h>
#include<algorithm>
#define N 15
using namespace std;
int map[N][N],v1[15],v2[15];
int flag,n,ok;
struct node
{
int x,y;
}s[6];
void judge1()//判断行和列
{
int i,j;
for(i = 0 ; i < 9 ; i ++)
{
memset(v1,0,sizeof(v1));
memset(v2,0,sizeof(v2));
for(j = 0 ; j < 9 ; j ++)
{
if(v1[map[i][j]])
{
ok = 0;
return;
}
else
v1[map[i][j]] = 1;
if(v2[map[j][i]])
{
ok = 0;
return;
}
else
v2[map[j][i]] = 1;
}
}
}
void judge2()//判断3*3矩形
{
int i,j,x,y;
for(i = 0 ; i <= 6 ; i += 3 )
{
for(j = 0 ; j <= 6 ; j += 3)
{
memset(v1,0,sizeof(v1));
for(x = 0 ; x < 3 ; x ++)
for(y = 0 ; y < 3 ; y ++)
{
if(v1[map[x + i][y + j]])
{
ok = 0;
return ;
}
else v1[map[x + i][y + j]] = 1;
}
}
}
}
void print()
{
ok = 1;
judge1();
if(!ok)
{
printf("Could not complete this grid.\n");
return ;
}
ok = 1;
judge2();
if(!ok)
printf("Could not complete this grid.\n");
else
{
for(int i = 0 ; i < 9 ; i ++)
{
for(int j = 0 ; j < 9 ; j ++)
printf("%d",map[i][j]);
printf("\n");
}
}
}
bool judge(int cur,int t)
{
int i,j;
for(i = 0 ; i < 9 ; i ++)
if(map[ s[cur].x ][i] == t || map[i][ s[cur].y ] == t)
return 0;
int x = s[cur].x/3 * 3;
int y = s[cur].y/3 * 3;
for(i = 0 ; i < 3 ; i ++)
for(j = 0 ; j < 3 ; j ++)
if(map[x + i][y + j] == t) return 0;
return 1;
}
void dfs(int cur)
{
if(cur == n)
{
flag = 1;
print();
return ;
}
if(flag) return ;
for(int i = 1 ; i <= 9 ; i ++)
if(judge(cur,i) && !flag)
{
map[s[cur].x][s[cur].y] = i;
dfs(cur + 1);
map[s[cur].x][s[cur].y] = 0;
}
}
int main()
{
int i,j,T;
char a[15];
scanf("%d",&T);
while(T--)
{
n = 0;
for(i = 0 ; i < 9 ; i ++)
{
scanf("%s",a);
for(j = 0 ; j < 9 ; j ++)
{
map[i][j] = a[j] - '0';
if(!map[i][j])
{
s[n].x = i;
s[n].y = j;
n ++;
}
}
}
flag = 0;
dfs(0);
if(!flag)
printf("Could not complete this grid.\n");
if(T) printf("\n");
}
return 0;
}

1. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

3. 可以参考算法导论中的时间戳。就是结束访问时间，最后结束的顶点肯定是入度为0的顶点，因为DFS要回溯