7
$\begingroup$

I asked this over on math.stackexchange.com, then I found out about this forum.

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)$.

$\endgroup$
3
  • $\begingroup$ Deciding requires checking a max of $\sum C (i, j)$ (for all i and j) choose n possibilities. $\endgroup$ – d'alar'cop Jul 14 '14 at 22:04
  • $\begingroup$ The "try-all-possibilities" algorithm has a worst-case runtime of ${n^2}\choose{n}$ which is something like $O(n!)$. $\endgroup$ – Amit Kumar Gupta Jul 14 '14 at 22:34
  • $\begingroup$ 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... $\endgroup$ – d'alar'cop Jul 15 '14 at 2:21
10
$\begingroup$

This problem can be solved in polynomial time, using bipartite matching.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.