The New Sudoku Players' Forum

by **Mathimagics** » Tue Jan 09, 2018 6:24 pm

Not long at all - each class took 20 to 30 mins, which I ran in 3 parallel streams (god bless multiple core CPU's!) so all completed in a couple of hours. 8-)

by **Mathimagics** » Tue Jan 09, 2018 6:32 pm

Interesting that the number of unique grids (6.5 billion) is similar to standard Sudoku (5.5 billion).

One is tempted to actually write them to disk thus being able to rapidly generate random SudokuP's on demand.

I estimate 235GB for 9 x 32 bit value format which fits comfortably on my drive, so no point really in "efficient" and/or tricky encodings.

by **Serg** » Tue Jan 09, 2018 11:41 pm

Hi, Mathimagics!

Mathimagics wrote:Interesting that the number of unique grids (6.5 billion) is similar to standard Sudoku (5.5 billion).

What do you say about? What is "unique grids" and by what method did you calculate 6.5 billion?

Serg

by **Mathimagics** » Wed Jan 10, 2018 9:19 am

Hi serg

My mistake, I shouldn't have used the word "unique"!

What meant was that we only need to store the 6,541,667,097 representative SudokuP grids corresponding to the 11 solved classes in order to represent the complete space of 201,105,135,151,764,480 different SudokuP grids.

From each different solution case for a given class with NE > 1 we can transform each grid into NE different grids by applying the same transformation that identified the class equivalence in the first place (obviously we need to remember these!).

As for uniqueness, that's really a different matter, which I will address shortly ...

by **Serg** » Sat Jan 13, 2018 7:38 pm

Hi, Mathimagics!

Mathimagics wrote:Table of Class #, NE = number of equivalent classes, NG = number of grids, total = NE * NG:

Code: Select all
# NE SudokuP Total SudokuP ------------------------------------------ 1 1 969,349,902 969,349,902 2 18 728,290,886 13,109,235,948 3 12 655,641,170 7,867,694,040 4 36 606,126,844 21,820,566,384 5 36 595,526,742 21,438,962,712 6 72 517,948,382 37,292,283,504 7 9 598,102,466 5,382,922,194 8 4 490,762,646 1,963,050,584 9 36 547,152,562 19,697,492,232 10 18 458,804,480 8,258,480,640 11 2 373,961,017 747,922,034 ------------------------------------------ 244 6,541,667,097 138,547,960,174

And 138,547,960,174 x 4 x 362,880 = 201,105,135,151,764,480

I've done all these calculations and confirm your (and Red Ed's ) results.

I confirm that there are 244 9-cell templates for "1" digit with following properties:
1. Cell r1c1 contains "1" digit.
2. Every cell of template "doesn't see" another template's cell - every row/column/P-set contains 1 cell of given template exactly.
3. If template's cell is located in B2 box, this cell must occupy r2 row.
4. If template's cell is located in B3 box, this cell must occupy r3 row.
5. If template's cell is located in B4 box, this cell must occupy c2 column.
6. If template's cell is located in B7 box, this cell must occupy c3 column.

Those 244 templates form 11 equivalence classes on the base of these isomorphic transformations:
1. Transposing - 2 ways.
2. Permutations of 3 bands - 6 ways.
3. Permutations of 3 stacks - 6 ways.
4. The same permutations of rows in every band - 6 ways.
5. The same permutations of columns in every stack - 6 ways.

Totally we have 2 x 6^4 = 2592 isomorphic transformations.

There are 976 templates for each other (not "1") digits. (Each template's cell is located in unique row/column/P-set and contains appropriate cell in B1 box.)
I counted all possible templates combinations giving P-sudoku and got the same numbers of P-sudoku grids in each class as Mathimagics exactly. Runnung times for every class processing varied from 52 minutes (class 11) to 2 hours (class 1) - it is comparable with Mathimagics timings, taking into account that my program used 1 CPU core.

It is surprising, that eleven found that Red Ed's post with "201,105,135,151,764,480" number. Well done, eleven!

But maybe it's more surprising, that nobody answered Red Ed. Such remarkable work was left completely unnoticed

.

Serg

by **eleven** » Sat Jan 13, 2018 9:02 pm

Serg wrote:It is surprising, that eleven found that Red Ed's post with "201,105,135,151,764,480" number. Well done, eleven!

It's on wikipedia's site "Mathematics of Sudoku". So as soon as Coloin revealed that SudokuP is the same as "Disjoint Groups", it was easy to find.

by **Mathimagics** » Sun Jan 14, 2018 2:14 pm

It seems that we can't easily identify the number of essentially diferent SudokuP grids in the same way that works for Sudoku (ie: using Burnside's lemma).

