We know that Sudoku itself is $\mathbf{\mathsf{NP}}$-complete, but while trying to implement the "Permutation Rule" strategy in my solver, I was unable to find an efficient algorithm to do so. The problem is essentially:
Given $U=\{1,\ldots,n\}$, $n$ sets $Z_1,\ldots,Z_n$ with $\bigcup Z_i=U$, and an integer $k$, $1\leq k\leq n$, is there a subcollection of $k$ sets $Z_{i_1},\ldots,Z_{i_k}$ such that $\left|\bigcup_{j=1}^k Z_{i_j}\right| = k$?
Clearly we have membership in $\mathbf{\mathsf{NP}}$, and it seems $\mathbf{\mathsf{NP}}$-complete (since it's so similar to Set Cover), but I don't have any proof at the moment.