The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.
class Solution {
private:
void search(int n, int r, vector<string>& v, vector<vector<string>>& vv, vector<int>& forward, vector<int>& backward,
vector<int>& columns)
{
if(r == n) vv.push_back(v);
for(int c = 0; c < n; c++)
{
if(!forward[c+r] && !backward[r+n-c-1] && !columns[c])
{
v[r][c] = 'Q';
forward[c+r] = backward[r+n-c-1] = columns[c] = 1;
search(n, r+1, v, vv, forward, backward, columns);
forward[c+r] = backward[r+n-c-1] = columns[c] = 0;
v[r][c] = '.';
}
}
}
public:
vector<vector<string>> solveNQueens(int n)
{
vector<int> forward(2*n-1), backward(2*n-1), columns(n);
vector<vector<string>> vv;
vector<string> v(n, string(n, '.'));
search(n, 0, v, vv, forward, backward, columns);
return vv;
}
};
