Rockdu's Blog

 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

Output

Sample Input

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

Sample Output

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127​

暴力搜索，每次枚举一个格子内填1~9。看起来时指数级复杂度，但是因为有很多判断剪枝，实际复杂度不高。最重要的是，写了这道题，还有什么数独题目能难得倒你呢？233~~~

#include<cstdio>
#include<cstring>

using namespace std;

int map[10][10]={ };
bool a[10][10],b[10][10],c[10][10];

bool dfs(int x,int y)
{
	if(x==9) return true;  //行到9，退出 
	bool flag=0;
	int kn=3*(x/3)+y/3;
	if(map[x][y]!=0)
	{
		if(y==8) flag=dfs(x+1,0);
		else flag=dfs(x,y+1);
		if(flag)	return true;
		else return false;
	}
	else
	{
		for(int i=1;i<=9;i++)
			if(!a[x][i]&&!b[y][i]&&!c[kn][i])
			{
				a[x][i]=b[y][i]=c[kn][i]=1;
				map[x][y]=i;
				if(y==8) flag=dfs(x+1,0);
				else flag=dfs(x,y+1);
				if(flag)	return true;
				else 
				map[x][y]=a[x][i]=b[y][i]=c[kn][i]=0;
			}
	}
	return false;
}

int main()
{
	int number;
	char s[10];
	scanf("%d",&number);
	for(int t=1;t<=number;t++)
		{
			memset(a,0,sizeof(a));
			memset(b,0,sizeof(b));
			memset(c,0,sizeof(c));
			for(int i=0;i<9;i++)
			{
				scanf("%s",s);
				
				for(int j=0;j<9;j++)	
				{
					int tot=s[j]-'0';
					map[i][j]=tot;
					int kn=3*(i/3)+j/3;
					a[i][tot]=b[j][tot]=c[kn][tot]=1;	
				}
			}
			dfs(0,0);
			for(int i=0;i<9;i++)
				{
					for(int j=0;j<9;j++)
						printf("%d",map[i][j]);
					printf("\n");
				}
		}
}