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.For example,
There exist two distinct solutions to the 4-queens puzzle:
[ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
class Solution {
public:
bool isValid(vector<int> placement, int row)
{
for(int i = 0; i< row; i++)
if (placement[i] == placement[row] || row - i == abs(placement[i] - placement[row]))
return false;
return true;
}
vector<string> getBoard(const vector<int> &placed)
{
vector<string> output;
for(int i = 0; i < placed.size(); i++)
{
string temp;
for(int j = 0; j < placed.size(); j++)
temp.push_back(j==placed[i]?'Q':'.');
output.push_back(temp);
}
return output;
}
void helper(int n, int row, vector<int>& placement, vector<vector<string>> &ans){
if (row == n) {
ans.push_back(getBoard(placement));
return;
}
for(int i = 0;i < n; i++) {
placement[row] = i;
if (isValid(placement, row))
helper(n, row+1, placement, ans);
}
}
vector<vector<string> > solveNQueens(int n) {
vector<vector<string>> ans;
vector<int> placement(n);
helper(n, 0, placement, ans);
return ans;
}
};
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> output;
vector<int> placed(n, 0);
int row = 0, col = 0;
while(true) {
if (col == n) {
if(row == 0) return output;
else {
row--;
col = placed[row]+1;
continue;
}
}
if (canPlace(placed, row, col)) {
placed[row] = col;
if (row == n-1) {
output.push_back(getBoard(placed));
col++;
}
else {
row++;
col = 0;
}
}
else
col++;
}
return output;
}
No comments:
Post a Comment