Accepted 4ms c++ solution use backtracking and bitmask, easy 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