Mathematics of Sudoku


The class of Sudoku puzzles consists of a partially completed row-column grid of cells partitioned into N regions each of size N cells, to be filled in using a prescribed set of N distinct symbols, so that each row, column and region contains exactly one of each element of the set. The properties of Sudoku puzzles and their solutions can be investigated using mathematics and algorithms.

Overview

The analysis of Sudoku falls into two main areas: analyzing the properties of completed grids and puzzles. Also studied are computer algorithms to solve Sudokus, and to develop new Sudokus. Analysis has largely focused on enumerating solutions, with results first appearing in 2004. There are many Sudoku variants, partially characterized by size, and the shape of their regions. Unless noted, discussion in this article assumes classic Sudoku, i.e. N=9. A rectangular Sudoku uses rectangular regions of row-column dimension R×C. Other variants include those with irregularly-shaped regions or with additional constraints or different constraint types.
A puzzle is a partially completed grid, and the initial values are givens or clues. 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 proper puzzle has a unique solution. See Glossary of Sudoku for other terminology. Solving Sudokus from the viewpoint of a player has been explored in Denis Berthier's book "The Hidden Logic of Sudoku" 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. For n=3, however, this result is of little practical relevance: algorithms such as Dancing Links can solve puzzles in a fraction of a second because of the small size of the problem.
A puzzle can be expressed as a graph coloring problem. 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, where x and y are integers between 1 and 9. In this case, two distinct vertices labeled by and are joined by an edge if and only if:
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. There are significantly fewer Sudoku grids than Latin squares because Sudoku imposes the additional regional constraint. Nonetheless, the number of Sudoku grids was calculated by Bertram Felgenhauer and Frazer Jarvis in 2005 to be 6,670,903,752,021,072,936,960. The number computed by Felgenhauer and Jarvis confirmed a result first identified in a Usenet discussion forum post of September 2003 by someone using the nickname "QSCGZ". This number is equal to 9! × 722 × 27 × 27,704,267,971, the last factor of which is prime. The result was derived through logic and brute force computation. Russell and Jarvis also showed that when symmetries were taken into account, there were 5,472,730,538 solutions. The number of grids for 16×16 Sudoku is not known.
The number of minimal Sudokus is not precisely known. However, statistical techniques combined with a generator, show that there are approximately :
Other authors used faster methods and calculated additional precise distribution statistics.

Sudokus from group tables

As in the case of Latin squares the multiplication 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 .
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, 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. 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 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 . Thus we arrive at a Sudoku. With the example and the row permutation above, we arrive at Grid 2.
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, that not all Sudokus can be generated this way.

Enumerating Sudoku solutions

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

Enumerating all possible Sudoku solutions

For the enumeration of all possible solutions, two solutions are considered distinct if any of their corresponding 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 to the rec.puzzles newsgroup in 2003, obtaining 6,670,903,752,021,072,936,960 distinct solutions.
In a 2005 study, Felgenhauer and Jarvis 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.

Enumerating essentially different Sudoku solutions

Equivalent sudokus and 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 . These transformations always transform a valid grid into another valid grid. There are two major types: symbol permutations and cell permutations. They are:

and rearranging :
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 the 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], but counting them is necessary for evaluating the exact number of essentially different sudokus.

Automorphisms and Burnside's lemma

