Shortest C++ solution in 0ms


  • 5
    L

    Idea is to use vectors to keep track of invalid positions , so validity can be checked in O(1) and put a queen in each column

    #include<vector>
    using namespace std;
    class Solution {
    public:
        int find(int n, int left, int i, int r, vector<int>&rows,vector<int>&d1,vector<int>&d2){
            if (left == 0)
                return 1;
            int j,sum=0;
                for (j=r; j<n; j++){
                    if (rows[j] || d1[i+j] || d2[n-1+i-j])
                        continue;
                    rows[j]=d1[i+j]=d2[n-1+i-j]=1;
                    sum += find(n, left-1, i+1, 0,rows,d1,d2 );
                    rows[j]=d1[i+j]=d2[n-1+i-j]=0;
                }
            return sum;
        }
        int totalNQueens(int n) {
            vector<int>  rows(n),d1(2*n-1),d2(2*n-1);
            return find(n,n,0,0,rows,d1,d2);
        }
    };

  • 2

    I share you with the same idea.

    Here is my 0ms c++ solution:

    class Solution {
    public:
        int totalNQueens(int n) {
            std::vector<int> flag(5 * n - 2, 1);
    		int res = 0;
            totalNQueens(flag, 0, n, res);
    		return res;
        }
    private:
        void totalNQueens(std::vector<int> &flag, int row, int &n, int &res) {
            if (row == n) {
                ++res;
    			return;
            }
            for (int col = 0; col != n; ++col)
                if (flag[col] && flag[col + row + n] && flag[col - row + 4 * n - 2]) {
                    flag[col] = flag[col + row + n] = flag[col - row + 4 * n - 2] = 0;
                    totalNQueens(flag, row + 1, n, res);
                    flag[col] = flag[col + row + n] = flag[col - row + 4 * n - 2] = 1;
                }
        }
    };
    

    Or:

    class Solution {
    public:
        int totalNQueens(int n) {
            std::vector<int> flag(5 * n - 2, 1);
            return totalNQueens(flag, 0, n);
        }
    private:
        int totalNQueens(std::vector<int> &flag, int row, int &n) {
            if (row == n)
                return 1;
            int res = 0;
            for (int col = 0; col != n; ++col)
                if (flag[col] && flag[col + row + n] && flag[col - row + 4 * n - 2]) {
                    flag[col] = flag[col + row + n] = flag[col - row + 4 * n - 2] = 0;
                    res += totalNQueens(flag, row + 1, n);
                    flag[col] = flag[col + row + n] = flag[col - row + 4 * n - 2] = 1;
                }
    		return res;
        }
    };
    

  • 1
    W

    The fourth argument r in find is unnecessary and you can remove it.


Log in to reply
 

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