Solve the Sudoku

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 

                                                C-Solution

#include<stdio.h>
#define UNASSIGNED 0
#define N 9
bool usedinrow(int grid[N][N],int row,int num)
{
   for(int cols=0;cols<N;cols++)
       if(grid[row][cols]==num)
          return true;
          return false;
}
bool usedincols(int grid[N][N],int cols,int num)
{
   for(int row=0;row<N;row++)
           if(grid[row][cols]==num)
            return true;
            return false;
}
bool checkbox(int grid[N][N],int srow,int scols,int num)
{
   for(int row=0;row<3;row++)
       for(int cols=0;cols<3;cols++)
        if(grid[row+srow][cols+scols]==num)
            return true;
            return false;
}   
bool findunassigned(int grid[N][N],int &row,int &cols)
{

  for(row=0;row<N;row++)
      for(cols=0;cols<N;cols++)
       if(grid[row][cols]==UNASSIGNED)
         return true;
         return false;
}
bool issafe(int grid[N][N],int row,int cols,int num)
{
     return !usedinrow(grid,row,num)&&!usedincols(grid,cols,num)&&

!checkbox(grid,row-row%3,cols-cols%3,num);
}
bool solveSudoku(int grid[N][N])
{
            int row,cols;
    if(!findunassigned(grid,row,cols))
      return true;
      for(int num=1;num<=9;num++)
      {
        if(issafe(grid,row,cols,num))
        {  grid[row][cols]=num;     
       
            if(solveSudoku(grid))
            return true;
           
        grid[row][cols]=UNASSIGNED;
        }
      }
      return false;
}
void printGrid(int grid[N][N])
{
    for (int row = 0; row < N; row++)
      for (int col = 0; col < N; col++)
         printf("%d ", grid[row][col]);   
}
int main()
{   
   int t,i,j,k,grid[N][N];
   scanf("%d",&t);
   for(i=0;i<t;i++)
   { 
       for(j=0;j<N;j++)
       {
           for(k=0;k<N;k++)
           {
               scanf("%d",&grid[j][k]);
           }
       }
    solveSudoku(grid);
     printGrid(grid);
     printf("\n");   
   }
    return 0;
}