The set of equivalent grids which can be reached using these operations 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; these conjugacy classes represent the different types of symmetry 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.
Name or compositionClass
Id.		Class
size		Cell cyclesNumber of fixed grids
,
per element		Number of fixed grids,
per element		Number of fixed grids
,
whole class		Number of fixed grids,
whole class
Identitye1118118,383,222,420,692,9926,670,903,752,021,072,936,96018,383,222,420,692,9926,670,903,752,021,072,936,960
Mini Rows ccc81627×330107,495,42439,007,939,461,1201,719,926,784624,127,031,377,920
2 MR, 1 MDccc | c 79627×33021,233,6647,705,271,992,3202,038,431,744739,706,111,262,720
1 MR, 2 MDccc | cc 919227×3304,204,2241,525,628,805,120807,211,008292,920,730,583,040
Mini Diagonals ccc | ccc 106427×3302,508,084910,133,521,920160,517,37658,248,545,402,880
Jumping Rows C2514427×33014,837,7605,384,326,348,8002,136,637,440775,342,994,227,200
2 JR, 1 GRC | c 2886427×3302,085,120756,648,345,6001,801,543,680653,744,170,598,400
1 JR, 2 GRC | cc 301,72827×330294,912107,017,666,560509,607,936184,926,527,815,680
Gliding Rows C | ccc 321,15227×3306,342,4802,301,559,142,4007,306,536,9602,651,396,132,044,800
Full Rows C9272889×9905,1841,881,169,9201,492,992541,776,936,960
2 FR, 1 WRC9 | c 261,7289×9902,592940,584,9604,478,9761,625,330,810,880
1 FR, 2 WRC9 | cc 293,4569×9901,296470,292,4804,478,9761,625,330,810,880
Waving Rows C9 | ccc 312,3049×990648235,146,2401,492,992541,776,936,960
Jumping Diagonals C | C 225,18427×330323,928117,546,992,6401,679,242,752609,363,609,845,760
Broken Columns C | C9 2420,7369×990288104,509,4405,971,9682,167,107,747,840
Full Diagonals C9 | C9 2320,7369×99016258,786,5603,359,2321,218,998,108,160
Diagonal Mirror T371,29636×22930,258,43210,980,179,804,16039,214,927,87214,230,313,026,191,360
DM+MDT ccc4010,3683×3, 12×6601,854672,779,52019,222,2726,975,378,063,360
DM+JDT C4393,3123×3, 12×660288104,509,44026,873,8569,751,984,865,280
Quarter Turn T sS8669,98420×44113,0564,737,761,280913,711,104331,567,485,419,520
Half Turn sS | sS 792,91640×221155,492,35256,425,064,693,760453,415,698,432164,535,488,647,004,160
Column Sticks S | sss 13497236×229449,445,888163,094,923,837,440436,861,403,136158,528,265,969,991,680
CS+MCcS6 | sss 1353,8883×3, 12×66027,64810,032,906,240107,495,42439,007,939,461,120
CS+GRcS6 | C6 14231,1043×3, 12×6606,4802,351,462,400201,553,92073,139,886,489,600
CS+ JR/B2,GR/B13S6 | C6 14315,5523×3, 12×6601,728627,056,64026,873,8569,751,984,865,280
CS+ GR/Band2,JR/B13cS | C6 14415,5523×3, 12×6603,4561,254,113,28053,747,71219,503,969,730,560
CS+JRS | C6 1457,7763×3, 12×66013,8245,016,453,120107,495,42439,007,939,461,120
949,129,933,824344,420,270,386,053,120

Note that a grid may exhibit a number of the abovementioned automorphisms simultaneously; for example, any grid which has a quarter-turn symmetry also has half-turn symmetry. The combination of all automorphisms of a particular grid is its automorphism group.

Number of essentially equivalent grids

Each of the essentially unique grids can be analyzed for self-similarities 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 have a form of self-similarity.
The size of the orbit can be calculated using the orbit-stabilizer theorem: it is the size of the sudoku symmetry group divided by the size of the [|automorphism] group. Multipling the number of essentially unique grids with the orbit size gives the total number of grids with that automorphism 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.
Size of
automorphism
group		No. of essentially
unique grids
Equivalent grids
,
ignoring relabeling		Number of grids,
ignoring relabeling		Equivalent grids,
including relabeling		Total number of grids
15,472,170,3873,359,23218,382,289,873,462,7841,218,998,108,1606,670,565,349,282,175,057,920
2548,4491,679,616921,183,715,584609,499,054,080334,279,146,711,121,920
37,3361,119,7448,214,441,984406,332,702,7202,980,856,707,153,920
42,826839,8082,373,297,408304,749,527,040861,222,163,415,040
61,257559,872703,759,104203,166,351,360255,380,103,659,520
829419,90412,177,216152,374,763,5204,418,868,142,080
942373,24815,676,416135,444,234,2405,688,657,838,080
1292279,93625,754,112101,583,175,6809,345,652,162,560
1885186,62415,863,04067,722,117,1205,756,379,955,200
272124,416248,83245,148,078,08090,296,156,160
361593,3121,399,68033,861,058,560507,915,878,400
541162,208684,28822,574,039,040248,314,429,440
72246,65693,31216,930,529,28033,861,058,560
108331,10493,31211,287,019,52033,861,058,560
162120,73620,7367,524,679,6807,524,679,680
64815,1845,1841,881,169,9201,881,169,920
>1560,151932,547,230,208338,402,738,897,879,040
5,472,730,53818,383,222,420,692,9926,670,903,752,021,072,936,960

