/**
knakul853
**/
class Solution {
public:
    int row[10][256]={0};
    int col[10][256]={0};
    int square[4][4][256] = {0};
    void solveSudoku(vector<vector<char>>& board) {

        int n = (int)board.size();
        int m = (int)board[0].size();

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                char c = board[i][j];
                if(c != '.')
                {
                    row[i][c] = col[j][c] = square[i/3][j/3][c] = 1;
                }
            }
        }

        solveSudoku(board, 0, 0);
    }

    bool check(int i,int j, char val)
    {
        if(row[i][val] || col[j][val] || square[i/3][j/3][val]) return false;

        return true;
    }
     bool solveSudoku(vector<vector<char>>& board, int i, int j)
     {
         if( i == 9) return true;

         if( j == 9) return solveSudoku(board, i+1, 0);

         if(board[i][j] !='.') return solveSudoku(board, i, j+1);

         for( char c='1'; c<='9'; c++ )
         {
             if(check(i, j, c))
             {
                 board[i][j] = c;
                 row[i][c] = col[j][c] = square[i/3][j/3][c] = 1;
                 if(solveSudoku(board, i, j+1))
                     return true;
                 board[i][j] = '.';
                 row[i][c] = col[j][c] = square[i/3][j/3][c] = 0;
             }
         }

         return false;
     }
};