The New Sudoku Players' Forum

[Mathimagics]

Thanks, Serg ...

Sigh ... that is so sad!

My automorphism counting process was completed in very quick time, just a few minutes, and I get the result that you forecast with your excellent statement of the problem above.

Ignoring relabellings, we have:

• number of different SudokuP grids, ND = 554,191,840,696

• number of automorphic SudokuP grids NA = 78,257,944

• (NA + ND) / 2592 = 213,838,772.623457 (uurgh!)

If this flawed process overestimates the essentially different figure, can we at least state with confidence that the number of essentially different SudokuP grids is less than 213,838,773?

And is there any strategy we could use to compensate for the error?

[David P Bird]

Serg, In my own limited way I'm attempting to follow this from the sidelines. Can you tell me if this is right?

Running through all the transformations possible, say the canonical distribution repeats 4 times.
However it would be wrong to assume that all other distributions will also repeat 4 times as a subset of distributions may exist that repeats 8 times.
Alternatively the canonical distribution could be a member of such a subset so that some other distributions may only occur once or twice.

If that is right, then the 'ingorant' assumption could either be an overestimate or underestimate.

David
.

[Mathimagics]

I never wanted to be a Computational Scientist ... I wanted to be .... a lumberjack!

[Serg]

Hi, David!
I do not quite understand you. Let's consider simple example.

Let's consider all possible 2 x 2 matrixes, containing zeros and ones only. There are 2^4 all different such matrixes:

Code: Select all

M1   M2   M3   M4   M5   M6   M7   M8   M9   M10  M11  M12  M13  M14  M15  M16

00   00   00   00   01   01   01   01   10   10   10   10   11   11   11   11
00   01   10   11   00   01   10   11   00   01   10   11   00   01   10   11

All these (16) matrixes constitutes M set. We can imagine, that each matrix is metal square, containing or not containing holes ("1") in its corners.

Now let's consider a set of all possible isomorphic (i.e. not changing entity of an object) transformations. We can imagine all possible reflections and rotations of mentioned metal squares with holes. It is possible to present those reflections and rotations by combinations of the following basic transformations.

1. Transposing - 2 ways.
2. Swapping rows - 2 ways.
3. Swapping columns - 2 ways.

Two matrixes are called equivalent, when one of them can be transformed to another by a series of isomorphic transformations. How many are there non-equivalent or essentially different matrixes?

We should consider set of 8 composite isomorphic transformations. One can naively decide to divide number of matrixes by number of transformations to get number of essentially different matrixes. Right answer is - 6 essentially different matrixes, but not 2 (16/8). Here they are.

Code: Select all

M1   M2   M4   M5   M6   M16

00   00   00   01   01   11
00   01   11   10   11   11

These are orbits of all 16 matrixes (different matrixes are shown only).

Code: Select all

Orbits of binary 2 x 2 matrixes

M1

00
00

M2

00   00   01   10
01   10   00   00

M3

00   00   01   10
10   01   00   00

M4

00   01   10   11
11   01   10   00

M5

01   00   00   10
00   01   10   00

M6

01   00   10   11
01   11   10   00

M7

01   10
10   01

M8

01   10   11   11
11   11   01   10

M9

10   00   00   01
00   01   10   00

M10

10   01
01   10

M11

10   00   01   11
10   11   01   00

M12

10   01   11   11
11   11   01   10

M13

11   00   01   10
00   11   01   10

M14

11   01   10   11
01   11   11   10

M15

11   01   10   11
10   11   11   01

M16

11
11

As you can see, there are 6 different orbits (not equal to each other sets) - 3 orbits, containing 4 matrixes, 2 orbits, containing 2 matrixes, and 2 orbits, containing 1 matrix. Totally we have 3 x 4 + 2 x 2 + 2x 1 = 16 (different matrixes).

David, can you illustrate your questions by this example?

Serg

[Serg]

Hi!

I never wanted to be a Computational Scientist ... I wanted to be .... a lumberjack!

I never wanted to be a lumberjack ... I wanted to be ... Computational Scientist! (Not exactly, I wanted to be mathematician.) But now I work as a manager in small IT-company.

Do you want now to be a lumberjack?

Serg

[Serg]

Hi, Mathimagics!

And is there any strategy we could use to compensate for the error?

The problem we are discussed is very complicated (hello, Red Ed!). I don't know solution at the moment.

I think, we should firstly calculate number of equivalent P-Sudoku grids for MC grid (it is evidently P-Sudoku grid) - size of its orbit.

Serg

[Mathimagics]

Hey Serg,

I tried once to become a mathematician, but could not get my head around Group Theory !!

So I became a Computational Lumberjack ...

Specialising in search trees ...

