# A 6ms C++ Solution Using DFS and Bit Manipulation

• ``````class Solution { // 6ms
public:
void solveSudoku(vector<vector<char> > &board) {
mark(board);
dfs(board, 0);
}

private:
int used_num[3][9];
bool used_block[9][9];
bool status = false;

void mark(vector<vector<char> > &board) {
int temp;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
used_block[i][j] = (board[i][j] != '.');
if (used_block[i][j]) {
temp = 1 << (board[i][j] - '1');
used_num[0][i] |= temp;
used_num[1][j] |= temp;
used_num[2][i / 3 * 3 + j / 3] |= temp;
}
}
}
}

void mark(vector<vector<char> > &board, int row, int col, int num, bool type) {
int temp = (1 << num);
if (type) {
board[row][col] = char(num + '1');
used_block[row][col] = true;
used_num[0][row] |= temp;
used_num[1][col] |= temp;
used_num[2][row / 3 * 3 + col / 3] |= temp;
} else {
board[row][col] = '.';
used_block[row][col] = false;
used_num[0][row] ^= temp;
used_num[1][col] ^= temp;
used_num[2][row / 3 * 3 + col / 3] ^= temp;
}
}

inline bool check(int row, int col, int num) {
int temp = 1 << num;
return !(used_num[0][row] & temp) &&
!(used_num[1][col] & temp) &&
!(used_num[2][row / 3 * 3 + col / 3] & temp);
}

void print(vector<vector<char> > &board) {
cout << endl;
for (const auto &row : board) {
for (const char c : row) {
cout << c;
}
cout << endl;
}
cout << endl;
}

void dfs(vector<vector<char> > &board, int position) {
if (position == 81) {
status = true;
//            print(board);
return;
}
int row = position / 9, col = position % 9;
if (!used_block[row][col]) {
for (int num = 0; num < 9; num++) {
if (check(row, col, num)) {
mark(board, row, col, num, true);
dfs(board, position + 1);
if (status) { return; }
mark(board, row, col, num, false);
}
}
} else {
dfs(board, position + 1);
}
}
};
``````

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