Accepted 4ms c++ solution use backtracking and bitmask, easy understand.


  • 94

    In this problem, we can go row by row, and in each position, we need to check if the column, the 45° diagonal and the 135° diagonal had a queen before.

    Solution A: Directly check the validity of each position, 12ms:

    class Solution {
    public:
        std::vector<std::vector<std::string> > solveNQueens(int n) {
            std::vector<std::vector<std::string> > res;
            std::vector<std::string> nQueens(n, std::string(n, '.'));
            solveNQueens(res, nQueens, 0, n);
            return res;
        }
    private:
        void solveNQueens(std::vector<std::vector<std::string> > &res, std::vector<std::string> &nQueens, int row, int &n) {
            if (row == n) {
                res.push_back(nQueens);
                return;
            }
            for (int col = 0; col != n; ++col)
                if (isValid(nQueens, row, col, n)) {
                    nQueens[row][col] = 'Q';
                    solveNQueens(res, nQueens, row + 1, n);
                    nQueens[row][col] = '.';
                }
        }
        bool isValid(std::vector<std::string> &nQueens, int row, int col, int &n) {
            //check if the column had a queen before.
            for (int i = 0; i != row; ++i)
                if (nQueens[i][col] == 'Q')
                    return false;
            //check if the 45° diagonal had a queen before.
            for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j)
                if (nQueens[i][j] == 'Q')
                    return false;
            //check if the 135° diagonal had a queen before.
            for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j)
                if (nQueens[i][j] == 'Q')
                    return false;
            return true;
        }
    };
    

    Solution B: Use flag vectors as bitmask, 4ms:

    The number of columns is n, the number of 45° diagonals is 2 * n - 1, the number of 135° diagonals is also 2 * n - 1. When reach [row, col], the column No. is col, the 45° diagonal No. is row + col and the 135° diagonal No. is n - 1 + col - row. We can use three arrays to indicate if the column or the diagonal had a queen before, if not, we can put a queen in this position and continue.

    NOTE: Please don't use vector<bool> flag to replace vector<int> flag in the following C++ code. In fact, vector<bool> is not a STL container. You should avoid to use it. You can also get the knowledge from here and here.

    /**    | | |                / / /             \ \ \
      *    O O O               O O O               O O O
      *    | | |              / / / /             \ \ \ \
      *    O O O               O O O               O O O
      *    | | |              / / / /             \ \ \ \ 
      *    O O O               O O O               O O O
      *    | | |              / / /                 \ \ \
      *   3 columns        5 45° diagonals     5 135° diagonals    (when n is 3)
      */
    class Solution {
    public:
        std::vector<std::vector<std::string> > solveNQueens(int n) {
            std::vector<std::vector<std::string> > res;
            std::vector<std::string> nQueens(n, std::string(n, '.'));
            std::vector<int> flag_col(n, 1), flag_45(2 * n - 1, 1), flag_135(2 * n - 1, 1);
            solveNQueens(res, nQueens, flag_col, flag_45, flag_135, 0, n);
            return res;
        }
    private:
        void solveNQueens(std::vector<std::vector<std::string> > &res, std::vector<std::string> &nQueens, std::vector<int> &flag_col, std::vector<int> &flag_45, std::vector<int> &flag_135, int row, int &n) {
            if (row == n) {
                res.push_back(nQueens);
                return;
            }
            for (int col = 0; col != n; ++col)
                if (flag_col[col] && flag_45[row + col] && flag_135[n - 1 + col - row]) {
                    flag_col[col] = flag_45[row + col] = flag_135[n - 1 + col - row] = 0;
                    nQueens[row][col] = 'Q';
                    solveNQueens(res, nQueens, flag_col, flag_45, flag_135, row + 1, n);
                    nQueens[row][col] = '.';
                    flag_col[col] = flag_45[row + col] = flag_135[n - 1 + col - row] = 1;
                }
        }
    };
    

    But we actually do not need to use three arrays, we just need one. Now, when reach [row, col], the subscript of column is col, the subscript of 45° diagonal is n + row + col and the subscript of 135° diagonal is n + 2 * n - 1 + n - 1 + col - row.

    class Solution {
    public:
        std::vector<std::vector<std::string> > solveNQueens(int n) {
            std::vector<std::vector<std::string> > res;
            std::vector<std::string> nQueens(n, std::string(n, '.'));
            /*
            flag[0] to flag[n - 1] to indicate if the column had a queen before.
            flag[n] to flag[3 * n - 2] to indicate if the 45° diagonal had a queen before.
            flag[3 * n - 1] to flag[5 * n - 3] to indicate if the 135° diagonal had a queen before.
            */
            std::vector<int> flag(5 * n - 2, 1);
            solveNQueens(res, nQueens, flag, 0, n);
            return res;
        }
    private:
        void solveNQueens(std::vector<std::vector<std::string> > &res, std::vector<std::string> &nQueens, std::vector<int> &flag, int row, int &n) {
            if (row == n) {
                res.push_back(nQueens);
                return;
            }
            for (int col = 0; col != n; ++col)
                if (flag[col] && flag[n + row + col] && flag[4 * n - 2 + col - row]) {
                    flag[col] = flag[n + row + col] = flag[4 * n - 2 + col - row] = 0;
                    nQueens[row][col] = 'Q';
                    solveNQueens(res, nQueens, flag, row + 1, n);
                    nQueens[row][col] = '.';
                    flag[col] = flag[n + row + col] = flag[4 * n - 2 + col - row] = 1;
                }
        }
    };

  • 1

    Thank you very for your solution-sharing and explanation. I have learned a lot from you.


  • 0
    D

    Very clear explanation~!!


  • 4

    my java code follow your opinion

    public class Solution {
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> res=new ArrayList<List<String>>();
            String[] queens=new String[n];
            char[] initial=new char[n];
            Arrays.fill(initial,'.');
            Arrays.fill(queens,String.valueOf(Arrays.copyOf(initial,n)));
            int[] flag=new int[5*n-2];
            Arrays.fill(flag,1);
            slove(res,queens,flag,0,n);
            return res;
        }
        private void slove(List<List<String>> res,String[] queens,int[] flag,int row,int n){
            if(row==n){
                res.add(new ArrayList<String>(Arrays.asList(queens)));
                return;
            }
            for(int col=0;col!=n;col++){
                if(flag[col]==1 && flag[n+col+row]==1 && flag[4*n-2+col-row]==1){
                    flag[col]=0;
                    flag[n+col+row]=0;
                    flag[4*n-2+col-row]=0;
                    char[] chars=queens[row].toCharArray();
                    
                    chars[col]='Q';
                    queens[row]=String.valueOf(chars);
                    
                    slove(res,queens,flag,row+1,n);
                    
                    chars=queens[row].toCharArray();
                    chars[col]='.';
                    queens[row]=String.valueOf(chars);
                    
                    flag[col]=1;
                    flag[n+col+row]=1;
                    flag[4*n-2+col-row]=1;
                }
            }
        }
    }

  • 0
    K

    Similar to sudoko solution.


  • 0
    W
    This post is deleted!

  • 0
    K

    Thanks for sharing, very clear and easy to understand !


  • 0
    A

    with reference, the program won't need to allocate memory can copy to generate a new vector<string>


  • 0
    F

    clear answer~


  • 0

    Thanks for sharing your solution. What is (and how to analyze) the time complexity of it?


  • 0
    D

    goooooood answer


  • 0
    B

    I changed the int to bool type, I thought it won't make any difference, but result shows that bool is slower (about 12ms).


  • 3

    In fact, vector<bool> is not a STL container. You should avoid to use it. You can also get the knowledge from http://stackoverflow.com/questions/17794569/why-is-vectorbool-not-a-stl-container and http://stackoverflow.com/questions/670308/alternative-to-vectorbool


  • 0
    K
    This post is deleted!

  • 0
    Y

    @qkhhly
    The time complexity of the improved solution which is the one with line indicators, is 0_1468382259321_nn.JPG


  • 0
    C
    This post is deleted!

  • 1
    E

    34 lines, 6ms. A little improvement based on your idea.
    Using an int array to record the column of queens in previous rows.

    class Solution {
    public:

    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string> > res;
    	vector<string> temp(n, string(n,'.'));
    	int dp[n];
    	helper(res, temp, dp, 0, n);
    	return res;
    }
    

    private:

    void helper(vector<vector<string> > &res, vector<string> &temp, int dp[], int row, int n){
    	if(row==n){
    		res.push_back(temp);
    		return;
    	}
    	for(int col=0;col<n;++col){
    		if(valid(dp, row, col, n)){
    			dp[row]=col;
    			temp[row][col]='Q';
    			helper(res, temp, dp, row+1,n);
    			temp[row][col]='.';
    		}
    	}
    }
    
    bool valid(int dp[], int row, int col, int n){
    	for(int i=0;i<row;++i){
    		if(dp[i]==col || abs(row-i)==abs(dp[i]-col)){
    			return false;
    		}
    	}
    	return true;
    }
    

    };


  • 0
    T

    @ericxu10101 said in Accepted 4ms c++ solution use backtracking and bitmask, easy understand.:

    abs(row-i) == abs(dp[i]-col) is very smart.


  • 0
    H

    How is my code too slow? It applies the same logic except that it is written in java.

    public List<List<String>> solveNQueens(int n) {
            List<List<String>> ans = new ArrayList<List<String>>();
            char[][] curr = new char[n][n];
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    curr[i][j] = '.';
            backtrack(ans, curr, n, 0, 0);
            return ans;
        }
        private static void backtrack(List<List<String>>ans, char[][] curr, int left, int row, int col){
            if(left==0){
                List<String> temp = new ArrayList<String>();
                for(int i=0;i<curr.length;i++)
                    temp.add(new String(curr[i]));
                ans.add(temp);
            }
            else{
                for(int i=row;i<curr.length;i++){
                    for(int j=col;j<curr.length;j++){
                        if(isValid(curr, i, j)){
                            curr[i][j] = 'Q';
                            backtrack(ans,curr,left-1, row+1, 0);
                            curr[i][j] = '.';
                        }
                    }
                }
            }
        }
        private static boolean isValid(char[][] curr, int row, int col){
            for(int i=0;i<curr.length;i++){
                if(curr[row][i]=='Q')
                    return false;
                if(curr[i][col]=='Q')
                    return false;
            }
            int i = 1;
            int n = curr.length;
            while(row+i<n || col+i<n || col-i>=0 || row-i>=0){
                if(row+i<n && col+i<n && curr[row+i][col+i]=='Q' 
                    || row+i<n && col-i>=0 && curr[row+i][col-i]=='Q'
                    || row-i>=0 && col-i>=0 && curr[row-i][col-i]=='Q'
                    || row-i>=0 && col+i<n && curr[row-i][col+i]=='Q')
                    return false;
                i++;
            }
            return true;
        }
    

  • 0

    Nice solution. Here is a 4ms Java solution, beats 99%.

    Any suggestions that make it faster will be appreciated.

    public class Solution {
        // pie = row + col;
        // na = n - 1 + col - row;
        int[] sol;
        public List<List<String>> solveNQueens(int n) {
            sol = new int[n];
            List<List<String>> res = new ArrayList();
            DFS(res, n, 0, 0, 0, 0);
            return res;
        }
        private void DFS(List<List<String>> res, int N, int row, int shu, int pie, int na) {
            int ok = ((1 << N) - 1) & ~(shu | pie | na);
            while (ok != 0) {
                int p = ok & -ok;
                ok ^= p;
                sol[row] = p;
                if (row == N - 1) {
                    List<String> list = new ArrayList();
                    for (int i = 0; i < N; i++) {
                        StringBuilder sb = new StringBuilder();
                        for (int c = 0; c < N; c++) {
                            if ((1 << c) == sol[i]) sb.append("Q");
                            else sb.append(".");
                        }
                        list.add(sb.toString());
                    }
                    res.add(list);
                } else {
                    DFS(res, N, row + 1, shu ^ p, (pie ^ p) >> 1, (na ^ p) << 1);
                }
            }
        }
    }
    

  • 0

    repost all the code!


Log in to reply