CodeChef submission 130682 (C++ 4.0.0-8) plaintext list. Status: TLE, problem J1, contest NOV09. By askvij (Ashok Vijay), 2009-11-11 11:44:32.
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<vector>
#include<sstream>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
bool col[11][11];
bool row[11][11];
bool diag [11] , anti_diag [11];
bool grid[11][3][3][11];
int sudo[11][11];
struct N
{
	int x,y;
};
int seti()
{
	int i,j;
	for(i=0;i<10;i++)
	for(j=0;j<10;j++)
	col[i][j]=row[i][j]=false;
	memset ( diag ,false ,sizeof (diag ) );
	memset ( anti_diag ,false ,sizeof (anti_diag ) );
	return(1);
}
int find_grid(int x,int y)
{
	int g;
	if(x<3 && y<3)
        g=0;
        if(x<6 && x>2 && y<3)
        g=3;
        if(x>5 && x<9 && y<3)
        g=6;
        if(x<3 && y<6 && y>2)
        g=1;
        if(x<3 && y<9 && y>5)
        g=2;
        if(x<6 && x>2 && y<6 && y>2)
        g=4;
        if(x<6 && x>2 && y<9 && y>5)
        g=5;
        if(x>5 && x<9 && y<6 && y>2)
        g=7;
        if(x>5 && x<9 && y<9 && y>5)
        g=8;
	return(g);
}
N G_x_y(int i,int j,int g)
{
	int x,y;
	if(g==0)
        x=i,y=j;
        if(g==1)
        x=i,y=j-3;
        if(g==2)
        x=i,y=j-6;
        if(g==3)
        x=i-3,y=j;
        if(g==4)
        x=i-3,y=j-3;
        if(g==5)
        x=i-3,y=j-6;
        if(g==6)
        x=i-6,y=j;
        if(g==7)
        x=i-6,y=j-3;
        if(g==8)
        x=i-6,y=j-6;
	N a;
	a.x=x,a.y=y;
	return(a);
}
bool G_chk(int x,int y,int k)
{
	int i,j,g;
	g=find_grid(x,y);
	for(i=0;i<3;i++)
	for(j=0;j<3;j++)
	if(grid[g][i][j][k])
	return(true);
	return(false);
}
bool chk()
{
	int i,j,k;
	for(i=0;i<9;i++)
        for(j=0;j<9;j++)
	if(sudo[i][j]==0)
	return(false);
	return(true);
}
 
bool solve()
{
	int i,j,k,cnt,a=1<<29,x,y,g;
	for(i=0;i<9;i++)
	{
		for(j=0;j<9;j++)
		{
			cnt=0;
			if(sudo[i][j]==0)
			{
				for(k=1;k<=9;k++)
				if(!row[i][k] && !col[j][k])
				{
                    if ( i == j  && diag [k] ) continue;
                    if ( j == 8-i && anti_diag [k] ) continue;
                    //if ( i == j && i == 3 ) cout << k << " ";          
					cnt++;
				}
                //if ( i == j && i == 3 ) cout <<"\n";
				if(cnt<a)
				{
					a=cnt;
					x=i;
					y=j;
				}
			}
		}
	}
	if(a!=(1<<29))
	for(k=9;k>=1;k--)
	{
		if(!row[x][k] && !col[y][k] && !G_chk(x,y,k))
		{
            if ( x == y  && diag [k] ) continue;
            if ( y == 8-x && anti_diag [k] ) continue; 
			sudo[x][y]=k;
			row[x][k]=col[y][k]=true;
			if ( x ==y ) diag [k] = true;
			if ( y == 8 - x ) anti_diag [k] = true;
			g=find_grid(x,y);
			N a=G_x_y(x,y,g);
			grid[g][a.x][a.y][k]=true;
			if(solve())
			return(true);
			sudo[x][y]=0;
			row[x][k]=col[y][k]=false;	
			grid[g][a.x][a.y][k]=false;
			if ( x ==y ) diag [k] = false;
			if ( y == 8 - x ) anti_diag [k] = false;
		}
	}
	if(chk())
	return(true);
	return(false);
}
void print()
{
	int i,j,k;
	for(i=0;i<9;i++,cout<<"\n")
	for(j=0;j<9;j++)
	cout<<sudo[i][j]<<" ";	
}
main()
{
    //double start = clock();
	int i,j,k,g,x,y,sum=0,z;
	char a;
	//freopen ( "J1.in", "r",stdin );
    //freopen ( "J1.out", "w",stdout );
	for(scanf("%d",&z);z;z--)
	{
		//cin>>n>>m;
		char in [11][11];
		memset(grid,false,sizeof(grid));
		//stringstream X;
		for(i=0;i<9;i++)
		{
            cin >>in[i];
            for ( j = 0; j < 9 ;j++ ) if (in [i][j] == '.' ) sudo [i][j] = 0;
            else sudo [i][j] = in [i][j] -'0'; 
        }
		seti();	
		for(i=0;i<9;i++)
		{
			for(j=0;j<9;j++)
			{
				k=sudo[i][j];
				if(k)
				{
					row[i][k]=col[j][k]=true;
					if ( i == j ) diag [k] = true;
					if ( j == 8-i ) anti_diag [k ] = true;
					g=find_grid(i,j);	
					N a=G_x_y(i,j,g);
					grid[g][a.x][a.y][k]=true;
				}		
			}
 
		}
		 //for ( j = 1 ;j <= 9 ;j++ )if ( diag [j] ) cout << j <<" ";cout<<"\n";
		 //for ( j = 1 ;j <= 9 ;j++ )if ( anti_diag [j] ) cout << j <<" ";cout<<"\n";
		solve();
		for ( i = 0 ;i < 9 ; i++ ,cout<<"\n" ) for ( j = 0 ;j < 9 ;j++ ) cout <<sudo[i][j];cout<<"\n";
	//	X.clear();
		//X<<sudo[0][0]<<sudo[0][1]<<sudo[0][2]<<"\n";
		//X>>i;
		//sum+=i;
		//print();
	}
	//double stop = clock();
	//cout << (stop - start )/CLOCKS_PER_SEC << "\n";
	return 0;
	//cout<<"\t"<<sum<<"\n";
}