<p>Write a program to solve a Sudoku puzzle by filling the empty cells.</p>

<p>A sudoku solution must satisfy <strong>all of the following rules</strong>:</p>

<ol>
	<li>Each of the digits <code>1-9</code> must occur exactly once in each row.</li>
	<li>Each of the digits <code>1-9</code> must occur exactly once in each column.</li>
	<li>Each of the digits <code>1-9</code> must occur exactly once in each of the 9 <code>3x3</code> sub-boxes of the grid.</li>
</ol>

<p>The <code>&#39;.&#39;</code> character indicates empty cells.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png" style="height:250px; width:250px" />
<pre>
<strong>Input:</strong> board = [[&quot;5&quot;,&quot;3&quot;,&quot;.&quot;,&quot;.&quot;,&quot;7&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;],[&quot;6&quot;,&quot;.&quot;,&quot;.&quot;,&quot;1&quot;,&quot;9&quot;,&quot;5&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;],[&quot;.&quot;,&quot;9&quot;,&quot;8&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;6&quot;,&quot;.&quot;],[&quot;8&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;6&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;3&quot;],[&quot;4&quot;,&quot;.&quot;,&quot;.&quot;,&quot;8&quot;,&quot;.&quot;,&quot;3&quot;,&quot;.&quot;,&quot;.&quot;,&quot;1&quot;],[&quot;7&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;2&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;6&quot;],[&quot;.&quot;,&quot;6&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;2&quot;,&quot;8&quot;,&quot;.&quot;],[&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;4&quot;,&quot;1&quot;,&quot;9&quot;,&quot;.&quot;,&quot;.&quot;,&quot;5&quot;],[&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;8&quot;,&quot;.&quot;,&quot;.&quot;,&quot;7&quot;,&quot;9&quot;]]
<strong>Output:</strong> [[&quot;5&quot;,&quot;3&quot;,&quot;4&quot;,&quot;6&quot;,&quot;7&quot;,&quot;8&quot;,&quot;9&quot;,&quot;1&quot;,&quot;2&quot;],[&quot;6&quot;,&quot;7&quot;,&quot;2&quot;,&quot;1&quot;,&quot;9&quot;,&quot;5&quot;,&quot;3&quot;,&quot;4&quot;,&quot;8&quot;],[&quot;1&quot;,&quot;9&quot;,&quot;8&quot;,&quot;3&quot;,&quot;4&quot;,&quot;2&quot;,&quot;5&quot;,&quot;6&quot;,&quot;7&quot;],[&quot;8&quot;,&quot;5&quot;,&quot;9&quot;,&quot;7&quot;,&quot;6&quot;,&quot;1&quot;,&quot;4&quot;,&quot;2&quot;,&quot;3&quot;],[&quot;4&quot;,&quot;2&quot;,&quot;6&quot;,&quot;8&quot;,&quot;5&quot;,&quot;3&quot;,&quot;7&quot;,&quot;9&quot;,&quot;1&quot;],[&quot;7&quot;,&quot;1&quot;,&quot;3&quot;,&quot;9&quot;,&quot;2&quot;,&quot;4&quot;,&quot;8&quot;,&quot;5&quot;,&quot;6&quot;],[&quot;9&quot;,&quot;6&quot;,&quot;1&quot;,&quot;5&quot;,&quot;3&quot;,&quot;7&quot;,&quot;2&quot;,&quot;8&quot;,&quot;4&quot;],[&quot;2&quot;,&quot;8&quot;,&quot;7&quot;,&quot;4&quot;,&quot;1&quot;,&quot;9&quot;,&quot;6&quot;,&quot;3&quot;,&quot;5&quot;],[&quot;3&quot;,&quot;4&quot;,&quot;5&quot;,&quot;2&quot;,&quot;8&quot;,&quot;6&quot;,&quot;1&quot;,&quot;7&quot;,&quot;9&quot;]]
<strong>Explanation:</strong>&nbsp;The input board is shown above and the only valid solution is shown below:

<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/3/31/Sudoku-by-L2G-20050714_solution.svg/250px-Sudoku-by-L2G-20050714_solution.svg.png" style="height:250px; width:250px" />
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>board.length == 9</code></li>
	<li><code>board[i].length == 9</code></li>
	<li><code>board[i][j]</code> is a digit or <code>&#39;.&#39;</code>.</li>
	<li>It is <strong>guaranteed</strong> that the input board has only one solution.</li>
