We know from this paper that there does not exist a puzzle that can be solved st

Question

We know from this paper that there does not exist a puzzle that can be solved starting with 16 or fewer clues, but it implies that there does exist a puzzle that can be solved from 17 clues. Can all valid sudoku puzzles be specified in 17 clues? If not, what is the minimum number of clues that can completely specify every valid puzzle? More formally, does there exist a valid sudoku puzzle (or, I guess it would be a set of puzzles) that cannot be uniquely solved from only 17 clues? If so, then what is the minimum number of clues, C, such that every valid sudoku puzzle can be uniquely specified in C or fewer clues?

Explanation / Answer

Since permuting two rows within a single block of a valid, completed sudoku produces another valid, completed sudoku, you can take any completed board (81 clues) and remove the first two rows (81-18=63 clues), which will give you an incomplete sudoku with two solutions. Note that even if you remove all but one of the 18 numbers there, the solution is immediately uniquely determined (since there can be no number repeated in the same column).

Another operation that produces another completed sudoku is applying a permutation of {1,

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.