<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:
    int f=0;
    void func(vector<vector<char>>& v,vector<vector<bool>> row,vector<vector<bool>> col,vector<vector<vector<bool>>> box,vector<vector<char>> vv,int ind){
        if(ind==81){
            f=1;
            v=vv;
            return;
        }
        int i,j,k;
        i=ind/9;
        j=ind%9;
        cout<<i<<" "<<j<<endl;
        if(v[i][j]=='.'){
            for(k=0;k<9;k++){
                if(!row[i][k]&&!col[j][k]&&!box[i/3][j/3][k]){
                    row[i][k]=true;
                    col[j][k]=true;
                    box[i/3][j/3][k]=true;
                    vv[i][j]='1'+k;
                    cout<<k+1<<" "<<'1'+k<<" "<<i/3<<" "<<j/3<<endl;
                    func(v,row,col,box,vv,ind+1);
                    vv[i][j]='.';
                    row[i][k]=false;
                    col[j][k]=false;
                    box[i/3][j/3][k]=false;
                    if(f==1){
                        break;
                    }
                }
            }
        }
        else{
            vv[i][j]=v[i][j];
            func(v,row,col,box,vv,ind+1);
        }
    }
    void solveSudoku(vector<vector<char>>& v) {
        vector<vector<bool>> row(9,vector<bool> (9,false));
        vector<vector<bool>> col(9,vector<bool> (9,false));
        vector<vector<vector<bool>>> box(3,vector<vector<bool>> (3,vector<bool> (9,false)));
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(v[i][j]!='.'){
                    row[i][v[i][j]-'1']=true;
                    col[j][v[i][j]-'1']=true;
                    int ii=i/3,jj=j/3;
                    box[ii][jj][v[i][j]-'1']=true;
                }
            }
        }
        int i,j,k;
        // cout<<"row\n";
        // for(i=0;i<9;i++){
        //     cout<<i<<endl;
        //     for(j=0;j<9;j++){
        //         cout<<row[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        // cout<<"col\n";
        // for(i=0;i<9;i++){
        //     cout<<i<<endl;
        //     for(j=0;j<9;j++){
        //         cout<<col[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        // cout<<"row col\n";
        // for(i=0;i<3;i++){
        //     for(j=0;j<3;j++){
        //         cout<<i<<" "<<j<<endl;
        //         for(k=0;k<9;k++){
        //             cout<<box[i][j][k]<<" ";
        //         }
        //         cout<<endl;
        //     }
        // }
        vector<vector<char>> vv(9,vector<char> (9,'.'));
        func(v,row,col,box,vv,0);
    }
};
256440