9
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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,\ldots,9\}$. If you take a permutation that is a transposition (permutes two elements, keeping the other fixed), again, as before, you can remove all appearances of those two elements and you have an incomplete sudoku with two possible solutions and 63 clues. Again, if you don't remove all 18 numbers, the solution will be unique.

Of the six elemental operations that produce a completed sudoku (see here), these two are the ones that can involve the least number of elements, so I'd say $C=63$ is an upper bound for what you're looking for. I know this does not exactly answers your question, but the general idea of removing sets of positions which produce two different solutions might be a good starting point.

$\endgroup$
1
$\begingroup$

The fewest clues required for a proper Sudoku is 17, but not all completed grids can be reduced to a proper 17 clue Sudoku. About 49,000 unique (non-equivalent) Sudokus with 17 clues have been found. (A proper Sudoku has only one solution).

The most clues in a minimal Sudoku is believed to be 40 (two are known to exist), but it has not been proven if this is the maximum. (minimal means that if any clue is removed, the Sudoku would have more than one solution, and therefore not be a proper Sudoku)

(This information is from Wikipedia, of which these statements are well referenced).

$\endgroup$
  • $\begingroup$ I'm interested in whether 41 is a proven upper bound (as $\Big\lceil\frac N 2\Big\rceil$). $\endgroup$ – rus9384 Sep 30 '17 at 15:34
  • $\begingroup$ I have not seen that proven in any paper. Interestingly, nearly all work to find high-clue "h" minimal Sudokus appears to be conducted by a search of known Sudokus, and modifying them to iteratively increase "h". The work to find the minimal 40 clue puzzles produced a database of more than 6,500,000,000 other high-clue minimal puzzles. Except for trivial problems, I have seen almost no rigorous investigation by any means other than "searching". But your proposition is an interesting one. $\endgroup$ – tomoka kazuki Sep 30 '17 at 16:08
  • $\begingroup$ Could you add the citations here, please? Or at least a link to the relevant Wikipedia page. $\endgroup$ – David Richerby Sep 30 '17 at 18:20
  • $\begingroup$ This information is from Wikipedia's article "Mathematics of Sudoku" section "Maximum number of givens". The cited reference (for discovery of 1st 40 clue minimal Sudoku) is: forum.enjoysudoku.com/high-clue-tamagotchis-t30020-135.html Key information is sheet 10, but related information is both before and after sheet 10. $\endgroup$ – tomoka kazuki Oct 1 '17 at 1:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.