Minimum number of givens

Ordinary Sudokus (proper puzzles) have a unique solution. A minimal Sudoku is a Sudoku from which no clue can be removed leaving it a proper Sudoku. Different minimal Sudokus can have a different number of clues. This section discusses the minimum number of givens for proper puzzles.

Ordinary Sudoku

Many Sudokus have been found with 17 clues, although finding them is not a trivial task.^[2][3] A 2014 paper by Gary McGuire, Bastian Tugemann, and Gilles Civario proved that the minimum number of clues in any proper Sudoku is 17 through an exhaustive computer search based on hitting set enumeration.^[4]

Total number of minimal puzzles

The number of minimal Sudokus (Sudokus in which no clue can be deleted without losing uniqueness of the solution) is not precisely known. However, statistical techniques combined with a generator ('Unbiased Statistics of a CSP – A Controlled-Bias Generator'),^[6] show that there are approximately (with 0.065% relative error):

• 3.10 × 10³⁷ distinct minimal puzzles,
• 2.55 × 10²⁵ minimal puzzles that are not pseudo-equivalent (i.e. same arrangement where all instances of one digit is switched with another digit).

Mathematical context

The general problem of solving Sudoku puzzles on n²×n² grids of n×n blocks is known to be NP-complete.^[8]

A puzzle can be expressed as a graph coloring problem.^[9] The aim is to construct a 9-coloring of a particular graph, given a partial 9-coloring. The Sudoku graph has 81 vertices, one vertex for each cell. The vertices are labeled with ordered pairs (x, y), where x and y are integers between 1 and 9. In this case, two distinct vertices labeled by (x, y) and (x′, y′) are joined by an edge if and only if:

• x = x′ (same column) or,
• y = y′ (same row) or,
• ⌈ x/3 ⌉ = ⌈ x′/3 ⌉ and ⌈ y/3 ⌉ = ⌈ y′/3 ⌉ (same 3×3 cell)

The puzzle is then completed by assigning an integer between 1 and 9 to each vertex, in such a way that vertices that are joined by an edge do not have the same integer assigned to them.

A Sudoku solution grid is also a Latin square.^[9] There are significantly fewer Sudoku grids than Latin squares because Sudoku imposes additional regional constraints.

Sudokus from group tables

As in the case of Latin squares the (addition- or) multiplication tables (Cayley tables) of finite groups can be used to construct Sudokus and related tables of numbers. Namely, one has to take subgroups and quotient groups into account:

Take for example ${\displaystyle \mathbb {Z} _{n}\oplus \mathbb {Z} _{n}}$ the group of pairs, adding each component separately modulo some ${\displaystyle n}$. By omitting one of the components, we suddenly find ourselves in ${\displaystyle \mathbb {Z} _{n}}$ (and this mapping is obviously compatible with the respective additions, i.e. it is a group homomorphism). One also says that the latter is a quotient group of the former, because some once different elements become equal in the new group. However, it is also a subgroup, because we can simply fill the missing component with ${\displaystyle 0}$ to get back to ${\displaystyle \mathbb {Z} _{n}\oplus \mathbb {Z} _{n}}$.

Under this view, we write down the example, Grid 1, for ${\displaystyle n=3}$.

Each Sudoku region looks the same on the second component (namely like the subgroup ${\displaystyle \mathbb {Z} _{3}}$), because these are added regardless of the first one. On the other hand, the first components are equal in each block, and if we imagine each block as one cell, these first components show the same pattern (namely the quotient group ${\displaystyle \mathbb {Z} _{3}}$). As outlined in the article of Latin squares, this is a Latin square of order ${\displaystyle 9}$.

Now, to yield a Sudoku, let us permute the rows (or equivalently the columns) in such a way, that each block is redistributed exactly once into each block – for example order them ${\displaystyle 1,4,7,2,5,8,3,6,9}$. This of course preserves the Latin square property. Furthermore, in each block the lines have distinct first component by construction and each line in a block has distinct entries via the second component, because the blocks' second components originally formed a Latin square of order ${\displaystyle 3}$ (from the subgroup ${\displaystyle \mathbb {Z} _{3}}$). Thus we arrive at a Sudoku (rename the pairs to numbers 1...9 if you wish). With the example and the row permutation above, we arrive at Grid 2.

Grid 1 – The addition table in ${\displaystyle \mathbb {Z} _{3}\oplus \mathbb {Z} _{3}}$ (0,0) (0,1) (0,2) (0,1) (0,2) (0,0) (0,2) (0,0) (0,1) (1,0) (1,1) (1,2) (1,1) (1,2) (1,0) (1,2) (1,0) (1,1) (2,0) (2,1) (2,2) (2,1) (2,2) (2,0) (2,2) (2,0) (2,1) (1,0) (1,1) (1,2) (1,1) (1,2) (1,0) (1,2) (1,0) (1,1) (2,0) (2,1) (2,2) (2,1) (2,2) (2,0) (2,2) (2,0) (2,1) (0,0) (0,1) (0,2) (0,1) (0,2) (0,0) (0,2) (0,0) (0,1) (2,0) (2,1) (2,2) (2,1) (2,2) (2,0) (2,2) (2,0) (2,1) (0,0) (0,1) (0,2) (0,1) (0,2) (0,0) (0,2) (0,0) (0,1) (1,0) (1,1) (1,2) (1,1) (1,2) (1,0) (1,2) (1,0) (1,1)

Grid 2 – Generating a Sudoku (0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2) (0,0) (0,1) (0,2) (2,0) (2,1) (2,2) (0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (0,1) (0,2) (0,0) (1,1) (1,2) (1,0) (2,1) (2,2) (2,0) (1,1) (1,2) (1,0) (2,1) (2,2) (2,0) (0,1) (0,2) (0,0) (2,1) (2,2) (2,0) (0,1) (0,2) (0,0) (1,1) (1,2) (1,0) (0,2) (0,0) (0,1) (1,2) (1,0) (1,1) (2,2) (2,0) (2,1) (1,2) (1,0) (1,1) (2,2) (2,0) (2,1) (0,2) (0,0) (0,1) (2,2) (2,0) (2,1) (0,2) (0,0) (0,1) (1,2) (1,0) (1,1)

For this method to work, one generally does not need a product of two equally-sized groups. A so-called short exact sequence of finite groups of appropriate size already does the job. Try for example the group ${\displaystyle \mathbb {Z} _{4}}$ with quotient- and subgroup ${\displaystyle \mathbb {Z} _{2}}$. It seems clear (already from enumeration arguments), that not all Sudokus can be generated this way.

Ordinary Sudoku