<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 done = false;
    int block_num(int i , int j){
        if(i >= 0 && i <= 2){
            if(j >= 0 && j <= 2){
                return 0;
            }
            if(j >= 3 && j <= 5){
                return 1;
            }
            if(j >= 6 && j <= 8){
                return 2;
            }
        }
        if(i >= 3 && i <= 5){
            if(j >= 0 && j <= 2){
                return 3;    
            }
            if(j >= 3 && j <= 5){
                return 4;
            }
            if(j >= 6 && j <= 8){
                return 5;
            }
        }
        if(i >= 6 && i <= 8){
            if(j >= 0 && j <= 2){
                return 6;
            }
            if(j >= 3 && j <= 5){
                return 7;
            }
            if(j >= 6 && j <= 8){
                return 8;
            }
        }
        return -1;
    }
    void solve(vector<vector<char>>& board ,vector<vector<int>>& hash1 , vector<vector<int>>& hash2 , vector<vector<int>> hash3){
        if(done)return;
        for(int row = 0 ; row <= 8; row++){
            for(int col = 0 ; col <= 9; col++){
                
                if(row == 8 && col == 9){
                    done = true;
                    return;
                }
                if(col == 9)continue;
                if(board[row][col] == '.'){
                    // cout<<"before placing: "<<row<<" "<<col<<endl;
                    // for(int i = 0 ; i < board.size() ; i++){
                    //     for(int j = 0; j < board[0].size() ; j++){
                    //         cout<<board[i][j]<<" ";
                    //     }
                    //     cout<<endl;
                    // }
                    for(int i = 1; i <= 9 ;i++){
                        if(hash1[row][i-1] != 1 && hash2[col][i-1] != 1 && hash3[block_num(row,col)][i-1] != 1){
                            board[row][col] = i + '0';
                            hash1[row][i-1] = 1;
                            hash2[col][i-1] = 1;
                            hash3[block_num(row,col)][i-1] = 1;
                            // cout<<"after placing: " <<row<<" "<<col<<endl;
                            // for(int i = 0 ; i < board.size() ; i++){
                            //     for(int j = 0; j < board[0].size() ; j++){
                            //         cout<<board[i][j]<<" ";
                            //     }
                            //     cout<<endl;
                            // }
                            solve(board , hash1 ,hash2 , hash3);
                            if(done == false){
                                board[row][col] = '.';
                                hash1[row][i-1] = 0;
                                hash2[col][i-1] = 0;
                                hash3[block_num(row,col)][i-1] = 0;
                            }else{
                                return;
                            }
                        }
                        if(i == 9 && done == false)return;
                    }
                }
                
            }
        }
    }
    void solveSudoku(vector<vector<char>>& board) {
        vector<vector<int>> hash1(9 , vector<int> (9,0));  
        vector<vector<int>> hash2(9 , vector<int> (9,0));  
        vector<vector<int>> hash3(9 , vector<int> (9,0));
        for(int i = 0 ; i < board.size() ; i++){
            for(int j = 0; j < board[0].size() ; j++){
                if(board[i][j] != '.'){
                    hash1[i][board[i][j] - 49] = 1;
                    hash2[j][board[i][j] - 49] = 1;
                    hash3[block_num(i,j)][board[i][j] - 49] = 1;
                }
            }
        }
        // bool done = false;
        solve(board ,hash1 , hash2 , hash3 );

    }
};
60503