# 數獨

#include <iostream>
#include <fstream>
using namespace std;

void readFile(char filename[],int Q[][9])
{
	int r,c;
	ifstream f1;
	f1.open(filename);
	for(r=0;r<9;r++)
	{
		for(c=0;c<9;c++)
		{
			f1 >> Q[r][c]; 
		}
	}
	f1.close();
}

void print(int Q[][9])
{
	int r,c;
	for(r=0;r<9;r++)
	{
		for(c=0;c<9;c++)
		{
			if(Q[r][c]==0)
			{
				cout << "  ";
			}
			else
			{
				cout << Q[r][c] << " ";
			}
		} 
		cout << endl;
	}
}

void update(int A[][9][10],int r,int c,int a)
{
	int m,n;
	A[r][c][0] = a;
	for(m=1;m<=9;m++)
		A[r][c][m] = 0;
	for(m=0;m<9;m++)
		A[r][m][a] = 0;
	for(m=0;m<9;m++)	
		A[m][c][a] = 0;
	for(m=r/3*3;m<=r/3*3+2;m++)
	{
		for(n=c/3*3;n<=c/3*3+2;n++)
		{
			A[m][n][a] = 0;
		}
	}
	A[r][c][a] = 1;
}

int onlyyou(int A[][9][10],int r,int c)
{
	int count = 0, a, i;
	for(i=1;i<=9;i++)
	{
		if(A[r][c][i]>0)
		{
			count++;
			a = i;
		}
	}
	if(count==1)
		return a;
	else
		return 0;
}

void init(int Q[][9],int A[][9][10])
{
	int r,c,i;
	for(r=0;r<9;r++)
	{
		for(c=0;c<9;c++)
		{
			A[r][c][0] = 0;
			for(i=1;i<=9;i++)
				A[r][c][i] = 1;
		}
	}
	for(r=0;r<9;r++)
	{
		for(c=0;c<9;c++)
		{
			if(Q[r][c]>0)
			{
				update(A,r,c,Q[r][c]);
			}
		}
	}
}

int main()
{
	int Q[9][9];
	int A[9][9][10];
	int ANS[9][9];
	readFile("Q3.txt",Q);
	print(Q);
	init(Q,A);
	int r,c,a,flag = 0;
	do{
		flag = 0;
		for(r=0;r<9;r++)
		{
			for(c=0;c<9;c++)
			{
				if(A[r][c][0]==0)
				{
					a = onlyyou(A,r,c);
					if(a>0)
					{
						update(A,r,c,a);
						flag = 1;
					} 
				}
			}
		}
	}while(flag==1);
	for(r=0;r<9;r++)
	{
		for(c=0;c<9;c++)
		{
			ANS[r][c] = A[r][c][0];
		}
	}
	print(ANS);
	return 0;
}