Practice › Recursion & Backtracking
N-Queens Count
Hard · Recursion & Backtracking · Asked at Amazon, Google, Microsoft, Adobe
Count the ways to place n queens on an n × n chessboard so that no two queens attack each other.
Input
One integer n.
Output
The number of solutions.
Constraints
- 1 ≤ n ≤ 10
Place one queen per row; track used columns and both diagonals.
Example 1
Input
4
Output
2
Example 2
Input
1
Output
1
Hints
- Each row must contain exactly one queen — place them row by row.
- A square (r, c) is attacked if its column, its "r − c" diagonal or its "r + c" anti-diagonal is already used. Track all three with boolean arrays.
Approach
place(row): if row == n, one full solution is found. Otherwise try each column c where col[c], diag[row − c + n − 1] and anti[row + c] are all free. Mark them, recurse to the next row, then unmark (backtrack). The boolean arrays make each safety check O(1), and pruning keeps the search small: n = 10 has 724 solutions.
Complexity: O(n!) worst-case time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int n, solutions = 0;
vector<bool> col, diag, anti;
void place(int row) {
if (row == n) {
solutions++;
return;
}
for (int c = 0; c < n; c++) {
if (col[c] || diag[row - c + n - 1] || anti[row + c]) continue;
col[c] = diag[row - c + n - 1] = anti[row + c] = true;
place(row + 1);
col[c] = diag[row - c + n - 1] = anti[row + c] = false;
}
}
int main() {
cin >> n;
col.assign(n, false);
diag.assign(2 * n, false);
anti.assign(2 * n, false);
place(0);
cout << solutions << "\n";
return 0;
}Python solution
n = int(input())
col, diag, anti = [False] * n, [False] * (2 * n), [False] * (2 * n)
def place(row):
if row == n:
return 1
count = 0
for c in range(n):
d, a = row - c + n - 1, row + c
if col[c] or diag[d] or anti[a]:
continue
col[c] = diag[d] = anti[a] = True
count += place(row + 1)
col[c] = diag[d] = anti[a] = False
return count
print(place(0))Java solution
import java.util.*;
public class Main {
static int n, solutions = 0;
static boolean[] col, diag, anti;
static void place(int row) {
if (row == n) {
solutions++;
return;
}
for (int c = 0; c < n; c++) {
if (col[c] || diag[row - c + n - 1] || anti[row + c]) continue;
col[c] = diag[row - c + n - 1] = anti[row + c] = true;
place(row + 1);
col[c] = diag[row - c + n - 1] = anti[row + c] = false;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
col = new boolean[n];
diag = new boolean[2 * n];
anti = new boolean[2 * n];
place(0);
System.out.println(solutions);
}
}