Solve Sudoku

• Time : O(1)

• Space : O(1)

• since input board is 9 x 9 we can solve problem in constant time. so we can say time complexity becomes O(1).

#include <vector>
using namespace std;

bool helper(vector<int>& cells, vector<int>& rows, vector<int>& cols, vector<vector<int>>& board, int pos) {
    if(pos == 81) return true;
    int y = pos / 9, x = pos % 9;
    if(board[y][x])
        return helper(cells, rows, cols, board, pos + 1);
    int mask = (1<<10) - 2;
    int row = y, col = x, cell = y / 3 * 3 + x / 3;
    mask &= ~(rows[row] | cols[col] | cells[cell]);
    while(mask) {
        int p = mask & -mask;
        mask -= p;
        rows[row] += p; cols[col] += p; cells[cell] += p;
        board[y][x] = log2(p);
        
        if(helper(cells, rows, cols, board, pos + 1))
            return true;
        
        board[y][x] = 0;
        rows[row] -= p; cols[col] -= p; cells[cell] -= p;
    }
    return false;
}

vector<vector<int>> solveSudoku(vector<vector<int>> board) {
    vector<int> cells(9), rows(9), cols(9);
    for(int i = 0; i < 9; i++)
        for(int j = 0; j < 9; j++) {
            if(board[i][j] == 0) continue;
            int row = i, col = j, cell = i / 3 * 3 + j / 3;
            rows[row] ^= (1<<board[i][j]);
            cols[col] ^= (1<<board[i][j]);
            cells[cell] ^= (1<<board[i][j]);
        }
    helper(cells, rows, cols, board, 0);
    return board;
}