Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Peter Norvig's approach may help – Ben Feb 24 '13 at 21:10
@Ben, thanks, though my question is a theoretical one about the abstract problem I defined. I already have a fast Sudoku solver implemented. – Nick Feb 24 '13 at 21:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.