Solve the Sudoku

PROBLEM :

Given an incomplete Sudoku configuration in terms of a 9x9  2-D square matrix (mat[][]) the task to print a solution of the Sudoku. For simplicity you may assume that there will be only one unique solution.

Example

For the above configuration the solution is
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9


Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains 9*9 space separated values of the matrix mat[][] representing an incomplete Sudoku state where a 0 represents empty block.

Output:
For each test case in a new line print the space separated values of the solution of the the sudoku.

Constraints:
1<=T<=10
0<=mat[]<=9

Example:
Input:
1
3 0 6 5 0 8 4 0 0 5 2 0 0 0 0 0 0 0 0 8 7 0 0 0 0 3 1 0 0 3 0 1 0 0 8 0 9 0 0 8 6 3 0 0 5 0 5 0 0 9 0 6 0 0 1 3 0 0 0 0 2 5 0 0 0 0 0 0 0 0 7 4 0 0 5 2 0 6 3 0 0

Output:
3 1 6 5 7 8 4 9 2 5 2 9 1 3 4 7 6 8 4 8 7 6 2 9 5 3 1 2 6 3 4 1 5 9 8 7 9 7 4 8 6 3 1 2 5 8 5 1 7 9 2 6 4 3 1 3 8 9 4 7 2 5 6 6 9 2 3 5 1 8 7 4 7 4 5 2 8 6 3 1 9
       
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
#define N 9

bool FindSpace(int chess[N][N],int *row,int *col)
{
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            if(!chess[i][j])
            {
                (*row)=i ;
                (*col)=j ;
                return false ;
            }
    return true ;
}

bool IsSafe(int chess[N][N],int row,int col,int no)
{
    for(int i=0;i<N;i++)
        if(chess[row][i]==no)
            return false ;
           
    for(int i=0;i<N;i++)
        if(chess[i][col]==no)
            return false ;
           
    row=row-(row%3) ;
    col=col-(col%3) ;
   
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(chess[i+row][j+col]==no)
                return false ;
               
    return true ;
}

bool SolveSudoku(int chess[N][N])
{
    int row,col ;
   
    if(FindSpace(chess,&row,&col))
        return true ;
       
    for(int i=1;i<=9;i++)
    {
        if(IsSafe(chess,row,col,i))
        {
            chess[row][col]=i ;
           
            if(SolveSudoku(chess))
                return true ;
               
            chess[row][col]=0 ;
        }
    }
   
    return false ;
}

int main()
{
int t ;
cin>>t ;
while(t--)
{
   int chess[N][N] ;
 
   for(int i=0;i<N;i++)
       for(int j=0;j<N;j++)
           cin>>chess[i][j] ;
         
        if(SolveSudoku(chess))
        {
            for(int i=0;i<N;i++)
           for(int j=0;j<N;j++)
               cout<<chess[i][j]<<" " ;
        }
        else
            cout<<"No solution exists" ;
        cout<<endl ;
}
return 0;
}

--------------------------------------------------------------------------------