[David P Bird]

Serg, thank you so much for taking all that effort for me!

I was taking your post explaining that the non-universal transformations accounting problem is not related to automorphisms accounting problem as being general theory. I therefore considered how it would apply to how I produce a canonical grid for a solution grid. I run through the 648 transformations and build the string in row-column order. As soon as the lexical value of the string exceeds that for the best transformation found so far, the procedure immediately jumps to the next transformation to test so it doesn't enumerate them.

I count how many times the canonical value repeats and call that the number of automorphisms. However, from your post that is not enough to determine how many transformations the grid has, not counting those that are duplicates. (This is something I have suspected before.) I then wondered if a different cell sequence was used to build the canonical value, it is possible that the apparent number of automorphisms would be different. This is when I posed my question to you.

Using your example as a crutch, I now realise that the number of automorphisms that would be reported in the example would always be 2, because the number of times a lexical value repeats is determined by the smallest orbit number - regardless of the cell sequence used. Therefore, the 'ignorant' assessment would be for 8 different grids, which is an overestimate (compared with 6) and an underestimate would be impossible.

I leave the far more complicated task of enumerating the possibilities to Mathimagics!

Thanks again Serg,
David
.

[coloin]

Hmmmmm....

i suppose we could easily find those grids with zero sudoku-p grids within - presumably this is the vast majority.

Where do we draw the line with different sudoku-p grids
each one has up to 36 trivial isomorphs - 6^2 with band swaps

another way of generating grids without sudoku-p grids within is to look at all the 181 ED 2-templates. [ 9x1 and 9x2]
If a 2-template has not got an isomorph which is sudoku-p compliant, then all grids with that 2-template are sudoku-p = zero

maybe a fruitful use for those 2-templates

[eleven]

Where do we draw the line with different sudoku-p grids
each one has up to 36 trivial isomorphs - 6^2 with band swaps

Also swapping rows/columns in all bands/stacks simultaneously and diagonal reflection preserves the sudokuP property. So you have 2*6^4=2592.

[Serg]

Hi, David!

Serg, thank you so much for taking all that effort for me!

Not at all!

I was taking your post explaining that the non-universal transformations accounting problem is not related to automorphisms accounting problem as being general theory. I therefore considered how it would apply to how I produce a canonical grid for a solution grid.

David, please note, that my statement applies to P-Sudoku solution grids only, not to "traditional"sudoku solution grids (in more wide sense it applies to sudoku solution grids with additional constraints, like vertically symmetry or full symmetry requirements). What kind of solution grid ("traditional" or P-Sudoku) do you mean?

I run through the 648 transformations and build the string in row-column order. As soon as the lexical value of the string exceeds that for the best transformation found so far, the procedure immediately jumps to the next transformation to test so it doesn't enumerate them.

I count how many times the canonical value repeats and call that the number of automorphisms. However, from your post that is not enough to determine how many transformations the grid has, not counting those that are duplicates. (This is something I have suspected before.) I then wondered if a different cell sequence was used to build the canonical value, it is possible that the apparent number of automorphisms would be different. This is when I posed my question to you.

The same question - what kind of solution grids do you mean?

Using your example as a crutch, I now realise that the number of automorphisms that would be reported in the example would always be 2, because the number of times a lexical value repeats is determined by the smallest orbit number - regardless of the cell sequence used.

I don't agree with you. We could expect orbits with 8 different matrixes (8 = 2^3 - total number of isomorphic transformations), but longest orbits contain 4 matrixes each. So, each matrix (M1-M16) has at least 2 automorphisms - matrixes with orbits of size 4 have 2 automorphisms exactly (8/4), matrixes with orbits of size 2 have 4 automorphisms (8/2) and matrixes with orbits of size 1 have 8 automorphisms (8/1). Actually, it's not normal that no matrixes have orbits of maximal possible size (8). This tells us that some transformations are redundant. And yes, one can see that transformation "Swapping columns" is not primitive - it is equivalent to "Transposing" + "Swapping rows" + "Transposing". So, we can reduce transformation set to 2 transformations only ("Transposing" and "Swapping rows"). This won't change orbits, and we'll get 1 automorphism (trivial) for matrixes with orbits of size 4, 2 automorphisms for matrixes with orbits of size 2 and 4 automorphisms for matrixes with orbits of size 1. (Hope, I am not wrong.)

Therefore, the 'ignorant' assessment would be for 8 different grids, which is an overestimate (compared with 6) and an underestimate would be impossible.

