```
/*
The idea is to use the lower 9 bits of an int to store the occurrence of 1~9 in a row/col/sub_board
e.g. row[0] is "..9748..." then the 9 low bits of the int representing row[0] are "111001000"(left to right = high to low bit)
col[0] is ".7.......", the 9 low bits are "001000000"
sub_board[0][0] is "..9"
"7.."
".2.", the 9 low bits are "101000010"
Thus for the empty cell at board[0][0], the candidates are row[0] | col[0] | sub[0][0] = "111001010"
All the 0 bits are possible candidates for this empty cell. (1, 3, 5, and 6, aka. the 1st, 3rd, 5th, and 6th bits are 0)
So for each empty cell at board[x][y], we could use (row[x] | col[y] | sub[x/3][y/3]) to generate the candidates for it.
We go through all the candidates (aka the 0 bits index) in the same backtracking method as the simple backtracking solution.
*/
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
initialize(board);
solve(board,0,0);
}
private:
vector<int> row; //store row info
vector<int> col; //store col info
vector<vector<int>> sub; //store sub_board info
/*given the board, initialize the row, col, and sub_board info*/
void initialize(vector<vector<char>>& board){
row = vector<int>(9,0);
col = vector<int>(9,0);
sub = vector<vector<int>>(3, vector<int>(3,0));
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
if(board[i][j] == '.') continue;
int num = board[i][j] - '0';
int mask = 1 << (num-1);
row[i] |= mask;
col[j] |= mask;
sub[i/3][j/3] |= mask;
}
}
}
/*use backtracking to solve the sudoku starting at cell board[r][c]*/
bool solve(vector<vector<char>>& board, int r, int c) {
for(; r < 9; r++){
for(; c < 9; c++){
//find the next empty cell
if(board[r][c] == '.'){
//generate the candidates for this cell
int cands = (row[r] | col[c] | sub[r/3][c/3]);
//all 1~9 are occupied, impossible to fill the cell, backtrack to the previous empty cell
if(cands == 511) return false;
for(int i = 0; i < 9; i++){
int mask = 1 << i;
//try candidates
if((cands & mask) == 0) {
//update all info
cands |= mask;
row[r] |= mask;
col[c] |= mask;
sub[r/3][c/3] |= mask;
//fill the cell
board[r][c] = (char)('1' + i);
//go to next empty space
if(solve(board, r, c)) return true;
//backtrack, need to rollback info to the state before update
int recover = ~mask;
cands &= recover;
row[r] &= recover;
col[c] &= recover;
sub[r/3][c/3] &= recover;
board[r][c]='.';
}
}
//tried all possible candidates, but still reached here, backtrack to the previous empty cell
return false;
}
}
c = 0;
}
//filled all empty cells, done!
return true;
}
};
```