Problem
Place n queens on an n×n chessboard so no two attack each other. Return all distinct solutions.
Example
Input: n = 4
Output: 2 solutions: [".Q..","...Q","Q...","..Q."] and ["..Q.","Q...","...Q",".Q.."]Solution
Backtracking row by row. Track which columns and diagonals are occupied.
def solve_n_queens(n):
result = []
cols, d1, d2 = set(), set(), set()
queens = [-1] * n
def backtrack(r):
if r == n:
result.append(['.' * q + 'Q' + '.' * (n - q - 1) for q in queens])
return
for c in range(n):
if c in cols or (r - c) in d1 or (r + c) in d2: continue
queens[r] = c
cols.add(c); d1.add(r - c); d2.add(r + c)
backtrack(r + 1)
cols.remove(c); d1.remove(r - c); d2.remove(r + c)
backtrack(0)
return resultfunction solveNQueens(n) {
const result = [], cols = new Set(), d1 = new Set(), d2 = new Set(), queens = new Array(n);
function backtrack(r) {
if (r === n) {
result.push(queens.map(q => '.'.repeat(q) + 'Q' + '.'.repeat(n - q - 1)));
return;
}
for (let c = 0; c < n; c++) {
if (cols.has(c) || d1.has(r - c) || d2.has(r + c)) continue;
queens[r] = c;
cols.add(c); d1.add(r - c); d2.add(r + c);
backtrack(r + 1);
cols.delete(c); d1.delete(r - c); d2.delete(r + c);
}
}
backtrack(0);
return result;
}void backtrack(int r, int n, vector<int>& queens, set<int>& cols, set<int>& d1, set<int>& d2, vector<vector<string>>& result) {
if (r == n) {
vector<string> board;
for (int q : queens) {
string row(n, '.');
row[q] = 'Q';
board.push_back(row);
}
result.push_back(board);
return;
}
for (int c = 0; c < n; c++) {
if (cols.count(c) || d1.count(r - c) || d2.count(r + c)) continue;
queens[r] = c;
cols.insert(c); d1.insert(r - c); d2.insert(r + c);
backtrack(r + 1, n, queens, cols, d1, d2, result);
cols.erase(c); d1.erase(r - c); d2.erase(r + c);
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> result;
vector<int> queens(n);
set<int> cols, d1, d2;
backtrack(0, n, queens, cols, d1, d2, result);
return result;
}public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
int[] queens = new int[n];
Set<Integer> cols = new HashSet<>(), d1 = new HashSet<>(), d2 = new HashSet<>();
backtrack(0, n, queens, cols, d1, d2, result);
return result;
}
private void backtrack(int r, int n, int[] queens, Set<Integer> cols, Set<Integer> d1, Set<Integer> d2, List<List<String>> result) {
if (r == n) {
List<String> board = new ArrayList<>();
for (int q : queens) {
char[] row = new char[n];
Arrays.fill(row, '.');
row[q] = 'Q';
board.add(new String(row));
}
result.add(board);
return;
}
for (int c = 0; c < n; c++) {
if (cols.contains(c) || d1.contains(r - c) || d2.contains(r + c)) continue;
queens[r] = c;
cols.add(c); d1.add(r - c); d2.add(r + c);
backtrack(r + 1, n, queens, cols, d1, d2, result);
cols.remove(c); d1.remove(r - c); d2.remove(r + c);
}
}Complexity
- Time: O(n!)
- Space: O(n)
Explanation
A diagonal where r – c is constant is the same diagonal. Same for anti-diagonal where r + c is constant. Tracking these in sets gives O(1) attack-check.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?