Compact C++ solution, 8ms


  • 1
    K
    class Solution {
    private:
        vector<int> rows;
        vector<vector<string>> results;
        
    public:
        vector<vector<string>> solveNQueens(int n) {
            rows.resize(n, 0);
            results.clear();
            Backtrack(0, n);
            return results;
        }
        
        void AddResult() {
            int n = rows.size();
            vector<string> result(n, string(n, '.'));
            for (int i = 0; i < rows.size(); ++i)
                result[rows[i]][i] = 'Q';
            results.push_back(result);
        }
        
        bool IsNewQValid(int n) {
            for (int i = 0; i < n; i++) {
                if (rows[i] == rows[n] || n - i == abs(rows[n] - rows[i]))
                    return false;
            }
            return true;
        }
        
        void Backtrack(int n, int N) {
            if (n == N) {
                AddResult();
                return;
            }
            
            for (int i = 0; i < N; i++) {
                rows[n] = i;
                if (IsNewQValid(n))
                    Backtrack(n+1, N);
            }
        }
    };

Log in to reply
 

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