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?
$\begingroup$
$\endgroup$
0
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
4
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).
-
$\begingroup$ I'm interested in whether 41 is a proven upper bound (as $\Big\lceil\frac N 2\Big\rceil$). $\endgroup$– rus9384Commented Sep 30, 2017 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$ Commented Sep 30, 2017 at 16:08
-
$\begingroup$ Could you add the citations here, please? Or at least a link to the relevant Wikipedia page. $\endgroup$ Commented Sep 30, 2017 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$ Commented Oct 1, 2017 at 1:10
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
3
This Sudoku has 77 clues and yet it has multiple solutions (2).
You can use 7-4 on the top row and 4-7 on the other one or using 4-7 on the top and 7-4 on the bottom. This particular Sudoku puzzle needs 78 clues to have a unique solution.
-
1$\begingroup$ This is a good point, but I think it's not exactly the question being asked, which is about minimal number of clues to specify the puzzle if you get to choose the clues strategically $\endgroup$ Commented Mar 30, 2020 at 15:17
-
$\begingroup$ I think it's a good answer, but it would be nice to add to this answer (1) a note why this is a bit different than the question asked, (2) convert the fuzzy image to a table in text and/or an explanation $\endgroup$ Commented Mar 30, 2020 at 15:18
-
2$\begingroup$ You say it "needs 78 clues". Yes, it is true that a puzzle with just these 77 clues does not have a unique solution. But the puzzle itself doesn't "need" 78 clues. Yes, it could be written as a puzzle with 78 clues, if you left 3 of the 4 whitened blocks blank. But a puzzle with the same solution could also be written with much less than 78 clues. $\endgroup$ Commented Mar 7, 2021 at 19:18