Maximum Givens in Minimal Sudoku

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $C=\{1,\ldots,9\}^2$ be the cells of a standard $9\times9$ Sudoku. A solution is a map $s:C\to\{1,\ldots,9\}$ whose values in each row, each column and each of the nine $3\times3$ boxes are exactly $1,\ldots,9$. A puzzle is a partial map $p:D\to\{1,\ldots,9\}$ with $D\subseteq C$; its givens are the $|D|$ assigned cells. Write $\operatorname{Comp}(p)=\{s:\ s\text{ is a solution and }s|_D=p\}$. A puzzle is minimal if $|\operatorname{Comp}(p)|=1$ and, for every $d\in D$, deleting that clue gives $|\operatorname{Comp}(p|_{D\setminus\{d\}})|\ge2$.

Statement recorded in the supplied source.

Determine \[ M=\max\left\{|D|:\ p:D\to\{1,\ldots,9\}\text{ is a minimal standard Sudoku puzzle}\right\}. \] Minimality means that every given is essential to uniqueness; it does not mean having the fewest givens among all puzzles. [S1][S2]

Short English statement

What is the largest number of givens that a standard 9 by 9 Sudoku can have while every individual given is essential to its unique solution?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1360 (GAME-003). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Gary McGuire, Bastian Tugemann and Gilles Civario, There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration (2013), arXiv:1201.0749v2, Section 1 (Sudoku rules and unique completion), and Section 5.1 (clue sets and unavoidable sets). https://arxiv.org/abs/1201.0749v2.