# Leetcode Title: N-Queens I and II

2023-03-17

### N-Queens

The n-queens puzzle is the problem of placing n queens on ann×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.

### N-Queens II

Now, instead outputting board configurations, return the total number of distinct solutions.

Thinking:

Classic N Queen’s question, you can refer to any algorithm book. Generally, it is solved through the retrospective method. Here is a solution that has not been optimized.

In fact, I have considered this problem, because the symmetry of the chessboard should have a better solution based on group theory. This is to consult a mathematician.

As long as the specific transformation is eliminated, only the number of solutions can be calculated. Of course, I hope the performance is better.

Question solution:

``````class Solution {
public:
vector<vector<string>> solution;

void generate_solution(const vector<int>& queen)
{
vector<string> s;
for(int i = 0; i < queen.size(); ++i)
{
string l(queen.size(), '.');
l[queen[i]] = 'Q';
s.emplace_back(move(l));     // avoid copy!
}
solution.emplace_back(move(s));
}

void traverse_solution_space(vector<int>& queen, int placed, int total)
{
if (placed == total)
{
generate_solution(queen);
return;
}

// try place the queens
for(int i = 0; i < queen.size(); ++i)
{
bool valid = true;
// verify the position
for(int j = 0; j < placed; ++j)
{
if (i == queen[j] ||  // same column
abs(queen[j] - i) == placed - j) // diagonal attack
{
valid = false;
break;
}
}

if (valid)
{
queen[placed] = i;
traverse_solution_space(queen, placed + 1, total);
}
}
}

vector<vector<string> > solveNQueens(int n) {
solution.clear();
vector<int> queen(n);

traverse_solution_space(queen, 0, n);

return solution;
}
};``````

``````class Solution {
public:
vector<int> board;
vector<int> avail;

int valid_solutions;

void traverse_solution_space(int k, int n)
{
if (k == n)
{
++valid_solutions;
return;
}

for(int i = 0; i < n; ++i)
if (avail[i] == 0)
{
bool iok = true;
for(int j = 0; j < k; ++j)
if (abs(board[j] - i) == k - j)
{
iok = false;
break;
}
if (iok)
{
avail[i] = 1;
board[k] = i;
traverse_solution_space(k + 1, n);
avail[i] = 0;
}
}
}

int totalNQueens(int n)
{
valid_solutions = 0;

board.resize(n);
avail.resize(n);

fill(begin(avail), end(avail), 0);

traverse_solution_space(0, n);

return valid_solutions;
}
};``````

source