</ul>

class Solution {
public:

bool isValid(vector < vector < char >> & board, int row, int col, int c) {
  for (int i = 0; i < 9; i++) {
    if (board[i][col] == char('0'+c))
      return false;

    if (board[row][i] == char('0'+c))
      return false;

    // if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == char('0'+c))
    //   return false;
  }

// vector<int>col_check(10,0);
//         for(int i=0;i<9;i++){
            
                
//                 if(board[i][col]!='.'){
//                     col_check[board[i][col]-'0']++;
//                     if(col_check[board[i][col]-'0']>1) return false;
//                 }
//         }
        // vector<int>row_check(10,0);
        // for(int j=0;j<9;j++){
            
            
                
        //         if(board[row][j]!='.'){
        //             row_check[board[row][j]-'0']++;
        //             if(row_check[board[row][j]-'0']>1) return false;
        //         }
        
        // }

        // int grid = (row/3) + (col/3);

        vector<int>box_check(10,0);
        for(int i=0;i<3;i++){
            int temp_row = ((row/3)*3)+i;
            for(int j=0;j<3;j++){
                int temp_col=((col/3)*3)+j;
                if(board[temp_row][temp_col]!='.'){
                    box_check[board[temp_row][temp_col]-'0']++;
                    if(box_check[board[temp_row][temp_col]-'0']>1) return false;
                }

            }
        }
  return true;
}

bool solve(vector < vector < char >> & board) {
  for (int i = 0; i < board.size(); i++) {
    for (int j = 0; j < board[0].size(); j++) {
      if (board[i][j] == '.') {
        for (int k=1;k<=9;k++) {
          if (isValid(board, i, j, k)) {
            board[i][j] = char('0'+k);

            if (solve(board))
              return true;
            else
              board[i][j] = '.';
          }
        }

        return false;
      }
    }
  }
  return true;
}



//     bool check(int num,vector<vector<char>>& board,int row,int col){
//         vector<int>col_check(10,0);
//         for(int i=0;i<9;i++){
            
                
//                 if(board[i][col]!='.'){
//                     col_check[board[i][col]-'0']++;
//                     if(col_check[board[i][col]-'0']>1) return false;
//                 }
//         }
//         vector<int>row_check(10,0);
//         for(int j=0;j<9;j++){
            
            
                
//                 if(board[row][j]!='.'){
//                     row_check[board[row][j]-'0']++;
//                     if(row_check[board[row][j]-'0']>1) return false;
//                 }
        
//         }

//     //     // int grid = (row/3) + (col/3);

//     //     vector<int>box_check(10,0);
//     //     for(int i=0;i<3;i++){
//     //         row = ((row/3)*3)+i;
//     //         for(int j=0;j<3;j++){
//     //             col=((col/3)*3)+j;
//     //             if(board[i][j]!='.'){
//     //                 box_check[board[i][j]-'0']++;
//     //                 if(box_check[board[i][j]-'0']>1) return false;
//     //             }

//     //         }
//     //     }

//     for (int i = 0; i < 9; i++) {
//     // if (board[i][col] == c)
//     //   return false;

//     // if (board[row][i] == c)
//     //   return false;

//     if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == char(num-'0'))
//       return false;
//   }
//   return true;
        
//     //     // if(row_check[num]>1 || col_check[num]>1 || box_check[num]>1)
//     //     // return false;

//     //     return true;
//     }


//     bool solve(vector<vector<char>>& board){

//         for(int i=0;i<9;i++){
//             for(int j=0;j<9;j++){
//                 cout<<board[i][j]<<" ";
//             }
//             cout<<endl;
//         }
//         cout<<endl;
//          for(int i=0;i<9;i++){
//             for(int j=0;j<9;j++){
//                 if(board[i][j]=='.'){
//                     for(int k=1;k<=9;k++){
                        
//                         if(check(k,board,i,j)){
//                             board[i][j]=char('0'+k);
//                             if(solve(board)){
//                                 return true;
//                             }
//                             else
//                             board[i][j]='.';
//                         }
//                         // board[i][j]='.';
//                     }
//                     return false;
//                 }
//                 // j++;
//             }
//             // i++;
//         }
//         return true;
//     }
    void solveSudoku(vector<vector<char>>& board) {
       solve(board);
    }
};
33071