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


  • 92

    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.

    /**    | | |                / / /             \ \ \
      *    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).


  • 2

    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.


Log in to reply