# Bacetrack C++ sollution with bit ops AC in 36ms

• ``````class Solution {public:
unordered_map<int,int> int2bit;
unordered_map<int,int> bit2int;
bool solveSudoku(int n, vector<pair<int,int> >& blank, vector<vector<char> > &board, vector<int>&row, vector<int>&col, vector<int>&cell)     {
if(n==blank.size())
{
return true;
}
int i=blank[n].first;
int j=blank[n].second;
int idx=(i/3)*3+j/3;
int pos=row[i]&col[j]&cell[idx];
while(pos)
{
int p=pos&(-pos);
pos=pos-p;
board[i][j]='0'+bit2int[p];
row[i]&=~p;
col[j]&=~p;
cell[idx]&=~p;
if(solveSudoku(n+1,blank,board,row,col,cell))
{

return true;
}
row[i]|=p;
col[j]|=p;
cell[idx]|=p;
}
return false;
}
void solveSudoku(vector<vector<char> > &board) {

for(int k=1;k<=9;k++)
{
int2bit[k]=1<<(k-1);
bit2int[1<<(k-1)]=k;
}
int limit=(1<<9)-1;
vector<int> row(9,limit);
vector<int> col(9,limit);
vector<int> cell(9,limit);
vector<pair<int,int> > blank;
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(board[i][j]!='.')
{
int k=int2bit[board[i][j]-'0'];
row[i]&=~k;
col[j]&=~k;
int idx=(i/3)*3+j/3;
cell[idx]&=~k;
}
else
{
blank.push_back(pair<int,int>(i,j));
}
}
}
solveSudoku(0,blank,board,row,col,cell);
}};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.