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