# My 6 ms C++ Solution Using Backtracking

• ``````class Solution {
private:
struct Block {
int row, column;
bitset<9> eliminate;
Block(int row, int column, bitset<9> eliminate) : row(row), column(column), eliminate(eliminate) {}
};

bool validate(vector<vector<char>>& checkMatrix, vector<int>& record, Block** minBlock) {
int minPossible = INT_MAX;

for (int row = 0; row != 9; row++) {
for (int column = 0; column != 9; column++) {
if (checkMatrix[row][column] != '.') {
continue;
}
bitset<9> eliminate;
for (int i = 0; i != 9; i++) {
if (checkMatrix[i][column] != '.') {
eliminate[checkMatrix[i][column] - '1'] = 1;
}
if (checkMatrix[row][i] != '.') {
eliminate[checkMatrix[row][i] - '1'] = 1;
}
int innerRow = (row / 3) * 3 + (i / 3),
innerColumn = (column / 3) * 3 + i % 3;

if (checkMatrix[innerRow][innerColumn] != '.') {
eliminate[checkMatrix[innerRow][innerColumn] - '1'] = 1;
}
}
int choices = 0;
for (int i = 0; i != 9; i++) {
choices += eliminate[i] ? 0 : 1;
}
if (choices == 1) {
for (int i = 0; i != 9; i++) {
if (!eliminate[i]) {
checkMatrix[row][column] = '1' + i;
record.push_back(row * 9 + column);
*minBlock = NULL;
return validate(checkMatrix, record, minBlock);
}
}
}
else {
if (choices == 0) {
if (*minBlock) delete *minBlock;
return false;
}
if (choices < minPossible){
minPossible = choices;
if (*minBlock) delete *minBlock;
*minBlock = new Block(row, column, eliminate);
}
}
}
}
return true;
}

void recover(vector<vector<char>>& checkMatrix, vector<int>& record) {
for (vector<int>::iterator it = record.begin(); it != record.end(); it++) {
checkMatrix[*it / 9][*it % 9] = '.';
}
}

int getTestIndex(Block* block) {
int i = 0;
for (; i != 9; i++) {
if (!block->eliminate[i]) {
block->eliminate[i] = true;
break;
}
}
return i == 9 ? -1 : i;
}

public:

void solveSudoku(vector<vector<char>>& board) {
Block* block;
vector<pair<Block*, vector<int>>> st;
do {
block = NULL;
vector<int> record;
if (validate(board, record, &block)){
if (block == NULL)  {
for (vector<pair<Block*, vector<int>>>::iterator it = st.begin(); it != st.end(); it++){
delete it->first;
}
return;
}
st.push_back(make_pair(block, record));
board[block->row][block->column] = '1' + getTestIndex(block);
}
else {
recover(board, record);
while (st.size()) {
vector<pair<Block*, vector<int>>>::iterator last = --st.end();
int index = getTestIndex(last->first);
if (index == -1) {
recover(board, last->second);
board[last->first->row][last->first->column] = '.';
delete last->first;
st.pop_back();
}
else {
board[last->first->row][last->first->column] = '1' + index;
break;
}
}
if (!st.size()) return;
}
} while (true);
}
};
``````

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