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

    /*
    void SolveUtil(vector<vector<char>>& board, vector<int>& row, vector<int>& col, vector<vector<int>>&grid, int i, int j)
    {
        if (i == board.size())
        {
            //cout<<"i: "<<i<<" Size: "<<board.size()<<endl;
            return;
        }
        
        if (board[i][j]!= '.')
        {
            //cout<<"Board: "<<board[i][j] - '0'<<endl;
            SolveUtil(board, row, col, grid, j == board[0].size() -1 ? i+1: i, j == board[0].size() -1 ? 0 : j+1);
        }
        else
        {
            for (int n = 1; n <= 9; n++)
            {
                int mask = 1 << (n-1);
                // If row's nth bit is off and col's nth bit is off and grid's nth bit is off then
                if ( (row[i] & mask) == 0 && (col[j] & mask) == 0 && (grid[i/3][j/3] & mask) == 0 )
                {
                    //cout<<"Board: " << board[i][j]<<" ";
                    board[i][j] = n + '0';
                    row[i] = row[i] ^ mask;
                    col[j] = col[j] ^ mask;
                    grid[i/3][j/3] = grid[i/3][j/3] ^ mask;
                    SolveUtil(board, row, col, grid, j == board[0].size() -1 ? i+1: i, j == board[0].size() -1 ? 0 : j+1);
                    row[i] = row[i] ^ mask;
                    col[j] = col[j] ^ mask;
                    grid[i/3][j/3] = grid[i/3][j/3] ^ mask;
                    board[i][j] = '.'; 
                }
            }
        }
    }
    
    void solveSudoku(vector<vector<char>>& board) 
    {
        vector<int> row(9);
        vector<int> col(9);
        vector<vector<int>> grid(3, vector<int>(3));
        
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (board[i][j] != '.')
                {
                    int n = board[i][j] - '1';
                    row[i] = row[i] | 1 << n;
                    col[j] = col[j] | 1 << n;
                    grid[i/3][j/3] = grid[i/3][j/3] | 1 << n;
                }
                
            }
        }
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            { 
                cout<<board[i][j]<<" , ";
            }
            cout<<endl;
        }
        
        SolveUtil(board, row, col, grid, 0, 0);
    }
*/
    
typedef unordered_map<int, unordered_set<int>> hmap;
typedef unordered_map<int, unordered_map<int, int>> gmap;
// Time Complexity: O(9 ^(m*n))
// Space Complexity: O(m*n)
struct State {
    vector<vector<char>> board;
    vector<int> row;
    vector<int> col;
    vector<vector<int>> grid;
    int i;
    int j;
};

bool isComplete(const vector<vector<char>>& board) {
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            if (board[i][j] == '.') {
                return false;
            }
        }
    }
    return true;
}

bool isValidMove(int n, int i, int j, const vector<int>& row, const vector<int>& col, const vector<vector<int>>& grid) {
    int mask = 1 << n;
    return !(row[i] & mask) && !(col[j] & mask) && !(grid[i/3][j/3] & mask);
}

void applyMove(int n, int i, int j, vector<int>& row, vector<int>& col, vector<vector<int>>& grid, vector<vector<char>>& board) {
    int mask = 1 << n;
    row[i] ^= mask;
    col[j] ^= mask;
    grid[i/3][j/3] ^= mask;
    board[i][j] = n + '0';
}

void undoMove(int n, int i, int j, vector<int>& row, vector<int>& col, vector<vector<int>>& grid, vector<vector<char>>& board) {
    int mask = 1 << n;
    row[i] ^= mask;
    col[j] ^= mask;
    grid[i/3][j/3] ^= mask;
    board[i][j] = '.';
}

void solveSudoku(vector<vector<char>>& board) {
    vector<int> row(9, 0), col(9, 0);
    vector<vector<int>> grid(3, vector<int>(3, 0));

    // Initialize the state with the given board and precompute the bitsets for rows, columns, and grids
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != '.') {
                int mask = 1 << (board[i][j] - '0');
                row[i] |= mask;
                col[j] |= mask;
                grid[i / 3][j / 3] |= mask;
            }
        }
    }

    queue<State> q;
    q.push({board, row, col, grid, 0, 0});

    while (!q.empty()) {
        State state = q.front();
        q.pop();

        if (isComplete(state.board)) {
            board = state.board;
            return;
        }

        while (state.i < 9 && state.board[state.i][state.j] != '.') {
            state.j++;
            if (state.j == 9) {
                state.i++;
                state.j = 0;
            }
        }

        if (state.i == 9) continue;

        for (int n = 1; n <= 9; n++) {
            if (isValidMove(n, state.i, state.j, state.row, state.col, state.grid)) {
                applyMove(n, state.i, state.j, state.row, state.col, state.grid, state.board);
                q.push({state.board, state.row, state.col, state.grid, state.i, state.j});
                undoMove(n, state.i, state.j, state.row, state.col, state.grid, state.board);
            }
        }
    }
}

    
};
178065