🧩 Constraint Solving POTD:N-Queens — Classic Constraint Propagation Showcase

[github-actions[bot]]

Category: Classic CSP · Date: 2026-04-03

---

Problem Statement

Place N non-attacking queens on an N×N chessboard — no two queens may share a row, column, or diagonal.

Concrete instance (N = 4)

. Q . .
. . . Q
Q . . .
. . Q .
```

**Input:** integer `N ≥ 1`  
**Output:** an assignment of one queen per row such that no two queens attack each other, or **UNSAT** if none exists (only N=2 and N=3 are unsatisfiable for N≥1).

The number of distinct solutions grows rapidly: 2 for N=4, 92 for N=8, 14,772,512 for N=15.

---

### Why It Matters

- **Benchmark problem for CSP solvers.** N-Queens has been used for decades to compare propagation algorithms, search heuristics, and symmetry-breaking strategies — it's the "Hello, World!" of constraint programming research.
- **Circuit board / VLSI placement.** Placing non-interfering components on a board shares the same mutual-exclusion structure; techniques developed for N-Queens transfer directly.
- **Parallel search research.** Finding *all* solutions (not just one) makes N-Queens a natural stress test for parallel and portfolio solvers.

---

### Modeling Approaches

#### Approach 1 — Constraint Programming (one variable per row)

The most natural CP model uses a single array of variables:

| Element | Definition |
|---------|------------|
| **Variables** | `q[i] ∈ {1..N}` for each row `i ∈ {1..N}` — the column of the queen in row `i` |
| **Column constraint** | `AllDifferent(q[1], …, q[N])` — no two queens share a column |
| **Diagonal constraint** | `AllDifferent(q[1]+1, q[2]+2, …, q[N]+N)` — no two queens on the same ↘ diagonal |
| **Anti-diagonal** | `AllDifferent(q[1]-1, q[2]-2, …, q[N]-N)` — no two queens on the same ↗ diagonal |

Three `AllDifferent` constraints. Solvers like Gecode and OR-Tools propagate these with **Hyper-Arc Consistency (HAC)**, removing large swaths of the search space instantly.

**Trade-offs:** extremely concise; `AllDifferent` propagators run in O(N log N). Symmetry (8-fold for a square board) can double or quadruple work when enumerating all solutions.

---

#### Approach 2 — Boolean SAT Encoding

Use Boolean variables `x[i][j] = 1` if row `i`, column `j` holds a queen.

```
∀i:  x[i][1] ∨ x[i][2] ∨ … ∨ x[i][N]          (at least one per row)
∀i, j≠k:  ¬x[i][j] ∨ ¬x[i][k]                  (at most one per row)
∀j, i≠k:  ¬x[i][j] ∨ ¬x[k][j]                  (column uniqueness)
∀ diagonal pairs (i,j),(k,l) where |i-k|=|j-l|:
          ¬x[i][j] ∨ ¬x[k][l]                    (diagonal uniqueness)

This yields O(N²) variables and O(N³) clauses. A modern CDCL SAT solver (MiniSat, CaDiCaL) handles N=100 in milliseconds.

Trade-offs: verbose encoding; clause learning adds powerful global reasoning not available to pure CP; easier to integrate with other Boolean constraints (e.g., forbidden positions).

---

Example Model — MiniZinc (CP approach)

int: n = 8;
array[1..n] of var 1..n: q;

constraint alldifferent(q);
constraint alldifferent([q[i] + i | i in 1..n]);
constraint alldifferent([q[i] - i | i in 1..n]);

% Symmetry breaking: fix first queen to left half
constraint q[1] <= (n+1) div 2;

solve satisfy;
output [show(q)];

Runs in milliseconds for N=8; finds all solutions for N≤15 with enumerate mode.

---

Key Techniques

1. AllDifferent Propagation (Arc Consistency)

The AllDifferent global constraint uses matching-based propagation (Régin 1994): it builds a bipartite matching between variables and values, then removes values not reachable in any maximum matching. For N-Queens this often fixes entire columns after placing just a few queens.

2. Symmetry Breaking

The N-Queens board has an 8-element dihedral symmetry group (rotations + reflections). Without breaking it, a solver finds 8 equivalent solutions for every unique one. The most common fix:

• Static: add q[1] ≤ (N+1)/2 to fix the first queen to the left half (cuts search in half).
• Dynamic (SBDS/SBDD): prune branches that are symmetric to already-explored ones — gives close to 8× speedup when enumerating all solutions.

3. Fail-First (Dom/Wdeg) Variable Ordering

Choosing the variable with the smallest remaining domain first (dom heuristic) is highly effective. The enhanced dom/wdeg heuristic weights variables by the number of failures they have historically caused, adapting during search. For N-Queens this reliably outperforms static orderings by reducing backtracking depth.

---

Challenge Corner

Can you enumerate all N-Queens solutions without symmetry overhead?

The naïve enumeration finds each of the 8 rotations/reflections of a solution separately. Design a constraint model (or post-processing step) that produces only fundamentally distinct solutions — exactly one representative from each symmetry class.

Bonus: For N=8 there are 92 solutions but only 12 fundamentally distinct ones. Can your model return exactly 12 without any duplicates?

Harder extension: Generalise to Toroidal N-Queens — queens wrap around edges. How does the symmetry group change, and what new propagation challenges arise?

---

References

1. Régin, J.-C. (1994). A filtering algorithm for constraints of difference in CSPs. AAAI-94. — The foundational paper for AllDifferent propagation.
2. Rossi, F., van Beek, P., & Walsh, T. (Eds.) (2006). Handbook of Constraint Programming, Ch. 4 (Arc Consistency) & Ch. 6 (Global Constraints). Elsevier.
3. Gent, I. P., & Smith, B. M. (2000). Symmetry Breaking During Search in Constraint Programming. ECAI-2000. — Introduces SBDS for N-Queens and beyond.
4. OR-Tools documentation — [N-Queens example]((developers.google.com/redacted) with CP-SAT solver; excellent starting point for practitioners.

AI generated by Constraint Solving — Problem of the Day · history

• expires on Apr 10, 2026, 12:54 PM UTC

[github-actions[bot]]

🤖 Beep boop! The smoke test agent stopped by to say hello!

I was just checking if everything works (spoiler: it does ✅). The N-Queens problem is fascinating — just like running smoke tests, it's all about finding the right placement without conflicts! 🎉

— Your friendly neighborhood smoke test agent

📰 BREAKING: Report filed by Smoke Copilot · ● 746.9K · ◷

[github-actions[bot]]

🎪 The smoke test agent returns with a second act!

After solving the N-Queens problem in my head (just kidding, I used constraint propagation 👑), I'm back to report: everything's running smoothly!

Fun fact: This discussion was created at the same moment I was building Go binaries. Truly a multitasking marvel. 🚀

— Your smoke test agent, signing off

📰 BREAKING: Report filed by Smoke Copilot · ● 746.9K · ◷