N-Queens: Backtracking When Constraints Get Geometric

N-Queens is the backtracking problem interviewers pull out when they want to see if you actually understand constraint propagation versus brute-force enumeration. It's not hard — but the naive "check after placing" approach does O(n) work per candidate cell where O(1) is available, and interviewers notice which one you write.

The queen placement rule is this: no two queens can share a row, column, or diagonal. Since we place one queen per row, the row constraint is free. The column and diagonal constraints are where the work happens.

Why the Naive Approach Is Slow

The brute approach places a queen at (row, col), then scans the board to check for conflicts:

// Naive conflict check — O(n) per cell check
const isValid = (board, row, col, n) => {
  // Check column above
  for (let r = 0; r < row; r++) {
    if (board[r][col] === 'Q') return false;
  }
  // Check upper-left diagonal
  for (let r = row - 1, c = col - 1; r >= 0 && c >= 0; r--, c--) {
    if (board[r][c] === 'Q') return false;
  }
  // Check upper-right diagonal
  for (let r = row - 1, c = col + 1; r >= 0 && c < n; r--, c++) {
    if (board[r][c] === 'Q') return false;
  }
  return true;
};

This is O(n) per placement. With n placements per board configuration and potentially many configurations to explore, it adds up. The problem isn't correctness — it's that you're doing redundant scanning every time.

O(1) Conflict Detection via Sets

The insight: diagonals have a constant signature. For the top-left-to-bottom-right diagonal, every cell (r, c) on the same diagonal shares the same value of r - c. For the anti-diagonal (top-right-to-bottom-left), every cell shares the same r + c.

Store used columns, diagonals, and anti-diagonals in Sets. Checking if a cell is under attack is a Set.has() call — O(1).

// N-Queens with O(1) conflict detection
// Time: O(n!) — at most n choices for row 1, n-1 for row 2, etc.
// Space: O(n^2) — the three sets and the recursion are O(n) each, but `board`
// is an n x n grid, and that dominates. Output is extra: O(n^2) per solution.
const solveNQueens = (n) => {
  const result = [];
  const cols = new Set();
  const diag = new Set();     // r - c
  const antiDiag = new Set(); // r + c
 
  const board = Array.from({ length: n }, () => Array(n).fill('.'));
 
  const backtrack = (row) => {
    if (row === n) {
      result.push(board.map(r => r.join('')));
      return;
    }
 
    for (let col = 0; col < n; col++) {
      const d = row - col;
      const ad = row + col;
 
      if (cols.has(col) || diag.has(d) || antiDiag.has(ad)) continue;
 
      // Place queen
      cols.add(col);
      diag.add(d);
      antiDiag.add(ad);
      board[row][col] = 'Q';
 
      backtrack(row + 1);
 
      // Remove queen (backtrack)
      cols.delete(col);
      diag.delete(d);
      antiDiag.delete(ad);
      board[row][col] = '.';
    }
  };
 
  backtrack(0);
  return result;
};

The structure is identical to any other backtracking solution. What changed: the conflict check is O(1) instead of O(n), and the state to undo is three Set entries instead of scanning the board.

Note the space annotation carefully, because it's the sort of thing people say wrong out of habit. The constraint state is O(n) — three sets holding at most n entries each, plus O(n) recursion depth. But this version also carries a full n × n board so it can emit the string representation, and that makes the auxiliary space O(n²). If you want the O(n) figure to be true, you need the version below that doesn't build a board, or you keep a single queens[row] = col array and materialise the strings only when you reach a solution.

N-Queens II — Just the Count (LeetCode 52)

If you only need the count of valid configurations, drop the board building entirely. Same logic, just increment a counter:

// N-Queens II — count solutions only
// Time: O(n!), Space: O(n) — no board here, so O(n) is accurate: three sets
// of at most n entries plus n frames of recursion
const totalNQueens = (n) => {
  let count = 0;
  const cols = new Set();
  const diag = new Set();
  const antiDiag = new Set();
 
  const backtrack = (row) => {
    if (row === n) { count++; return; }
 
    for (let col = 0; col < n; col++) {
      const d = row - col;
      const ad = row + col;
      if (cols.has(col) || diag.has(d) || antiDiag.has(ad)) continue;
 
      cols.add(col); diag.add(d); antiDiag.add(ad);
      backtrack(row + 1);
      cols.delete(col); diag.delete(d); antiDiag.delete(ad);
    }
  };
 
  backtrack(0);
  return count;
};

In practice n <= 9 for this problem, so both solutions run plenty fast. But the O(1) conflict check still earns its keep at n = 9. Instrumenting the naive isValid above on n = 9: it gets called 72,378 times and scans 419,612 board cells in total — up to 16 in a single call, 5.8 on average. The Set version replaces all of that with three has() calls per candidate cell.

Palindrome Partitioning (LeetCode 131)

Different flavor of constrained backtracking. Given a string s, partition it such that every substring in the partition is a palindrome. Return all valid partitions.

This one pairs constraint checking with backtracking. Instead of geometric constraints (queens attacking each other), the constraint is: every chosen substring must be a palindrome.

Brute force — check palindrome inline, no caching:

