Which digits can a Sudoku puzzle leave out?
1 Introduction
I started doing Sudoku puzzles because a classmate I admired did one every day, the conversations between us did not go far, but my love for puzzles did. I aimed to create a tribute in the form of a website that generated 3 Sudoku daily with a range of difficulties for people to play through. Throughout the development and design process, a common pattern within the clues appeared, where the clues in a puzzle are not spread evenly across the nine digits. While some digits turn up several times, every so often a digit does not appear at all. With an aim to figure out truly how difficult a puzzle could be I had to investigate. First, how many digits can a proper Sudoku puzzle leave out? Could a puzzle be set using only four different digits, what about three? Second, if one digit can be omitted, what is the lowest number of clues are needed to do it?
The first question reveals that a proper Sudoku can omit exactly one digit. The proof uses the fact that Sudoku symbols can be relabelled as letters without changing the rules. An explicit proper puzzle whose clues use exactly eight digits is then shown.
The more general idea behind the proof is an unavoidable set: a collection of cells where two completed grids can differ. A proper puzzle must contain a clue in every unavoidable set, or else the second grid would also solve it. This turns the search for valid puzzles into a hitting-set problem, which is tied to the exhaustive algorithms that underlie the 17-clue minimum for ordinary Sudoku [MTC14].
The computational part of this paper looks at the eight-digit problem. The search described finds a proper 20-clue puzzle using eight digits, giving \[ 17\leq m_8\leq20, \] where \(m_8\) is the minimum number of clues in a proper puzzle whose clues use exactly eight digits.
Throughout, a completed grid is a \(9\times9\) array in which every row, column and \(3\times3\) box contains each of \(1,\ldots,9\) exactly once. A puzzle is a partially filled grid, its filled cells being aptly named clues, and a puzzle is proper if it has exactly one completed grid as its solution. The distinct clue digits are the digits occurring among the clues; this counts the clues alone, not including the solution, which always contains all nine.
2 Relabelling symmetry
The digits in a Sudoku are just labels, as they don't depends on any numerical facts like \(17+4=21\). The nine symbols could just as well be letters or colours and all results could be reproduced in a similar manner.
Let \(G\) be a completed Sudoku grid, if we replace every number \(v\) in \(G\) with \(\pi(v)\), where \(\pi\) is any arrangement of \(\{1,\ldots,9\}\), the result is a second completed Sudoku grid.
Every row, column and box of \(G\) contains a digit of \(1,\ldots,9\) exactly once. Applying a permutation simply changes their labels, so each row, column and box still contains each of \(1,\ldots,9\) once. Therefore the new array is also a completed Sudoku grid.
There are \(9!=362\,880\) permutations of the nine digits, so every completed grid belongs to a family of \(362\,880\) grids simply by relabelling its symbols.
3 A proper Sudoku needs eight digits
The clues of a proper \(9\times9\) Sudoku puzzle contain at least eight distinct digits.
Take instead that the clues contain a maximum of seven unique digits. Then at least two digits, \(a\) and \(b\), are absent from the clues.
Let \(G\) be the unique solution of the puzzle. \(G'\) can be defined as a completed grid where \(a\) and \(b\) have been swapped for everywhere in \(G\). By Lemma 2.1, \(G'\) is a valid completed Sudoku.
Since every clue is a digit other than \(a\) or \(b\), the swap leaves every clue as it was prior to the swap. Therefore \(G'\) satisfies every clue and is also a solution of the same puzzle.
But \(G'\neq G\), because the nine cells containing \(a\) in \(G\) contain \(b\) in \(G'\). Hence the puzzle has at least two solutions, making it improper.
A proper Sudoku can omit at most one of the nine digits.
4 Eight digits are achievable
The lower bound is quite literally only half the answer, This paper must also show that eight digits can actually occur in a proper puzzle. The following example uses the digits \(\{1,2,4,5,6,7,8,9\}\) with no clue being equal to~\(3\).
The puzzle was found by starting from a completed grid ({b}), then randomly choosing a digit to remove, by deleting all clues containing that digit, and then repeatedly attempting the puzzle with less and less digits. A digit that had been removed was noted only when the resulting puzzle still had a unique solution. The process was repeated with different puzzles and random deletion orders, with the puzzles then being saved and then used as starting points for a local search.
For the displayed puzzle, independent backtracking leads back to one unique completion. Therefore the example proves that the lower bound in Theorem 3.1 is feasible:
The example is also minimal with respect to its 20 clues: removing any one of the 20 clues leads to multiple solutions. However this does not mean that 20 is the global minimum for eight-digit puzzles.
5 Unavoidable sets
The proof of Theorem 3.1 is a generalized concept, where the two solutions \(G\) and \(G'\) are only different in a specific collection of cells. If a puzzle has no clue in that collection, the clues cannot distinguish the two grids as the digits could simply be swapped to achieve either solution.
Let \(G\) be a completed Sudoku grid. A set \(U\) of cells of \(G\) is labelled as unavoidable if a completed Sudoku grid \(G'\neq G\) that matches with \(G\) at every cell outside \(U\) exists.
Let \(P\) be a proper puzzle with solution \(G\). Then \(P\) contains a clue in all unavoidable sets of \(G\)
Let \(U\) be unavoidable, and let \(G'\neq G\) be a completed grid agreeing with \(G\) except for \(U\). Suppose that \(P\) has no clue in \(U\). Therefore another way of saying this would be that every clue of \(P\) lies outside \(U\), where \(G\) and \(G'\) agree. Meaning \(G'\) satisfies every clue of \(P\). Since \(G'\neq G\), the puzzle has at least two solutions, and is hence improper.
If we were to take \(a\) and \(b\), or any two digits. The 18 cells of \(G\) holding \(a\) or \(b\) form an unavoidable set, because swapping the two digits throughout the solution gives a different completed grid that still satisfies every clue. There are \(\binom{9}{2}=36\) such sets, one for each pair, and a proper puzzle must contain a clue in all of them.
Much smaller unavoidable sets exist, and those impose tighter requirements on a sparse puzzle.
Let \(G\) be a completed Sudoku containing four cells in distinct rows \(r_1\neq r_2\) and distinct columns \(c_1\neq c_2\) such that \[ G_{r_1c_1}=G_{r_2c_2}=v,\qquad G_{r_1c_2}=G_{r_2c_1}=w, \qquad v\neq w. \] If both \(c_1\) and \(c_2\) lie in the same vertical stack of three columns, or \(r_1\) and \(r_2\) lie in the same horizontal band of three rows, then those four cells form an unavoidable set.
By swapping \(v\) and \(w\) across these four cells while leaving everything else the same, the grid remains intact. Each of the two affected rows still contains exactly one \(v\) and one \(w\), and the same holds true for both of the affected columns.
Lets suppose that \(c_1\) and \(c_2\) lie in the same stack. Then for each row \(r \in \{r_1, r_2\}\), the two cells \((r,c_1)\) and \((r,c_2)\) belong to the same box. Together, these two cells contain exactly one \(v\) and one \(w\) both before and after the swap. As a result, the multi-set of entries within each box remains the same . If instead \(r_1\) and \(r_2\) lie in the same band, the exact same principles can be applied by reversing the roles of the rows and columns. In either scenario, no box gains or loses a digit.
Consequently, the modified array leaves a valid, completed Sudoku grid that is distinct from \(G\). This proves that these four cells constitute an unavoidable set. It is important to keep in mind however, that if neither hypothesis holds, the four cells will be scattered across four distinct boxes. The swap would then alter the contents of each individual box, meaning these conditions cannot simply be dropped.
For the solution in Figure 1, one such set occurs in rows 2 and 3 and columns 2 and 7: \[ G_{2,2}=1,\quad G_{2,7}=5,\quad G_{3,2}=5,\quad G_{3,7}=1. \] Rows 2 and 3 lie in the same band, so by swapping these four entries it gives another valid grid. Consequently, every proper puzzle with this solution must contain at least one clue in these four cells. Its found as the \(5\) in row 2, column 7. This illustrates why small unavoidable sets are useful, as it is much harder for a sparse collection of clues to hit every four-cell set compared to hitting large 18-cell sets by coincidence.
6 Larger Sudoku grids
The relabelling argument does not depend on the \(9\times9\) size. For a general \(n^2\times n^2\) Sudoku using \(n^2\) symbols, the same proof gives:
The clues of a proper \(n^2\times n^2\) Sudoku contain at least \(n^2-1\) distinct symbols.
If two symbols \(a\) and \(b\) were both removed from the clues, its possible to swap them throughout the solution. The relabelled grid is again a valid completed Sudoku, yet with every clue remaining the same. The resulting grid is different, so the puzzle would have two distinct solutions. Therefore at most one symbol can be omit whilst also preserving a proper puzzle.
The bound is attained for ordinary Sudoku by Figure 1. Whether it is tight for every \(n\) is not established here.
7 From unavoidable sets to hitting sets
Theorem 5.2 can be flipped around. With a completed grid \(G\), a proper puzzle with solution \(G\) must have clues that meet with every unavoidable set of \(G\). In combinatorics a set meeting every member of a family is called a hitting set, so to construct new puzzles it would be simplest to find the smallest hitting set of all unavoidable sets of \(G\) which would result in your clues.
However, a hitting set can fail to give a uniquely solvable puzzle, so the final uniqueness check must be done separately. Though, every proper puzzle is a hitting set, so unavoidable sets eliminate large numbers of possible puzzle candidates. This is what made the minimum-clue problem workable as puzzles with 17 clues were known for years [Royle], but no proper 16-clue puzzle could be found. McGuire, Tugemann and Civario proved that 16 clues are impossible by exhaustive hitting-set computation [MTC14], establishing that 17 is the true minimum.
8 A computational search for eight-digit puzzles
Define \[ m_8=\min\{\text{number of clues in a proper Sudoku whose clues use exactly eight digits}\}. \] Since every proper Sudoku has at least 17 clues, \(m_8\geq17\), and Figure 1 gives \(m_8\leq20\), so
The search ran in two stages, summarised in Figure 5: the first produces puzzles from which no single clue can be removed, and the second repeatedly removes and repairs clues to those found puzzles in an attempt to escape the local optima that the first stage might arrive into.
8.1 Stage 1: greedy random erasure
For each of 788 randomly generated completed grids, one digit was selected to be removed. All cells containing that digit were removed from the clue set. Further cells were then considered in a random order. A cell was only erased when the remaining puzzle still had a unique solution. The procedure was repeated 12 times independently for each starting grid, producing \(788\times12=9\,456\) minimal puzzles in total.
| Clues | Frequency | Relative | Cumulative |
|---|---|---|---|
| Total | 9456 |
The smallest result from Stage 1 had 21 clues, this reached in only 15 of the 9,456 runs. Once a clue is retained because deleting it would remove its uniqueness, the algorithm does not reconsider that decision, and it just moves on so you end up with a puzzle where every clue is necessary locally but the overall count is not minimal as its just the first good enough answer found.
Figure 4 visualises the greediness in a bar chart. A typical run stops four clues short of the best one, and the shape of the distribution shows that simply running Stage 1 more often would be an inefficient way to find smaller puzzles.
8.2 Stage 2: iterated local search
To escape local optima, the best Stage 1 puzzles were used as starting points for a second search. In each move, two or three clues were removed at random. Cells from the completed solution were then added back one at a time, while still never reintroducing the removed digit, until the puzzle became proper again. The erasure procedure was applied until it had no more clues than its predecessor then the result was accepted. Accepting moves of equal cost lets the search drift between puzzles of the same size instead of stopping at the first one it cannot further reduce.
Approximately 5,300 such moves were performed across three runs (seeds 77, 915 and 31337). All three reached 20 clues and found no example with fewer. The 20-clue puzzle is Figure 1.
The search establishes an upper bound only. Failing to find a 19-clue eight-digit puzzle is not evidence that none exists as the search examines a negligible fraction of the \(6.67\times10^{21}\) completed grids [FJ06] and local search can miss a global optimum. The true value of \(m_8\) remains open, with \(m_8\in\{17,18,19,20\}\).
9 Discussion
The main result of this paper is that the number of distinct symbols in a valid Sudoku puzzle cannot be reduced arbitrarily. If two symbols do not appear anywhere in the given clues, they can be swapped in the final solution without changing what information the clues provide. This allows the puzzle to be solved in multiple ways, which destroys the unique solution that makes it a proper puzzle in the first place.
This symmetry leads to unavoidable sets, providing a general method to study sparse Sudoku grids. Small unavoidable sets create strict rules about where clues must be placed, and these requirements can be framed as a hitting-set problem. The famous proof that 17 clues are necessary [MTC14] relies on this same fundamental idea, carried out through an exhaustive computer search.
The eight-digit problem remains open in this work. The search establishes a 20-clue upper bound, while the known general minimum provides a lower bound of 17. Determining the exact value of \(m_8\) would require an exhaustive hitting-set enumeration or a satisfiability (SAT) argument compared to the logical approach taken throughout the paper.
Acknowledgements
I would like to thank the people who read early versions of this paper and gave comments on its presentation and mathematical clarity. As well as the educators at Firrhill High School for being so open and welcoming, particularly to this research.
A Computational details and verification
The search was implemented in Python 3 using only the standard library. A grid is stored as a list of 81 integers in row-major order, with \(0\) denoting an empty cell. The solution counter keeps one 9-bit mask per row, column and box, and at each step branches on the empty cell with the fewest candidates (minimum-remaining-values). It stops as soon as two solutions have been found, which is used as a uniqueness test. The Stage 1 seed was 2024 and each Stage 2 run used independent seeds (77, 915 and 31337)
| Test | Result |
|---|
The Python scripts sudoku_core.py, sudoku_search.py and sudoku_verify.py are available from the author on request for personal exploration or futher verification of the data found. [mokshnanwani1@gmail.com]
References
- FJ06 B. Felgenhauer and F. Jarvis, Mathematics of sudoku I, Mathematical Spectrum 39 (2006), 15–22.
- MTC14 G. McGuire, B. Tugemann and G. Civario, There is no 16-clue sudoku: solving the sudoku minimum number of clues problem via hitting set enumeration, Experimental Mathematics 23 (2014), 190–217.
- Royle G. Royle, Minimum sudoku, staffhome.ecm.uwa.edu.au/~00013890/sudokumin.php, last accessed on [1/09/26].