<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 HasItem(vector<char> &v, char item) {
        auto it = find(v.begin(), v.end(), item);
        if (it != v.end()) return true;
        return false;
    }
    void RemoveItem(vector<char> &v, char k) {
        auto it = find(v.begin(), v.end(), k);
        if (it != v.end()) v.erase(it);
    }
    void Refresh(vector<vector<char> > &board, vector<vector<char> > &hints, char row, char col) {
        char number = board[row][col];
        if (number == '.') return;

        for (char pos = row * 9; pos < row * 9 + 9; pos++) RemoveItem(hints[pos], number);
        for (char pos = col; pos < col + 81; pos += 9) RemoveItem(hints[pos], number);

        const int a = row / 3, b = col / 3;
        char pos;
        for (int i = 3 * a; i < 3 * a + 3; i++) {
            for (int j = 3 * b; j < 3 * b + 3; j++) {
                pos = 9 * i + j;
                RemoveItem(hints[pos], number);
            }
        }
    }
    bool SolveSudokuBackTrackingLoop(vector<vector<char> > &board, vector<vector<char> > &hints, vector<char > hint_order) {
        if(hint_order.empty()) return true;

        const char pos = hint_order[0];
        hint_order.erase(hint_order.begin());
        const char row = pos / 9, col = pos % 9;

        for(char hint : hints[pos]) {
            board[row][col] = hint;
            vector<vector<char> > hints_copy = hints;
            hints_copy[pos].clear();
            Refresh(board, hints_copy, row, col);

            for(char i:hint_order) {
                if(hints_copy[i].empty()) {
                    goto break_twice;
                }
            }
            if(SolveSudokuBackTrackingLoop(board, hints_copy, hint_order)) return true;
            break_twice: {}
        }
        board[row][col] = '.';
        return false;
    }
    void SolveSudokuBackTracking(vector<vector<char> > &board) {
        vector<vector<char> > hints(81, vector<char>{'1', '2', '3', '4', '5', '6', '7', '8', '9'});
        vector<char> hint_order;
        char pos;

        for (char row = 0; row < 9; row++) {
            for (char col = 0; col < 9; col++) {
                if (board[row][col] != '.') {
                    pos = 9 * row + col;
                    hints[pos].clear();
                    Refresh(board, hints, row, col);
                }
            }   
        }
        for (char i = 2; i < 10; i++) {
            for (pos = 0; pos < 81; pos++) {
                if (hints[pos].size() == i) {
                    hint_order.push_back(pos);
                }   
            }
        }

        SolveSudokuBackTrackingLoop(board, hints, hint_order);
    }
    void solveSudoku(vector<vector<char>>& board) {
        vector<vector<char> > hints(81, vector<char>{'1', '2', '3', '4', '5', '6', '7', '8', '9'});
        char empty_cells = 0, prev_empty_cells = 0;

        for (char row = 0; row < 9; row++) {
            for (char col = 0; col < 9; col++) {
                if (board[row][col] == '.') empty_cells++;
                else { hints[9 * row + col].clear(); };
            }
        }

        while (empty_cells != prev_empty_cells) {
            prev_empty_cells = empty_cells;
            for (char row = 0; row < 9; row++) {
                for (char col = 0; col < 9; col++) {
                    Refresh(board, hints, row, col);
                }
            }
            int a, b;
            for (int i = 0; i < 81; i++) {
                if (hints[i].size() == 1) {
                    a = i / 9;
                    b = i % 9;
                    board[a][b] = hints[i][0];
                    empty_cells--;
                    hints[i].clear();
                    Refresh(board, hints, a, b);
                }   
            }
            char count, index, pos;
            for (char number = '1'; number <= '9'; number++) {
                for (char row = 0; row < 9; row++) {
                    count = 0;
                    for (char col = 0; col < 9; col++) {
                        pos = 9 * row + col;
                        if (HasItem(hints[pos], number)) {
                            count++;
                            index = pos;
                        }
                    }
                    if (count == 1) {
                        board[index / 9][index % 9] = number;
                        hints[index].clear();
                        empty_cells--;
                        Refresh(board, hints, index / 9, index % 9);
                    }
                }
                for (char col = 0; col < 9; col++) {
                    count = 0;
                    for (char row = 0; row < 9; row++) {
                        pos = 9 * row + col;
                        if (HasItem(hints[pos], number)) {
                            count++;
                            index = pos;
                        }
                    }
                    if (count == 1) {
                        board[index / 9][index % 9] = number;
                        hints[index].clear();
                        empty_cells--;
                        Refresh(board, hints, index / 9, index % 9);
                    }
                }
                char a, b, c, d;
                for (char box = 0; box < 9; box++) {
                    count = 0;
                    a = box / 3;
                    b = box % 3;
                    // printf("Box: %d, %d\n", a, b);
                    for (char i = 0; i < 9; i++) {
                        c = 3 * a + i / 3;
                        d = b * 3 + i % 3;
                        if (HasItem(hints[9 * c + d], number)) {
                            count++;
                            index = 9 * c + d;
                        }
                    }   
                    // printf("Count: %d\n", count);
                    if (count == 1) {
                        // printf("FITTTTTTTTTTTTTTTTTT: %d, %d: %c\n", index / 9, index % 9, number);
                        board[index / 9][index % 9] = number;
                        hints[index].clear();
                        empty_cells--;
                        Refresh(board, hints, index / 9, index % 9);
                    }
                }
            }
        }
        if (empty_cells) {
            SolveSudokuBackTracking(board);
        }
    }
};
13478