My concise DFS C++ solution using three unordered_map<int, bool>.


  • 3
    V
    class Solution {
    public:
        unordered_map<int, bool> column, obliqueLeft, obliqueRight;
        int total;
        void NQueensHelper(int row, int n) {
            if (row == n+1) {
                total++;
                return;
            }
            for (int i = 1; i <= n; i++) {
                if (!column[i] && !obliqueLeft[i + row] && !obliqueRight[i - row]) {
                    column[i] = obliqueLeft[i + row] = obliqueRight[i - row] = true;
                    NQueensHelper(row+1, n);
                    column[i] = obliqueLeft[i + row] = obliqueRight[i - row] = false;
                }
            }
        }
        int totalNQueens(int n) {
            column.clear();
            obliqueLeft.clear();
            obliqueRight.clear();
            total = 0;
            NQueensHelper(1, n);
            return total;
        }
    };
    

    Each unordered_map represents whether column/left oblique line/right oblique line is occupied before.


Log in to reply
 

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