// Brute force palindrome check on every substring
// Time: O(n * 2^(n-1)) — a length-n string has 2^(n-1) contiguous partitions
// (one binary choice per gap between characters, and there are n-1 gaps),
// times an O(n) palindrome check. Same thing as O(n * 2^n) up to a constant.
// Space: O(n) recursion depth, plus the result
const partitionBrute = (s) => {
  const result = [];
 
  const isPalindrome = (str, l, r) => {
    while (l < r) {
      if (str[l] !== str[r]) return false;
      l++; r--;
    }
    return true;
  };
 
  const backtrack = (start, current) => {
    if (start === s.length) {
      result.push([...current]);
      return;
    }
 
    for (let end = start + 1; end <= s.length; end++) {
      if (isPalindrome(s, start, end - 1)) {
        current.push(s.slice(start, end));
        backtrack(end, current);
        current.pop();
      }
    }
  };
 
  backtrack(0, []);
  return result;
};

Optimized with palindrome DP memoization:

// Precompute palindrome table to avoid redundant checks
// Time: O(n * 2^(n-1)) — still exponential; the DP kills the O(n) palindrome
// check but you still have to enumerate every valid partition, and copying
// each one out is O(n)
// Space: O(n^2) for the palindrome table, plus the result
const partition = (s) => {
  const n = s.length;
  const result = [];
 
  // dp[i][j] = true if s[i..j] is a palindrome
  const dp = Array.from({ length: n }, () => new Array(n).fill(false));
 
  // Every single character is a palindrome
  for (let i = 0; i < n; i++) dp[i][i] = true;
 
  // Two-character palindromes
  for (let i = 0; i < n - 1; i++) {
    dp[i][i + 1] = s[i] === s[i + 1];
  }
 
  // Substrings of length 3+
  for (let len = 3; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      dp[i][j] = s[i] === s[j] && dp[i + 1][j - 1];
    }
  }
 
  const backtrack = (start, current) => {
    if (start === n) {
      result.push([...current]);
      return;
    }
 
    for (let end = start; end < n; end++) {
      if (dp[start][end]) {           // O(1) palindrome check
        current.push(s.slice(start, end + 1));
        backtrack(end + 1, current);
        current.pop();
      }
    }
  };
 
  backtrack(0, []);
  return result;
};

The precomputed dp[i][j] table turns every palindrome check from O(n) to O(1). For a string of length 16 with many valid palindromes, this is a meaningful speedup. The overall complexity is still exponential because you're generating all valid partitions — you can't avoid that — but you eliminate the redundant string scanning.

One thing to get right if you're asked to state the bound: the number of contiguous partitions of a length-n string is 2^(n-1), not 2^n. You're making one independent yes/no choice at each of the n−1 gaps between characters. Counting them directly: n=1 → 1, n=4 → 8, n=8 → 128, n=14 → 8,192, which is 2^(n-1) at every step. 2^n would be off by a factor of two, and while that vanishes in big-O it's a visible slip when you write the reasoning out. (For Palindrome Partitioning the palindrome constraint prunes below this, so 2^(n-1) is the ceiling, hit only by a string like "aaaa…" where every substring is a palindrome.)

The Constraint Propagation Pattern

N-Queens and Palindrome Partitioning share a structural idea: instead of trying every possible placement and then validating, precompute or maintain the constraint state so you can reject invalid choices instantly.

In N-Queens, the constraint state is three Sets tracking occupied columns and diagonals. In Palindrome Partitioning, it's the dp[i][j] table.

The general pattern:

// 1. Set up constraint state (Sets, DP table, etc.)
// 2. At each backtracking step:
//    a. Check if current choice violates constraint — O(1) if state is precomputed
//    b. Update constraint state
//    c. Recurse
//    d. Undo constraint state update

This pattern generalizes to Sudoku Solver (LeetCode 37), where you maintain row, column, and 3x3-box Sets and check O(1) per cell placement.

Interview Tips

O(1) conflict detection is the interview filter. Writing the naive O(n) board scan in N-Queens is a yellow flag — it works, but an interviewer at a top company will ask "can we check conflicts faster?" Know that row - col and row + col are diagonal signatures before you walk in.

For Palindrome Partitioning, if asked "can you optimize?", the DP precomputation is the expected answer. Walk through: "I'll precompute whether each substring is a palindrome in O(n^2) using expand-from-center logic or bottom-up DP. Then backtracking checks are O(1)." That's enough — you don't always have to code the optimization if you articulate it clearly.

Draw the decision tree on the board. For N-Queens with n = 4, there are only 2 solutions. Trace one path through the tree showing what gets pruned. This demonstrates you understand why the algorithm terminates quickly despite the apparent n! search space.

Know the counts by heart for small n. N=1: 1 solution. N=4: 2 solutions. N=5: 10 solutions. N=8: 92 solutions. Rattling off "N-Queens for n=4 has exactly 2 solutions" while tracing through it on a whiteboard is the kind of detail that separates prepared candidates.

The brute force matters. For Palindrome Partitioning, the brute force with inline palindrome checks is the most common solution people write. The optimized DP table version is a follow-up optimization. In an interview, implement the cleaner brute-force first, then optimize — don't start with the DP table and fumble through it.