C++ well structured backtracking


  • 0
    public:
        vector<vector<string>> res;
        vector<string> board;
        unordered_set<int> rows; // unsafe rows
        unordered_set<int> diag45; // unsafe 45 degree diagnals (row-col is constant)
        unordered_set<int> diag135; // unsafe 135 degree diagnals (row+col is constant)
        
        vector<vector<string>> solveNQueens(int n) {
            board = vector<string>(n, string(n, '.'));
            backTracking(n);
            return res;
        }
        
    private:
        void backTracking(int n, int col = 0) {
            if (col == n) {
                res.push_back(board);
                return;
            }
            
            for (int row = 0; row < n; ++row) {
                if (isInvalid(row, col)) continue;
                updateUnsafe(row, col, true);
                backTracking(n, col+1);
                updateUnsafe(row, col, false);
            }
        }
        
        void updateUnsafe(int row, int col, bool add) {
            if (add)
                board[row][col] = 'Q', rows.insert(row), diag45.insert(row-col), diag135.insert(row+col); 
            else 
                board[row][col] = '.', rows.erase(row), diag45.erase(row-col), diag135.erase(row+col); 
        }
        
        bool isInvalid(int row, int col) {
            return rows.count(row) or diag45.count(row-col) or diag135.count(row+col);
        }
    

Log in to reply
 

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