Back Tracking

//Solving suduko with backtracking


#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
void pS(int g[9][9]){
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++)
           cout<<g[i][j]<<" ";
        cout<<endl;
    }
}
bool getNextAvailable(int grid[9][9], int *x, int *y){
   for(int i=0;i<9;i++){
       for(int j=0;j<9;j++){
           if(grid[i][j]==0){
               *x=i;
               *y=j;
               return true;
           }
       }
   }
   return false;
}
bool isSafe(int g[9][9],int x,int y,int v){
      for(int i=0;i<9;i++)if( g[x][i]==v)return false;
      for(int i=0;i<9;i++)if(g[i][y]==v)return false;
      int box_i=0, box_j=0;
      if(x!=0)box_i = floor(x/3)*3;
      if(y!=0)box_j  = floor(y/3)*3;
     for(int i=box_i;i<box_i+3;i++){
           for(int j=box_j;j<box_j+3;j++)
               if(g[i][j]==v)return false;
      }
      return true;
}
bool solvesuduko_bt(int grid[9][9]){
    int x,y;
    if(!getNextAvailable(grid,&x,&y))return true;
    for(int i=1;i<=9;i++){
        if(isSafe(grid,x,y,i)){
            grid[x][y]=i;
            if(solvesuduko_bt(grid))return true;
             grid[x][y]=0;   //backtrack
        }
    }
    return false;
}
void sudoku_solve(int g[9][9]) {
    solvesuduko_bt(g);pS(g);
}
int main(void) {
    int n, board[9][9];
    cin >> n;
    for(int i=0;i<n;i++) {
        for(int j=0;j<9;j++) {
            for(int k=0;k<9;k++) {
                board[j][k] = 0;
                cin >> board[j][k];
            }
        }
        sudoku_solve(board);
    }
    return 0;
}