https://leetcode.com/problems/n-queens/description/
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
Example:
Input: 4 Output: [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
[Solution]
Recursively decide the Queen's position under previous condition.
Main operation of recursive function:
Each recursive call represents a row.
1.Put the queen on a position(column) of current row.
2.Check if this queen's position conflict with previous queen's position
If not conflict, start next row.
If conflict, skip this position.
3.repeat 1&2 until every position has been tried.
Recursive function terminates when :
When the n-th queen's legal position is decided, you get a legal solution.
There is no more queen's position needed to be decided.
Let's write code:
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ret;
vector<string> ans;
vector<int> pos(n,0);
putqueen(n,0,pos,ans,ret);
return ret;
}
void putqueen(int n, int row,
vector<int>& pos,
vector<string>& ans,
vector<vector<string>>& ret){
//terminate condition
if(row >= n){
ret.push_back(ans);
return;
}
//n possible position
for(int p=0;p<n;p++){
int i=row-1;
for(;i>=0;i--){ //check if p is a legal position
if(pos[i]==p || pos[i]-p == row-i || p-pos[i] == row-i )
break;
}
if(i<0){//if p is legal, start next row
pos[row]=p;
string str(n,'.');
str[p]='Q';
ans.push_back(str);
putqueen(n, row+1, pos, ans, ret);
ans.pop_back();
}
}
}
};
