My simple DFS C++ code (4ms)


  • 0
    D

    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);
            }
        };

  • 0
    D

    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;
        }
    

  • 0
    R

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


Log in to reply
 

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