Recursive solution in C++, maybe concise if without comment.


  • 0
    J

    My solution uses c++. Please see the comment in the code for detail.
    For space complexity: O(n) because of calling at most n recursive functions.
    For time complexity, I think it is O(n^2) + O(time to check conflicts).
    O(time to check conflicts): I think it is O(n^3), looks like somehow inefficient. I don't know whether there is faster method to find conflicts.

    class Solution {
    public:
        /**
         * Recursive. r is row, c is column, which means the queen should place on this position. 
         * solveNQueens(row) = sum of possible solveNQueens(row-1)
         * vector<location> placed: stores the location that has been used.
         **/
        struct location{
            int row;
            int col;
            location(int r, int c):row(r),col(c){}
        };
        void solveNQueens(int r, vector<location>& placed, vector<vector<string> >& ret, vector<string>& board)
        {
            /**
             * If r < 0, means that all 0 ~ n-1 row has been succesfully filled with Q.
             * so we add the board into result.
             **/
            if(r < 0){
                ret.push_back(board);
                return;
            }
            for(int i = 0; i < board.size(); i++){
                //first check whether location (r, i) is valid or not
                bool conflict = false;
                for(int j = 0; j < placed.size(); j++){
                    //check whether the column or the diagonal line is used.
                    if(placed[j].col == i || std::abs(placed[j].row-r) == std::abs(placed[j].col-i)){
                        conflict = true;
                        break;
                    }
                }
                //if this location(r, j) has conflict with prevoius locations, ignore it.
                if(conflict) continue;
                //else, this location(r,j) do not have conflict, use it and go into a upper row: r-1.
                board[r][i] = 'Q';
                placed.push_back(location(r, i));
                solveNQueens(r-1,placed, ret, board);
                placed.pop_back();
                board[r][i] = '.';
            }
        }
        
        vector<vector<string> > solveNQueens(int n) {
            vector<string> board(n,string(n, '.'));
            vector<location> placed;
            vector<vector<string> > ret;
            for(int i = 0; i < n; i++){
                board[n-1][i] = 'Q';
                placed.push_back(location(n-1, i));
                solveNQueens(n-2,placed, ret, board);
                placed.pop_back();
                board[n-1][i] = '.';
            }
            return ret;
        }
    };

  • 0
    J

    Since there is no formula to solve this puzzle, you must check all N! (factorial N) permutations of N queens. So the time complexity is at least O(N!). And your conflict checking method takes O(N) time, so it is O(N! * N) totally.


  • 0
    J

    Oh yes, you are right, thank you. I am not good at analysing complexity, it seems my solution is generally O(n^(n+1)).


Log in to reply
 

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