Jump to content

Mathematics of Sudoku

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by PatmaxDaddy (talk | contribs) at 13:17, 26 June 2022 (12x12 (4x3) exact count now verified, with link to source code). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

A 24-clue automorphic sudoku with translational symmetry.
A 24-clue automorphic Sudoku with translational symmetry

Sudoku puzzles can be studied mathematically to answer questions such as "How many filled Sudoku grids are there?", "What is the minimal number of clues in a valid puzzle?" and "In what ways can Sudoku grids be symmetric?" through the use of combinatorics and group theory.

The main results are that for the classical Sudoku the number of filled grids is 6,670,903,752,021,072,936,960 (6.67×1021), which reduces to 5,472,730,538 essentially different groups under the validity preserving transformations. There are 26 types of symmetry, but they can only be found in about 0.005% of all filled grids. 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. The largest minimal puzzle found so far has 40 clues.

Similar results are known for variants and smaller grids. No exact results are known for Sudokus larger than the classical 9×9 grid, although there are estimates which are believed to be fairly accurate.

Overview

The analysis of Sudoku falls into two main areas:

  1. analyzing the properties of completed grids
  2. analyzing the properties of completed puzzles.

Initial analysis was largely focused on enumerating solutions, with results first appearing in 2004.[1]

There are many Sudoku variants, partially characterized by size (N), and the shape of their regions. Unless noted, discussion in this article assumes classic Sudoku, i.e. N=9 (a 9×9 grid and 3×3 regions). A rectangular Sudoku uses rectangular regions of row-column dimension R×C. Other variants include those with irregularly-shaped regions or with additional constraints (hypercube) or different constraint types (Samunamupure).

Regions are also called blocks or boxes. A band is a part of the grid that encapsulates 3 rows and 3 boxes, and a stack is a part of the grid that encapsulates 3 columns and 3 boxes. A puzzle is a partially completed grid, and the initial values are givens or clues. A proper puzzle has a unique solution. A minimal puzzle is a proper puzzle from which no clue can be removed without introducing additional solutions. See Glossary of Sudoku for other terminology.[2]

Solving Sudokus from the viewpoint of a player has been explored in Denis Berthier's book "The Hidden Logic of Sudoku" (2007)[3] which considers strategies such as "hidden xy-chains".

Mathematical context

The general problem of solving Sudoku puzzles on n2×n2 grids of n×n blocks is known to be NP-complete.[4] For n=3 (classical Sudoku), however, this result is of little practical relevance: algorithms can solve puzzles in a fraction of a second because of the small size of the problem.[5]

