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

[github-actions[bot]]

Problem Statement

The N-Queens Problem is one of the most iconic problems in constraint satisfaction. It asks: How can you place N queens on an N×N chessboard such that no two queens attack each other?

In chess, a queen can attack any piece in the same row, column, or diagonal. The challenge is to find a valid placement—or count all valid placements—without conflicts.

Concrete Instance

For the 4-Queens problem (shown below), one valid solution is:

  1 2 3 4
1 . Q . .
2 . . . Q
3 Q . . .
4 . . Q .

Here, queens are placed at positions (1,2), (2,4), (3,1), (4,3). We can verify:

• Rows: Each row has exactly one queen. ✓
• Columns: Each column has exactly one queen. ✓
• Diagonals: No two queens share a diagonal. ✓

Input & Output

• Input: An integer N (board size)
• Output: A valid assignment of N queens to the N×N board, or a count of all solutions

For N=8, there are exactly 92 distinct solutions (and 12 fundamental solutions under symmetry).

---

Why It Matters

Historical & Educational Significance

The N-Queens problem emerged in 1848 and became a foundational benchmark for constraint-solving algorithms. It inspired generations of researchers to develop new search and pruning techniques.

Modern Applications

• Resource Allocation: Assigning N tasks to N time slots or machines without conflicts mirrors N-Queens' symmetry-breaking requirements.
• Frequency Assignment: Allocating radio frequencies or wavelengths to transmitters such that nearby transmitters don't interfere is a direct analog.
• Circuit Layout & VLSI: Placing components on a chip while respecting electrical and thermal constraints follows similar constraint logic.

---

Modeling Approaches

Approach 1: Constraint Programming (CP) — Permutation Model

Decision Variables:

• queens[i] = column position of the queen in row i (i ∈ 1..N)
• Domain: each queens[i] ∈ {1..N}

Constraints:

1. All-different (columns): all_distinct(queens[1], queens[2], ..., queens[N])
2. Diagonal constraint (↘): For all i < j: queens[i] - queens[j] ≠ i - j
3. Diagonal constraint (↙): For all i < j: queens[i] + queens[j] ≠ i + j

Why this model?

• Compact: Only N variables (vs. N2 binary variables).
• Strong propagation: all_distinct is a powerful global constraint; arc consistency removes vast portions of the search space.
• Symmetry-aware: The permutation structure naturally respects column uniqueness.

---

Approach 2: Integer Linear Programming (ILP) — Positional Model

Decision Variables:

• x[i][j] ∈ {0, 1} for each cell (i, j) on the board
  • 1 if a queen is placed at row i, column j; 0 otherwise

Constraints:

1. Exactly one queen per row: ∑_j x[i][j] = 1 for each i
2. Exactly one queen per column: ∑_i x[i][j] = 1 for each j
3. Diagonals (↘): ∑_{(i,j): i-j=k} x[i][j] ≤ 1 for all diagonals k
4. Diagonals (↙): ∑_{(i,j): i+j=k} x[i][j] ≤ 1 for all diagonals k

Why this model?

• Relaxation friendly: Solving the LP relaxation gives a fractional bound; useful for branch-and-bound.
• Scalability: Standard MIP solvers (CPLEX, Gurobi) can handle large N efficiently.
• Trade-off: N2 variables create higher computational overhead than the CP model, but ILP has mature solver technology.

---

Approach 3: SAT Encoding

Encode the problem as a Boolean satisfiability instance with clause-based reasoning:

• Variables: queen[i][j] = TRUE iff a queen is at (i, j)
• Clauses: Encode constraints as conjunctions of disjunctions
  • Row constraints: ¬queen[i][j1] ∨ ¬queen[i][j2] for j1 ≠ j2 (at most one per row)
  • Column & diagonal constraints similarly

Why SAT?

• Leverage CDCL solvers: Modern SAT solvers (MiniSat, CaDiCaL) use conflict-driven clause learning.
• Proof generation: SAT solvers can produce unsatisfiability proofs if N is infeasible.
• Trade-off: Encoding is verbose (many clauses), but competitive on some problem sizes.

---

Modeling Example (Pseudo-code)

Below is a concise CP model in pseudo-notation (resembling MiniZinc):

model NQueens {
  % Decision variables
  array[1..N] of var 1..N: queens;
  
  % Constraints
  all_distinct(queens);  % Column uniqueness
  
  % Diagonal constraints
  forall(i in 1..N, j in i+1..N) {
    queens[i] - queens[j] != i - j;  % ↘ diagonals
    queens[i] + queens[j] != i + j;  % ↙ diagonals
  }
  
  solve satisfy;
}

This model is so compact and natural that many CP solvers can derive strong propagation automatically—often finding a solution for N=1000 within milliseconds!

---

Key Techniques

1. Arc Consistency & Global Constraints

The all_distinct constraint enforces arc consistency, immediately pruning many combinations. Specialized propagation algorithms for all_distinct and diagonal constraints are far more efficient than checking each pair independently.

2. Variable & Value Ordering Heuristics

• Static: Place queens from left to right (row 1 to N).
• Dynamic: Use "most constrained variable" (MCV)—choose a row with the fewest remaining valid column positions.
• Value ordering: Prefer column positions near the middle (they tend to reduce future conflicts).

3. Symmetry Breaking

N-Queens has rotational and reflectional symmetries. Adding redundant constraints like queens[1] < queens[N] can halve the search tree without losing solutions:

queens[1] < N/2 + 1  % Break left-right symmetry

These symmetry-breaking constraints are optional but dramatically speed up complete enumeration.

---

Challenge Corner

🤔 Can you extend N-Queens to the "N-Queens + Bishops" variant, where you must place N bishops and N knights on an N×N board such that no piece attacks another? What new constraints emerge? How would propagation change?

---

References

1. Rossi, F., van Beek, P., & Walsh, T. (2006). Handbook of Constraint Programming. Elsevier.

   • Chapter on CSP fundamentals and the N-Queens problem as a canonical example.

2. Hooker, J. N. (2012). Integrated Methods for Optimization (2nd ed.). Springer.

   • Covers CP, MIP, and SAT from a unified optimization perspective.

3. Gecode Documentation: N-Queens Example

   • (www.gecode.org/redacted) — includes ready-to-run C++ and Python models.

4. Helmert, M. (2006). The Metric-FFP Planner: System Description. ICAPS Competition.

   • Shows how N-Queens generalizes to planning and constraint-based reasoning in AI.

Generated by 🧩 Constraint Solving — Problem of the Day · haiku45 · 5.49 AIC · ⌖ 4.42 AIC · ⊞ 6.2K · ◷

• expires on Aug 26, 2026, 3:38 AM UTC-08:00

[github-actions[bot]]

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

A newer discussion is available at Discussion #54212.