Solve the Sudoku

Given an incomplete Sudoku configuration in terms of a 9 x 9 2-D square matrix (grid[][]), the task to find a solved Sudoku. For simplicity, you may assume that there will be only one unique solution.

• Time : O(9^(n*n))
• Space : O(1)

c++

vector<int> cells(9), rows(9), cols(9);
class Solution
{
    bool helper(int grid[N][N], int pos) {
        if(pos == 81) return true;
        int y = pos / 9, x = pos % 9;
        if(grid[y][x]) return helper(grid, pos + 1);
        int row = y, col = x, cell = (y / 3) * 3 + (x / 3);
        int mask = rows[row] | cols[col] | cells[cell];
        for(int i = 1; i <= 9; i++) {
            if(mask & (1<<i)) continue;
            rows[row] ^= (1<<i);
            cols[col] ^= (1<<i);
            cells[cell] ^= (1<<i);
            grid[y][x] = i;
            if(helper(grid, pos + 1))
                return true;
            grid[y][x] = 0;
            rows[row] ^= (1<<i);
            cols[col] ^= (1<<i);
            cells[cell] ^= (1<<i);
        }
        return false;
    }
public:
    //Function to find a solved Sudoku.
    bool SolveSudoku(int grid[N][N])
    {
        for(int i = 0; i < 9; i++)
            rows[i] = cols[i] = cells[i] = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(grid[i][j]) {
                    int row = i;
                    int col = j;
                    int cell = (i / 3) * 3 + (j / 3);
                    rows[row] |= (1<<grid[i][j]);
                    cols[col] |= (1<<grid[i][j]);
                    cells[cell] |= (1<<grid[i][j]);
                }
            }
        }

        return helper(grid, 0);
    }

    //Function to print grids of the Sudoku.
    void printGrid (int grid[N][N])
    {
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++)
                cout<<grid[i][j]<<' ';
        }
    }
};