Short with less space and time complexity comparison to editorial

amazon
Tags: #<Tag:0x00007f2428349b50>

#1

`
//to keep track of row ,column and box has particular element or not
unordered_map<int,int>r,c,box;

bool find(vector<vector>&A,int i,int j)
{
// i==9 && j== 9 mean completed sudoku
if(i+1==A.size() && j==A[0].size()) return true;

// j==9 mean end of row so move to next row
if(j==A[0].size()) {i++; j=0;}

//if A[i][j]=='.' move to next column
if(A[i][j]!='.') return find(A,i,j+1);

// traverse all possible value at particular position i , j
for(int k=1;k<=9;k++)
{
    // to check kth bit is set of not
    int p=1<<k;
    // if not set
    if((r[i] & p )==0 && (c[j] & p)==0 && (box[(i/3)*3+(j/3)] & p)==0)
    {
        //set row , column and box bit 
        r[i]|=p;
        c[j]|=p;
        
        // ((i/3)*3+(j/3)) will give index of box from 0 to 8
        box[(i/3)*3+(j/3)]|=p;
        A[i][j]=(k+'0');
        if(find(A,i,j+1)) return true;
        
        // unable to complete sudoku backtrack and unset kth bit in row, column and box
        r[i]^=p;
        c[j]^=p;
        box[(i/3)*3+(j/3)]^=p;
        A[i][j]='.';
    }
}
return false;

}
void Solution::solveSudoku(vector<vector > &A) {
// clear all global variables
r.clear();
c.clear();
box.clear();
for(int i=0;i<A.size();i++)
{
for(int j=0;j<A[0].size();j++)
{
if(A[i][j]==’.’) continue;
int p=1<<(A[i][j]-‘0’);
//set row , column and box bit with given value in the grid
r[i]|=p;
c[j]|=p;
// ((i/3)*3+(j/3)) will give index of box from 0 to 8
box[(i/3)*3+(j/3)]|=p;
}
}
find(A,0,0);
}
`