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

#include <algorithm>
#include <vector> 
#include <set>

class Solution {
public:
    bool findNextFreeCell(vector<vector<char>>& board, int prevR, int prevC, int& r, int& c) {
        bool found = false;
        int i, j;
        if (prevR == 8 && prevC ==8) {
            return false;
        }
        if (prevC ==8) {
            i = prevR+1;
            j = 0;
        } else {
            i=prevR;
            j=prevC+1;
        }

        for (; i<9; i++) {
            for (; j<9; j++) {
                if (board[i][j] == '.') {
                    r =i;
                    c =j;
                    found = true;
                    break;
                }
            }
            j = 0;
            if (found) {
                break;
            }
        }
        return found;
    }
    bool lastFreeCell(vector<vector<char>>& board, int r, int c) {
        int tmpR, tmpC;
        return !findNextFreeCell(board, r, c, tmpR, tmpC);

    }
    set<int> findFitDigits(vector<vector<char>>& board, int r, int c) {
        static set<int> fullRange = {1,2,3,4,5,6,7,8,9};
        static map<unsigned int,unsigned int> forSquaresStart = {{0,0},{1,0},{2,0},{3,3},{4,3},{5,3},{6,6},{7,6},{8,6}};
        set<int> tmp;
        set<int> tmp2;
        set<int> res;
        set<int> rowTaken;
        set<int> colTaken;
        set<int> squareTaken;
        for (int i=0; i<9; i++) {
            if (board[r][i] != '.') {
                rowTaken.insert(board[r][i]-'0');
            }
            if (board[i][c] != '.') {
                colTaken.insert(board[i][c] - '0');
            }
        }
        for (int i=forSquaresStart[r]; i<forSquaresStart[r]+3; i++) {
            for (int j=forSquaresStart[c]; j<forSquaresStart[c]+3; j++) {
                if (board[i][j] != '.') {
                    squareTaken.insert(board[i][j]-'0');
                }
            }
        }
        set_union(rowTaken.begin(), rowTaken.end(), colTaken.begin(), colTaken.end(),std::inserter(tmp,tmp.begin()));
        set_union(squareTaken.begin(), squareTaken.end(), tmp.begin(), tmp.end(),std::inserter(tmp2,tmp2.begin()));
        set_difference(fullRange.begin(), fullRange.end(), tmp2.begin(), tmp2.end(), std::inserter(res,res.begin()));
        return res;
    }
    void solveSudoku(vector<vector<char>>& board) {
        int firstR, firstC;
        bool found = findNextFreeCell(board, 0, -1, firstR, firstC);
        cout << firstR << " " << firstC << endl;
        if (!found) {
            //sudoku full
            return;
        }
        solveSudokuRec(board, firstR, firstC);
    }

private:

bool solveSudokuRec(vector<vector<char>>& board, int r, int c) {
    cout << "  start R = " << r << " C= " << c << endl;
    set<int> digitsForThisCell = findFitDigits(board, r, c);
    if (digitsForThisCell.size() == 0) { 
        cout << "!!!! return false !!!!" << endl;
        return false;
    }
    if (lastFreeCell(board, r, c) && digitsForThisCell.size() == 1) {
        board[r][c] = *digitsForThisCell.begin() + '0';
        return true;
    }
    for (auto& dig : digitsForThisCell) 
    {
        if (r==0 && c == 2) {
            cout << " dig= " << dig << endl;
        }
        board[r][c] = dig + '0';
        int nextR, nextC;
        bool status;
        status = findNextFreeCell(board, r, c, nextR, nextC);
        cout << " found next r= " << nextR << " c= " << nextC << endl;
        status = solveSudokuRec(board, nextR, nextC);
        if (status) { 
            return true;
        }
        
    } 
    board[r][c] = '.';
    return false;
}

};
131040