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

• 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;
}
};``````

• 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.

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

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