## Unique Sudokus (Russell & Jarvis)

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

### Re: Unique Sudokus (Russell & Jarvis)

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?

Mathimagics
2017 Supporter

Posts: 1480
Joined: 27 May 2015
Location: Canberra

### Re: Unique Sudokus (Russell & Jarvis)

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
.
David P Bird
2010 Supporter

Posts: 1042
Joined: 16 September 2008
Location: Middle England

### Re: Unique Sudokus (Russell & Jarvis)

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

Mathimagics
2017 Supporter

Posts: 1480
Joined: 27 May 2015
Location: Canberra

### Re: Unique Sudokus (Russell & Jarvis)

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  M1600   00   00   00   01   01   01   01   10   10   10   10   11   11   11   1100   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   M1600   00   00   01   01   1100   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 matrixesM10000M200   00   01   1001   10   00   00M300   00   01   1010   01   00   00M400   01   10   1111   01   10   00M501   00   00   1000   01   10   00M601   00   10   1101   11   10   00M701   1010   01M801   10   11   1111   11   01   10M910   00   00   0100   01   10   00M1010   0101   10M1110   00   01   1110   11   01   00M1210   01   11   1111   11   01   10M1311   00   01   1000   11   01   10M1411   01   10   1101   11   11   10M1511   01   10   1110   11   11   01M161111`

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
2018 Supporter

Posts: 690
Joined: 01 June 2010
Location: Russia

### Re: Unique Sudokus (Russell & Jarvis)

Hi!
Mathimagics wrote: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
2018 Supporter

Posts: 690
Joined: 01 June 2010
Location: Russia

### Re: Unique Sudokus (Russell & Jarvis)

Hi, Mathimagics!
Mathimagics wrote: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
Serg
2018 Supporter

Posts: 690
Joined: 01 June 2010
Location: Russia

### Re: Unique Sudokus (Russell & Jarvis)

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 ...

Mathimagics
2017 Supporter

Posts: 1480
Joined: 27 May 2015
Location: Canberra

### Re: Unique Sudokus (Russell & Jarvis)

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
.
David P Bird
2010 Supporter

Posts: 1042
Joined: 16 September 2008
Location: Middle England

### Re: Unique Sudokus (Russell & Jarvis)

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
coloin

Posts: 1861
Joined: 05 May 2005

### Re: Unique Sudokus (Russell & Jarvis)

coloin wrote: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.
eleven

Posts: 2241
Joined: 10 February 2008

### Re: Unique Sudokus (Russell & Jarvis)

Hi, David!
David P Bird wrote:Serg, thank you so much for taking all that effort for me!

Not at all!
David P Bird wrote: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?
David P Bird wrote: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?
David P Bird wrote: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.)
David P Bird wrote: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
Serg
2018 Supporter

Posts: 690
Joined: 01 June 2010
Location: Russia

### Re: Unique Sudokus (Russell & Jarvis)

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
2010 Supporter

Posts: 1042
Joined: 16 September 2008
Location: Middle England

### Re: Unique Sudokus (Russell & Jarvis)

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
David P Bird
2010 Supporter

Posts: 1042
Joined: 16 September 2008
Location: Middle England

### Re: Unique Sudokus (Russell & Jarvis)

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
2017 Supporter

Posts: 1480
Joined: 27 May 2015
Location: Canberra

### Re: Unique Sudokus (Russell & Jarvis)

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,056134      972            449,445,888135     3888                 27,648142    31104                  6,480143    15552                  1,728144    15552                  3,456145     7776                 13,824===================================T = Sum(N.A) 18,384,171,550,626,816U = 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?
Last edited by Mathimagics on Mon Jan 22, 2018 1:40 am, edited 1 time in total.

Mathimagics
2017 Supporter

Posts: 1480
Joined: 27 May 2015
Location: Canberra

PreviousNext