<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:
bool isSpotValid(std::vector<std::vector<char>>& board, int row, int col) {
    int N = 9;
    //check row
    std::unordered_set<char> set;
    for(int i = 0; i < N; i++) {
        char c = board[row][i];
        if(c != '.') {
            auto s = set.insert(c);
            if (!s.second) return false;
        }
    }
    set.clear();

    //check col
    for(int i = 0; i < N; i++) {
        char c = board[i][col];
        if(c != '.') {
            auto s = set.insert(c);
            if (!s.second) return false;
        }
    }
    set.clear();
    //check box;
    int row_offset = (row/3)*3;
    int col_offset = (col/3)*3;

    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            char c = board[row_offset + i][col_offset + j];
            if(c != '.') {
                auto s = set.insert(c);
                if (!s.second) return false;
            }
        }
    }
    return true;
}



void solveSudoku(std::vector<std::vector<char>>& board) {
    int N = 9;
    std::unordered_set<loc> filled_spots;

    //store spots that are not to be changed.
    for(int row = 0; row < N; row++) {
        for(int col = 0; col < N; col++) {
            char c = board[row][col];
            if(c != '.') {
                filled_spots.insert({row, col});
            }
        }
    }

    std::vector<std::pair<loc, int>> stack;
    for(int row = 0; row < N; row++) {
        for(int col = 0; col < N; col++) {
            loc l = {row, col};
            //if spot is filled from start we dont do anything with it.
            if(filled_spots.count(l) != 0) {
                continue;
            }

            char& c = board[row][col]; // current char
            bool valid = false; // flag for if a number can be placed in.
            int starting_number = 0; // starting number to put in.

            if(!stack.empty() && l == stack.back().first) {
                //if this spot is on the stack then we use the next number
                starting_number = stack.back().second + 1;
            } else {
                //if not place it on the stack
                stack.emplace_back(l, starting_number);
            }
            for(int i = starting_number; i < numbers.size(); i++) {
                c = numbers[i]; //place next number
                if(isSpotValid(board, row, col)) { // check if valid
                    valid = true; //flag if valid
                    stack.back().second = i; // store number
                    break; //break loop
                }
            }

            if(!valid) { //if we could not place a number we backtrack
                stack.pop_back();
                c = '.'; //clear the current spot.
                auto t = stack.back().first;
                row = t.first;
                col = t.second - 1;
            }

        }
    }
}
};
240765