1#include <bits/stdc++.h>
2using namespace std;
3
4// Classic N-Queens via backtracking.
5// cols[r] = column of the queen on row r.
6bool safe(const vector<int>& cols, int row, int col) {
7 for (int r = 0; r < row; ++r)
8 if (cols[r] == col || abs(cols[r] - col) == row - r)
9 return false;
10 return true;
11}
12
13void solve(int row, int n, vector<int>& cols,
14 vector<vector<int>>& solutions) {
15 if (row == n) { solutions.push_back(cols); return; }
16 for (int c = 0; c < n; ++c) {
17 if (safe(cols, row, c)) {
18 cols[row] = c;
19 solve(row + 1, n, cols, solutions);
20 cols[row] = -1; // backtrack
21 }
22 }
23}
24
25vector<vector<int>> nQueens(int n) {
26 vector<int> cols(n, -1);
27 vector<vector<int>> solutions;
28 solve(0, n, cols, solutions);
29 return solutions;
30}
