Place the Queens

The N-Queens problem: place 4 queens on a 4×4 board so that no two queens share a row, column, or diagonal.

You will place one queen per row, starting from the top. After each placement, watch what happens to the remaining cells — the constraint sets update in real time.

Each color represents a different constraint:

  • Red = same column
  • Amber = same main diagonal (top-left to bottom-right)
  • Purple = same anti-diagonal (top-right to bottom-left)
Row 1/4 — 4 cells available
column diagonal anti-diag

What You Just Did

You experienced constraint propagation — a technique more powerful than simple pruning.

Simple pruning checks one condition at the current level: “Is remaining negative? Skip.” It is a local check.

Constraint propagation is global. When you placed a queen in column 2, three things happened simultaneously:

  • Column 2 was blocked for all future rows
  • The main diagonal through that cell was blocked for all future rows
  • The anti-diagonal through that cell was blocked for all future rows

In code, this means maintaining three sets that are updated on every placement:

1
cols.add(col)              // column blocked
2
diags.add(row - col)       // main diagonal: row-col is constant along a diagonal
3
antiDiags.add(row + col)   // anti-diagonal: row+col is constant along an anti-diagonal

Before placing a queen, check: cols.has(c) || diags.has(r-c) || antiDiags.has(r+c). If any is true, prune — this cell is under attack.

The diagonal formulas are the key insight: along any top-left-to-bottom-right diagonal, the value row - col is constant. Along any top-right-to-bottom-left diagonal, row + col is constant. These two numbers uniquely identify every diagonal on the board.

Watch the Branching Factor

Place queens one more time. This time, a number beside each row shows how many cells are still available.

Notice how the available count drops after each placement. On a 4×4 board, the first row has 4 options. After placing one queen, the second row might have only 2. After two queens, the third row might have just 1 — or even 0, forcing a backtrack.

This is constraint propagation in action: each choice narrows the remaining search space. The branching factor collapses as you go deeper, making the actual number of explored nodes far smaller than the theoretical worst case.

Row 1/4 — 4 cells available
4
4
4
4
column diagonal anti-diag

Build the Solver

You placed queens by hand. You watched the constraint sets update. Now construct the code that does it.

Three blanks — all in the backtracking core. The check that prunes invalid cells, the adds when placing a queen, and the deletes when backtracking.

function solveNQueens(n) {
const cols = new Set(), diags = new Set(), antiDiags = new Set();
const board = Array.from({ length: n }, () => '.'.repeat(n));
const result = [];
function backtrack(row) {
if (row === n) { result.push([...board]); return; }
for (let c = 0; c < n; c++) {
if () continue;
;
board[row] = board[row].substring(0, c) + 'Q' + board[row].substring(c + 1);
backtrack(row + 1);
board[row] = '.'.repeat(n);
;
}
}
backtrack(0);
return result;
}

Your Call

Three questions on constraint propagation — how it differs from simple pruning, what constraint sets N-Queens requires, and how it affects the branching factor.

Question 1/3
Constraint propagation

How does constraint propagation differ from simple pruning?