# My C++ solution (3ms)

• It is just simply depth first search. The cell which has least choices always goes first.

``````class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
int i, j;
blank = 0;
for(i = 0; i < 9; i++) {
for(j = 0; j < 9; j++) {
if(board[i][j]=='.') {
dboard[i][j] = 0;
blank++;
}
else
dboard[i][j] = board[i][j] - '0';
}
}
setCandidate();
dfs();
for(i = 0; i < 9; i++) {
for(j = 0; j < 9; j++) {
if(board[i][j] == '.')
board[i][j] = '0'+dboard[i][j];
}
}
}

bool dfs() {
if(blank == 0) return true;
int x, y, i, j, k;
getCandidate(x, y);
for(k = 1; k < 10; k++) {
if(candidate[x][y][k] == 0) continue;
dboard[x][y] = k;
--blank;
int candidate_copy[9][9][10];
copyArr(candidate_copy, candidate);
updateCandidate(x, y, k);
if(dfs()) return true;
copyArr(candidate, candidate_copy);
++blank;
dboard[x][y] = 0;
}
return false;
}

void setCandidate() {
int i, j, k, r, c;
for(i = 0; i < 9; i++) {
for(j = 0; j < 9; j++) {
for(k = 1; k < 10; k++) {
candidate[i][j][k] = 1;
}
}
}
for(i = 0; i < 9; i++) {
for(j = 0; j < 9; j++) {
int digit = dboard[i][j];
if(digit != 0) {
updateCandidate(i, j, digit);
}
}
}
for(i = 0; i < 9; i++) {
for(j = 0; j < 9; j++) {
int cnt = 0;
for(k = 1; k < 10; k++) {
if(candidate[i][j][k] != 0)
++cnt;
}
candidate[i][j][0] = cnt;
}
}
}

void getCandidate(int &x, int &y) {
int i, j, min = 10;
for(i = 0; i < 9; i++) {
for(j = 0; j < 9; j++) {
if(dboard[i][j] == 0 && candidate[i][j][0] < min) {
min = candidate[i][j][0];
x = i;
y = j;
}
}
}
}

void updateCandidate(int x, int y, int d) {
int i, j;
for(i = 0; i < 9; i++) {
if(dboard[i][y] == 0 && candidate[i][y][d] == 1) {
candidate[i][y][d] = 0;
candidate[i][y][0]--;
}
}
for(j = 0; j < 9; j++) {
if(dboard[x][j] == 0 && candidate[x][j][d] == 1) {
candidate[x][j][d] = 0;
candidate[x][j][0]--;
}
}
int a = 3*(x/3), b = 3*(y/3);
for(i = a; i < a+3; i++) {
for(j = b; j < b+3; j++) {
if(dboard[i][j] == 0 && candidate[i][j][d] == 1) {
candidate[i][j][d] = 0;
candidate[i][j][0]--;
}
}
}
}

void copyArr(int dst[][9][10], int src[][9][10]) {
int i, j, k;
for(i = 0; i < 9; i++) {
for(j = 0; j < 9; j++) {
for(k = 0; k < 10; k++) {
dst[i][j][k] = src[i][j][k];
}
}
}
}

int dboard[9][9];
/* candidate[x][y][0] is the count of valid choices.
candidate[x][y][digit] = 0 or 1, marks if a digit is valid at position (x,y) */
int candidate[9][9][10];
int blank; // the count of blank cell to be fill
};
``````

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