# Sudoku: Maximal minimum number of starting clues

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): 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.

• There's a trivial upper bound $M \le 64$. – Peter Taylor Jun 26 '19 at 8:51
• @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. – hexomino Jun 26 '19 at 9:05
• @PeterTaylor In fact, I can show quite easily that $M \leq 60$. Do you think it's worth adding this to the question? – hexomino Jun 26 '19 at 11:54
• Definitely. The context of what you already know about the question nearly always improves it. – Peter Taylor Jun 26 '19 at 12:50