But we can still count the number of automorphic SudokuP grids, and do so very quickly (< 2 minutes). That turns out to be 78,257,944 (ignoring relabelling).

These occur in just 2 types of transformations (ie in just 2 of 54 conjugacy classes). Examples of each type are given below:

Type 1 (328,816 cases):

Code: Select all: G ==> T(G) 1 2 3 | 4 5 6 | 7 8 9 6 4 5 | 9 7 8 | 3 1 2 7 8 9 | 1 2 3 | 4 5 6 3 1 2 | 6 4 5 | 9 7 8 4 5 6 | 7 8 9 | 1 2 3 9 7 8 | 3 1 2 | 6 4 5 --------------------- --------------------- 2 1 7 | 6 3 4 | 5 9 8 4 6 3 | 8 5 9 | 7 2 1 5 9 8 | 2 1 7 | 6 3 4 7 2 1 | 4 6 3 | 8 5 9 6 3 4 | 5 9 8 | 2 1 7 8 5 9 | 7 2 1 | 4 6 3 --------------------- --------------------- 9 7 1 | 3 6 2 | 8 4 5 2 3 6 | 5 8 4 | 1 9 7 8 4 5 | 9 7 1 | 3 6 2 1 9 7 | 2 3 6 | 5 8 4 3 6 2 | 8 4 5 | 9 7 1 5 8 4 | 1 9 7 | 2 3 6 G ==> T(G) 1 2 3 | 4 5 6 | 7 8 9 8 7 9 | 1 3 2 | 6 4 5 5 4 6 | 7 8 9 | 3 2 1 3 1 2 | 6 4 5 | 9 7 8 7 9 8 | 3 2 1 | 4 5 6 6 5 4 | 9 7 8 | 1 3 2 --------------------- --------------------- 6 3 4 | 8 7 5 | 9 1 2 2 9 1 | 4 6 3 | 5 8 7 8 7 5 | 9 1 2 | 6 3 4 4 6 3 | 5 8 7 | 2 9 1 9 1 2 | 6 3 4 | 8 7 5 5 8 7 | 2 9 1 | 4 6 3 --------------------- --------------------- 3 6 1 | 5 4 7 | 2 9 8 9 2 8 | 3 1 6 | 7 5 4 4 5 7 | 2 9 8 | 1 6 3 1 3 6 | 7 5 4 | 8 2 9 2 8 9 | 1 6 3 | 5 4 7 7 4 5 | 8 2 9 | 3 1 6

Type 2 ( 77,929,128 cases):

Code: Select all: G ==> T(G) 1 2 3 | 4 5 6 | 7 8 9 1 3 2 | 7 9 8 | 4 6 5 7 8 9 | 1 2 3 | 4 5 6 4 6 5 | 1 3 2 | 7 9 8 4 5 6 | 7 8 9 | 1 2 3 7 9 8 | 4 6 5 | 1 3 2 --------------------- --------------------- 2 1 4 | 5 9 8 | 6 3 7 3 1 7 | 9 5 6 | 8 2 4 6 3 7 | 2 1 4 | 5 9 8 8 2 4 | 3 1 7 | 9 5 6 5 9 8 | 6 3 7 | 2 1 4 9 5 6 | 8 2 4 | 3 1 7 --------------------- --------------------- 3 7 1 | 8 4 2 | 9 6 5 2 4 1 | 6 7 3 | 5 8 9 9 6 5 | 3 7 1 | 8 4 2 5 8 9 | 2 4 1 | 6 7 3 8 4 2 | 9 6 5 | 3 7 1 6 7 3 | 5 8 9 | 2 4 1 G ==> T(G) 1 2 3 | 4 5 6 | 7 8 9 1 3 2 | 7 9 8 | 4 6 5 6 5 4 | 8 7 9 | 3 2 1 8 9 7 | 6 4 5 | 2 3 1 8 7 9 | 2 1 3 | 6 5 4 6 4 5 | 3 1 2 | 8 9 7 --------------------- --------------------- 5 6 7 | 3 9 4 | 8 1 2 9 8 4 | 2 5 7 | 6 1 3 4 9 2 | 1 8 7 | 5 6 3 7 5 3 | 1 6 4 | 9 8 2 3 8 1 | 5 6 2 | 4 9 7 2 6 1 | 9 8 3 | 7 5 4 --------------------- --------------------- 9 4 8 | 6 3 1 | 2 7 5 5 7 6 | 8 2 1 | 3 4 9 2 1 6 | 7 4 5 | 9 3 8 3 1 8 | 4 7 9 | 5 2 6 7 3 5 | 9 2 8 | 1 4 6 4 2 9 | 5 3 6 | 1 7 8