I disagree with you. Suppose we want to estimate number of essentially different matrixes without orbits/automorphisms calculations. We should assume in this case, that all matrixes have trivial automorphism ("Do nothing") only and have orbits of maximal possible sizes (8 matrixes per orbit for 3 basic transformations and 4 matrixes per orbit for 2 basic transformations). Because all orbits must be disjoint, 8 matrixes per orbit gives 2 essentially different matrixes (16/8), 4 matrixes per orbit gives 4 essentially different matrixes (16/4). I see underestimation in both cases!

Serg

[David P Bird]

Hi Serge,

I was only considering normal (traditional) grids, as your post did not define that your description was only for PSudoku grids.
If I find the canonical form repeats twice (what I assume is your orbit number) my 'ignorant' assumption would be that there were 648/2 = 324 different grids that were equivalent.
However within that set if subsets of cells had more repeats, some proportion of those 324 grids would be identical and so the total would have to be reduced.
I presume that would happen when there was partial symmetry in the distribution.

I'm dog tired now and am going to bed, but I post this in case you are a night owl.
I'll try to understand your post better tomorrow

David

[David P Bird]

Serge, I now appreciate that in your conversation with Mathimagics I previously misunderstood what you meant by 'orbits' and 'non-universal' transformations. The case I have been considering is for regular Sudoku grids, and the way I have considered how a full enumeration of all the possible transformations for one of these could produce duplicates is quite a different approach. The English phrase for this is that we have been 'talking at cross purposes'. I therefore apologise for wasting your time, as my posts were really off-topic for this thread.

Nevertheless, I feel I have gained from your posts as they have improved the way I think about the issues for regular puzzles, for which I owe you many thanks.

David

[Mathimagics]

I came across this in a document about non-existence of 16-clue Sudokus:

in actual fact there are only 560,151 essentially different grids having nontrivial automorphism group

Does anybody know where that figure comes from, and what it actually means?

All this Group Theory is messing with my head!

[Mathimagics]

in actual fact there are only 560,151 essentially different grids having nontrivial automorphism group

Well, nobody replied, but I worked it out, and in the process have learned some interesting facts that I will describe here.

Code: Select all

                 5,472,730,538  number of unique Sudoku solution grids
                     3,359,232  possible geometric permutations of solution grid
                       362,880  number of ways to renumber a grid

 6,671,248,172,291,458,990,080  5,472,730,538 * 3,359,232 * 362,880
 6,670,903,752,021,072,936,960  exact number of Sudoku solution grids
 -----------------------------
       344,420,270,386,053,120  grid deficiency


Now that last figure divided by 9! is 949,129,933,824, let's call this D.

D is exactly the number of "invariant grids" reported in the Russell & Jarvis table:

Code: Select all

Class  Size(N)       Invariants (A)
===================================
  1        1 18,383,222,420,692,992
  7       96             21,233,664
  8       16            107,495,424
  9      192              4,204,224
 10       64              2,508,084
 22     5184                323,928
 23    20736                    162
 24    20736                    288
 25      144             14,837,760
 26     1728                  2,592
 27      288                  5,184
 28      864              2,085,120
 29     3456                  1,296
 30     1728                294,912
 31     2304                    648
 32     1152              6,342,480
 37     1296             30,258,432
 40    10368                  1,854
 43    93312                    288
 79     2916            155,492,352
 86    69984                 13,056
134      972            449,445,888
135     3888                 27,648
142    31104                  6,480
143    15552                  1,728
144    15552                  3,456
145     7776                 13,824
===================================
T = Sum(N.A) 18,384,171,550,626,816
U = T / 3359232       5,472,730,538
===================================


The "grid deficiency" D is just the Sum of (N x A) in the table, but excluding the value for Class 1. So D = T - A(1).

Now there is another table, produced originally by gsf, that lists the number of essentially different grids by automorphism group:

Code: Select all

Aut#      Grids 
----------------
   1 5472170387   
   2     548449       
   3       7336       
   4       2826       
   6       1257       
   8         29       
   9         42       
  12         92       
  18         85       
  27          2       
  36         15       
  54         11       
  72          2       
 108          3       
 162          1       
 648          1       
===============
     5472730538      total   
   - 5472170387   
         560151 
===============


Now I'm not certain, but believe gsf produced this table independently, thus providing confirmation of Red Ed's results.

And I have done a little subtraction there at the end to find 560,151 which is the number I asked about.

Finally, an interesting fact about D = 949,129,933,824, the number of individual cases of automorphism identified by Russell & Jarvis. I'd have thought that to be a "fundamental" number in the Sudoku world, just as 5472730538 is.

Remarkably, a Google search for "Sudoku 949,129,933,824" turned up just one hit! That has never happened to me before - the hit was a sample page of a book called "Mathematical Sudoku Theory" (written in German).

Will this post make that search term now turn up TWO hits?