🧩 Constraint Solving POTD:Problem of the Day: N-Queens — A Gateway to Constraint Programming

[github-actions[bot]]

The N-Queens Problem: A Gateway to Constraint Programming

Problem Statement

Place n queens on an n × n chessboard such that no two queens attack each other. Two queens attack if they share the same row, column, or diagonal.

Concrete Instance (n = 4):

. Q . .
. . . Q
Q . . .
. . Q .

Here, queens are at positions (0,1), (1,3), (2,0), (3,2). Each row has exactly one queen; no two share a column or diagonal.

Input/Output:

• Input: Integer n (board size)
• Output: One or more valid placements of n non-attacking queens (or "no solution" if n ∈ {2, 3})
• Extension: Count all solutions (e.g., 92 distinct solutions for n=8)

---

Why It Matters

The N-Queens problem appears in real-world scenarios:

• Circuit design and chip layout: Avoiding signal interference or thermal conflicts in specific geometric patterns mimics the attack constraint structure.
• Frequency assignment: Assigning communication channels to transmitters such that geographically proximal transmitters don't interfere.
• Scheduling with exclusion zones: Allocating resources where certain pairs cannot coexist (rows), cannot overlap (columns), or cannot be too close (diagonals).

Beyond applications, N-Queens is a canonical teaching tool in constraint programming: it illustrates search trees, pruning, variable ordering heuristics, and symmetry breaking in an intuitive visual setting.

---

Modeling Approaches

Approach 1: Constraint Programming (CP)

Variables:
queen[i] ∈ {0..n-1} for row i = column position of queen in row i.

Constraints:

AllDifferent(queen[0], queen[1], ..., queen[n-1])           // No two in same column
∀i, j : i ≠ j ⟹ |queen[i] - queen[j]| ≠ |i - j|            // No diagonal attacks

Why it works: Column uniqueness is enforced by AllDifferent, a global constraint with strong propagation. Diagonal constraints are posted as inequalities. Most CP solvers include specialized algorithms for these constraints.

Trade-offs:

• ✅ Concise, declarative model
• ✅ Strong propagation (especially AllDifferent)
• ✅ Easily scales to n=100+
• ❌ Fewer low-level tuning knobs than SAT/MIP

Approach 2: Integer Linear Programming (MIP)

Variables:
x[i,j] ∈ {0,1} = 1 iff queen is at row i, column j.

Constraints:

∑_j x[i,j] = 1         ∀i (exactly one queen per row)
∑_i x[i,j] ≤ 1         ∀j (at most one per column)
∑_{(i,j): i+j=k} x[i,j] ≤ 1    ∀ diagonals (sum / product)
∑_{(i,j): i-j=k} x[i,j] ≤ 1    ∀ anti-diagonals

Why it works: Integer linear constraints model the attack structure directly. Standard branch-and-cut can solve it.

Trade-offs:

• ✅ General-purpose solvers (CPLEX, Gurobi, CBC)
• ✅ Can prove optimality certificates
• ❌ More variables/constraints than CP (n2 vs n)
• ❌ Weaker propagation for combinatorial structure

Example Model (MiniZinc)

int: n;
array [1..n] of var 1..n: queen;

constraint all_different(queen);
constraint forall (i in 1..n, j in i+1..n) (
  abs(queen[i] - queen[j]) != abs(i - j)
);

solve satisfy;

output ["Solution for n=\(n):\n"] ++
       ["\(queen)\n"];

---

Key Techniques

1. Variable Ordering Heuristics (First-Fail)

Assign queens from top row to bottom row. At each step, branch on the column with the fewest remaining consistent positions (minimum remaining values / MRV heuristic). This prunes the search tree dramatically by making hard decisions early and detecting conflicts quickly.

2. Arc Consistency & Constraint Propagation

• AllDifferent propagation: When a queen is placed in column c, remove c from all subsequent rows' domains.
• Diagonal constraints: When queen i is at column j, eliminate column j ± (k - i) for all future rows k. Modern solvers achieve arc consistency on these diagonals in O(n2) or better.

3. Symmetry Breaking

The N-Queens problem has 8-fold symmetry (4 rotations × 2 reflections). To count unique solutions or avoid redundant search:

• Lexicographic ordering: queen[0] < queen[n-1] (or other breaking constraints)
• Fix first queen: Place the first queen at a specific position (e.g., column 0), then solve n-1 queens on the remainder
• These reduce search space by a factor of ~8 for symmetric problems.

---

Challenge Corner

Question for you:

1. Symmetry: The 8 symmetries of the board mean many solutions are rotations/reflections of others. How would you add the fewest constraints to ensure your solver finds only canonical solutions (one per equivalence class)?

2. Scaling: Can you model N-Queens such that the constraint propagation (without search) reduces the domains significantly before the solver even branches? What global constraints might help?

3. All-solutions: If you want to count all N-Queens solutions efficiently, would you use backtracking with symmetry breaking, or SAT enumeration? Why?

---

References

1. Rossi, F., van Beek, P., & Walsh, T. (2006). Handbook of Constraint Programming. Elsevier. § 1 & 15 (foundational CP theory and CSP tutorial).

2. Gent, I. P., & Walsh, T. (1999). "CSPlib: a benchmark library for constraints." Technical report, available at csplib.org. Includes N-Queens as CSP benchmark #4 with extensive experimental data.

3. Hooker, J. N. (2012). Integrated Methods for Optimization (2nd ed.). Springer. Chapter on constraint programming with N-Queens as case study.

4. OR-Tools & MiniZinc documentation: Both solvers ship with N-Queens examples and tutorials demonstrating CP vs. SAT modeling side-by-side.

---

Next Problem: Check back tomorrow for a routing or hybrid-optimization challenge!

Generated by 🧩 Constraint Solving — Problem of the Day · haiku45 35.2K · ◷

• expires on Jun 6, 2026, 11:55 AM UTC

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #36109.