by **eleven** » Sun Jan 14, 2018 6:09 pm

It's not clear to me, what you are doing here. What do you mean by automorphic SudokuP grids ? What are the transformations you apply ?
What i see is that your right sides are renumbered grids of the left side, and the first examples of both cases have an automorphism with Gliding Row symmetry (move the stacks right and the rows in all bands down to get the same grid).
For the other 2 examples i could not identify an automorphism symmetry (looking at the minirows).

by **Mathimagics** » Sun Jan 14, 2018 10:24 pm

My apologies, eleven! The dog ate my description of what these examples represent and how they were produced.

The methodology is (or should be ) an emulation of the Russell & Jarvis method described in:

"There are 5,472,730,538 essentially different Sudoku grids"

and currently being discussed in companion thread "Unique Sudokus (Russell & Jarvis)".

So I used GAP to obtain a set of 54 conjugacy classes from the reduced permutation group defined just like theirs, but with only permutations of rows/cols in all 3 bands/stacks, not individual bands/stacks. This reflects the fact that only those transformations guarantee preservation of SudokuP property.

I then counted the number of automorphic (aka "invariant") grids for a representative transformation T of each class. Automorphic/invariant means that a grid G when transformed by T is just a relabelled G.

Only 2 of the 54 conjugacy classes produced automorphisms, you may recall that for normal Sudoku this figure was 26 of 175 classes.

============================================
Now, about those specific examples above! They are the first and last entries in the automorphism lists produced by my automorphism enumerator program for the two transformations T1 and T2 corresponding to the two conjugacy classes with automorphisms.

What exactly, however, are T1 and T2? The problem with the GAP results is that you get for each class a more-or-less random representative T, expressed in terms of cycles. These are not easily translated into combination of grid transformations to which they correspond.

Your observation of the same symmetry obvious in the first grid of each pair is, I think, just a case of those particular grids having multiple automorphisms, ie they are invariant under more than one T.

The two T's used for the examples are given below in their cyclic form, if anyone wants to verify that the examples above really are kosher. Actually it would be nice if somebody did just that! 8-)

They are listed as one cycle per line, each being a list of cell indices, along with the (R,C) pairs for each cell index.

T1:

Hidden Text: Show

T2:

Hidden Text: Show

by **Mathimagics** » Sun Jan 14, 2018 10:52 pm

Mathimagics wrote:But we can still count the number of automorphic SudokuP grids, and do so very quickly (< 2 minutes). That turns out to be 78,257,944 (ignoring relabelling).

Aha, that doesn't take into account multiple automorphisms, does it! For completeness I still need to identify the number of grids with 1 or more non-trivial automorphism. I think this has been done for standard Sudoku?

by **eleven** » Sun Jan 14, 2018 11:32 pm

Your first class has a mini-diagonal symmetry, move the columns right and the rows down in each stack/band (and renumber the 3-cycles). It is listed as number 10 in Red Ed's table.
But i can't find that in your example.
Your second one is not listed in that table, and i doubt, that it defines an automorphism for sudoku grids.
Instead i would expect Red Ed's classes 8,10,22,25,32,37,40,43,79,86,143,135,142,145 in your list, because they all don't use single row/column swaps (only those in all bands/stacks).

by **Mathimagics** » Mon Jan 15, 2018 12:39 am

eleven wrote:Your first class has a mini-diagonal symmetry, move the columns right and the rows down in each stack/band (and renumber the 3-cycles). It is listed as number 10 in Red Ed's table.
But i can't find that in your example.

Ok, I really need to look into that, thanks!

eleven wrote:Your second one is not listed in that table, and i doubt, that it defines an automorphism for sudoku grids.

