<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{
    using compact = std::array<char, 81>;

    compact compactify(auto const& board) noexcept{
        compact result{};
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                result[i * 9 + j] = board[i][j];
        return result;
    }

    struct compact_hash{
        size_t operator()(auto const& board) const noexcept{
            return std::hash<std::string_view>{}(std::string_view(board.data(), board.size()));
        }
    };

    auto get_row_numbers(auto const& board, int row){
        std::unordered_set<int> result{};
        for (int i = 0; i < 9; i++)
            if (char at = board[row][i]; at != '.')
                result.insert(at - '0');
        return result;
    }

    auto get_col_numbers(auto const& board, int col){
        std::unordered_set<int> result{};
        for (int i = 0; i < 9; i++)
            if (char at = board[i][col]; at != '.')
                result.insert(at - '0');
        return result;
    }

    auto get_3x3_numbers(auto const& board, int row, int col){
        std::unordered_set<int> result{};
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (char at = board[row / 3 * 3 + i][col / 3 * 3 + j]; at != '.')
                    result.insert(at - '0');
        return result;
    }

    inline static std::unordered_set<compact, compact_hash> cannot_solve{};

    // Pre & post: all rows, cols, and 3x3s have no repeat numbers
    // Tries to solve sudoku
    bool can_solve_sudoku(auto& board){
        bool remaining_dots = false;
        int dot_row{};
        int dot_col{};
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                if (board[i][j] == '.'){
                    remaining_dots = true;
                    dot_row = i;
                    dot_col = j;
                }
        if (!remaining_dots)
            return true;
        if (cannot_solve.count(compactify(board)))
            return false;
        std::unordered_set<int> this_row_numbers = get_row_numbers(board, dot_row);
        std::unordered_set<int> this_col_numbers = get_col_numbers(board, dot_col);
        std::unordered_set<int> this_3x3_numbers = get_3x3_numbers(board, dot_row, dot_col);
        for (int i = 1; i <= 9; i++){
            if (this_row_numbers.count(i) || this_col_numbers.count(i) || this_3x3_numbers.count(i))
                continue;
            board[dot_row][dot_col] = i + '0';
            if (can_solve_sudoku(board))
                return true;
        }
        board[dot_row][dot_col] = '.';
        cannot_solve.insert(compactify(board));
        return false;
    }

    public:
        void solveSudoku(std::vector<std::vector<char>>& board){
            can_solve_sudoku(board);
        }
};
87934