Constraint Search

Constraint search asks you to build an assignment while obeying rules. The generic loop is:

Try a legal placement, update the constraints, recurse, then restore the constraints.

The hard part is making legality cheap. Use sets for N-Queens and bucket sums for equal-partition problems.

Pattern summary

Problem	Decision	State for fast validity	Output
N-Queens	column for the next row	occupied columns and diagonals	all boards
N-Queens II	column for the next row	occupied columns and diagonals	count
Matchsticks to Square	side for the next stick	four side sums	boolean

13. N-Queens

Problem

Recognition

Place exactly one queen in each row. Choosing row by row removes row conflicts automatically. A placement at (row, col) is invalid if another queen uses:

the same column: col;
the same top-left to bottom-right diagonal: row - col;
the same top-right to bottom-left diagonal: row + col.

DFS contract

dfs(row) finds every valid board extension when rows 0...row - 1 already contain non-attacking queens.

JavaScript

function solveNQueens(n) {
  const columns = new Set();
  const positiveDiagonals = new Set(); // row + col
  const negativeDiagonals = new Set(); // row - col
  const board = Array.from({ length: n }, () => Array(n).fill("."));
  const result = [];
 
  function dfs(row) {
    if (row === n) {
      result.push(board.map(line => line.join("")));
      return;
    }
 
    for (let col = 0; col < n; col++) {
      const positive = row + col;
      const negative = row - col;
 
      if (
        columns.has(col) ||
        positiveDiagonals.has(positive) ||
        negativeDiagonals.has(negative)
      ) {
        continue;
      }
 
      columns.add(col);
      positiveDiagonals.add(positive);
      negativeDiagonals.add(negative);
      board[row][col] = "Q";
 
      dfs(row + 1);
 
      board[row][col] = ".";
      negativeDiagonals.delete(negative);
      positiveDiagonals.delete(positive);
      columns.delete(col);
    }
  }
 
  dfs(0);
  return result;
}

Complexity

Time: O(n!) in the common interview bound; constraints prune many candidate placements.
Auxiliary space: O(n^2) for the board plus O(n) sets and recursion, excluding returned boards.

14. N-Queens II

Problem

What changes

The decision tree and validity checks are identical. Only the value at a complete placement changes: increment a counter instead of copying the board. Because no board is returned, we do not need to maintain one.

JavaScript

function totalNQueens(n) {
  const columns = new Set();
  const positiveDiagonals = new Set();
  const negativeDiagonals = new Set();
  let count = 0;
 
  function dfs(row) {
    if (row === n) {
      count++;
      return;
    }
 
    for (let col = 0; col < n; col++) {
      const positive = row + col;
      const negative = row - col;
 
      if (
        columns.has(col) ||
        positiveDiagonals.has(positive) ||
        negativeDiagonals.has(negative)
      ) {
        continue;
      }
 
      columns.add(col);
      positiveDiagonals.add(positive);
      negativeDiagonals.add(negative);
 
      dfs(row + 1);
 
      negativeDiagonals.delete(negative);
      positiveDiagonals.delete(positive);
      columns.delete(col);
    }
  }
 
  dfs(0);
  return count;
}

Time: O(n!) in the common interview bound.
Auxiliary space: O(n), excluding recursion bookkeeping.

15. Matchsticks to Square

Problem

Recognition

Every stick must be assigned to one of four sides. That makes this a small bin-packing search:

compute the required side length;
place larger sticks first to fail early;
never let a side exceed the target;
avoid trying equivalent side states.

DFS contract

dfs(i) returns whether sticks at indices i... can be assigned to sides whose current sums are stored in sides.

JavaScript

function makesquare(matchsticks) {
  const total = matchsticks.reduce((sum, stick) => sum + stick, 0);
  if (total % 4 !== 0) return false;
 
  const target = total / 4;
  matchsticks.sort((a, b) => b - a);
  if (matchsticks[0] > target) return false;
 
  const sides = [0, 0, 0, 0];
 
  function dfs(i) {
    if (i === matchsticks.length) return true;
 
    const stick = matchsticks[i];
    const triedSums = new Set();
 
    for (let side = 0; side < 4; side++) {
      if (sides[side] + stick > target) continue;
      if (triedSums.has(sides[side])) continue;
 
      triedSums.add(sides[side]);
      sides[side] += stick;
 
      if (dfs(i + 1)) return true;
 
      sides[side] -= stick;
    }
 
    return false;
  }
 
  return dfs(0);
}

Why `triedSums` is safe

Two sides with the same current sum are interchangeable. Putting the current stick on either one produces the same multiset of side sums, so exploring both branches repeats work. This is symmetry pruning, not an arbitrary shortcut.

Time: O(4^n) worst case, with strong practical pruning.
Auxiliary space: O(n) recursion plus four side sums.