Enumeration results

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

Sudoku with rectangular regions

In the table, "Dimensions" are those of the regions. The "Rel Err" column indicates how a simple approximation, using the generalised method of Kevin Kilfoil, compares to the true grid count: it is an underestimate in all cases evaluated so far.

Sudoku bands

For large, the method of Kevin Kilfoil is used to estimate the number of grid completions. The method asserts that the Sudoku row and column constraints are, to first approximation, conditionally independent given the box constraint. Omitting a little algebra, this gives the Kilfoil-Silver-Pettersen formula:
where bR,C is the number of ways of completing a Sudoku band of R horizontally adjacent R×C boxes. Petersen's algorithm, as implemented by Silver, is currently the fastest known technique for exact evaluation of these bR,C.
The band counts for problems whose full Sudoku grid-count is unknown are listed below. As in the previous section, "Dimensions" are those of the regions.
The expression for the 4×C case is:
where:

Sudoku with additional constraints

The following are all restrictions of 3×3 Sudokus. The type names have not been standardised: click on the attribution links to see the definitions.
TypeNr GridsAttributionVerified?
Quasi-Magic Sudoku248832Jones, Perkins and RoachYes
3doku104015259648StertenbrinkYes
Disjoint Groups201105135151764480RussellYes
Hypercube37739520StertenbrinkYes
Magic Sudoku5971968StertenbrinkYes
Sudoku X55613393399531520RussellYes
NRC Sudoku6337174388428800BrouwerYes

A Sudoku will remain valid under the actions of the [|Sudoku preserving symmetries]. Some Sudokus are special in that some operations merely have the effect of relabelling the digits; several of these are listed below.
TransformationNr GridsVerified?
Transposition10980179804160Indirectly
Quarter Turn4737761280Indirectly
Half Turn56425064693760Indirectly
Band cycling5384326348800Indirectly
Within-band row cycling39007939461120Indirectly

Further calculations of this ilk combine to show that the number of essentially different Sudoku grids is 5,472,730,538, for example as demonstrated by Jarvis / Russell and verified by Pettersen. Similar methods have been applied to the 2×3 case, where Jarvis / Russell showed that there are 49 essentially different grids, to the 2×4 case, where Russell showed that there are 1,673,187 essentially different grids, and to the 2×5 case where Pettersen showed that there are 4,743,933,602,050,718 essentially different grids.

Minimum number of givens

Ordinary Sudokus 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. 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, and this was independently confirmed in September 2013. 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. 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. 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.
A Sudoku with 24 clues, dihedral 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. 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.

Sudokus of other sizes

Additional constraints lead to a smaller minimum number of clues.
"Du-sum-oh" puzzles replace the 3×3 regions of Sudoku with irregular shapes of a fixed size. Bob Harris has proved that it is always possible to create -clue du-sum-ohs on an N×N grid, and has constructed several examples. Johan de Ruiter has proved 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, the regions are of irregular shape and various sizes. The usual constraints of no repeated value in any row, column or region apply. The clues are given as sums of values within regions. The minimum number of clues for Samunampure is not known, nor even conjectured. A variant on Miyuki Misawa's web site replaces sums with relations: the clues are symbols =, < and > showing the relative values of 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

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. 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.
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, the uniqueness of the solution constraint still dominates over the minimality constraint.
As for the most clues possible in a Sudoku while still not rendering a unique solution, it is four short of a full grid. 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.

Constraints of clue geometry

