Smallest integer kk so that no Sudoku grid has exactly kk solutions

Inspired by this question,
consider hints on a Sudoku board. A regular puzzle has a unique solution.
It is clear that there are puzzles with 2 or 3 solutions, and therefore, I guess, puzzles with say 4, and 6 solutions.

Now, what is the smallest integer k such that there is no set of Sudoku clues resulting in exactly k solutions?

Answer

Like it usually happens with these conjectures, if the solution is not k=7 or k=11, it may be really hard to find. Of course, there exists a solution, for there is a maximum (huge) number of solutions that a blank sudoku allows. A property that may help to construct solutions is that for small values, if we have a sudoku that allows a solutions and another that allows b solutions, we can probably find a sudoku that allows a·b solutions. For example:

This allows k=4 fillings:
2,9,6|3,1,8|5,7,45,8,4|9,7,2|6,1,37,1,3|6,4,5|2,8,96,2,?|?,9,7|3,4,19,3,1|4,2,6|8,5,74,7,?|?,3,1|9,2,61,?,7|2,?,3|4,9,88,?,9|7,?,4|1,3,23,4,2|1,8,9|7,6,5

And this allows k=3 fillings:
2,9,6|3,1,8|5,7,45,?,4|9,7,2|6,?,37,?,3|6,4,5|2,?,?6,2,5|8,9,7|3,4,19,3,1|4,2,6|8,5,74,7,8|5,3,1|9,2,61,6,7|2,5,3|4,?,?8,5,9|7,6,4|1,3,23,4,2|1,8,9|7,6,5

From this, we can easily see that this:
2,9,6|3,1,8|5,7,45,?,4|9,7,2|6,?,37,?,3|6,4,5|2,?,?6,2,?|?,9,7|3,4,19,3,1|4,2,6|8,5,74,7,?|?,3,1|9,2,61,?,7|2,?,3|4,?,?8,?,9|7,?,4|1,3,23,4,2|1,8,9|7,6,5

allows k = 4·3 = 12 fillings.

Although it is hard to generalize, probably the number you are looking for is prime, because if it was to be a composite number, its factors (smaller than the number) would have to be a number of fillings for some sudoku, and then this non-rigorous multiplication rule would fail.

Attribution
Source : Link , Question Author : Per Alexandersson , Answer Author : gonthalo

Leave a Comment