The n queens problem – analysis of the solution
Task:
Write a program that finds all placements of n queens on an n × n chessboard so that no two queens attack each other.
For the queens to be placed correctly, every row must contain exactly one queen, and no two queens may be in the same column or diagonal.
Input: The number n (4 ≤ n ≤ 11) is read from standard input.
Output: Print all possible placements of the queens, where each combination is shown as a sequence of n numbers representing the columns of the queens in rows 1 to n.
Example:
Input: 4 Output: 2 4 1 3 3 1 4 2
Instructions and idea of the solution
This task is a classic example of the backtracking algorithm. The idea is to place the queens row by row, and at every step check whether a queen can be placed without a conflict with the previous queens.
- We use an array (vector) that records the column of the queen in every row.
- For every new queen we check whether it attacks one of the previous queens (in the same column or diagonal).
- If the position is safe, we move recursively to the next row.
- If it is not, we go back and try the next possibility (a typical backtracking approach).
Solution in C++
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> queens; // Vector that stores the column of each queen
int n;
// Checks whether it is safe to place a queen in row 'currentRow'
bool isSafe(int currentRow) {
for (int previousRow = 0; previousRow < currentRow; previousRow++) {
// If two queens are in the same column
if (queens[previousRow] == queens[currentRow])
return false;
// If two queens are on the same diagonal
if (abs(queens[previousRow] - queens[currentRow]) == abs(previousRow - currentRow))
return false;
}
return true;
}
// Recursive function that places the queens row by row
void placeQueens(int row) {
if (row == n) {
// When all n queens are placed, print the solution
for (int i = 0; i < n; i++) {
cout << queens[i] + 1 << " "; // +1 so that columns go from 1 to n
}
cout << endl;
return;
}
// Try to place the queen in every column of the current row
for (int column = 0; column < n; column++) {
queens[row] = column; // Place the queen in the column
if (isSafe(row)) {
placeQueens(row + 1); // Continue with the next row
}
}
}
int main() {
cout << "Enter the number n (4 <= n <= 11): ";
cin >> n;
if (n < 4 || n > 11) {
cout << "Allowed values are from 4 to 11." << endl;
return 1;
}
queens.resize(n); // Initialize a vector of size n
placeQueens(0); // Start the recursion from the first row
return 0;
}
Code explanation
The program uses the vector queens, where each element is the column of the queen in a given row.
The function isSafe() checks whether the current queen conflicts with one of the previous queens according to these rules:
- If they are in the same column → conflict;
- If they are on the same diagonal → conflict;
- Otherwise → the placement is safe.
The recursive function placeQueens() goes in order from the first to the last row.
When it reaches the case row == n, it means that all queens have been placed successfully and we have found a valid solution, which is printed on the screen.
Comment on efficiency and possible improvements
This algorithm uses pure recursion and has exponential complexity (of order O(n!)), because it checks a large number of possible combinations.
Possible improvements:
- Using helper arrays to track occupied columns and diagonals (
column[],diag1[],diag2[]) — this avoids going through all previous rows again and again in the functionisSafe(). - Using the symmetry of the board (reflection and rotation) can reduce the number of necessary checks.
- For larger values of n, heuristics or constraint-based approaches (e.g. constraint programming) can be used.
For n = 8 (the classic eight queens problem) there are 92 different solutions. This approach finds all of them, but for larger n it can become slow because of the exponential growth of combinations.
The n queens problem – optimized solution
Task:
Place n queens on an n×n chessboard so that no two queens attack each other.
Every row must contain exactly one queen, and queens may not be in the same column or on the same diagonal.
Input: The number n (4 ≤ n ≤ 11).
Output: All possible placements of the queens are printed, where each placement is shown as a sequence of the columns of the queens in rows 1 to n.
Example:
Input: 4 Output: 2 4 1 3 3 1 4 2
Instructions and idea of the solution
This is an improved version of the previous backtracking algorithm for the n queens problem. The key difference is that conflicting positions are checked in O(1) time, using three helper arrays:
usedColumn[k]– marks whether column k is already occupied,usedDiagonal1[r - k + n]– the main diagonal,usedDiagonal2[r + k]– the anti-diagonal.
This way we avoid going through all previous rows and check only three logical conditions, which makes the program much faster.
Solution in C++
#include <iostream>
#include <vector>
using namespace std;
static const int MAX = 16;
int n;
int positions[MAX]; // positions[i] = column of the queen in row i
bool usedColumn[MAX]; // whether the column is occupied
bool usedDiagonal1[MAX*2]; // main diagonals
bool usedDiagonal2[MAX*2]; // anti-diagonals
bool canPlace(int row, int column) {
if (usedColumn[column]) return false;
int idx1 = row - column + n;
if (usedDiagonal1[idx1]) return false;
int idx2 = row + column;
if (usedDiagonal2[idx2]) return false;
return true;
}
void placeQueen(int row) {
if (row > n) {
for (int i = 1; i <= n; i++)
cout << positions[i] << (i < n ? ' ' : '\n');
return;
}
for (int col = 1; col <= n; col++) {
if (canPlace(row, col)) {
positions[row] = col;
usedColumn[col] = true;
usedDiagonal1[row - col + n] = true;
usedDiagonal2[row + col] = true;
placeQueen(row + 1);
usedColumn[col] = false;
usedDiagonal1[row - col + n] = false;
usedDiagonal2[row + col] = false;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) usedColumn[i] = false;
for (int d = 1; d <= 2*n; d++) {
usedDiagonal1[d] = false;
usedDiagonal2[d] = false;
}
placeQueen(1);
return 0;
}
Code explanation
The program uses global arrays so that at every moment it knows which columns and diagonals are occupied. Every queen that is placed marks three values as occupied, and when going back (backtracking) these values are reset.
The function canPlace() checks only three logical conditions, so every check is constant (O(1)).
When all queens have been placed successfully (i.e. row > n), a valid solution is printed.
The recursive calls search all possible combinations until all placements are found.
Analysis and efficiency
This algorithm has the same theoretical complexity as the previous one (of order O(n!)), but in practice it is much faster because:
- every validity check takes O(1),
- it discards early the branches that cannot lead to a solution,
- it uses minimal data structures in memory.
For values up to n = 11 the program finishes in a fraction of a second and prints all solutions. The number of solutions for the classic 8 queens problem is 92, and this algorithm finds all of them quickly.
Possible extensions
- Instead of printing the solutions, they can be stored in a vector and analysed (e.g. the number of symmetric placements).
- By adding heuristics (e.g. "Least Conflicts") larger n can also be solved.
- The solution can easily be adapted to show the board visually (e.g. with 'Q' and '.').
This optimized solution is an efficient and elegant approach to a classic backtracking search problem.
The n queens problem – optimized solution
Task:
Write a program that finds all possible placements of n queens on an n × n chessboard so that no two queens attack each other.
Every row must contain exactly one queen, and no two queens may be in the same column or on the same diagonal.
Input: One natural number n (4 ≤ n ≤ 11).
Output: All possible placements of the queens, one placement per line.
Each placement is printed as n numbers separated by spaces, where the number at position i is the column of the queen in row i.
Example:
Input: 4 Output: 2 4 1 3 3 1 4 2
Instructions and idea of the solution
This task is solved with the recursive method known as backtracking. The idea is to place the queens row by row, checking whether they attack each other.
To avoid searching through all previous queens every time, an optimization with three helper arrays is used:
usedColumn[k]– marks whether column k is occupied,usedDiagonal1[r - k + n]– for the main diagonals,usedDiagonal2[r + k]– for the anti-diagonals.
With this approach every occupancy check takes O(1) instead of O(n), which makes the algorithm much more efficient.
Solution in C++
#include <iostream>
#include <vector>
using namespace std;
static const int MAX = 16;
int n;
int positions[MAX]; // positions[i] = column of the queen in row i
bool usedColumn[MAX]; // whether the column is occupied
bool usedDiagonal1[MAX*2]; // main diagonals
bool usedDiagonal2[MAX*2]; // anti-diagonals
bool canPlace(int row, int column) {
if (usedColumn[column]) return false;
int idx1 = row - column + n;
if (usedDiagonal1[idx1]) return false;
int idx2 = row + column;
if (usedDiagonal2[idx2]) return false;
return true;
}
void placeQueen(int row) {
if (row > n) {
for (int i = 1; i <= n; i++)
cout << positions[i] << (i < n ? ' ' : '\n');
return;
}
for (int col = 1; col <= n; col++) {
if (canPlace(row, col)) {
positions[row] = col;
usedColumn[col] = true;
usedDiagonal1[row - col + n] = true;
usedDiagonal2[row + col] = true;
placeQueen(row + 1);
usedColumn[col] = false;
usedDiagonal1[row - col + n] = false;
usedDiagonal2[row + col] = false;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) usedColumn[i] = false;
for (int d = 1; d <= 2*n; d++) {
usedDiagonal1[d] = false;
usedDiagonal2[d] = false;
}
placeQueen(1);
return 0;
}
Code explanation
Step 1 – Initialization: All arrays are set to false at the start, which means that all columns and diagonals are free.
Step 2 – Placing a queen: For every row we try to place the queen in some column and check whether the position is safe using the function canPlace().
Step 3 – Recursion: If the position is safe, the function calls itself recursively for the next row.
When all n queens have been placed successfully, one solution is printed.
Step 4 – Going back (Backtracking): After each attempt, the values are reset to their previous state so that other possibilities can be tried.
Analysis and efficiency
- Checking whether a column or a diagonal is occupied takes O(1).
- The total number of possible queen placements is n!, but the vast majority is eliminated before it is even checked.
- For n ≤ 11 the program is extremely fast – e.g. for n = 8 it prints all 92 solutions in a fraction of a second.
Possible improvements
- Storing the solutions in vectors for later analysis (e.g. symmetry).
- Adding heuristics (e.g. "least conflicts") for larger values of n.
- Visualizing the board with a matrix of characters ('Q' and '.').
Comparison of solutions 1 and 2
| Property | Solution 1 | Solution 2 (optimized) |
|---|---|---|
| Conflict check | Goes through all previous rows (O(n) per check) | Uses three boolean arrays → O(1) check |
| Data structure | One vector with the queen positions | One array of positions + three helper arrays for columns and diagonals |
| Efficiency | Slow for larger n (n ≈ 10) | Very fast and stable for n up to 11 |
| Implementation | Shorter and simpler | More detailed, but more efficient |
| Suitability for larger n | Limited | Much better, can be extended with heuristics |
Conclusion:
Both approaches use the same idea of recursive search, but the optimized solution achieves much better efficiency thanks to smart tracking of occupied columns and diagonals.
This makes it more suitable for analysing larger problems and a basis for more advanced versions of the algorithm.
Solution 3 — Iterative approach using permutations
In this solution we use an iterative approach without recursion. The idea is that every permutation of the n numbers 1..n represents a placement of the queens, since every row and every column can contain only one queen. Then we check whether there is a conflict on the diagonals. If there is none, the placement is valid.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
// Function that checks whether the queens attack each other diagonally
bool isValidPermutation(const vector<int>& columns) {
int n = columns.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (abs(columns[i] - columns[j]) == abs(i - j))
return false;
}
}
return true;
}
int main() {
int n;
cout << "Enter the number n (4 <= n <= 11): ";
cin >> n;
if (n < 4 || n > 11) {
cout << "Allowed values are from 4 to 11." << endl;
return 1;
}
vector<int> columns(n);
for (int i = 0; i < n; i++)
columns[i] = i + 1;
do {
if (isValidPermutation(columns)) {
for (int i = 0; i < n; i++)
cout << columns[i] << " ";
cout << endl;
}
} while (next_permutation(columns.begin(), columns.end()));
return 0;
}
Code explanation
- We create the vector
columnscontaining the numbers from 1 to n, wherecolumns[i]is the column of the queen in row i. - The function
isValidPermutationchecks whether any two queens attack each other on a diagonal. If the difference of the columns is equal to the difference of the rows, there is a conflict. - We go through all permutations of the vector using
next_permutationand print the valid ones. - This approach is completely iterative and does not use recursion.
Efficiency and analysis
- Total complexity: O(n! * n²), because we generate all permutations and check the diagonals.
- Advantage: simple and easy to understand; no recursion.
- Disadvantage: quickly becomes infeasible for larger n (n ≥ 10). For n=11 there are 39,916,800 permutations.
- Possible improvements:
- Checking the permutations in parallel.
- Using a bitmask representation for faster diagonal checks.
- Heuristic approaches, e.g. the min-conflicts algorithm.
Solution 4 — Heuristic approach: the Min-Conflicts algorithm
In this solution we use a heuristic approach known as the min-conflicts algorithm. The idea is to start with an arbitrary placement of n queens and then iteratively reduce the conflicts by moving queens to the columns that cause the smallest number of conflicts.
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;
// Function that counts the conflicts for a queen in the given row and column
int conflicts(int row, int column, const vector<int>& positions) {
int n = positions.size();
int cnt = 0;
for (int i = 0; i < n; i++) {
if (i == row) continue;
if (positions[i] == column || abs(positions[i] - column) == abs(i - row))
cnt++;
}
return cnt;
}
int main() {
srand(time(nullptr));
int n;
cout << "Enter the number n (4 <= n <= 100): ";
cin >> n;
if (n < 4) {
cout << "Invalid value of n." << endl;
return 1;
}
// Random starting placement (every row has one queen in some column)
vector<int> positions(n);
for (int i = 0; i < n; i++)
positions[i] = rand() % n;
const int MAX_ITER = 10000;
for (int iter = 0; iter < MAX_ITER; iter++) {
// Find the queens that are in conflict
vector<int> conflicted;
for (int i = 0; i < n; i++) {
if (conflicts(i, positions[i], positions) > 0)
conflicted.push_back(i);
}
if (conflicted.empty()) break; // No conflicts - a solution is found
int row = conflicted[rand() % conflicted.size()];
// Move the queen to the column with the fewest conflicts
int minConflict = n+1;
vector<int> bestColumns;
for (int k = 0; k < n; k++) {
int c = conflicts(row, k, positions);
if (c < minConflict) {
minConflict = c;
bestColumns = {k};
} else if (c == minConflict) {
bestColumns.push_back(k);
}
}
positions[row] = bestColumns[rand() % bestColumns.size()];
}
// Print the solution
for (int i = 0; i < n; i++)
cout << positions[i]+1 << " ";
cout << endl;
return 0;
}
Code explanation
- The starting placement of the queens is generated randomly, one per row.
- The function
conflictscounts how many queens attack a given queen in a certain column. - In every iteration we choose a queen that is in conflict and move it to the column that minimizes the number of conflicts.
- The procedure is repeated until we get a placement without conflicts or until we reach the maximum number of iterations.
Efficiency and analysis
- The algorithm is very fast and practical for larger n (even n ~ 100 and more).
- The time complexity depends on the number of iterations and on n, but in practice it almost always finishes in hundreds or thousands of steps.
- Advantage: it makes it possible to solve large instances of the n queens problem, which is not feasible with recursive backtracking approaches for n ≥ 15.
- Disadvantage: the result is heuristic; it may need a restart if it gets stuck in a local minimum.
- Possible improvements:
- Multiple starts with different random starting states.
- Adding a small probability of a random move to avoid local minima.
- A bitmask representation for faster conflict checks.
Solution 5 — Bitmask Dynamic Programming (advanced)
This solution uses bitmask dynamic programming to efficiently count all solutions of the N queens problem. The idea is to represent every column and diagonal as bits, so that we can check in O(1) whether a cell is free. This approach is more advanced, but it greatly speeds up solving for larger n (n ≤ 16).
#include <iostream>
using namespace std;
int n;
int total = 0;
// Bitmask DP function: row = current row, colMask = occupied columns,
// diag1Mask = occupied main diagonals, diag2Mask = occupied anti-diagonals
void solve(int row, int colMask, int diag1Mask, int diag2Mask) {
if (row == n) {
total++;
return;
}
// All free positions in this row
int available = ((1 << n) - 1) & ~(colMask | diag1Mask | diag2Mask);
while (available) {
int p = available & -available; // take the lowest free bit (rightmost)
available -= p; // remove it from the available positions
// Recursively place a queen in the next row
solve(row + 1, colMask | p, (diag1Mask | p) << 1, (diag2Mask | p) >> 1);
}
}
int main() {
cin >> n;
total = 0;
solve(0, 0, 0, 0);
cout << total << endl;
return 0;
}
Code explanation:
- Every bit in
colMaskmarks whether a column is occupied. - The main diagonals and anti-diagonals are also represented with bitmasks (
diag1Maskanddiag2Mask). availablecomputes all free columns in the current row.- The expression
p = available & -availabletakes the lowest (rightmost) free bit. - The recursive call updates the masks for the next row using bit shift operations.
- When
row == n, one valid solution has been found, sototalis increased.
Efficiency:
- The time complexity is O(n!) in practice, but bitmasking makes checking free cells extremely fast.
- The memory complexity is O(1), because only a few integer variables are used.
- This is especially suitable when we want only the number of solutions and not all placements.
Possible improvements / advanced optimization: Use the symmetries of the board (rotations and reflections) to halve the number of solutions to search, which speeds up the execution even more for n ≥ 12.
Comparative analysis of the 5 solutions — the N queens problem
The following table and comments show the different approaches to solving the N queens problem, with a focus on efficiency, the type of solution and complexity.
| Solution | Approach | Description | Time complexity | Memory complexity | Notes / advantages |
|---|---|---|---|---|---|
| 1 | Classic backtracking (recursive) | Places the queens row by row and checks whether the current position is safe (columns + diagonals). | O(n!) | O(n) (for the array of positions and the recursion stack) | Simple and educational; fast for n ≤ 10; shows all solutions. |
| 2 | Backtracking with tracking of occupied columns and diagonals (bool arrays) | An optimization of classic backtracking; checks conflicts in O(1) time using helper arrays. | O(n!) in practice, but faster than solution 1 because of fast checks | O(n + 2n + 2n) ≈ O(n) | Very fast for n ≤ 11; still generates all solutions; easy to implement. |
| 3 | Permutations (we generate all permutations of the columns) | Every permutation of n columns represents a possible placement; the diagonals are checked. | O(n! * n) | O(n) | Easy to implement; good for small n; checks all permutations unnecessarily, which is not efficient for n ≥ 10. |
| 4 | Heuristic approach (e.g. min-conflicts) | Uses local search and resolves conflicting positions iteratively; can find one solution quickly. | O(n) to O(n^2) per iteration (empirically) | O(n) | Finds one solution quickly for larger n; does not guarantee all solutions; ideal for practical cases where one solution is enough. |
| 5 | Bitmask dynamic programming | Represents columns and diagonals as bits; uses recursion with bitmasks to count all solutions quickly. | O(n!) in practice, but very fast because of bit operations | O(1) | Efficient for counting solutions; less suitable for generating all configurations; advanced, but optimal for n ≤ 16. |
Conclusion:
- For learning and small sizes (n ≤ 10) — solutions 1, 2 and 3 are enough.
- For practical needs when only one solution is required — heuristic approaches (solution 4) are excellent.
- For quickly counting all solutions for larger n (n ≤ 16) — bitmask DP (solution 5) is the most efficient.
- It is always a good idea to start with simple backtracking solutions to understand the structure of the problem, and then move on to optimizations and advanced approaches.
Previous
|<Preparation for the national competition and SIO (SR)
