## enumeration of sudoku-classes

Everything about Sudoku that doesn't fit in one of the other sections

### enumeration of sudoku-classes

this is a repost of Kjell's important post to a new thread
so it can be found with the forum's search function.
Maybe we can gather all the important posts here

http://forum.enjoysudoku.com/viewtopic.php?t=44&postdays=0&postorder=asc&start=454

--------------------------------------------------------

The number of S-classes and T-classes as well as (once again)
the number of grids for 3x3-sudoku [81 cells] is now confirmed.

Let A be the subgroup of S_9xS_81 of transforms acting on 3x3-sudoku grids,
generated by symbol permutations in S_9x{Id}, band permutations,
stack permutations, permutations of rows within a given band and of columns
within a given stack. [we omit transposition here]
For any grid G, let K(G) be the transforms in A leaving G fixed.
[the "isotropy-group" of G]
And let T[G] be the equivalence class of G modulo A.
[the "orbit" of G by the action of A = the T-class of G]

Then #T[G] = #A/#K(G) = 9!*6^8/#K(G)

I have written a program that runs through all T-classes,
and for each class T[G] (where G is a grid) finds the size of K(G),
and whether G is transpose-invariant (i.e. T[G]=T[transpose(G)]).
The result of the counting:

Code: Select all
` i |  N |           X  |      Y---|----|-------------|-----------   |    |Classes T[G] with #K(G)=N   |    |not transpose|  transpose    |    | invariant   |  invariant---|----+-------------+----------- 1 |  1 | 10944340774 | 23201 2 |  2 |     1050496 |   637 2 |  3 |       14672 |    36 4 |  4 |        4378 |    29  5 |  6 |        2442 |     6 6 |  9 |          84 |     1 7 | 12 |         172 |     0 8 | 18 |         168 |     4 9 | 27 |           4 |     110 | 36 |          22 |     211 | 54 |          20 |     112 |108 |           4 |     013 |162 |           2 |     014 |324 |           0 |     1---|----|-------------|-------   |sum:| 10945413238 | 23919`

Let the entries in above table in row i be denoted by (N_i,X_i,Y_i) then

The number of T-classes = Sum (X_i + Y_i) = 10945437157
The number of S-classes = Sum (X_i/2 + Y_i) = 5472730538
The number of S-classes that split into two T-classes = Sum X_i/2 =
5472706619
The number of S-classes with only one T-class = Sum Y_i = 23919
The number of grids = 9! * 6^8 * Sum (X_i+Y_i)/N_i = 6670903752021072936960
The number of transpose-invariant grids = #A * Sum Y_i/N_i =
14347728127918080
dukuso

Posts: 479
Joined: 25 June 2005