Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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

 
discard

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

Browse other questions tagged or ask your own question.