Isn't Red Ed's table just a list of one representative for each class? My class 1 rep happens to coincide with his class 10,rep but that's not always going to happen. GAP doesn't provide class representatives in any particular order.

eleven wrote:Instead i would expect Red Ed's classes 8,10,22,25,32,37,40,43,79,86,143,135,142,145 in your list, because they all don't use single row/column swaps (only those in all bands/stacks).

They should presumably correspond (but not necessarily with matching representatives) to classes in my full list of 54, but don't necessarily produce automorphisms for SudokuP.

I have given my set of 54 class representatives here in GAP format, perhaps you can find anomalies. I will double check my examples.

Thanks for the feedback! 8-)

Hidden Text: Show

by **Mathimagics** » Mon Jan 15, 2018 1:53 am

Hi eleven!

I have double-checked the grids above, and believe that you have confused symmetry with automorphism.

It is simply not true to say that the T transformation corresponding to Ed's class 10 is equivalent to "move the columns right and the rows down in each stack/band (and renumber the 3-cycles)".

What T actually does is, among other things, to cycle each mini-diagonal, and you can see in both examples it has done exactly that in every block. The remaining 6 cells in each block are cycled the same way in each block.

If you look at the cycle list you can see that's exactly what it does.

What you observe in case 1 as "G is itself shifted right one band and one row down" is a symmetry property of that particular G, and indeed one that is preserved by T, but isn't the same as T.

eleven wrote:Your second one is not listed in that table, and i doubt, that it defines an automorphism for sudoku grids.

The second pair of grids is also valid, and on inspection of the cycle list, I can now see that the transformation here is easily recognised as permuting the columns of G to 132798465.
[EDIT and permuting the rows to 132798465]

When applied to both examples, this gives T(G), which is just a relabelling, for these particular G's. So they too are automorphic.

The T's don't define automorphisms, they just identify valid grid transformations. A given grid is either automorphic, ie. invariant under one or more of these transformations, or not.

by **coloin** » Mon Jan 15, 2018 11:04 am

Mathimagics wrote:But we can still count the number of automorphic SudokuP grids, and do so very quickly (< 2 minutes). That turns out to be 78,257,944 (ignoring relabelling).
Aha, that doesn't take into account multiple automorphisms, does it! For completeness I still need to identify the number of grids with 1 or more non-trivial automorphism. I think this has been done for standard Sudoku?

201,105,135,151,764,480 = no of different sudoku-p grids

/ 9!
/6^8 * 2

so there are only at most 164975 grids which have a sudoku-p grid

some will have only 1 sudoku-p grid and many will have >1

is this correct ?

by **Mathimagics** » Mon Jan 15, 2018 1:17 pm

Hi coloin,

I don't think it makes sense to divide by 6 ^ 8 * 2 = 3,359,232, the applicable figure is 6 ^ 4 * 2 = 2,592 .

A quick recap of the state of play:

For normal Sudoku, we have:

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 = 949,129,933,824 x 362,880 (# of automorphisms)

Russell & Jarvis counted the # of automorphisms, from which they then obtained the number of unique (essentially different) grids.

For SudokuP we have:

Code: Select all: ? number of unique SudokuP solution grids 2,592 possible geometric permutations of solution grid 362,880 number of ways to renumber a grid ?? = ? * 2,592 * 362,880 201,105,135,151,764,480 exact number of SudokuP solution grids ----------------------- 28,398,242,718,720 = 78,257,944 * 362,880 (# of automorphisms)

Our problem is that no integer ? balances this account! As Serg has explained, this is due to the problem of non-universality of isomorphisms in SudokuP, in other words the non-applicability of Burnside's Lemma.

The New Sudoku Players' Forum

SudokuP - Analysis

Re: SudokuP - Frequency Analysis

Re: SudokuP - Frequency Analysis

Re: SudokuP - Frequency Analysis

Re: SudokuP - Frequency Analysis

Re: SudokuP - Frequency Analysis

Re: SudokuP - Frequency Analysis

Re: SudokuP - Frequency Analysis

Re: SudokuP - Frequency Analysis

Re: SudokuP - Frequency Analysis

Re: SudokuP - Frequency Analysis

Re: SudokuP - Frequency Analysis

Re: SudokuP - Frequency Analysis

Re: SudokuP - Frequency Analysis

Re: SudokuP - Frequency Analysis

Re: SudokuP - Frequency Analysis