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

typedef std::pair<int, int> loc;

namespace std
{
    template<class A,class B>
    struct hash<pair<A,B>>{
        size_t operator() (const pair<A,B>& p) const {
            return hash<A>{}(p.first) << 1 ^ hash<B>{}(p.second);
        }
    };
}

class Solution {
    const std::array<char, 9> numbers = {'1','2','3','4','5','6','7','8','9'};
public:
void solveSudoku(std::vector<std::vector<char>>& board) {
    const int N = 9;
    const int offset = 3;
    std::array<std::unordered_set<char>, N> row_sets;
    std::array<std::unordered_set<char>, N> col_sets;
    std::array<std::array<std::unordered_set<char>, offset>, offset> box_sets;
    std::unordered_set<loc> fixed_spots;

    //the first thing to do is to build the sets and find all the starting points that cannot be changed.
    for(int row = 0; row < N; row++) {
        for(int col = 0; col < N; col++) {
            int row_offset = (row/3)%3;
            int col_offset = (col/3)%3;
            char c = board[row][col];
            if(c != '.') {
                row_sets[row].insert(c);
                col_sets[col].insert(c);
                box_sets[row_offset][col_offset].insert(c);
                fixed_spots.insert({row, col});
            }
        }
    }

    //now that its done, we are going to start the back tracing algo.
    std::vector<std::pair<std::pair<int, int>, int>> stack;
    for(int row = 0; row < N; row++) {
        for(int col = 0; col < N; col++) {
            loc l = {row, col};
            if(fixed_spots.count(l) != 0) { // If this spot was fixed in the inital board move on.
                continue;
            }

            int starting_number = 0; //starting number to search
            int valid = false; //flag if it is possible to insert
            if(!stack.empty() && l == stack.back().first) { //checking if spot is in stack.
                starting_number = stack.back().second + 1;
            } else {
                stack.emplace_back(l, 0); //if not place one.
            }

            int row_offset = (row/offset)%offset; // finding box
            int col_offset = (col/offset)%offset;

            for(int i = starting_number; i < numbers.size(); i++) {
                char c = numbers[i];
                //checking if number can be inserted.
                int rc = row_sets[row].count(c);
                int cc = col_sets[col].count(c);
                int bc = box_sets[row_offset][col_offset].count(c);
                if(rc + cc + bc == 0) { //if it can insert it and break out of loop.
                    row_sets[row].insert(c);
                    col_sets[col].insert(c);
                    box_sets[row_offset][col_offset].insert(c);
                    valid = true;
                    stack.back().second = i;
                    board[row][col] = c;
                    break;
                }
            }

            if(!valid) {
                 // clear board
                stack.pop_back(); //pop stack
                char c = numbers[stack.back().second]; // get last number
                row = stack.back().first.first;
                col = stack.back().first.second;
                row_offset = (row/offset)%offset; // finding box
                col_offset = (col/offset)%offset;
                board[row][col] = '.';
                row_sets[row].erase(c);
                col_sets[col].erase(c);
                box_sets[row_offset][col_offset].erase(c);
                col = col - 1; // take into account increment
            }
        }
    }
}
};
17396