<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 {
    inline void updatePossible(unordered_set<char> possible[9][9], int x, int y, int num)
    {
        for (int i = 0; i != 9; i++)
        {
            possible[x][i].erase(num);
            possible[i][y].erase(num);
            possible[x/3*3+i/3][y/3*3+i%3].erase(num);
        }
    }
    bool trySolve(vector<vector<char>>& board, unordered_set<char> possible[9][9], const vector<int> &path, int index)
    {
        int x = path[index] >> 16;
        int y = path[index] & 0x0000FFFF;

        if (possible[x][y].size() == 1)
        {
            board[x][y] = *possible[x][y].begin();
            if (index + 1 < path.size())
            {
                unordered_set<char> newpossible[9][9];
                for (int i = 0; i != 9; i++)
                for (int j = 0; j != 9; j++)
                {
                    newpossible[i][j] = possible[i][j];
                }
                updatePossible(newpossible, x, y, board[x][y]);
                bool result = trySolve(board, newpossible, path, index+1);
                if (!result)
                {
                    board[x][y] = '.';
                }
                return result;
            }
            else
                return true;
        }
        else if (possible[x][y].size() == 0)
        {
            return false;
        }
        else
        {
            if (index + 1 < path.size())
            {
                for (int num : possible[x][y])
                {
                    board[x][y] = num;
                    unordered_set<char> newpossible[9][9];
                    for (int i = 0; i != 9; i++)
                    for (int j = 0; j != 9; j++)
                    {
                        newpossible[i][j] = possible[i][j];
                    }
                    updatePossible(newpossible, x, y, board[x][y]);
                    bool result = trySolve(board, newpossible, path, index+1);
                    if (!result)
                    {
                        board[x][y] = '.';
                        continue;
                    }
                    else
                        return true;
                }
            }

            return false;
        }
    }
public:
    void solveSudoku(vector<vector<char>>& board) {
        vector<int> path;
        unordered_set<char> possible[9][9];
        unordered_set<char> area[9] = 
       {{'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'}};
        unordered_set<char> row[9] = 
       {{'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'}};
        unordered_set<char> column[9] = 
       {{'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'},
        {'1','2','3','4','5','6','7','8','9'}};

        for (int x = 0; x != 9; x++)
        {
            for (int y = 0; y != 9; y++)
            {
                if (board[x][y] != '.')
                {
                    area[x/3*3+y/3].erase(board[x][y]);
                    row[x].erase(board[x][y]);
                    column[y].erase(board[x][y]);
                }
            }
        }

        for (int x = 0; x != 9; x++)
        {
            for (int y = 0; y != 9; y++)
            {
                if (board[x][y] == '.')
                {
                    for (auto num : area[x/3*3+y/3])
                    {
                        if (row[x].count(num) > 0 && column[y].count(num) > 0)
                            possible[x][y].insert(num);                        
                    }

                }
            }
        }

        bool has1 = false;
        do
        {
            has1 = false;
            for (int x = 0; x != 9; x++)
            {
                for (int y = 0; y != 9; y++)
                {
                    if (possible[x][y].size() == 1)
                    {
                        board[x][y] = *possible[x][y].begin();
                        updatePossible(possible, x, y, board[x][y]);
                        has1 = true;
                    }
                }
            }
        }
        while (has1);


        for (int x = 0; x != 9; x++)
        {
            for (int y = 0; y != 9; y++)
            {
                if (board[x][y] == '.')
                {
                    path.emplace_back((x<<16)|y);
                }
            }
        }

        if (path.size() > 0)
            trySolve(board, possible, path, 0);
    }
};
142796