poj 2676 Sudoku暴捜
3387 ワード
//
// 9*9 , 1 9
// , , 3*3 1—9
// , r[i][j],c[i][j],s[i][j] , , j
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
const int maxn = 200 ;
char map[maxn][maxn] ;
int r[maxn][maxn];
int c[maxn][maxn];
int s[maxn][maxn];
int x[maxn] , y[maxn] ;
int len ;
int dfs(int pos)
{
if(pos == len + 1)return 1;
int u = x[pos] , v = y[pos] ,num = (u-1)/3*3+(v+2)/3;
for(int i = 1;i <= 9;i++)
{
if(r[u][i]||c[v][i]||s[num][i])continue ;
r[u][i] = c[v][i] = s[num][i] = 1;
map[u][v] = i + '0';
if(dfs(pos+1))return 1;
map[u][v] = '0' ;
r[u][i] = c[v][i] = s[num][i] = 0;
}
return 0 ;
}
int main()
{
//freopen("in.txt","r",stdin) ;
int T ;
scanf("%d" , &T) ;
while(T--)
{
len = 0 ;
memset(r , 0 , sizeof(r)) ;
memset(c , 0 , sizeof(c)) ;
memset(s , 0 ,sizeof(s)) ;
for(int i = 1;i <= 9;i++)
{
scanf("%s" ,&map[i][1]) ;
for(int j = 1;j <= 9;j++)
{
if(map[i][j] == '0')x[++len]=i,y[len]=j;
int t = map[i][j] - '0';
r[i][t] = 1;
c[j][t] = 1;
int pos = (i-1)/3*3+(j+2)/3 ;
s[pos][t] = 1;
}
}
if(dfs(1) == 0){puts("-1");continue ;}
for(int i = 1;i <= 9;i++)
{
for(int j = 1;j <= 9;j++)
printf("%c",map[i][j]);
puts("");
}
}
return 0;
}