A puzzle can be expressed as a graph coloring problem.[6] 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.[6] There are significantly fewer Sudoku grids than Latin squares because Sudoku imposes the additional regional constraint.

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 the group of pairs, adding each component separately modulo some . By omitting one of the components, we suddenly find ourselves in (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 to get back to .

Under this view, we write down the example, Grid 1, for .

Each Sudoku region looks the same on the second component (namely like the subgroup ), 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 ). As outlined in the article of Latin squares, this is a Latin square of order .

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 . 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 (from the subgroup ). 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
(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 with quotient- and subgroup . It seems clear (already from enumeration arguments), that not all Sudokus can be generated this way.

Variants

A Sudoku can be interpreted as a tiling (or cover) of a Latin square with polyominoes (the regions of the Sudoku). The classic 9×9 Sudoku is made of square nonominoes. It is possible to apply the rules of Sudoku to puzzles of other sizes, although only N2×N2 Sudoku puzzles can be tiled with square polyominoes.

See the Glossary of Sudoku for an expanded list of variants.

Rectangular regions

A popular variant is made of rectangular regions (blocks or boxes) – for example, 2×3 hexominoes tiled in a 6×6 grid. The following notation is used for discussing this variant:

  • R×C denotes a rectangular region with R rows and C columns.
  • The implied grid configuration has:
    • grid dimensions N×N, where N = R×C
    • N blocks (boxes) of size R×C, arranged in a C×R 'supergrid'
    • C bands of size R×N, consisting of R horizontally adjacent blocks
    • R stacks of size N×C, consisting of C vertically adjacent blocks

Sudoku with square N×N regions are more symmetrical than rectangular Sudoku since each row and column intersects N regions and shares N cells with each. The number of bands and stacks also equals N. The "3×3" Sudoku is additionally unique: N is also the number of row-column-region constraints from the One Rule (i.e. there are N=3 types of units).

Jigsaw sudokus

A Sudoku whose regions are not (necessarily) square or rectangular is known as a Jigsaw Sudoku. In particular, an N×N square where N is prime can only be tiled with irregular N-ominoes. For small values of N the number of ways to tile the square (excluding symmetries) has been computed (sequence A172477 in the OEIS).[7] For N ≥ 4 some of these tilings are not compatible with any Latin square; i.e. all Sudoku puzzles on such a tiling have no solution.[7]

Solutions

The answer to the question 'How many Sudoku grids are there?' depends on the definition of when similar solutions are considered different.

Ordinary Sudoku

All solutions

For the enumeration of all possible solutions, two solutions are considered distinct if any of their corresponding (81) cell values differ. Symmetry relations between similar solutions are ignored., e.g. the rotations of a solution are considered distinct. Symmetries play a significant role in the enumeration strategy, but not in the count of all possible solutions.

The first known solution to complete enumeration was posted by QSCGZ (Guenter Stertenbrink) to the rec.puzzles newsgroup in 2003,[8][9][10] obtaining 6,670,903,752,021,072,936,960 (6.67×1021) distinct solutions.

In a 2005 study, Felgenhauer and Jarvis[11][10] analyzed the permutations of the top band used in valid solutions. Once the Band1 symmetries and equivalence classes for the partial grid solutions were identified, the completions of the lower two bands were constructed and counted for each equivalence class. Summing completions over the equivalence classes, weighted by class size, gives the total number of solutions as 6,670,903,752,021,072,936,960, confirming the value obtained by QSCGZ. The value was subsequently confirmed numerous times independently. A second enumeration technique based on band generation was later developed that is significantly less computationally intensive. This subsequent technique resulted in roughly needing 1/97 of the number of computation cycles as the original techniques, but was significantly more complicated to set up.

Essentially different solutions

Validity preserving transformations

Two valid grids are essentially the same if one can be derived from the other, using a so-called validity preserving transformation (VPT). These transformations always transform a valid grid into another valid grid. There are two major types: symbol permutations (relabeling) and cell permutations (rearrangements). They are:

  • Relabeling symbols (9!)
    (Once all possible relabeling combinations are eliminated, except for one: for instance, keeping the top row fixed at [123456789], the number of fixed grids reduces to 18,383,222,420,692,992. This value is 6,670,903,752,021,072,936,960 divided by 9!)

and rearranging (shuffling):

  • Band permutations (3!)
  • Row permutations within a band (3!×3!×3!)
  • Stack permutations (3!)
  • Column permutations within a stack (3!×3!×3!)
  • Reflection, transposition and rotation (2)
    (Given a single transposition or quarter-turn rotation in conjunction with the above permutations, any combination of reflections, transpositions and rotations can be produced, so these operations only contribute a factor of 2)

These operations define a relation between equivalent grids. With respect to the 81 grid cell values, the rearranging operations form a subgroup of the symmetric group S81, of order 3!8×2 = 3,359,232. The relabeling operations are isomorphic with S9 and generate an additional 9! = 362,880 equivalent grids. Applying these operations on a grid results in 3!8×2×9! or 1,218,998,108,160 essentially equivalent grids. However, there is a small number of sudokus for which the above operations generate fewer grids; these are the self-similar, or automorphic sudokus. Only about 0.01% of all essentially unique grids are automorphic,[12] but counting them is necessary for evaluating the exact number of essentially different sudokus.

The sudoku symmetry group

The precise structure of the sudoku symmetry group can be expressed succinctly using the wreath product (≀). The possible row (or column) permutations form a group isomorphic to S3S3 of order 3!4 = 1,296.[13] The whole rearrangement group is formed by letting the transposition operation (isomorphic to C2) act on two copies of that group, one for the row permutations and one for the column permutations. This is S3S3C2, a group of order 1,2962 × 2 = 3,359,232. Finally, the relabelling operations commute with the rearrangement operations, so the full sudoku (VPT) group is (S3S3C2) × S9 of order 1,218,998,108,160.

Fixed points and Burnside's lemma

The set of equivalent grids which can be reached using these operations (excluding relabeling) forms an orbit of grids under the action of the rearrangement group. The number of essentially different solutions is then the number of orbits, which can be computed using Burnside's lemma. The Burnside fixed points are grids that either do not change under the rearrangement operation or only differ by relabeling. To simplify the calculation the elements of the rearrangement group are sorted into conjugacy classes, whose elements all have the same number of fixed points. It turns out only 27 of the 275 conjugacy classes of the rearrangement group have fixed points;[14] these conjugacy classes represent the different types of symmetry (self-similarity or automorphism) that can be found in completed sudoku grids. Using this technique, Ed Russell and Frazer Jarvis were the first to compute the number of essentially different sudoku solutions as 5,472,730,538.[14][15]

Conjugacy classes of the rearrangement group with fixed points ("automorphisms" and their prevalence)[14]
Name or composition[16]

A systematic description of the row and column permutations:

e: Do nothing s: Swap two rows/columns within a band/stack c: Cycle three rows/columns within a band/stack

S: Swap all rows/columns between two bands/stacks (r/c move in three 2-cycles) S4: Swap all rows/columns between two bands/stacks (r/c move in a 2-cycle and a 4-cycle) S6: Swap all rows/columns between two bands/stacks (r/c move in a 6-cycle)

C: Cycle all rows/columns through three bands/stacks (r/c move in three 3-cycles) C6: Cycle all rows/columns through three bands/stacks (r/c move in a 3-cycle and a 6-cycle) C9: Cycle all rows/columns through three bands/stacks (r/c move in a 9-cycle)

T: Transpose the grid (can be combined with a net permuation of either rows or columns)

and | separates the dimensions (row and column permutations or vice versa)

Class
Id.[14]
Class
size[14]
Cell cycles Order

[16]

Fixed cells

[16]

Number of fixed grids
(up to relabeling),

per element[14]

Number of fixed grids,

per element

Number of fixed grids
(up to relabeling),

whole class

Number of fixed grids,

whole class

Identity e 1 1 1 81 18,383,222,420,692,992 6,670,903,752,021,072,936,960 18,383,222,420,692,992 6,670,903,752,021,072,936,960
Mini Rows (MR) ccc 8 16 27×3 3 0 107,495,424 39,007,939,461,120 1,719,926,784 624,127,031,377,920
2 MR, 1 MD ccc | c 7 96 27×3 3 0 21,233,664 7,705,271,992,320 2,038,431,744 739,706,111,262,720
1 MR, 2 MD ccc | cc 9 192 27×3 3 0 4,204,224 1,525,628,805,120 807,211,008 292,920,730,583,040
Mini Diagonals (MD) ccc | ccc 10 64 27×3 3 0 2,508,084 910,133,521,920 160,517,376 58,248,545,402,880
Jumping Rows (JR) C 25 144 27×3 3 0 14,837,760 5,384,326,348,800 2,136,637,440 775,342,994,227,200
2 JR, 1 GR C | c 28 864 27×3 3 0 2,085,120 756,648,345,600 1,801,543,680 653,744,170,598,400
1 JR, 2 GR C | cc 30 1,728 27×3 3 0 294,912 107,017,666,560 509,607,936 184,926,527,815,680
Gliding Rows (GR) C | ccc 32 1,152 27×3 3 0 6,342,480 2,301,559,142,400 7,306,536,960 2,651,396,132,044,800
Full Rows (FR) C9 27 288 9×9 9 0 5,184 1,881,169,920 1,492,992 541,776,936,960
2 FR, 1 WR C9 | c 26 1,728 9×9 9 0 2,592 940,584,960 4,478,976 1,625,330,810,880
1 FR, 2 WR C9 | cc 29 3,456 9×9 9 0 1,296 470,292,480 4,478,976 1,625,330,810,880
Waving Rows (WR) C9 | ccc 31 2,304 9×9 9 0 648 235,146,240 1,492,992 541,776,936,960
Jumping Diagonals (JD) C | C 22 5,184 27×3 3 0 323,928 117,546,992,640 1,679,242,752 609,363,609,845,760
Broken Columns (BC) C | C9 24 20,736 9×9 9 0 288 104,509,440 5,971,968 2,167,107,747,840
Full Diagonals (FD) C9 | C9 23 20,736 9×9 9 0 162 58,786,560 3,359,232 1,218,998,108,160
Diagonal Mirror (DM) T 37 1,296 36×2 2 9 30,258,432 10,980,179,804,160 39,214,927,872 14,230,313,026,191,360
DM+MD T ccc 40 10,368 3×3, 12×6 6 0 1,854 672,779,520 19,222,272 6,975,378,063,360
DM+JD T C 43 93,312 3×3, 12×6 6 0 288 104,509,440 26,873,856 9,751,984,865,280
Quarter Turn (QT) T sS 86 69,984 20×4 4 1 13,056 4,737,761,280 913,711,104 331,567,485,419,520
Half Turn (HT) sS | sS 79 2,916 40×2 2 1 155,492,352 56,425,064,693,760 453,415,698,432 164,535,488,647,004,160
Column Sticks (CS) S | sss 134 972 36×2 2 9 449,445,888 163,094,923,837,440 436,861,403,136 158,528,265,969,991,680
CS+MC cS6 | sss 135 3,888 3×3, 12×6 6 0 27,648 10,032,906,240 107,495,424 39,007,939,461,120
CS+GR cS6 | C6 142 31,104 3×3, 12×6 6 0 6,480 2,351,462,400 201,553,920 73,139,886,489,600
CS+ JR/B2,GR/B13 S6 | C6 143 15,552 3×3, 12×6 6 0 1,728 627,056,640 26,873,856 9,751,984,865,280
CS+ GR/Band2,JR/B13 cS | C6 144 15,552 3×3, 12×6 6 0 3,456 1,254,113,280 53,747,712 19,503,969,730,560
CS+JR S | C6 145 7,776 3×3, 12×6 6 0 13,824 5,016,453,120 107,495,424 39,007,939,461,120
(non-trivial) 949,129,933,824 344,420,270,386,053,120
total 18,384,171,550,626,816 6,671,248,172,291,458,990,080

Note that a grid may be a fixed point of several transformations simultaneously; for example, any grid which has a quarter-turn symmetry also has half-turn symmetry. The combination of all transformations that fix a particular grid is the stabilizer subgroup ("automorphism group") of that grid.

Stabilizer subgroups

Russell has compiled a list of 122 "essentially different" non-trivial stabilizer subgroup conjugacy classes ("automorphism groups"),[17][18] along with an example grid, the VPT conjugacy classes in the group, a set of generators and the number of essentially different grids (orbits) with that stabilizer class. Up to isomorphism there are 26 different group structures.[19] There are 15 different possible stabilizer group sizes, listed in the next section.

Number of essentially equivalent grids

Each of the essentially unique grids can be analyzed[12] for self-similarities ("automorphisms") to evaluate the 'deficiency' in the number of essentially equivalent grids. The results are summarized in the table below. In total 560,151 of the 5,472,730,538 essentially unique grids (about 1/10,000) have a form of self-similarity (a non-trivial stabilizer).

The size of the orbit (that is, number of essentially equivalent grids) can be calculated using the orbit-stabilizer theorem: it is the size of the sudoku symmetry group divided by the size of the stabilizer (or "automorphism") group. Multipling the number of essentially unique grids (the number of orbits) with the orbit size gives the total number of grids with that stabilizer group size; summation then once again provides the total number of possible sudoku grids. "Automorphic" grids have smaller orbits so the probability that a random grid has a symmetry drops: from about 1 in 10,000 for essentially different grids to about 1 in 20,000 for all grids.

Number of sudoku grids by stabilizer group size[12]
Size of
stabilizer
group
No. of essentially
unique grids
(number of orbits)
Equivalent grids
(orbit size),
ignoring relabeling
Number of grids,
ignoring relabeling
Equivalent grids (orbit size),
including relabeling
Total number of grids
1 5,472,170,387 3,359,232 18,382,289,873,462,784 1,218,998,108,160 6,670,565,349,282,175,057,920
2 548,449 1,679,616 921,183,715,584 609,499,054,080 334,279,146,711,121,920
3 7,336 1,119,744 8,214,441,984 406,332,702,720 2,980,856,707,153,920
4 2,826 839,808 2,373,297,408 304,749,527,040 861,222,163,415,040
6 1,257 559,872 703,759,104 203,166,351,360 255,380,103,659,520
8 29 419,904 12,177,216 152,374,763,520 4,418,868,142,080
9 42 373,248 15,676,416 135,444,234,240 5,688,657,838,080
12 92 279,936 25,754,112 101,583,175,680 9,345,652,162,560
18 85 186,624 15,863,040 67,722,117,120 5,756,379,955,200
27 2 124,416 248,832 45,148,078,080 90,296,156,160
36 15 93,312 1,399,680 33,861,058,560 507,915,878,400
54 11 62,208 684,288 22,574,039,040 248,314,429,440
72 2 46,656 93,312 16,930,529,280 33,861,058,560
108 3 31,104 93,312 11,287,019,520 33,861,058,560
162 1 20,736 20,736 7,524,679,680 7,524,679,680
648 1 5,184 5,184 1,881,169,920 1,881,169,920
>1 560,151 932,547,230,208 338,402,738,897,879,040
5,472,730,538 18,383,222,420,692,992 6,670,903,752,021,072,936,960

Other variants

Enumeration results for many Sudoku variants have been calculated: these are summarised below.

Sudoku with additional constraints

The following are all restrictions of the classic 3×3 Sudoku (9×9 grid). The type names have not been standardised: click on the attribution links to see the definitions.

Type Number of grids Attribution Verified?
Quasi-Magic Sudoku 248,832 Jones, Perkins and Roach[20] Yes[citation needed]
Magic Sudoku 5,971,968 Stertenbrink[21] Yes[citation needed]
Hypercube 37,739,520 Stertenbrink[22] Yes[citation needed]
3doku 104,015,259,648 Stertenbrink[23] Yes[citation needed]
NRC Sudoku 6,337,174,388,428,800 Brouwer[24] Yes[citation needed]
Sudoku X 55,613,393,399,531,520 Russell[25] Yes[citation needed]
Disjoint Groups 201,105,135,151,764,480 Russell[26] Yes[citation needed]

Sudoku with rectangular regions

In the table, block dimensions are those of the regions (e.g. 3×3 in normal Sudoku). The "Rel Err" column indicates how a simple approximation[27] based on calculated band counts (detailed in the sections below) compares to the true grid count: it is an underestimate in all cases evaluated so far. The numbers for square block grids (n2 × n2) are listed in (sequence A107739 in the OEIS), and the numbers for 2 × n blocks (2n × 2n grids) are listed in (sequence A291187 in the OEIS).

Similar to Latin squares, the number of sudoku grids can be reduced by noting that there is a one-to-one correspondence with a partially standardized form, in which the first block has the canonical labels and both the top row and leftmost column are sorted (for as much as the rules allow, i.e. within blocks and the stacks/bands themselves). For a grid with blocks, each such reduced grid corresponds to total grids,[28][29] which is 9! × 722 or 1,881,169,920 for the normal 3×3 Sudoku. This reduction is always one-to-one, unlike the action of the full set of validity preserving transformations ('Sudoku symmetries') discussed below.

Dimensions Number of full grids Est. error

(see below)

Fraction of

Latin squares

Grid Blocks Exact Magnitude Attribution Verified?
4×4 2×2 288 2.8800×102 various[30] Yes −11.1% 5.0×10−1
6×6 2×3 28,200,960 2.8201×107 Pettersen[31] Yes[32] −5.88% 3.5×10−2
8×8 2×4 29,136,487,207,403,520 2.9136×1016 Russell[32] Yes[33] −1.91% 2.7×10−4
9×9 3×3 6,670,903,752,021,072,936,960 6.6709×1021 Stertenbrink[8] Yes[10] −0.207% 1.2×10−6
10×10 2×5 1,903,816,047,972,624,930,994,913,280,000 1.9038×1030 Pettersen[34] Yes[35] −0.375% 1.9×10−7
12×12 3×4 81,171,437,193,104,932,746,936,103,027,318,645,818,654,720,000 8.1171×1046 Pettersen/Silver[36] Yes[37] −0.132%[36] unknown
12×12 2×6 38,296,278,920,738,107,863,746,324,732,012,492,486,187,417,600,000 3.8296×1049 Pettersen[38] No −0.238%[38] unknown
15×15 3×5 unknown est. 3.5086×1084 Silver[39] No n/a unknown
16×16 4×4 unknown est. 5.9584×1098 Silver[40] No n/a unknown
20×20 4×5 unknown est. 3.1764×10175 Silver[41] No n/a unknown
25×25 5×5 unknown est. 4.3648×10308 Silver/Pettersen[42] No n/a unknown

A solved Sudoku will remain valid under the actions of the validity preserving transformations (see also Jarvis[14]). By carefully counting the number of invariant grids for each transformation one can compute the number of essentially different Sudoku grids (see above). Similar methods have been applied to sudoku grids of other dimensions; the results are summarized in the table below. For square block grids (sequence A109741 in the OEIS) the transposition transformation may or may not (see below) be included in the VPT (symmetry) group. The number of essentially different grids can be estimated by dividing the total number of grids (either known or estimated) by the size of the VPT group (which is easily computed), which essentially assumes the number of automorphic sudokus is negligible. The numbers for 2 × n blocks (2n × 2n grids) are listed in (sequence A291188 in the OEIS).

Dimensions VPT group Number of essentially different grids Reference
Grid Blocks Transposition included Size Conj. classes

(w/o relabelling)

4×4 2×2 yes 128 × 4! 2 [43][44]
no 64 × 4! 3
6×6 2×3 no 3,456 × 6! 90 49 Jarvis/Russell,[45] Pettersen[43]
8×8 2×4 no 4,423,368 × 8! 400 1,673,187 Russell,[46] Pettersen[43]
9×9 3×3 yes 3,359,232 × 9! 275 5,472,730,538 Jarvis/Russell,[14] Pettersen[47][43]
no 1,679,616 × 9! 484 10,945,437,157
10×10 2×5 no 110,592,000 × 10! 1260 4,743,933,602,050,718 Pettersen/Russell[48][49]
16×16 4×4 yes (4!)10 × 2 × 16! est. 2.2458×1071 (estimation explained in text)[50]
no (4!)10 × 16! est. 4.4916×1071
Estimation method

The method of Kevin Kilfoil[51] (generalised by Pettersen[27]) can be used to estimate the number of completed grids using the number of possible completed bands and stacks. The method asserts that the Sudoku row and column constraints are, to first approximation, conditionally independent given the box constraint. This gives the Kilfoil-Silver-Pettersen formula:[27]

where is the number of ways of filling a R×RC band of R horizontally adjacent R×C boxes (equivalently, is the number of ways of filling a RC×C stack of C vertically adjacent R×C boxes), and the denominator (RC)!RC is the number of ways to fill the grid while satisfying only the box contraints.

As explained by Pettersen: "This is how: Let X be the space of -grids built by legal sudoku bands, but with no attention put on whether the columns follow the rules of Sudoku. The size of X is . Let also Y be the set of grids built by legal stacks with no attention put on the rows, #Y is then . The nxm-sudoku grids are then the intersection of X and Y. A random and are identical in a given box with probability , and under the assumption that these probabilities are independent for each box, we arrive at the estimate above."[27]

This estimation has proven to be accurate to about 0.2% for the classical 9×9 grid, and within 1% for larger grids for which exact values are known (see table above).

Number of bands

Exact formulae for the number of possible bands in a filled sudoku grid with blocks of size R×C are known:

Dimensions Number of bands Attribution Verified?
Band Blocks
2×2C C (obvious result) Yes[citation needed]
3×3C C

where the summation is known as the Cth Franel number (sequence A000172 in the OEIS)
Pettersen[31] Yes[citation needed]
4×4C C

where:

the outer summand is taken over all a,b,c such that 0≤a,b,c and a+b+c=2C.
the inner summand is taken over all k12,k13,k14,k23,k24,k34 ≥ 0 such that
k12,k34a    and
k13,k24b    and
k14,k23c    and
k12+k13+k14 = ak12+k23+k24 = bk13+ck23+k34 = ck14+bk24+ak34 = C

The outer summation corresponds to a split of the band into two "subbands" of 2 boxes each; the numbers a, b and c describe the split and must match for both subbands, so the summand can be squared.

The split variables are described as: "a is the number of symbols in row 1 and 2 in the first boxes (that is, symbols that are either in row 1 in box 1 and row 2 in box 2 OR in row 1 in box 2 and row 2 in box 1). It will then also be the number of symbols in row 3 and 4 in the first two boxes, as well as the number of symbols in row 1 and 2 in the two last boxes, and the number of symbols in row 3 and 4 in the first two boxes. b is the number of symbols in row 1 and 3 in the first two boxes, together with other combinations as for the variable a. c is the number of symbols in row 1 and 4 in the first two boxes."[52]

The inner summation counts the number of subbands for a given a,b,c specification: "Among the a symbols that lie in row 1 and 2 in box 1 and 2, k12 counts how many of them that lie in row 1 in box 1 (and thus also in row 2 in box 2). In general, for i<j, among the symbols on row i and j in the first two boxes, kij tells how many of them that are in row i in box 1 and row j in box 2."[52]

Pettersen[53] Yes[54]

Several known band counts are listed below. Petersen's algorithm,[55] as implemented and improved by Silver,[56] splits the band into subbands, which are then grouped into equivalence classes; it is currently the fastest known technique for exact evaluation of these bR,C.

Dimensions Number of bands Attribution Verified?
Band Blocks
3×6 3×2 6! × 2!6 × 10 = 460800 Pettersen (formula)
3×9 3×3 9! × 3!6 × 56 = 9! × 2612736 = 948109639680 ≈ 9.4811×1011 (44 equivalence classes[11][57]) Various[11][31]
3×12 3×4 12! × 4!6 × 346 = 31672366418991513600 ≈ 3.1672×1019 Stertenbrink[citation needed] Yes[58]
3×15 3×5 15! × 5!6 × 2252 ≈ 8.7934×1027 Pettersen (formula)[39]
(larger 3×C values can easily be computed using the formula given above)
4×8 4×2 8! × 2!12 × 5016 = 828396011520 ≈ 8.2840×1011 [citation needed]
4×12 4×3 12! × 3!12 × 2180544 = 2273614462643364849254400 ≈ 2.2736×1024 Pettersen[31] Yes[58]
4×16 4×4 16! × 4!12 × 1273431960 ≈ 9.7304×1038 Silver[40][59] Yes[citation needed]
4×20 4×5 20! × 5!12 × 879491145024 ≈ 1.9078×1055 Russell[59] Yes[citation needed]
4×24 4×6 24! × 6!12 × 677542845061056 ≈ 8.1589×1072 Russell[59] Yes[citation needed]
4×28 4×7 28! × 7!12 × 563690747238465024 ≈ 4.6169×1091 Russell[59] Yes[citation needed]
(calculations up to 4×100 have been performed by Silver,[60] but are not listed here)
5×10 5×2 10! × 2!20 × 364867776 ≈ 1.3883×1021 (355 equivalence classes[34]) [citation needed] No
5×15 5×3 15! × 3!20 × 324408987992064 ≈ 1.5510×1042 Silver[41] Yessame author, different method
5×20 5×4 20! × 4!20 × 518910423730214314176 ≈ 5.0751×1066 Silver[41] Yessame author, different method
5×25 5×5 25! × 5!20 × 1165037550432885119709241344 ≈ 6.9280×1093 Pettersen / Silver[42] No
5×30 5×6 30! × 6!20 × 3261734691836217181002772823310336 ≈ 1.2127×10123 Pettersen / Silver[42] No
5×35 5×7 35! × 7!20 × 10664509989209199533282539525535793414144 ≈ 1.2325×10154 Pettersen / Silver[61] No
5×40 5×8 40! × 8!20 × 39119312409010825966116046645368393936122855616 ≈ 4.1157×10186 Pettersen / Silver[56] No
5×45 5×9 45! × 9!20 × 156805448016006165940259131378329076911634037242834944 ≈ 2.9406×10220 Pettersen / Silver[citation needed] No
5×50 5×10 50! × 10!20 × 674431748701227492664421138490224315931126734765581948747776 ≈ 3.2157×10255 Pettersen / Silver[citation needed] No
 
6×12 6×2 12! × 2!30 × 9480675056071680 = 4876139207527966044188061990912000 ≈ 4.8761×1033 Pettersen[62] No

Puzzles

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

A Sudoku with 17 clues.
A Sudoku with 17 clues and diagonal symmetry.[63]
A Sudoku with 18 clues and orthogonal symmetry.[64]
An automorphic Sudoku with 24 clues and complete geometric symmetry.[65]
A Sudoku with 19 clues and two-way orthogonal symmetry.[66]

Many Sudokus have been found with 17 clues, although finding them is not a trivial task.[67][68] A paper by Gary McGuire, Bastian Tugemann, and Gilles Civario, released on 1 January 2012, explains how it was proved through an exhaustive computer search that the minimum number of clues in any proper Sudoku is 17,[69][70][13] and this was independently confirmed in September 2013.[71] A few 17-clue puzzles with diagonal symmetry were provided by Ed Russell, after a search through equivalence transformations of Gordon Royle's database of 17-clue puzzles.[72][63] Sudoku puzzles with 18 clues have been found with 180° rotational symmetry, and others with orthogonal symmetry, although it is not known if this number of clues is minimal in either case.[64] Sudoku puzzles with 19 clues have been found with two-way orthogonal symmetry, and again it is unknown if this number of clues is minimal for this case.[66]

A Sudoku with 24 clues, dihedral symmetry (symmetry on both orthogonal axis, 90° rotational symmetry, 180° rotational symmetry, and diagonal symmetry) is known to exist, and is also automorphic. Again here, it is not known if this number of clues is minimal for this class of Sudoku.[65][73] The fewest clues in a Sudoku with two-way diagonal symmetry is believed to be 18, and in at least one case such a Sudoku also exhibits automorphism.

Among the 5,472,730,538 essentially different solution grids, only 4 don't have a 20 clue puzzle - those 4 grids do have a 21-clue puzzle.[74]

Sudokus of other sizes

  • 4×4(2×2) Sudoku: The fewest clues in any 4×4 Sudoku is 4, of which there are 13 non-equivalent puzzles. (The total number of non-equivalent minimal Sudokus of this size is 36.[75])
  • 6×6(2×3) Sudoku: The fewest clues is 8.[76]
  • 8×8(2×4) Sudoku: The fewest clues is 14.[76]
  • 10×10(2×5) Sudoku: At least one puzzle with 22 clues has been created.[77] It is not known if this is the fewest possible.
  • 12×12(2×6) Sudoku: At least one puzzle with 32 clues has been created.[77] It is not known if this is the fewest possible.
  • 12×12(3×4) Sudoku: At least one puzzle with 30 clues has been created.[77] It is not known if this is the fewest possible.
  • 15×15(3×5) Sudoku: At least one puzzle with 48 clues has been created.[77] It is not known if this is the fewest possible.
  • 16×16(4×4) Sudoku: At least one puzzle with 55 clues has been created.[77] It is not known if this is the fewest possible.
  • 25×25(5×5) Sudoku: A puzzle with 151 clues has been created.[78][citation needed] It is not known if this is the fewest possible.

Sudoku with additional constraints

Disjoint Groups: 11 clues

Additional constraints (here, on 9×9 Sudokus) lead to a smaller minimum number of clues.

  • Disjoint Groups: some 12-clue puzzles[79] have been demonstrated by Glenn Fowler. Later, 11-clue puzzles were also found. It is not known if this is the best possible.
  • Hypercube: various 8-clue puzzles[80] have been demonstrated by Guenter Stertenbrink. This is the best possible.
  • Magic Sudoku: a 7-clue example[81] has been provided by Guenter Stertenbrink. It is not known if this is the best possible.
  • Anti-Knight Sudoku: exactly 4 essentially different 8-clue puzzles exist and have been generated by David Clamage et al.[82] These are the best possible.
  • Sudoku X: a list of 552952 12-clue puzzles[83] has been collected. It is not known if this is the best possible.
  • NRC Sudoku: an 11-clue example[24] has been provided by Andries Brouwer. It is not known if this is the best possible.
  • 2-Quasi-Magic Sudoku: a 4-clue example[84] has been provided by Tony Forbes. It is suspected that this is the best possible.
By combining multiple constraints, it is possible to create a valid 2-clue sudoku.[85]

Sudoku with irregular regions

"Du-sum-oh"[86] (a.k.a. "geometry number place") puzzles replace the 3×3 (or R×C) regions of Sudoku with irregular shapes of a fixed size. Bob Harris has proved[87] that it is always possible to create (N − 1)-clue du-sum-ohs on an N×N grid, and has constructed several examples. Johan de Ruiter has proved[88] that for any N>3 there exist polyomino tilings that can not be turned into a Sudoku puzzle with N irregular shapes of size N.

Sum number place ("Killer Sudoku")

In sum number place (Samunampure), the usual constraints of no repeated value in any row, column or region apply; additionally, extra regions ("cages") of various size and shape which cannot contain repeats are present, with clues providing the sum of digits within the cage (e.g. a 4-cell cage with sum 10 must consist of values 1,2,3,4 in some order). The minimal cell coverage known is 18 cells[89] provided by Philip Newman, and this is conjectured to be the fewest possible (a 17-cell example would imply a currently unknown 17-clue classic sudoku). The minimum number of cages known is 7,[90] also provided by Philip Newman; it is not known if this is the fewest possible.

A variant on Miyuki Misawa's web site[91] replaces sums with relations: the clues are symbols =, < and > showing the relative values of (some but not all) adjacent region sums. She demonstrates an example with only eight relations. It is not known whether this is the best possible.

Maximum number of givens

A minimal Sudoku with 40 clues.[92]

The most clues for a minimal Sudoku is believed to be 40, of which only two are known. If any clue is removed from either of these Sudokus, the puzzle would have more than one solution (and thus not be a proper Sudoku). In the work to find these Sudokus, other high-clue puzzles were catalogued, including more than 6,500,000,000 minimal puzzles with 36 clues. About 2600 minimal Sudokus with 39 clues were also found.[92]

If dropping the requirement for the uniqueness of the solution, 41-clue minimal pseudo-puzzles are known to exist, but they can be completed to more than one solution grid. Removal of any clue increases the number of the completions and from this perspective none of the 41 clues is redundant. With slightly more than half the grid filled with givens (41 of 81 cells), the uniqueness of the solution constraint still dominates over the minimality constraint.[93]

As for the most clues possible in a Sudoku while still not rendering a unique solution, it is four short of a full grid (77). If two instances of two numbers each are missing and the cells they are to occupy are the corners of an orthogonal rectangle, and exactly two of these cells are within one region, there are two ways the last digits can be added (two solutions).

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'),[94] show that there are approximately (with 0.065% relative error):

  • 3.10 × 1037 minimal puzzles,
  • 2.55 × 1025 non-essentially-equivalent minimal puzzles.

Other authors used faster methods and calculated additional precise distribution statistics.[95]

Constraints of clue geometry

A range of clue positions insufficient for a proper Sudoku.
Sudoku with a 30 cell (5 x 6) empty rectangle. (22 clues)
Sudoku with nine empty groups. (22 clues)

It has been conjectured that no proper Sudoku can have clues limited to the range of positions in the clear space of the first image above.[96] The largest rectangular orthogonal "hole" (region with no clues) in a proper Sudoku is believed to be a rectangle of 30 cells (a 5×6 rectangular area).[97][98] One example is a Sudoku with 22 clues (second image). The largest total number of empty groups (rows, columns, and boxes) in a Sudoku is believed to be nine. One example is a Sudoku with 3 empty rows, 3 empty columns, and 3 empty boxes (third image).[99][100]

Automorphic Sudokus

A Sudoku grid is automorphic if it can be transformed in a way that leads back to the original grid, when that same transformation would not otherwise lead back to the original grid. One example of a grid which is automorphic would be a grid which can be rotated 180 degrees resulting in a new grid where the new cell values are a permutation of the original grid. Automorphic Sudokus are Sudoku puzzles which solve to an automorphic grid. Two examples of automorphic Sudokus, and an automorphic grid are shown below.

An automorphic Sudoku with 18 clues (two-way diagonal symmetry)[101]
An automorphic Sudoku with 24 clues (two-way diagonal symmetry, and translational symmetry)[102]
The "Most Canonical" solution grid (648 automorphisms)
Number of essentially different grids at each
automorphism count
Auto-
morphisms
No. grids Auto-
morphisms
No.
grids
1 5472170387 18 85
2 548449 27 2
3 7336 36 15
4 2826 54 11
6 1257 72 2
8 29 108 3
9 42 162 1
12 92 648 1

In the first two examples, notice that if the Sudoku is rotated 180 degrees, and the clues relabeled with the permutation (123456789) -> (987654321), it returns to the same Sudoku. Expressed another way, these Sudokus have the property that every 180-degree rotational pair of clues (a, b) follows the rule (a) + (b) = 10.

Since these Sudokus are automorphic, so too their solutions grids are automorphic. Furthermore, every cell which is solved has a symmetrical partner which is solved with the same technique (and the pair would take the form a + b = 10). Notice that in the second example, the Sudoku also exhibits translational (or repetition) symmetry; clues are clustered in groups, with the clues in each group ordered sequentially (i.e., n, n+1, n+2, and n+3).

The third image is the Most Canonical solution grid.[103] This grid has 648 automorphisms and contributes to all ~6.67×1021 solution grids by factor of 1/648 compared to any non-automorphic grid.

In these examples the automorphisms are easy to identify, but in general automorphism is not always obvious. The table at right shows the number of the essentially different Sudoku solution grids for all existing automorphisms.[12]

Details of enumerating distinct grids (9×9)

An enumeration technique based on band generation was developed that is significantly less computationally intensive. The strategy begins by analyzing the permutations of the top band used in valid solutions. Once the Band1 symmetries and equivalence class for the partial solutions are identified, the completions of the lower two bands are constructed and counted for each equivalence class.

Counting the top band permutations

1 2 3
4 5 6
7 8 9

The Band1 algorithm proceeds as follows:

  • Choose a canonical labeling of the digits by assigning values for B1 (see grid), and compute the rest of the Band1 permutations relative B1.
  • Compute the permutations of B2 by partitioning the B1 cell values over the B2 row triplets. From the triplet combinations compute the B2 permutations. There are k=0..3 ways to choose the:
B1 r11 values for B2 r22, the rest must go to r16,
B1 r12 values for B2 r23, the rest must go to r16,
B1 r13 values for B2 r21, the rest must go to r16, i.e.

(This expression may be generalized to any R×3 box band variant. (Pettersen[31]). Thus B2 contributes 56 × 63 permutations.

  • The choices for B3 triplets are row-wise determined by the B1 B2 row triplets. B3 always contributes 63 permutations.

The permutations for Band1 are 9! × 56 × 66 = 9! × 2612736 ≈ 9.48×1011.

Band1 permutation details

Triplet rBR(box/row) Labels
r 1 1
r 1 2
r 1 3
r 2 1
r 2 2
r 2 3
r 3 1
r 3 2
r 3 3

The permutations of B1 are the number of ways to relabel the 9 digits, 9! = 362880. Counting the permutations for B2 is more complicated, because the choices for B2 depend on the values in B1. (This is a visual representation of the expression given above.) The conditional calculation needs a branch (sub-calculation) for each alternative. Fortunately, there are just 4 cases for the top B2 triplet (r21): it contains either 0, 1, 2, or 3 of the digits from the B1 middle row triplet(r12). Once this B2 top row choice is made, the rest of the B2 combinations are fixed. The Band1 row triplet labels are shown on the right.

(Note: Conditional combinations becomes an increasingly difficult as the computation progresses through the grid. At this point the impact is minimal.)

Case 0 Matching Cells Triplets
1 2 3
4 5 6
7 8 9
7 8 9
1 2 3
4 5 6
4 5 6
7 8 9
1 2 3

Case 0: No Overlap. The choices for the triplets can be determined by elimination.

r21 can't be r11 or r12 so it must be = r13; r31 must be = r12 etc.

The Case 0 diagram shows this configuration, where the pink cells are triplet values that can be arranged in any order within the triplet. Each triplet has 3! = 6 permutations. The 6 triplets contribute 66 permutations.

Case 3: 3 Digits Match: triplet r21 = r12. The same logic as case 0 applies, but with a different triplet usage. Triplet r22 must be = r13, etc. The number of permutations is again 66 (Felgenhauer/Jarvis).[11] Call the cases 0 and 3 the pure match case.

Case 1 Match – Triplet Cell Options
1 2 3
4 5 6
7 8 9
3 3 2
1 3 2
1 2 1
3 2 1
3 2 1
3 2 1

Case 1: 1 Match for r21 from r12

In the Case 1 diagram, B1 cells show canonical values, which are color-coded to show their row-wise distribution in B2 triplets. Colors reflect distribution but not location or values. For this case: the B2 top row triplet (r21) has 1 value from B1 middle triplet, the other colorings can now be deduced. E.g. the B2 bottom row triplet (r23) coloring is forced by r21: the other 2 B1 middle values must go to bottom, etc. Fill in the number of B2 options for each color, 3..1, beginning top left. The B3 color-coding is omitted since the B3 choices are row-wise determined by B1, B2. B3 always contributes 3! permutations per row triplet, or 63 for the block.

For B2, the triplet values can appear in any position, so a 3! permutation factor still applies, for each triplet. However, since some of the values were paired relative to their origin, using the raw option counts would overcount the number of permutations, due to interchangeability within the pairing. The option counts need to be divided by the permuted size of their grouping (2), here 2! = 2 (See ) The pair in each row cancels the 2s for the B2 option counts, leaving a B2 contribution of 33 × 63. The B2×B3 combined contribution is 33 × 66.

Case 2 Match – Triplet Cell Options
1 2 3
4 5 6
7 8 9
3 2 3
2 1 3
2 1 1
3 2 1
3 2 1
3 2 1

Case 2: 2 Matches for r21 from r12. The same logic as case 1 applies, but with the B2 option count column groupings reversed. Case 3 also contributes 33×66 permutations.

Totaling the 4 cases for Band1 B1..B3 gives 9! × 2 × (33 + 1) × 66 = 9! 56 × 66 permutations.

Band1 symmetries and equivalence classes

Symmetries are used to reduce the computational effort to enumerate the Band1 permutations. A symmetry is an operation that preserves a quality of an object. For a Sudoku grid, a symmetry is a transformation whose result is also a valid grid. The following symmetries apply independently for the top band:

  • Block B1 values may be relabeled, giving 9! permutations
  • Blocks B1..3 may be interchanged, with 3!=6 permutations
  • Rows 1..3 may be interchanged, with 3!=6 permutations
  • Within each block, the 3 columns may be interchanged, giving 3!3 = 63 permutations.

Combined, the symmetries give 9! × 65 = 362880 × 7776 equivalent permutations for each Band1 solution.

A symmetry defines an equivalence relation, here, between the solutions, and partitions the solutions into a set of equivalence classes. The Band1 row, column and block symmetries divide the permutations into (not less than) 336 (56×6) equivalence classes with (up to) 65 permutations in each, and 9! relabeling permutations for each class. (Min/Max caveats apply since some permutations may not yield distinct elements due to relabeling.)

Since the solution for any member of an equivalence class can be generated from the solution of any other member, we only need to enumerate the solutions for a single member in order to enumerate all solutions over all classes. Let

  • sb : be a valid permutation of the top band
  • Sb = [sb] : be an equivalence class, relative to sb and some equivalence relation
  • Sb.z = |Sb| : the size of Sb, be the number of sb elements (permutations) in [sb]
  • Sb.n : be the number of Band2,3 completions for (any) sb in Sb
  • {Sb} : be the set of all Sb equivalence classes relative to the equivalence relation
  • {Sb}.z = |{Sb}| : be the number of equivalence classes

The total number of solutions N is then:

N =  Σ{Sb} Sb.z  ×  Sb.n

Solution and counting permutation symmetry

The Band1 symmetries (above) are solution permutation symmetries defined so that a permuted solution is also a solution. For the purpose of enumerating solutions, a counting symmetry for grid completion can be used to define band equivalence classes that yield a minimal number of classes.

Counting symmetry partitions valid Band1 permutations into classes that place the same completion constraints on lower bands; all members of a band counting symmetry equivalence class must have the same number of grid completions since the completion constraints are equivalent. Counting symmetry constraints are identified by the Band1 column triplets (a column value set, no implied element order). Using band counting symmetry, a minimal generating set of 44 equivalence classes[57] was established.

(1) Band1 Example
1 2 3
4 5 6
7 8 9
5 8 6
9 1 7
4 3 2
7 4 9
8 2 3
5 1 6
(2) Column Triplets
1 2 3
4 5 6
7 8 9
4 1 2
5 3 6
9 8 7
5 1 3
7 2 6
8 4 9
(3) Ordered Col. Triplets
1 2 3
4 5 6
7 8 9
1 3 5
2 6 7
4 9 8
1 2 4
3 6 5
8 7 9

The following sequence demonstrates mapping a band configuration to a counting symmetry equivalence class. Begin with a valid band configuration (1). Build column triplets by ordering the column values within each column. This is not a valid Sudoku band, but does place the same constraints on the lower bands as the example (2). Construct an equivalence class ID from the B2, B3 column triplet values. Use column and box swaps to achieve the lowest lexicographical ID. The last figure shows the column and box ordering for the ID: 124 369 578 138 267 459. All Band1 permutations with this counting symmetry ID will have the same number of grid completions as the original example. An extension of this process can be used to build the largest possible band counting symmetry equivalence classes (3).

Note, while column triplets are used to construct and identify the equivalence classes, the class members themselves are the valid Band1 permutations: class size (Sb.z) reflects column triplet permutations compatible with the One Rule solution requirements. Counting symmetry is a completion property and applies only to a partial grid (band or stack). Solution symmetry for preserving solutions can be applied to either partial grids (bands, stacks) or full grid solutions. Lastly note, counting symmetry is more restrictive than simple numeric completion count equality: two (distinct) bands belong to the same counting symmetry equivalence class only if they impose equivalent completion constraints.

Band 1 reduction details

Symmetries group similar object into equivalence classes. Two numbers need to be distinguished for equivalence classes, and band symmetries as used here, a third:

  • the number of equivalence classes ({Sb}.n).
  • the cardinality, size or number of elements in an equivalence class, which may vary by class (Sb.z)
  • the number of Band2,3 completions compatible with a member of a Band1 equivalence class (Sb.n)

The Band1 (65) symmetries divide the (56×66) Band1 valid permutations into (not less than) 336 (56×6) equivalence classes with (up to) permutations each. The not less than and up to caveats are necessary, since some combinations of the transformations may not produce distinct results, when relabeling is required (see below). Consequently, some equivalence classes may contain less than 65 distinct permutations and the theoretical minimum number of classes may not be achieved.

Each of the valid Band1 permutations can be expanded (completed) into a specific number of solutions with the Band2,3 permutations. By virtue of their similarity, each member of an equivalence class will have the same number of completions. Consequently, we only need to construct the solutions for one member of each equivalence class and then multiply the number of solutions by the size of the equivalence class. We are still left with the task of identifying and calculating the size of each equivalence class. Further progress requires the dexterous application of computational techniques to catalogue (classify and count) the permutations into equivalence classes.

Felgenhauer/Jarvis[11] catalogued the Band1 permutations using lexicographical ordered IDs based on the ordered digits from blocks B2,3. Block 1 uses a canonical digit assignment and is not needed for a unique ID. Equivalence class identification and linkage uses the lowest ID within the class.

Application of the (2×62) B2,3 symmetry permutations produces 36288 (28×64) equivalence classes, each of size 72. Since the size is fixed, the computation only needs to find the 36288 equivalence class IDs. (Note: in this case, for any Band1 permutation, applying these permutations to achieve the lowest ID provides an index to the associated equivalence class.)

Application of the rest of the block, column and row symmetries provided further reduction, i.e. allocation of the 36288 IDs into fewer, larger equivalence classes. When the B1 canonical labeling is lost through a transformation, the result is relabeled to the canonical B1 usage and then catalogued under this ID. This approach generated 416 equivalence classes, somewhat less effective than the theoretical 336 minimum limit for a full reduction. Application of counting symmetry patterns for duplicate paired digits achieved reduction to 174 and then to 71 equivalence classes. The introduction of equivalence classes based on band counting symmetry (subsequent to Felgenhauer/Jarvis by Russell[57]) reduced the equivalence classes to a minimum generating set of 44.

The diversity of the ~2.6×106, 56×66 Band1 permutations can be reduced to a set of 44 Band1 equivalence classes. Each of the 44 equivalence classes can be expanded to millions of distinct full solutions, but the entire solution space has a common origin in these 44. The 44 equivalence classes play a central role in other enumeration approaches as well, and speculation will return to the characteristics of the 44 classes when puzzle properties are explored later.

Band 2–3 completion and results

Enumerating the Sudoku solutions breaks into an initial setup stage and then into two nested loops. Initially all the valid Band1 permutations are grouped into equivalence classes, who each impose a common constraint on the Band2,3 completions. For each of the Band1 equivalence classes, all possible Band2,3 solutions need to be enumerated. An outer Band1 loop iterates over the 44 equivalence classes. In the inner loop, all lower band completions for each of the Band1 equivalence class are found and counted.

The computation required for the lower band solution search can be minimised by the same type of symmetry application used for Band1. There are 6! (720) permutations for the 6 values in column 1 of Band2,3. Applying the lower band (2) and row within band (6×6) permutations creates 10 equivalence classes of size 72. At this point, completing 10 sets of solutions for the remaining 48 cells with a recursive descent, backtracking algorithm is feasible with 2 GHz class PC so further simplification is not required to carry out the enumeration. Using this approach, the number of ways of filling in a blank Sudoku grid has been shown to be 6,670,903,752,021,072,936,960 (6.67×1021).[11]

The result, as confirmed by Russell,[57] also contains the distribution of solution counts for the 44 equivalence classes. The listed values are before application of the 9! factor for labeling and the two 72 factors (722 = 5184) for each of Stack 2,3 and Band2,3 permutations. The number of completions for each class is consistently on the order of 100,000,000, while the number of Band1 permutations covered by each class however varies from 4 – 3240. Within this wide size range, there are clearly two clusters. Ranked by size, the lower 33 classes average ~400 permutations/class, while the upper 11 average ~2100. The disparity in consistency between the distributions for size and number of completions or the separation into two clusters by size is yet to be examined.

See also

References

  1. ^ Lin, Keh Ying (2004), "Number of Sudokus", Journal of Recreational Mathematics, 33 (2): 120–24.
  2. ^ "Basic terms: About the New Sudoku Players' Forum". Forum.enjoysudoku.com. 16 May 2006. Retrieved 20 October 2013.
  3. ^ Berthier, Denis (November 2007). The Hidden Logic of Sudoku (Second, revised and extended ed.). Lulu.com. ISBN 978-1847534729.
  4. ^ Yato, Takayuki; Seta, Takahiro (2003). "Complexity and Completeness of Finding Another Solution and Its Application to Puzzles". IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences. E86-A (5): 1052–1060.
  5. ^ "Nerd Sniped: A Sudoku Story".
  6. ^ a b Lewis, R. A Guide to Graph Colouring: Algorithms and Applications. Springer International Publishers, 2015.
  7. ^ a b de Ruiter, Johan (15 March 2010). "On Jigsaw Sudoku Puzzles and Related Topics (Bachelor Thesis)" (PDF). Leiden Institute of Advanced Computer Science (LIACS).
  8. ^ a b QSCGZ (Guenter Stertenbrink) (21 September 2003). "combinatorial question on 9x9 (rec.puzzles)". Google Discussiegroepen. Retrieved 20 October 2013.
  9. ^ Russell, Ed (1 February 2008). "6670903752021072936960 is old hat". The New Sudoku Players' Forum. Retrieved 20 October 2013.
  10. ^ a b c Jarvis, Frazer (2 February 2008). "Sudoku enumeration problems". Frazer Jarvis's home page. University of Sheffield. Retrieved 20 October 2013.
  11. ^ a b c d e f Felgenhauer, Bertram; Jarvis, Frazer (20 June 2005), Enumerating possible Sudoku grids (PDF).
  12. ^ a b c d Fowler, Glenn (15 February 2007). "Number of automorphisms for any grid". The New Sudoku Players' Forum. Retrieved 29 April 2017.
  13. ^ a b G. McGuire, B. Tugemann, G. Civario. "There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem". Arxiv.org.
  14. ^ a b c d e f g h Ed Russell and Frazer Jarvis (7 September 2005). "There are 5472730538 essentially different Sudoku grids... and the Sudoku symmetry group". Frazer Jarvis's home page. University of Sheffield. Retrieved 20 October 2013.
  15. ^ Ed Russell, Frazer Jarvis (25 January 2006). "Mathematics of Sudoku II" (PDF).
  16. ^ a b c eleven (25 December 2008). "About Red Ed's Sudoku symmetry group". The New Sudoku Players' Forum. Retrieved 13 July 2020.
  17. ^ Russell (24 January 2009). "Re: About Red Ed's Sudoku symmetry group (p. 8) [list of automorphism groups]". The New Sudoku Players' Forum. Retrieved 19 October 2020.
  18. ^ Russell (6 February 2009). "Re: About Red Ed's Sudoku symmetry group (p. 13) [revised list of automorphism groups]". The New Sudoku Players' Forum. Retrieved 19 October 2020.
  19. ^ Russell (14 February 2009). "Re: About Red Ed's Sudoku symmetry group (p. 14) [automorphism group structures]". The New Sudoku Players' Forum. Retrieved 19 October 2020.
  20. ^ Jones, Siân K.; Perkins, Stephanie; Roach, Paul A. (6 July 2011). "Properties, isomorphisms and enumeration of 2-Quasi-Magic Sudoku grids". Discrete Mathematics. 311 (13): 1098–1110. doi:10.1016/j.disc.2010.09.026.
  21. ^ "Sudoku Programmers :: View topic – Number of "magic sudokus" (and random generation)". Setbb.com. Archived from the original on 6 February 2012. Retrieved 20 October 2013.
  22. ^ "Su-Doku's maths : General – p. 27". Forum.enjoysudoku.com. Retrieved 20 October 2013.
  23. ^ "Su-Doku's maths : General – p. 27". Forum.enjoysudoku.com. Retrieved 20 October 2013.
  24. ^ a b "NRC Sudokus". Homepages.cwi.nl. Retrieved 20 October 2013.
  25. ^ "Calling all sudoku experts : General". Forum.enjoysudoku.com. Retrieved 20 October 2013.
  26. ^ "Su-Doku's maths : General – Page 13". Forum.enjoysudoku.com. Retrieved 20 October 2013.
  27. ^ a b c d Pettersen, Kjell (12 December 2005). "Re: estimate for 4x4 [KSP estimation formula]". The New Sudoku Players' Forum. forum.enjoysudoku.com. Retrieved 20 October 2013.
  28. ^ Pettersen (15 April 2006). "4x3 Sudoku counting - Reliability (pg. 2)". The New Sudoku Players' Forum. Retrieved 3 October 2020.
  29. ^ Sian K. Jones; Stephanie Perkins; Paul Alun Roach (May 2014). "On the number of Sudoku Grids". Journal of Combinatorial Mathematics and Combinatorial Computing. April: 94–95. Retrieved 28 February 2021.{{cite journal}}: CS1 maint: url-status (link)
  30. ^ geoff (14 June 2005). "Sudoku maths – can mortals work it out for the 2x2 square ? - A counting method". The New Sudoku Players' Forum. Retrieved 20 October 2013.
  31. ^ a b c d e Pettersen (11 October 2005). "Su-Doku's maths - Some thoughts about higher sudokus than 3x3 (p. 28)". The New Sudoku Players' Forum. Retrieved 2 October 2020.
  32. ^ a b Red Ed (16 October 2005). "Re: Su-Doku's maths (p. 29)". The New Sudoku Players' Forum. Retrieved 20 October 2013.
  33. ^ Pettersen (17 October 2005). "Re: Su-Doku's maths (p. 29)". The New Sudoku Players' Forum. Retrieved 5 October 2020.
  34. ^ a b Pettersen (20 October 2005). "Re:Su-Doku's maths (p. 29) [5x2-sudoku grids counting]". The New Sudoku Players' Forum. Retrieved 20 October 2013.
  35. ^ Kaspar, Matthias & Lars (18 July 2006). "Su-Doku's maths (p. 41) - 5x2 verified?". The New Sudoku Players' Forum. Retrieved 22 October 2020.
  36. ^ a b Pettersen (14 April 2006). "4x3 Sudoku counting - 4x3 Counting complete (p. 2)". The New Sudoku Players' Forum. Retrieved 20 October 2013.
  37. ^ Silver (25 June 2022). "Sudoku 4x3 Exact Count".
  38. ^ a b Pettersen, Kjell (14 November 2006). "Re: 6x2 counting [no. 6x2 grids]". The New Sudoku Players' Forum. Retrieved 20 October 2013.
  39. ^ a b PatmaxDaddy (5 January 2006). "Su-Doku's maths - 5x3 grid estimate (p. 38)". The New Sudoku Players' Forum. Retrieved 20 October 2013.
  40. ^ a b PatmaxDaddy (12 December 2005). "Su-Doku's maths - estimate for 4x4 (p. 36)". The New Sudoku Players' Forum. Retrieved 20 October 2013.
  41. ^ a b c PatmaxDaddy (5 January 2006). "Su-Doku's maths - 5xC band 1 results". The New Sudoku Players' Forum. Retrieved 20 October 2013.
  42. ^ a b c PatmaxDaddy (23 January 2006). "RxC Sudoku band counting algorithm - 5xC band results". The New Sudoku Players' Forum. Retrieved 20 October 2013.
  43. ^ a b c d Pettersen, Kjell (8 June 2006). "Number of essentially different Sudoku grids". The New Sudoku Players' Forum. Retrieved 11 September 2020.
  44. ^ Arnold, Elizabeth; Field, Rebecca; Lucas, Stephen; Taalman, Laura (24 February 2013). "Minimal complete Shidoku symmetry groups". Journal of Combinatorial Mathematics and Combinatorial Computing. 87: 209–228. arXiv:1302.5949 – via arXiv.
  45. ^ Ed Russell, Frazer Jarvis. "There are 49 essentially different Sudoku 2x3 grids... and the 2x3 Sudoku symmetry group". Frazer Jarvis's home page. University of Sheffield. Retrieved 20 October 2013.
  46. ^ Ed Russell. "There are 1673187 essentially different Sudoku 2x4 grids... and the 2x4 Sudoku symmetry group". Frazer Jarvis's home page. University of Sheffield. Retrieved 20 October 2013.
  47. ^ Pettersen (5 November 2005). "Su-Doku's maths (p. 31)". The New Sudoku Players' Forum. Retrieved 20 October 2013.
  48. ^ Kjell Fredrik Pettersen (after work by Ed Russell). "There are 4743933602050718 essentially different Sudoku 2x5 grids... and the 2x5 Sudoku symmetry group". Frazer Jarvis's home page. Retrieved 11 September 2020.
  49. ^ Pettersen (28 July 2006). "Re: Number of essentially different Sudoku grids". The New Sudoku Players' Forum. Retrieved 20 October 2013.
  50. ^ Mathimagics (11 January 2020). "Re: Number of possible 16x16 sudoku grids?". The New Sudoku Players' Forum. Retrieved 14 September 2020.
  51. ^ "Su-Doku's maths : General – p. 3". Forum.enjoysudoku.com. Retrieved 20 October 2013.
  52. ^ a b Pettersen (10 January 2006). "Su-Doku's maths : General - Page 39". The New Sudoku Players' Forum. Retrieved 8 November 2020.
  53. ^ "Su-Doku's maths - Re: estimate for 4x4 (p. 37)". The New Sudoku Players' Forum. 15 December 2005. Retrieved 20 October 2013.
  54. ^ PatmaxDaddy (12 January 2006). "RxC Sudoku band counting algorithm - Proof of 4xC". The New Sudoku Players' Forum. Retrieved 20 October 2013.
  55. ^ Pettersen (9 January 2006). "RxC Sudoku band counting algorithm". The New Sudoku Players' Forum. Retrieved 20 October 2013.
  56. ^ a b PatmaxDaddy (11 February 2006). "Re: RxC Sudoku band counting algorithm". The New Sudoku Players' Forum. Retrieved 20 October 2013.
  57. ^ a b c d Jarvis, Frazer (17 June 2005). "Enumerating possible Sudoku grids - Summary of method and results". Frazer Jarvis's home page. University of Sheffield. Retrieved 20 October 2013.
  58. ^ a b Russell, Ed (18 October 2005). "Su-Doku's maths : General - Page 29". forum.enjoysudoku.com. Retrieved 2 October 2020.
  59. ^ a b c d Red Ed (13 December 2005). "Su-Doku's maths - Re: estimate for 4x4 (p. 37)". The New Sudoku Players' Forum. Retrieved 20 October 2013.
  60. ^ "RxC Sudoku band counting algorithm : General". Forum.enjoysudoku.com. Retrieved 20 October 2013.
  61. ^ PatmaxDaddy (25 January 2006). "Re: RxC Sudoku band counting algorithm". The New Sudoku Players' Forum. Retrieved 20 October 2013.
  62. ^ Pettersen, Kjell (31 October 2006). "Re: 6x2 counting [no. of 6x2 bands]". The New Sudoku Players' Forum. Retrieved 5 October 2020.
  63. ^ a b "Symmetrical 17 Clue Puzzle" Symmetrical 17 Clue Puzzle.
  64. ^ a b "Raphael – 18 Clue Symmetrical" Raphael – an 18 clue Sudoku with orthogonal symmetry.
  65. ^ a b "Total symmetry" Total symmetry – a 24 clue Sudoku with total symmetry.
  66. ^ a b "Tourmaline – 19 Clue Two-Way Symmetry" Tourmaline – a 19 clue Sudoku with two-way orthogonal symmetry.
  67. ^ "プログラミングパズル雑談コーナー". .ic-net.or.jp. Archived from the original on 12 October 2016. Retrieved 20 October 2013.
  68. ^ "Minimum Sudoku". Csse.uwa.edu.au. Archived from the original on 26 November 2006. Retrieved 20 October 2013.
  69. ^ Yirka, Bob (6 January 2012). "Mathematicians Use Computer to Solve Minimum Sudoku Solution Problem". PhysOrg. Retrieved 6 January 2012.
  70. ^ McGuire, Gary (1 January 2012). "There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem". arXiv:1201.0749.
  71. ^ H.H. Lin, I-C. Wu. "No 16-clue Sudoku puzzles by sudoku@vtaiwan project" Archived 14 February 2014 at the Wayback Machine, September 2013.
  72. ^ "Symmetrically-clued 17s". Forum.enjoysudoku.com. Retrieved 30 November 2013.
  73. ^ Taalman, Laura (2007), "Taking Sudoku seriously", Math Horizons, 15 (1): 5–9, doi:10.1080/10724117.2007.11974720, JSTOR 25678701, S2CID 126371771. See in particular Figure 7, p. 7.
  74. ^ "Low/Hi Clue Thresholds". Forum.enjoysudoku.com. 14 August 2019. Retrieved 14 August 2019.
  75. ^ "The New Sudoku Players' Forum". forum.enjoysudoku.com. Retrieved 28 February 2021.{{cite web}}: CS1 maint: url-status (link)
  76. ^ a b [1] Minimal number of clues for Sudokus
  77. ^ a b c d e "Minimum givens on larger puzzles". forum.enjoysudoku.com. Retrieved 28 February 2021.{{cite web}}: CS1 maint: url-status (link)
  78. ^ とん (January 2015). ヒントの少ないナンプレの作り方 (in Japanese) (2 ed.). 暗黒通信団. ISBN 978-4873102238. Archived from the original on 11 August 2014.
  79. ^ "Minimum number of clues in Sudoku DG : Sudoku variants". Forum.enjoysudoku.com. Retrieved 20 October 2013.
  80. ^ "100 randomized minimal sudoku-like puzzles with 6 constraints". Magictour.free.fr. Retrieved 20 October 2013.
  81. ^ "Number of "magic sudokus" (and random generation) : General – p. 2". Forum.enjoysudoku.com. Retrieved 20 October 2013.
  82. ^ "CUDA Anti-Knight 8 Given Unique Solution Search". github.com/dclamage. 22 January 2022. Retrieved 25 January 2022.
  83. ^ "SudokuX (Diagonal Sudoku)". forum.enjoysudoku.com. Retrieved 2 February 2022.
  84. ^ "Download Attachment" (PDF). Anthony.d.forbes.googlepages.com. Retrieved 20 October 2013.
  85. ^ Puzzled man solving 'miracle' sudoku becomes YouTube sensation, by Simon Usborne, in The Guardian; published May 22, 2020; retrieved October 28, 2021
  86. ^ "Du-Sum-Oh Puzzles". Bumblebeagle.org. Retrieved 20 October 2013.
  87. ^ "Du-Sum-Oh Puzzles". Bumblebeagle.org. Retrieved 20 October 2013.
  88. ^ "Universiteit Leiden Opleiding Informatica : Internal Report 2010-4 : March 2010" (PDF). Liacs.nl. Retrieved 20 October 2013.
  89. ^ "Can You Solve It? Clueless Sudoku". TheGuardian.com. 26 July 2021. Retrieved 7 September 2021.
  90. ^ "New killer setter". Retrieved 7 September 2021.
  91. ^ "Sum Number Place". Archived from the original on 24 December 2005. Retrieved 28 February 2021.
  92. ^ a b http://forum.enjoysudoku.com/high-clue-tamagotchis High clue tamagotchis (forum: pages 1–14; 40 clue minimal: page 10).
  93. ^ http://forum.enjoysudoku.com/high-clue-tamagotchis High clue tamagotchis (forum: p. 5).
  94. ^ Berthier, Denis (4 December 2009). "Unbiased Statistics of a CSP – A Controlled-Bias Generator". Retrieved 4 December 2009.
  95. ^ "Counting minimal puzzles: subsets, supersets, etc". Forum.enjoysudoku.com. 11 June 2013. Retrieved 18 April 2017.
  96. ^ "Ask for some patterns that they don't have puzzles. : General". Forum.enjoysudoku.com. Retrieved 20 October 2013.
  97. ^ "Largest 'hole' in a Sudoku; Largest 'emtpy space' : General". Forum.enjoysudoku.com. Retrieved 20 October 2013.
  98. ^ "Large Empty Space". Flickr. 6 May 2008. Retrieved 20 October 2013.
  99. ^ "Largest number of empty groups? : General – p. 2". Forum.enjoysudoku.com. Retrieved 20 October 2013.
  100. ^ "Clues Bunched in Clusters | Flickr – Photo Sharing!". Flickr. 25 March 2008. Retrieved 20 October 2013.
  101. ^ "18 Clue Automorphic Sudoku" 18 Clue Automorphic Sudoku.
  102. ^ "Six Dots with 5 × 5 Empty Hole | Flickr – Photo Sharing!". Flickr. 1 July 2008. Retrieved 20 October 2013.
  103. ^ "Canonical Form". sudopedia.enjoysudoku.com. Retrieved 28 February 2021.{{cite web}}: CS1 maint: url-status (link)

Further reading