N-Queens
Place one queen per row, trying each column from the left. If a square is attacked by a queen above it, skip it. If a row has no safe square left, the queen in the row above was a bad choice: remove it and try its next column. That stepping back is backtracking.
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | ||||
| 1 | ||||
| 2 | ||||
| 3 |
Place 4 queens on a 4 × 4 board so that no two share a row, a column or a diagonal. One queen per row, left to right.
1function solve(n, row = 0, cols = []) {2 if (row === n) return cols;3 for (let c = 0; c < n; c++) {4 if (cols.some((pc, pr) => pc === c || Math.abs(pc - c) === row - pr)) continue;5 cols.push(c);6 if (solve(n, row + 1, cols)) return cols;7 cols.pop();8 }9 return null;10}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n | the first square tried in every row works |
| average | n! | pruning cuts most of it, but growth is still explosive |
| worst | n! | no solution: every placement is tried and undone |
| space | n | one column per row placed |
Where it breaks
- Some boards have no answer. Pick 3 queens: every placement is tried and undone. Boards of 2 and 3 are the only sizes above 1 with no solution.
- Checking whole boards instead. Trying every arrangement of n queens on n² squares is hopeless. Placing one per row and pruning as soon as two clash cuts the search down by orders of magnitude.
- The diagonal check. Two queens share a diagonal when the difference in their columns equals the difference in their rows. Forget the absolute value and only one direction of diagonal gets checked.