Missing undo step on backtrack
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
Example 1:
Input: n = 4 Output: 2 Explanation: There are two distinct solutions to the 4-queens puzzle as shown.
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 9Problem summary: The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return the number of distinct solutions to the n-queens puzzle.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Backtracking
4
1
n-queens)class Solution {
public int totalNQueens(int n) {
boolean[] cols = new boolean[n];
boolean[] diag1 = new boolean[2 * n]; // row - col + n
boolean[] diag2 = new boolean[2 * n]; // row + col
return backtrack(0, n, cols, diag1, diag2);
}
private int backtrack(int row, int n, boolean[] cols, boolean[] diag1, boolean[] diag2) {
if (row == n) return 1; // One valid arrangement completed.
int count = 0;
for (int col = 0; col < n; col++) {
int d1 = row - col + n;
int d2 = row + col;
if (cols[col] || diag1[d1] || diag2[d2]) continue;
cols[col] = diag1[d1] = diag2[d2] = true;
count += backtrack(row + 1, n, cols, diag1, diag2);
cols[col] = diag1[d1] = diag2[d2] = false;
}
return count;
}
}
func totalNQueens(n int) int {
cols := make([]bool, n)
diag1 := make([]bool, 2*n) // row - col + n
diag2 := make([]bool, 2*n) // row + col
var backtrack func(row int) int
backtrack = func(row int) int {
if row == n {
return 1
}
count := 0
for col := 0; col < n; col++ {
d1 := row - col + n
d2 := row + col
if cols[col] || diag1[d1] || diag2[d2] {
continue
}
cols[col], diag1[d1], diag2[d2] = true, true, true
count += backtrack(row + 1)
cols[col], diag1[d1], diag2[d2] = false, false, false
}
return count
}
return backtrack(0)
}
class Solution:
def totalNQueens(self, n: int) -> int:
cols = set()
diag1 = set() # row - col
diag2 = set() # row + col
def backtrack(row: int) -> int:
if row == n:
return 1
count = 0
for col in range(n):
d1 = row - col
d2 = row + col
if col in cols or d1 in diag1 or d2 in diag2:
continue
cols.add(col)
diag1.add(d1)
diag2.add(d2)
count += backtrack(row + 1)
cols.remove(col)
diag1.remove(d1)
diag2.remove(d2)
return count
return backtrack(0)
impl Solution {
pub fn total_n_queens(n: i32) -> i32 {
let n = n as usize;
let mut cols = vec![false; n];
let mut diag1 = vec![false; 2 * n];
let mut diag2 = vec![false; 2 * n];
fn backtrack(
row: usize,
n: usize,
cols: &mut Vec<bool>,
diag1: &mut Vec<bool>,
diag2: &mut Vec<bool>,
) -> i32 {
if row == n {
return 1;
}
let mut count = 0;
for col in 0..n {
let d1 = row + n - col;
let d2 = row + col;
if cols[col] || diag1[d1] || diag2[d2] {
continue;
}
cols[col] = true;
diag1[d1] = true;
diag2[d2] = true;
count += backtrack(row + 1, n, cols, diag1, diag2);
cols[col] = false;
diag1[d1] = false;
diag2[d2] = false;
}
count
}
backtrack(0, n, &mut cols, &mut diag1, &mut diag2)
}
}
function totalNQueens(n: number): number {
const cols = new Set<number>();
const diag1 = new Set<number>(); // row - col
const diag2 = new Set<number>(); // row + col
const backtrack = (row: number): number => {
if (row === n) return 1;
let count = 0;
for (let col = 0; col < n; col++) {
const d1 = row - col;
const d2 = row + col;
if (cols.has(col) || diag1.has(d1) || diag2.has(d2)) continue;
cols.add(col);
diag1.add(d1);
diag2.add(d2);
count += backtrack(row + 1);
cols.delete(col);
diag1.delete(d1);
diag2.delete(d2);
}
return count;
};
return backtrack(0);
}
Use this to step through a reusable interview workflow for this problem.
Generate every possible combination without any filtering. At each of n positions we choose from up to n options, giving nⁿ total candidates. Each candidate takes O(n) to validate. No pruning means we waste time on clearly invalid partial solutions.
Backtracking explores a decision tree, but prunes branches that violate constraints early. Worst case is still factorial or exponential, but pruning dramatically reduces the constant factor in practice. Space is the recursion depth (usually O(n) for n-level decisions).
Review these before coding to avoid predictable interview regressions.
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.