<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:
    vector<int> rowMoves = {0, 0, -1, 1};
    vector<int> colMoves = {1, -1, 0, 0};
    bool valid = false;
    void solveSudoku(vector<vector<char>>& board) {
        int n = 0;
        vector<pair<int, int>> positions;
        for(int i=0; i<board.size(); i++) {
            for(int j=0; j<board.size(); j++) {
                if ( board[i][j] == '.') { 
                    n = n + 1;
                    positions.push_back(make_pair(i, j));
                }
            }
        }
        cout << "N is: " << n <<"\n";
        backtrack(board, 0, n, positions);
        // return;
    }

    void backtrack(vector<vector<char>>&board, int k, int n, vector<pair<int, int>> positions) {
        // cout << "k " << k << "\n";
        
        if ( k == n ) {
            processSolution(board, positions);
            if ( valid ) {
                cout << "Its Valid!" <<"\n"; return;
            };
        } else {
            // cout << "positions: " << positions[k].first << " , " << positions[k].second << "\n";

            k = k + 1;
            vector<char> candidates = getCandidates(board, k, n, positions[k - 1]);
            if (!valid) {
                for(int i=0; i<candidates.size(); i++) {
                    board[positions[k-1].first][positions[k-1].second] = candidates[i];
                    backtrack(board, k, n, positions); // backtrack using the value 
                    if (valid ) break;
                    board[positions[k-1].first][positions[k-1].second] = '.';
                }
            }
        }
    }

    void processSolution(vector<vector<char>>& board, vector<pair<int, int>> positions) {

        for(int i=0; i<board.size(); i++ ) {
            for(int j=0; j<board[0].size(); j++) {
                if (!isValid(i, j, board)) {
                    // initialiseBoard(board, positions);
                    return;
                }
            }
        }
        valid = true;
    }

    // checks if the current cell holds a valid value or not 
    bool isValid (int x, int y, vector<vector<char>>&board) { 
        // check for the row and column
        int currentVal = board[x][y];
        for(int i=0; i<board.size(); i++) {
            if ( i != x && board[i][y] == currentVal ) return false;
            if ( i != y && board[x][i] == currentVal ) return false;
        }
        int startRow = (x / 3) * 3;
        int startCol = (y / 3) * 3;
        // check for the 3x3 grid 
        for(int i=startRow; i< startRow + 3; i ++) {
            for(int j = startCol; j < startCol + 3; j++){
                if ( (i != x || j!= y) && board[i][j] == currentVal ) return false;
            }
        }
        return true;
    }

    vector<char> getCandidates(vector<vector<char>>&board, int k, int n, pair<int, int> position) {
        vector<char> candidates;
        int temp[10];
        memset(temp, 0, sizeof(temp));
        int row = position.first;
        int col = position.second;

        
        for(int i=0; i<board.size(); i++) {
            if (board[i][col] != '.' ) temp[board[i][col] - '0']++; // check the entire column 
            if (board[row][i] != '.' ) temp[board[row][i] - '0']++; // check the entire row 
        }
        // check the grid 
        int matrixRow = row/3, matrixCol = col/3;
        for(int i= matrixRow * 3; i< matrixRow * 3 + 3; i++) {
            for(int j=matrixCol * 3; j< matrixCol * 3 + 3; j++) {
                if (board[i][j] != '.' && i!=row && j!=col) temp[board[i][j] - '0']++;
            }
        }
        // cout << "candidates for position " << position.first << " , " << position.second << " are: " << "\n";

        for(char i='1'; i<='9'; i++) {
            if (temp[i - '0'] == 0)  { 
                // cout << i << " ";
                candidates.push_back(i); 
            }
        }
        // cout << "\n";
        
        return candidates;
    }

    




};
40909