# How hard is this constrained $n$-rooks problem?

Suppose you have an $(n\times n)$-chessboard, together with a constraining function $C : n \times n \to 2$ where $C(i,j) = 1$ iff you're allowed to place a rook in the $ij$-square. Consider the problem:

Can $n$ non-attacking rooks be placed on the board in squares allowed by $C$?

Is it NP-Hard?

Here's an alternative formulation: Let $x_1, \dots, x_n$ be elements (integers, say) and $P_1, \dots, P_n$ unary predicates such that $P_ix_j$ can be evaluated in constant time. Is there a permutation $\sigma \in S_n$ such that $P_ix_{\sigma(i)}$ for all $i$?

The equivalence can be seen by letting $C(i,j) = 1$ iff $P_i(x_j)$. Then a placement of rooks yields a witness to the permutation problem by letting $\sigma(i) = j$ iff there's a rook in square $ij$. $\sigma$ is a permutation because all $n$ rooks are placed in a non-attacking arrangement. $P_ix_{\sigma(i)}$ holds because $\sigma(i)=j$ implies theres'a rook in the $ij$ square, which implies $C(i,j) =1$, which, by definition, implies that $P_i(x_j)$.

• Deciding requires checking a max of $\sum C (i, j)$ (for all i and j) choose n possibilities. – d'alar'cop Jul 14 '14 at 22:04
• The "try-all-possibilities" algorithm has a worst-case runtime of ${n^2}\choose{n}$ which is something like $O(n!)$. – Amit Kumar Gupta Jul 14 '14 at 22:34
• Yes I know it's the most naive way, but I just thought it should be part of any further discussion. As a chess player I'm not sure you can do much better anyway. Someone better with algorithms will answer... – d'alar'cop Jul 15 '14 at 2:21

For a bipartite graph with $n$ vertices on the left, corresponding to the $n$ rows, and $n$ vertices on the right, corresponding to the $n$ columns. Include an edge from $i$ to $j$ if $C(i,j)=1$, i.e., if you're allowed to place a rook in the $(i,j)$ square (in the $i$th row and $j$th column). Now check whether there exists a perfect matching of this bipartite graph. This can be done in polynomial time using standard algorithms.
Notice that there exists a perfect matching if and only if there exists a way to place the rooks so they are non-attacking. Each edge in the matching corresponds to a place where a rook should be placed. Two rooks can attack each other only if they share the same row or the same column. A matching cannot have two edges that share the same left-vertex (same row) or same right-vertex (column), which means that any matching containing $n$ edges corresponds to a way to place $n$ rooks so they don't attack each other.