Simple yet efficient solution 4ms in C++


  • 1
    class Solution {
    private:
        void search(int n, int r, vector<string>& v, vector<vector<string>>& vv, vector<int>& forward, vector<int>& backward, 
        vector<int>& columns)
        {
            if(r == n) vv.push_back(v);
            for(int c = 0; c < n; c++)
            {
                if(!forward[c+r] && !backward[r+n-c-1] && !columns[c])
                {
                    v[r][c] = 'Q';
                    forward[c+r] = backward[r+n-c-1] = columns[c] = 1;
                    search(n, r+1, v, vv, forward, backward, columns);
                    forward[c+r] = backward[r+n-c-1] = columns[c] = 0;
                    v[r][c] = '.';
                }
            }
        }
    public:
        //AC - 4ms - best submission;
        vector<vector<string>> solveNQueens(int n) 
        {
            vector<int> forward(2*n-1), backward(2*n-1), columns(n); //using int instead of bool accelerate from 16ms to 8ms;
            vector<vector<string>> vv;
            vector<string> v(n, string(n, '.')); //using predefined board instead of creating a new string each time, accelerating from 8ms to 4ms;
            search(n, 0, v, vv, forward, backward, columns);
            return vv;
        }
    };

  • 1

    Primitive

    test

    class Solution {
    private:
        void search(int n, int r, vector<string>& v, vector<vector<string>>& vv, vector<int>& forward, vector<int>& backward, 
        vector<int>& columns) {
            if(r == n) vv.push_back(v);
            for(int c = 0; c < n; c++) {
                if(!forward[c+r] && !backward[r+n-c-1] && !columns[c]) {
                    v[r][c] = 'Q';
                    forward[c+r] = backward[r+n-c-1] = columns[c] = 1;
                    search(n, r+1, v, vv, forward, backward, columns);
                    forward[c+r] = backward[r+n-c-1] = columns[c] = 0;
                    v[r][c] = '.';
                }
            }
        }
    public:
        vector<vector<string>> solveNQueens(int n) {
            vector<int> forward(2*n-1), backward(2*n-1), columns(n);
            vector<vector<string>> vv;
            vector<string> v(n, string(n, '.'));
            search(n, 0, v, vv, forward, backward, columns);
            return vv;
        }
    };
    

    Follow-up

    test

    class Solution {
    private:
        int search(int n, int r, vector<int>& forward, vector<int>& backward, vector<int>& cols) {
            if(n == r) return 1;
            int sum = 0;
            for(int c = 0; c < n; ++c) {
                if(!forward[r+c] && !backward[n+r-c-1] && !cols[c]) {
                    forward[r+c] = backward[n+r-c-1] = cols[c] = 1;
                    sum += search(n, r+1, forward, backward, cols);
                    forward[r+c] = backward[n+r-c-1] = cols[c] = 0;
                }
            }
            return sum;
        }
    
    public:
        int totalNQueens(int n) {
            vector<int> forward(2*n-1), backward(2*n-1), cols(n);
            return search(n, 0, forward, backward, cols);
        }
    };
    

Log in to reply
 

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