# My simple DFS C++ code (4ms)

• Standard DFS and backtracking problem. For each '.', try to fill it with a valid number (valid is defined as the number is not used in its row, column, block). Three bool arraies are used to faciliate such check.

``````   class Solution {
private:
void buildUsedFlag(vector<vector<char>> &board, bool rowUsed[9][9], bool colUsed[9][9], bool blkUsed[9][9])
{
for(auto i=0; i<9 ; ++i)
for(auto j=0; j<9; ++j)
if(board[i][j]!='.') rowUsed[i][board[i][j]-'1'] = colUsed[j][board[i][j]-'1'] = blkUsed[(i/3) *3 +(j/3)][board[i][j]-'1'] =true  ;
}
bool dfs(vector<vector<char>> &board, bool rowUsed[9][9], bool colUsed[9][9], bool blkUsed[9][9], int row, int col)
{
while(row < 9 && board[row][col] != '.') { row += (col+1)/9; col = (col+1) % 9; }
if(row==9) return true;
int i, blkIdx = (row/3) * 3 + col/3;
for(i=0; i<9; i++)
{
if(rowUsed[row][i] || colUsed[col][i] || blkUsed[blkIdx][i]) continue;
rowUsed[row][i] = colUsed[col][i] = blkUsed[blkIdx][i] = true;
board[row][col] = '1' + i;
if(dfs(board, rowUsed, colUsed, blkUsed, row ,col)) return true;
rowUsed[row][i] = colUsed[col][i] = blkUsed[blkIdx][i] = false;
}
board[row][col] = '.';
return false;
}

public:
void solveSudoku(vector<vector<char>>& board) {
bool rowUsed[9][9], colUsed[9][9], blkUsed[9][9];
fill_n(&rowUsed[0][0], 81, false);
fill_n(&colUsed[0][0], 81, false);
fill_n(&blkUsed[0][0], 81, false);
buildUsedFlag(board, rowUsed, colUsed, blkUsed);
dfs(board, rowUsed, colUsed, blkUsed, 0 ,0);
}
};``````

• first, the dfs is actually for cycle, not a real dfs.

second, the correct place of "board[row][col] = '.';" should be in for cycle, that's what backtracking does. (yes, you can get correct result since you only judge ***used matrices)

``````    bool dfs(vector<vector<char>> &board, bool rowUsed[9][9], bool colUsed[9][9], bool blkUsed[9][9], int row, int col)
{
while(row < 9 && board[row][col] != '.') { row += (col+1)/9; col = (col+1) % 9; }
if(row==9) return true;
int i, blkIdx = (row/3) * 3 + col/3;
for(i=0; i<9; i++)
{
if(rowUsed[row][i] || colUsed[col][i] || blkUsed[blkIdx][i]) continue;
rowUsed[row][i] = colUsed[col][i] = blkUsed[blkIdx][i] = true;
board[row][col] = '1' + i;
/*-->*/     board[row][col] = '.';
if(dfs(board, rowUsed, colUsed, blkUsed, row ,col)) return true;
rowUsed[row][i] = colUsed[col][i] = blkUsed[blkIdx][i] = false;
}
//      board[row][col] = '.';
return false;
}
``````

• I think that you mean /-->/ board[row][col] = '.'; should be added under if(dfs(board, rowUsed, colUsed, blkUsed, row ,col)) return true;, right?

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