It has been conjectured that no proper Sudoku can have clues limited to the range of positions in the pattern above. The largest rectangular orthogonal "hole" in a proper Sudoku is believed to be a rectangle of 30 cells. One example is a Sudoku with 22 clues. The largest total number of empty groups in a Sudoku is believed to be nine. One example is a Sudoku with 3 empty rows, 3 empty columns, and 3 empty boxes.

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.
Auto-
morphisms		No. GridsAuto-
morphisms		No.
Grids
154721703871885
2548449272
373363615
428265411
61257722
8291083
9421621
12926481

In the first two examples, notice that if the Sudoku is rotated 180 degrees, and the clues relabeled with the permutation ->, it returns to the same Sudoku. Expressed another way, these Sudokus have the property that every 180-degree rotational pair of clues follows the rule + = 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. Notice that in the second example, the Sudoku also exhibits translational symmetry; clues are clustered in groups, with the clues in each group ordered sequentially.
The third image is the Most Canonical solution grid. This grid has 648 automorphisms and contributes to all ~ 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.

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

The Band1 algorithm proceeds as follows:
. Thus B2 contributes 56 × 63 permutations.
The permutations for Band1 are 9! × 56 × 66 = 9! × 2612736 ~.

Band1 permutation details

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. The conditional calculation needs a branch for each alternative. Fortunately, there are just 4 cases for the top B2 triplet : it contains either 0, 1, 2, or 3 of the digits from the B1 middle row triplet. 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.
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. Call the cases 0 and 3 the pure match case.
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 has 1 value from B1 middle triplet, the other colorings can now be deduced. E.g. the B2 bottom row triplet 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, here 2!.= 2 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: 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 × × 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:
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 56*6^6 permutations into 336 equivalence classes with 65 permutations in each, and 9! relabeling permutations for each class.
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
The total number of solutions N is then:

Solution and counting permutation symmetry

The Band1 symmetries 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. Using band counting symmetry, a minimal generating set of 44 equivalence classes was established.
The following sequence demonstrates mapping a band configuration to a counting symmetry equivalence class. Begin with a valid band configuration. 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. 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.
Note, while column triplets are used to construct and identify the equivalence classes, the class members themselves are the valid Band1 permutations: class size reflects column triplet permutations compatible with the One Rule solution requirements. Counting symmetry is a completion property and applies only to a partial grid. Solution symmetry for preserving solutions can be applied to either partial grids or full grid solutions. Lastly note, counting symmetry is more restrictive than simple numeric completion count equality: two 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 Band1 symmetries divide the Band1 valid permutations into 336 equivalence classes with 6^5 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. 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 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 the permutations into equivalence classes.
Felgenhauer/Jarvis 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 B2,3 symmetry permutations produces 36288 equivalence classes, each of size 72. Since the size is fixed, the computation only needs to find the 36288 equivalence class IDs.
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 reduced the equivalence classes to a minimum generating set of 44.
The diversity of the ~, 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! permutations for the 6 values in column 1 of Band2,3. Applying the lower band and row within band 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.
The result, as confirmed by Russell, 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 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.

Variants

Sudoku regions are polyominoes. Although the classic 9×9 Sudoku is made of square nonominoes, it is possible to apply the rules of Sudoku to puzzles of other sizes – the 2×2 and 4×4 square puzzles, for example. Only N2×N2 Sudoku puzzles can be tiled with square polyominoes. Another popular variant is made of rectangular regions – for example, 2×3 hexominoes tiled in a 6×6 grid. The following notation is used for discussing this variant.
Puzzles of size N×N, where N is prime can only be tiled with irregular N-ominoes. Each N×N grid can be tiled multiple ways with N-ominoes. Before enumerating the number of solutions to a Sudoku grid of size N×N, it is necessary to determine how many N-omino tilings exist for a given size.
The size ordering of Sudoku puzzle can be used to define an integer series, e.g. for square Sudoku, the integer series of possible solutions. Sudoku with square N×N regions are more symmetrical than immediately obvious from the One Rule. Each row and column intersects N regions and shares N cells with each. The number of bands and stacks also equals N. Rectangular Sudoku do not have these properties. The "3×3" Sudoku is additionally unique: N is also the number of row-column-region constraints from the One Rule. See the Glossary of Sudoku for an expanded list of variants.