🧩 Constraint Solving POTD:Problem of the Day: N-Queens Problem

[github-actions[bot]]

Problem Statement

The N-Queens problem asks: can you place N chess queens on an N×N chessboard such that no two queens attack each other?

Two queens attack each other if they share:

• The same row
• The same column
• The same diagonal (either direction)

Concrete Instance

For a 4×4 board, one valid solution is:

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

Here, queens at positions (0,1), (1,3), (2,0), (3,2) don't attack each other. For N=8 (standard chessboard), there are exactly 92 distinct solutions.

Input/Output

• Input: An integer N (board size)
• Output: One assignment of queens to the board, or all solutions, or a yes/no answer to feasibility

---

Why It Matters

AI & Algorithm Research: N-Queens is a textbook constraint satisfaction problem used to teach and benchmark CP solvers, backtracking algorithms, and heuristic search. Papers on branching strategies, constraint propagation, and solver performance routinely benchmark on N-Queens.

Symmetry & Optimality: The problem is feasible for all N ≥ 4 (and N = 1), making it ideal for studying solution structure, symmetry breaking, and counting solutions—a problem space where exact results are known and solutions can be verified quickly.

---

Modeling Approaches

Approach 1: Constraint Programming (Binary Matrix)

Variables: q[i][j] ∈ {0, 1} for each cell (i, j), where 1 means a queen is present.

Constraints:

∀ i:  Σj q[i][j] = 1          (exactly one queen per row)
∀ j:  Σi q[i][j] = 1          (exactly one queen per column)
∀ d:  Σ(i,j on diag d) q[i][j] ≤ 1  (at most one per diagonal)

Trade-offs:

• Intuitive and general—works well with existing CP/MIP solvers.
• O(N2) variables; constraint propagation can be strong if diagonals are modeled as global constraints.
• Slightly more verbose than permutation-based models.

Approach 2: Constraint Programming (Permutation)

Variables: q[i] ∈ {0..N-1} for row i, representing the column of the queen in that row.

Constraints:

AllDifferent(q)  (all columns distinct)
∀ i,j: i ≠ j ⟹ q[i] - q[j] ≠ i - j  (no diagonal /)
∀ i,j: i ≠ j ⟹ q[i] - q[j] ≠ j - i  (no diagonal \)

Trade-offs:

• Compact: O(N) variables vs. O(N2).
• The AllDifferent constraint benefits from strong propagation algorithms (e.g., matching algorithms).
• Diagonal constraints are arithmetic, making them amenable to fine-grained propagation.
• This is the preferred model for most CP solvers.

Example Model (MiniZinc)

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

constraint alldifferent(q);
constraint forall(i, j in 1..N where i < j) (
    abs(q[i] - q[j]) != abs(i - j)
);

solve satisfy;

output ["Queens at columns: "] ++ [show(q)] ++ ["
"];

This model declares N variables (one per row), ensures all queens occupy different columns, and forbids queens from being on the same diagonal. Most modern CP solvers solve this in milliseconds.

---

Key Techniques

1. AllDifferent Constraint & Arc Consistency

The AllDifferent constraint is a global constraint with strong propagation. Solvers use algorithms like matching or bipartite-flow reasoning to prune the domain of q[i] values aggressively. For N-Queens, this alone eliminates many invalid partial solutions early.

2. Variable & Value Ordering Heuristics

• Variable order: Leftmost variable (first unassigned row) is a simple strategy.
• Value order: Choose columns in order, or use a heuristic like "least constraining value" (pick the column that eliminates the fewest future options).
• For N-Queens, intelligent value ordering can reduce the search tree exponentially.

3. Symmetry Breaking

N-Queens has rich symmetry (rotations, reflections). Adding symmetry-breaking constraints—e.g., "the first queen in row 0 must be in column ⌊N/2⌋"—reduces the search space by the symmetry group's size (a factor of 8 for full symmetry). This allows solvers to find one solution much faster, though counting all solutions requires care.

---

Challenge Corner

🤔 Open Questions for Readers:

1. Symmetry Breaking: If you want to count all distinct solutions to N-Queens, how would you modify the constraints to avoid counting symmetric variants as separate solutions? (Hint: consider lexicographic ordering or fixed rows.)

2. Redundant Constraints: The permutation model uses O(N) variables. Can you add redundant (implied but non-trivial) constraints that strengthen propagation without changing feasibility? For example, what global properties must the queen positions satisfy?

3. Search vs. Propagation Trade-off: Compare the time to solve N-Queens (for N = 20, 50, 100) using:

   • Backtracking alone (check constraints only at leaves)
   • Backtracking + arc consistency (prune domains during search)
   • A complete CP solver (strong propagation, intelligent heuristics)

   How do runtimes scale?

---

References

1. Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier.
   → Definitive reference; Chapter 1 introduces N-Queens as a canonical CSP.

2. Hooker, J. N. (2012). Integrated Methods for Optimization (2nd ed.). Springer.
   → Excellent treatment of hybrid CP/operations research; includes N-Queens as a running example.

3. OEIS A000170: Sequence of the number of solutions to the N-Queens problem.
   → (oeis.org/redacted)
   → Provides verified solution counts for N=1 to N=27; useful for validating solver results.

4. MiniZinc Documentation: Global Constraints.
   → (www.minizinc.org/redacted)
   → Shows how alldifferent and other global constraints are modeled and propagated.

---

Happy solving! Drop a comment below with your approach, solution count for a large N, or a clever symmetry-breaking idea. 🎯

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 7.12 AIC · ⌖ 6.65 AIC · ⊞ 6.2K · ◷

• expires on Sep 11, 2026, 3:34 AM UTC-08:00