# 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.

Update: A proof that $$M \leq 48$$ was given here on Puzzling SE

Also, $$M \geq 18$$, as verified by examples given here

• There's a trivial upper bound $M \le 64$. Commented Jun 26, 2019 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. Commented Jun 26, 2019 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? Commented Jun 26, 2019 at 11:54
• Definitely. The context of what you already know about the question nearly always improves it. Commented Jun 26, 2019 at 12:50
• @Sigur On the other extreme, it's possible to have a Sudoku grid with 77 clues and multiple possible solutions. Number of clues says very little if those clues aren't optimally distributed. Commented May 19, 2020 at 17:52

I guess the page https://en.wikipedia.org/wiki/Mathematics_of_Sudoku says ,,A puzzle with a unique solution must have at least 17 clues, and there is a solvable puzzle with at most 21 clues for every solved grid.'' As I understand the second part of the sentence means $$M \le 21$$ in this context.