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

[github-actions[bot]]

Problem Statement

Place n queens on an n × n chessboard so that no two queens attack each other. Queens attack along rows, columns, and both diagonals, so every row, every column, and every diagonal may hold at most one queen.

Small instance (4×4): there are exactly two solutions, shown here as the column of the queen in each row (1-indexed):

• (2, 4, 1, 3)
• (3, 1, 4, 2)

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

Input: board size n.
Output: one (or all) placements that satisfy the constraints, or a proof that none exists.

Solution counts for n = 1..10 are 1, 0, 0, 2, 10, 4, 40, 92, 352, 724. Up to the board's eight symmetries (rotations and reflections), 8-queens has only 12 distinct solutions.

Why It Matters

• Benchmarking: N-Queens is a standard test for new CSP propagators, search heuristics, and local-search methods.
• Resource placement: placing non-interfering items on a grid (for example, radar or cell-tower sites that must not share a line of sight in a simplified model) is the same structure.
• Teaching: it shows, in one picture, how a single global constraint such as alldifferent captures several families of pairwise conflicts at once.

Modeling Approaches

1. Constraint Programming (one variable per row)

• Variables: x_i ∈ {1..n}, the column of the queen in row i. This gives only n variables.
• Constraints: alldifferent(x), alldifferent(x_i + i), and alldifferent(x_i − i). These cover columns and both diagonal directions.
• Trade-off: the row constraint is built in, so the search space is n^n rather than 2^(n2). Propagation of alldifferent removes many values early. The model is compact and scales well to dozens of queens.

Example Model (Pseudo-code)

vars   x[1..n] ∈ {1..n}          # x[i] = column of queen in row i
alldifferent(x)                  # at most one queen per column
alldifferent([x[i] + i | i])     # at most one per "/" diagonal
alldifferent([x[i] - i | i])     # at most one per "\" diagonal
solve satisfy                    # or enumerate all solutions

2. 0/1 Linear / SAT Encoding (one variable per cell)

• Variables: b[i,j] ∈ {0,1}, 1 if a queen sits at row i, column j. This gives n2 variables.
• Constraints: Σ_j b[i,j] = 1 for each row, and Σ ≤ 1 over each column and each diagonal.
• Trade-off: this is a natural fit for MIP or pseudo-Boolean solvers and for SAT encodings. Each "at most one" line becomes a pairwise clause set, which is roughly O(n3) clauses in total. The LP relaxation is weak (fractional solutions are easy to find), so the solver relies on branching and clause learning rather than bounding. Expect this to scale worse than model 1.

Key Techniques

• Global-constraint propagation. alldifferent is usually filtered with generalized arc consistency using bipartite matching (Régin, 1994). This detects values that cannot appear in any solution, which prunes far more than pairwise ≠ constraints do.
• Symmetry breaking. The eight board symmetries multiply the solution count. For 8-queens, adding a lex-leader constraint (for example, requiring the first queen to lie in a fundamental corner region) cuts the search by roughly a factor of 8 without losing any symmetry class.
• Local search for large n. Min-conflicts (Minton et al., 1992) starts from a random placement and repeatedly moves a conflicting queen to the least-conflicting column in its row. It finds solutions for very large boards with little memory, which systematic search cannot match.

Challenge Corner

• Fewer variables: can you model N-Queens with n variables and no diagonal alldifferent, using auxiliary variables instead? What does propagation look like?
• Symmetry: write the lex-leader constraints that keep exactly one representative from each group of symmetric solutions. Check that you get 12 for n = 8.
• Toroidal boards: what changes if the board wraps around at its edges, so diagonals continue across the boundary? For which n does a solution exist?

References

• Rossi, van Beek & Walsh (eds.), Handbook of Constraint Programming, Elsevier, 2006. Covers CSP modeling, global constraints, and symmetry breaking.
• Régin, J.-C. "A filtering algorithm for constraints of difference in CSPs." AAAI, 1994. The matching-based GAC algorithm for alldifferent.
• Minton, S., Johnston, M. D., Philips, A. B., & Laird, P. "Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems." Artificial Intelligence, 58(1–3), 1992.
• OEIS A000170, the sequence of N-Queens solution counts, with the values listed above.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · routed: haiku55 xhigh · ~2 AIC · ⌖ ~2 AIC · ⊞ 4.1K · ◷

• expires on Nov 17, 2026, 3:32 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 #76840.