4
$\begingroup$

It is well known (as shown here) that the minimum number of starting clues a Sudoku puzzle may have to generate a unique solution is 17.

My main question is

Given a completed Sudoku grid, is it always possible to find a subset of 17 starting clues which generate the grid uniquely?

I suspect the answer might be 'no' as, accounting for symmetries, there are 3,359,232 distinct Sudoku grids and I think there are only around 50,000 known 17-clue Sudoku puzzles. This leads me to a follow-up question.

Let $\mathbb{S}$ be the set of all completed Sudoku grids. For a given $S \in \mathbb{S}$, let $m(S)$ be the minimum number of starting clues required to generate $S$ uniquely.
What is $$M = \max\{ m(S) | S \in \mathbb{S}\}?$$

If the answer is not known, do we have an upper bound for $M$?


What do I know so far?

We can demonstrate, by hand, that $M \leq 60$.
Take any completed Sudoku grid and remove the following entries (marked by an X):

enter image description here

The solution to this Sudoku is fully determined and some subset of the remaining clues will constitute a minimal set of starting clues.


I am almost certain that $M < 40$.

According to the mathematics of Sudoku, "The most clues for a minimal Sudoku is believed to be 40, of which only two are known." One way of generating Sudoku puzzles would be to start with a completed grid and remove entries using some algorithmic procedure until a minimal set of clues was reached. So much analysis has been done on this that, in my opinion, if somebody encountered a grid where they could not generate a set of starting clues with less than 40 entries, this would be of considerable note.


I suspect that $M$ is around $20$ and it's conceivable to me that somebody may have indirectly encountered a much better upper bound for $M$ while trying to generate puzzles from completed grids.

$\endgroup$
  • $\begingroup$ There's a trivial upper bound $M \le 64$. $\endgroup$ – Peter Taylor Jun 26 '19 at 8:51
  • $\begingroup$ @PeterTaylor My thinking is that we may be able to say $M \leq 40$ as the most clues for a minimal Sudoku is believed to be $40$ although I don't know if this has been proven. $\endgroup$ – hexomino Jun 26 '19 at 9:05
  • $\begingroup$ @PeterTaylor In fact, I can show quite easily that $M \leq 60$. Do you think it's worth adding this to the question? $\endgroup$ – hexomino Jun 26 '19 at 11:54
  • $\begingroup$ Definitely. The context of what you already know about the question nearly always improves it. $\endgroup$ – Peter Taylor Jun 26 '19 at 12:50

Your Answer

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

Browse other questions tagged or ask your own question.