<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:
    static constexpr size_t sudokuSize = 9;

    using used_digits_t = std::bitset<9>;

    struct SudokuState {
        char UNSET_CELL = -1;

        array<used_digits_t, sudokuSize> rowsUsed;
        array<used_digits_t, sudokuSize> colsUsed;
        array<used_digits_t, sudokuSize> boxesUsed;
        std::vector<vector<char>> board = std::vector<vector<char>>(sudokuSize, vector<char>(sudokuSize, UNSET_CELL));

        // pair<size_t, size_t> firstUnset{0,0};

        bool checkAndSetUsed(size_t i, size_t j, char digit) {
            auto& rowUsed = rowsUsed[i];
            auto& colUsed = colsUsed[j];
            auto& boxUsed = boxesUsed[(i / 3) * 3 + (j / 3)];

            std::cout << "checkAndSetUsed: " << i << " " << j << "\n";
            bool canSet = !rowUsed.test(digit) && !colUsed.test(digit) && !boxUsed.test(digit);
            if (!canSet) {
                return false;
            }

            rowUsed.set(digit);
            colUsed.set(digit);
            boxUsed.set(digit);

            // cout << i << " " << j << "\n";
            board[i][j] = digit;

            return true;
        }

        pair<size_t, size_t> findFirstUnset() {
            // if (firstUnset.first >= sudokuSize && firstUnset.second >= sudokuSize) {
            //     return {sudokuSize, sudokuSize};
            // }

            // auto [i, j] = firstUnset;
            for (size_t i = 0; i < sudokuSize; ++i) {
                for (size_t j = 0; j < sudokuSize; ++j) {
                    if (board[i][j] == UNSET_CELL) {
                        // firstUnset = {i, j};
                        return {i, j};
                    }
                }
            }

            return {sudokuSize, sudokuSize};
        }        
    };

    SudokuState parseSudoku(const vector<vector<char>>& board) {

        SudokuState state{};

        for (size_t i = 0; i < sudokuSize; ++i) {
            for (size_t j = 0; j < sudokuSize; ++j) {
                if (board[i][j] == '.') {
                    continue;
                }
                char digit = board[i][j] - '1';

                state.checkAndSetUsed(i, j, digit);
            }
        }

        return state;
    }
    SudokuState solveSudokuImpl(SudokuState initState) {
        stack<SudokuState> states;

        states.push(initState);

        auto isStateFinished = [] (SudokuState& s) {
            auto firstUnset = s.findFirstUnset();
            std::cout << "firstUnset check: " << firstUnset.first << " " << firstUnset.second << "\n";
            return firstUnset.first == sudokuSize && firstUnset.second == sudokuSize;
        };

        while (!states.empty()) {
            auto currState = std::move(states.top());
            states.pop();

            bool isFinished = isStateFinished(currState);
            std::cout << "isStateFinished" << " " << isFinished << "\n";

            if (isFinished) {
                return currState;
            }
            auto firstUnset = currState.findFirstUnset();
            for (size_t digit = 0; digit < 9; ++digit) {
                auto nextState = currState;
                if (nextState.checkAndSetUsed(firstUnset.first, firstUnset.second, digit)) {
                    states.push(std::move(nextState));
                }
            }
            std::cout << "finish\n";
        }
        
        return initState;
    }

    vector<vector<char>> printSolvedState(vector<vector<char>> board) {
        for (size_t i = 0; i < sudokuSize; ++i) {
            for (size_t j = 0; j < sudokuSize; ++j) {
                board[i][j] += '1';
            }
        }
        return board;
    }

    void solveSudoku(vector<vector<char>>& board) {
        auto initialState = parseSudoku(board);

        auto solvedState = solveSudokuImpl(initialState);
        board = printSolvedState(solvedState.board);
    }
};
166309