<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:

    // vector<vector<int>> intsudoku(vector<vector<char>> board){
    //     vector<vector<int>> sudoku(9, vector<int>(9, -1));
    //     for (int i=0; i<9; i++)
    //     {    
    //         for (int j=0; j<9; j++)
    //         {
    //             if (int (board[i][j])>=48 && int (board[i][j])<=57)
    //                 sudoku[i][j] = int (board[i][j])-48;
    //             cout << sudoku[i][j] << ',';

    //         }
            
    //         cout << endl;
    //     }
    //     return sudoku;
    // }
    vector<char> getPotentialNum(vector<vector<char>>& board, int i, int j){
        vector<bool> used(9, true);
        int x = 0;

        // row [j]
        for ( x=0; x<9; x++)
        {
            if (board[i][x] != '.'){
                used[int (board[i][x])-49] = false;
            }
        }
        // col [i]
        for ( x=0; x<9; x++)
        {
            if (board[x][j] != '.'){
                used[int (board[x][j])-49] = false;
            }
        }
        // 3x3
        int grid_i = (i/3)*3;
        int grid_j = (j/3)*3;
        
        for (int gi=0; gi<3; gi++)
        {
            for (int gj=0; gj<3; gj++)
            {
                if (board[grid_i+gi][grid_j+gj] != '.'){
                    used[int (board[grid_i+gi][grid_j+gj])-49] = false;
                }
            }
        }
        vector<char> nums;
        for (x=0; x<9; x++)
            if (used[x]){
                nums.push_back(char(x+1+48));
            }
        return nums;
    }

    bool helper(vector<vector<char>>& board, int idx){
        vector<vector<char>>tmp = board;

        while (board[idx/9][idx%9] != '.' && idx<80){
            idx = idx+1;
        }
        int i = idx/9;
        int j = idx%9;
        vector<char> nums;
        nums = getPotentialNum(tmp, i, j);
        if (idx == 80){
            if (nums.size()>=1){
                tmp[i][j] = nums[0];
                board = tmp;
            }
            return true;
        }
        
        if (nums.size()<=0)
            return false;
        
        // if (idx > 75){

        // cout << "idx:" << idx << "i:" << i << ", j:" << j << "   ";
        // for (auto &n : nums){
        //     cout << n << ',';
        // }
        // cout << endl;
        // }
        
        for (auto &n : nums){
            tmp[i][j] = n;
            if (helper(tmp, idx+1)){
                // cout << "TRUE " << "i:" << i << ", j:" << j << '.' << n << endl;
                board = tmp;
                return true;
            }
        }
        return false;

    }


    void solveSudoku(vector<vector<char>>& board) {
        helper(board, 0);
    }
};

// [
// [".",".","4","6","7","8","9","1","2"],
// ["6","7","2","1","9","5","3","4","8"],
// ["1","9","8","3","4","2","5","6","7"],
// ["8","5","9","7","6","1","4","2","3"],
// ["4","2","6","8","5","3","7","9","1"],
// ["7","1","3","9","2","4","8","5","6"],
// ["9","6","1","5","3","7","2","8","4"],
// ["2","8","7","4","1","9","6","3","5"],
// [".","4","5","2","8","6","1","7","9"]]
52665