🧩 Constraint Solving POTD:Problem of the Day: Rook Placement Problem

[github-actions[bot]]

Problem Statement

The Rook Placement Problem asks: Can you place n non-attacking rooks on an n × n chessboard, with a constraint that each rook must respect certain forbidden positions?

In the simplest variant (unrestricted), this is trivial—place one rook per row and column in any order. The interesting variant adds forbidden cells: regions or patterns where rooks cannot be placed. This transforms it into a genuine constraint satisfaction problem.

Concrete Instance (n=4, small forbidden set):

4×4 board with forbidden cells marked as X:

  1 2 3 4
1 . . X .
2 X . . .
3 . X . .
4 . . . X

Can you place 4 rooks (one per row, one per column) avoiding all X positions?

Solution (if one exists):

  1 2 3 4
1 . . . R
2 . R . .
3 . . . .  (wait, need to recount—this needs correction)
4 R . . .

One solution: (1,4), (2,2), (3,1), (4,3) assigns rooks to positions row 1 col 4, row 2 col 2, etc.

Why It Matters

Real-world applications:

• Board placement verification: Circuit board design often requires placing non-interfering components (rooks model rigid placement constraints).
• Non-attacking placement: Extensions apply to turrets, antennas, or sensors that must not interfere with each other in grid-based configurations.
• Permutation problems with obstacles: Any scenario requiring a permutation (one-to-one mapping between rows and columns) where certain pairings are forbidden.
• Graph matching on bipartite graphs: Finding a perfect matching in a bipartite graph where edge absence represents forbidden combinations.

Practitioners in embedded systems, robotics, and operations research encounter this repeatedly in layout and assignment problems.

Modeling Approaches

Approach 1: Explicit Permutation Model (CP)

Decision variables: perm[i] ∈ {1..n} for each row i, representing the column of the rook in row i.

Constraints:

• alldifferent(perm[1], perm[2], ..., perm[n]) — each column used exactly once
• (i, perm[i]) ∉ forbidden_set for all i — rooks avoid forbidden cells

Trade-offs:

• Pros: Compact representation; alldifferent is a strong global constraint with excellent propagation (arc consistency).
• Cons: Less natural if forbidden patterns are complex; harder to reason about column-wise constraints directly.

Approach 2: Binary Matrix Model (MIP/SAT)

Decision variables: x[i,j] ∈ {0,1} for each cell (i,j).

Constraints:

• ∑_j x[i,j] = 1 for all rows i — one rook per row
• ∑_i x[i,j] = 1 for all columns j — one rook per column
• x[i,j] = 0 for all (i,j) ∈ forbidden_set — no rooks on forbidden cells

Trade-offs:

• Pros: Naturally encodes forbidden positions; easier to integrate with MIP solvers; familiar to operations research practitioners.
• Cons: n2 variables instead of n; less direct exploitation of permutation structure; linear relaxation may be weak.

Example Model (MiniZinc Pseudo-code)

int: n = 4;
set of int: Rows = 1..n;
set of int: Cols = 1..n;

% Define forbidden cells
set of tuple(int, int): forbidden = {(1,3), (2,1), (3,2), (4,4)};

% Permutation model
array[Rows] of var Cols: perm;
constraint alldifferent(perm);

% Forbidden constraint
constraint forall(i in Rows) (
  (i, perm[i]) not in forbidden
);

solve satisfy;

Key Techniques

1. Global Constraint Propagation (alldifferent)

The permutation model leverages alldifferent, which maintains arc consistency via bipartite matching algorithms (e.g., Hungarian algorithm or augmenting paths). When domain wipeout occurs for any variable, propagation detects infeasibility early.

2. Symmetry Breaking

Rook placement exhibits symmetry: permutations can be reordered without changing the underlying problem structure. Breaking symmetries via lexicographic ordering (e.g., perm[i] < perm[i+1] in certain contexts) or by constraining the first rook's position reduces search space.

3. Constraint Propagation with Forbidden Sets

Model forbidden cells as domain restrictions: pre-process to remove forbidden (i,j) from variable domains. Combined with alldifferent propagation, this shrinks search space before search begins.

Challenge Corner

**For you to think (redacted)

1. Symmetry-breaking question: The rook placement problem has multiple symmetries (row/column swaps, rotations). How would you phrase symmetry-breaking constraints that don't remove valid solutions?

2. Extension to partial placement: Suppose some rooks are already placed (fixed positions). How would you modify the model to verify feasibility and count solutions efficiently?

3. Complexity trade-off: For large n with sparse forbidden sets, would the permutation model or the binary matrix model scale better? Why?

References

1. Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier. — Chapter on permutation CSPs and global constraints.

2. Régin, J. C. (1994). "A filtering algorithm for constraints of difference in CSPs." AAAI, pp. 362–367. — Seminal work on alldifferent propagation.

3. Combinatorics and Permutations: Wikipedia article on Rook Polynomials and Problème des rencontres for mathematical background on forbidden permutations.

4. Hooker, J. N. (2021). Integrated Methods for Optimization (2nd ed.). Springer. — Chapters on permutation problems and hybrid CP/MIP.

---

Next problem: Stay tuned for tomorrow's challenge in the Scheduling category. What's your favorite constraint-solving technique? Share your thoughts below!

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 6.89 AIC · ⌖ 6.21 AIC · ⊞ 6K · ◷

• expires on Oct 9, 2026, 3:35 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 #65305.