The New Sudoku Players' Forum

[eleven]

Not sure, what you are asking for.
T or t(1) is a transformation from the identity (cells 1,2,..,81) to a grid with cell orders X.
U or t(3) a transformation to a grid with cell orders Y.
So if you want to get from Y to X, you apply U'=t(32), then T.

If you do that for sudoku grids, for the different transformations you will have different renumberings to get the same puzzle again.
E.g. when for T1 you need a number cycle (123), for the inverse transformation it would be (132) (but it's the same for 1- and 2-cycles).

[Mathimagics]

What am I trying to do?

As I mentioned somewhere above, to find all "e-d SudokuP" (classical mode, ie: S-equivalence not the restricted P-equivalence) I have to run the 26 S-classes through the mill of the automorphism counter.

But I have to do more - the normal process just counts invariants for t(1) of each class, knowing that the number is the same for each t(n) in that class.

But this is not the case for SudokuP invariants. Each S-invariant needs individual checking.

We could use brute-force and expand all classes, generating every individual t(n), but that is a job of quite intimidating proportions.

This time could be greatly reduced, however, if only we could generate the n invariants corresponding to each t(n) for each t(1) invariant . There's a 1-1 correspondence, and I'm just trying to figure out what that correspondence is!

[Mathimagics]

Pitfalls indeed!

Have you seen estimated ed-SudokuP above?

Very strong evidence to suggest that the true count is under 180,000.

Take S-class 7 - it does not correspond to any P-class. And yet, we find on inspection that there are 556,146 SudokuP invariants in that class. These are simply not found by using P-classes, presumably because they can ONLY be automorphic for non-P transformations. But it took several hours to determine that number, and I'm trying to speed up the process.

I have marked with a * each S-class in that table that is in the same category.

[EDIT] Ooh! your post disappeared when I replied!

[eleven]

[EDIT] Ooh! your post disappeared when I replied!

Yes, i already saw, that i was missing something.

[Mathimagics]

I keep looking over my shoulder to see if I am there ...

[Serg]

Hi, Mathimagics!

• this table describes calculation of NUP = number of essentially P-different SudokuP grids, using restricted symmetry group GP of 2592 elements, with 54 conjugacy classes

• the GAP group definition will be listed below

• the "Class" number, C in first column identifies a conjugacy class (1 to 54) of GP, with class 1 = the identity transformation. These numbers correspond to those given by the GAP function ConjugacyClasses(SudokuP)

• the "Size" number, N in second column is number of elements in class #C

• the "Invariants" number, PA in 3rd column is the # of invariant (automorphic) grids in each element of the class (up to relabelling). This number for class #1 is the total # of different grids (which we already know), the rest are identified by my "Automorphism Enumerator", ie my reconstruction of Red Ed's "digit-template algorithm".

• the table lists only classes with non-zero invariants (20 of 54)

Please let me know if any errors/omissions are found in this description!

Very impressive work! It would be nice to crosscheck your result... But enumeration of essentially different SudokuP solution grids (when all 3,359,232 commonly used isomorphic transformations are allowed) is more complicated task. Good luck!

Serg

[Mathimagics]

Hi "Serg",

But enumeration of essentially different SudokuP solution grids (when all 3,359,232 commonly used isomorphic transformations are allowed) is more complicated task. Good luck!

Cheers!

I was hoping with your Group Theory expertise you might be able to shed some light on the problem I describe above ("what I am trying to do"), ie how to "generate" the invariants for same conjugacy class ... any thoughts?

[Mathimagics]

... this time could be greatly reduced, however, if only we could generate the n invariants corresponding to each t(n) for each t(1) invariant . There's a 1-1 correspondence, and I'm just trying to figure out what that correspondence is!

There may well be an answer to that question, but I now realise that it wouldn't matter! A quick recap of where we are at:

• we want to count the number of essentially different SudokuP grids, NUSP

• we are using an adapted form of Russell & Jarvis's conjugacy class model, but because SudokuP invariant grids are not evenly distributed for a given conjugacy class, we have to use brute-force to do the enumeration for all class members, ie we have to "unfold" the enumeration at the class level

• we enumerate the Sudoku invariants in each member of each class, and count those that are SudokuP

I was thinking we could somehow exploit the even distribution of Sudoku invariants across a conjugacy class, which R & J exploited for their enumeration of e-d Sudoku grids (they only needed to count invariants in a single member of each class, then multiply that count by the size of the class).

If there was a "magic" transformation that generated all the Sudoku invariants for a class, then this job would run more quickly.

But we'd then have to sacrifice a valuable optimisation that reduces job time already. This optimisation is based on the fact that we don't actually have to enumerate all the Sudoku invariants and then test each one for SudokuP property - we can monitor SudokuP compatibility at each level of the recursion, and this trims the search tree quite significantly.

Of course the savings in class processing offered by "invariant generation" might well outweigh the loss of this optimisation, but it's a moot point as we don't have that option just now, but we do have the search-tree optimisation available.

So we are running the "brute force class expansion" model, with the search-tree optimisation, and while it's a bit sluggish (there are thousands of class members in most of the active classes), it's going to take days, as against weeks it would most likely take without the optimisation.

In any case, the count will almost certainly be accurate, searching every applicable class member by member and counting the SudokuP invariants.

[Serg]

Hi, Mathimagics!

What am I trying to do?

As I mentioned somewhere above, to find all "e-d SudokuP" (classical mode, ie: S-equivalence not the restricted P-equivalence) I have to run the 26 S-classes through the mill of the automorphism counter.

But I have to do more - the normal process just counts invariants for t(1) of each class, knowing that the number is the same for each t(n) in that class.

But this is not the case for SudokuP invariants. Each S-invariant needs individual checking.

We could use brute-force and expand all classes, generating every individual t(n), but that is a job of quite intimidating proportions.

This time could be greatly reduced, however, if only we could generate the n invariants corresponding to each t(n) for each t(1) invariant . There's a 1-1 correspondence, and I'm just trying to figure out what that correspondence is!

Some words about estimated number of essentially different SudokuP solution grids.
As I wrote earlier, rough estimate of those grids can be obtained as follows:

Therefore, there must exist around (201,105,135,151,764,480/9!)/2,592 = 213,808,581 essentially different P-Sudoku solution grids (approx.).

Taking into account P-automorphisms of SudokuP solution grids (i.e. automorphisms within group of 2592 P-isomorphic transformations),

we should get number slightly higher than 213,808,581

And yes, you got 214,038,113 P-different SudokuP solution grids using classic Russell & Jarvis method involving conjugacy classes and Burnside's Lemma.
Now you should correct this number to get number of essentially different SudokuP solution grids. Accounting for connected orbits should decrease that number, but I think you should get about 212 millions of essentially different SudokuP solution grids. In any case "correction" must decrease "214,038,113" number.

The main problem of your method of essentially different SudokuP solution grids enumeration is your attempt to use "conjugacy classes" technique and Burnside's Lemma, but because basic requirements of Burnside's enumeration method are not met, it's not clear may we use conjugacy classes in this case. What are "26 S-classes" you are talking about in your post?

As I mentioned somewhere above, to find all "e-d SudokuP" (classical mode, ie: S-equivalence not the restricted P-equivalence) I have to run the 26 S-classes through the mill of the automorphism counter.

Serg

[Serg]

Hi, Mathimagics!
I have a proposal - to put aside the task of enumerating e-d SupokuP (temporarily). But discuss a task of enumerating e-d fully symmetrical patterns. This task is much simpler - there are 2^15 all different fully symmetrical patterns only. And the main benefit - right answer is known!

Serg

[eleven]

Mathimagics,

please can you post an example for the members/transformations of a class, maybe 7 ? I have no idea yet, what they look like, apart from trivial ones like repeating one or inverse ones.
The latter cannot give you new SudokuP's, therefore they need not to be tested.

[Mathimagics]

Hi Serg!

The main problem of your method of essentially different SudokuP solution grids enumeration is your attempt to use "conjugacy classes" technique and Burnside's Lemma, but because basic requirements of Burnside's enumeration method are not met, it's not clear may we use conjugacy classes in this case.

I am not using Burnside's Lemma, we agree that can't be used here. But we are still basically counting automorphic grids, and the conjugacy classes allow us to reduce the problem because only a small number of the 3,359,232 transformation elements can possibly be automorphic.

What are "26 S-classes" you are talking about in your post?

The 3,359,232 group elements for the Sudoku symmetry group partition into 275 conjugacy classes, and automorphism only occurs in 26 of these.

We use "S-class" to distinguish Sudoku group conjugacy classes from the "P-classes" of the "SudokuP" symmetry group (which has 2592 elements, and 54 conjugacy classes).

The class numbers we use correspond to the classes in the Russell & Jarvis paper quoted above, so these get used a lot in this forum.

So it is legitimate, and indeed necessary, to use conjugacy classes for counting problem based on S-equivalence, unless you want to waste time testing all 3,359,232 group elements.

For counting essentially different Sudoku grids, Burnside's Lemma reduces the problem still further, we need only count the automorphic grids in ONE element of each conjugacy class (ie one of the 26, all others we can ignore) and take the average over the group.

For counting essentially different SudokuP grids under S-equivalence, no we can't use the Burnside "trick", but we can still restrict ourselves to thos 26 classes, we just have to count automorphisms in every element of those classes. I call this "unfolding" the classes.

[Mathimagics]

Hi eleven,

I can certainly do that, S-class 8 has the fewest elements (16),so might be easiest to work with, but if you prefer working with class 7 (96 elements) I can give you those too.

The permutations are defined on the grid cells, and these are labelled 1 to 81. Is this ok for you? I can turn them into "rNcN" representation if necessary, just let me know.

The 1-1 correspondence only applies to Sudoku's, not SudokuP's. So not all SudokuP's in the class will still be SudokuP's under the hypothetical mapping.

Here is class 8 in the meanwhile:

Hidden Text: Show

Code: Select all

( 1, 2, 3)( 4, 5, 6)( 7, 9, 8)(10,11,12)(13,14,15)(16,18,17)(19,20,21)(22,23,24)(25,27,26)(28,29,30)(31,32,33)(34,36,35)(37,38,39)(40,41,42)(43,45,44)(46,47,48)(49,50,51)(52,54,53)(55,56,57)(58,59,60)(61,63,62)(64,65,66)(67,68,69)(70,72,71)(73,74,75)(76,77,78)(79,81,80),
( 1, 2, 3)( 4, 5, 6)( 7, 8, 9)(10,11,12)(13,14,15)(16,17,18)(19,20,21)(22,23,24)(25,26,27)(28,29,30)(31,32,33)(34,35,36)(37,38,39)(40,41,42)(43,44,45)(46,47,48)(49,50,51)(52,53,54)(55,56,57)(58,59,60)(61,62,63)(64,65,66)(67,68,69)(70,71,72)(73,74,75)(76,77,78)(79,80,81),
( 1, 2, 3)( 4, 6, 5)( 7, 9, 8)(10,11,12)(13,15,14)(16,18,17)(19,20,21)(22,24,23)(25,27,26)(28,29,30)(31,33,32)(34,36,35)(37,38,39)(40,42,41)(43,45,44)(46,47,48)(49,51,50)(52,54,53)(55,56,57)(58,60,59)(61,63,62)(64,65,66)(67,69,68)(70,72,71)(73,74,75)(76,78,77)(79,81,80),
( 1, 2, 3)( 4, 6, 5)( 7, 8, 9)(10,11,12)(13,15,14)(16,17,18)(19,20,21)(22,24,23)(25,26,27)(28,29,30)(31,33,32)(34,35,36)(37,38,39)(40,42,41)(43,44,45)(46,47,48)(49,51,50)(52,53,54)(55,56,57)(58,60,59)(61,62,63)(64,65,66)(67,69,68)(70,71,72)(73,74,75)(76,78,77)(79,80,81),
( 1, 3, 2)( 4, 5, 6)( 7, 9, 8)(10,12,11)(13,14,15)(16,18,17)(19,21,20)(22,23,24)(25,27,26)(28,30,29)(31,32,33)(34,36,35)(37,39,38)(40,41,42)(43,45,44)(46,48,47)(49,50,51)(52,54,53)(55,57,56)(58,59,60)(61,63,62)(64,66,65)(67,68,69)(70,72,71)(73,75,74)(76,77,78)(79,81,80),
( 1, 3, 2)( 4, 5, 6)( 7, 8, 9)(10,12,11)(13,14,15)(16,17,18)(19,21,20)(22,23,24)(25,26,27)(28,30,29)(31,32,33)(34,35,36)(37,39,38)(40,41,42)(43,44,45)(46,48,47)(49,50,51)(52,53,54)(55,57,56)(58,59,60)(61,62,63)(64,66,65)(67,68,69)(70,71,72)(73,75,74)(76,77,78)(79,80,81),
( 1, 3, 2)( 4, 6, 5)( 7, 9, 8)(10,12,11)(13,15,14)(16,18,17)(19,21,20)(22,24,23)(25,27,26)(28,30,29)(31,33,32)(34,36,35)(37,39,38)(40,42,41)(43,45,44)(46,48,47)(49,51,50)(52,54,53)(55,57,56)(58,60,59)(61,63,62)(64,66,65)(67,69,68)(70,72,71)(73,75,74)(76,78,77)(79,81,80),
( 1, 3, 2)( 4, 6, 5)( 7, 8, 9)(10,12,11)(13,15,14)(16,17,18)(19,21,20)(22,24,23)(25,26,27)(28,30,29)(31,33,32)(34,35,36)(37,39,38)(40,42,41)(43,44,45)(46,48,47)(49,51,50)(52,53,54)(55,57,56)(58,60,59)(61,62,63)(64,66,65)(67,69,68)(70,71,72)(73,75,74)(76,78,77)(79,80,81),
( 1,10,19)( 2,11,20)( 3,12,21)( 4,13,22)( 5,14,23)( 6,15,24)( 7,16,25)( 8,17,26)( 9,18,27)(28,37,46)(29,38,47)(30,39,48)(31,40,49)(32,41,50)(33,42,51)(34,43,52)(35,44,53)(36,45,54)(55,73,64)(56,74,65)(57,75,66)(58,76,67)(59,77,68)(60,78,69)(61,79,70)(62,80,71)(63,81,72),
( 1,10,19)( 2,11,20)( 3,12,21)( 4,13,22)( 5,14,23)( 6,15,24)( 7,16,25)( 8,17,26)( 9,18,27)(28,37,46)(29,38,47)(30,39,48)(31,40,49)(32,41,50)(33,42,51)(34,43,52)(35,44,53)(36,45,54)(55,64,73)(56,65,74)(57,66,75)(58,67,76)(59,68,77)(60,69,78)(61,70,79)(62,71,80)(63,72,81),
( 1,10,19)( 2,11,20)( 3,12,21)( 4,13,22)( 5,14,23)( 6,15,24)( 7,16,25)( 8,17,26)( 9,18,27)(28,46,37)(29,47,38)(30,48,39)(31,49,40)(32,50,41)(33,51,42)(34,52,43)(35,53,44)(36,54,45)(55,73,64)(56,74,65)(57,75,66)(58,76,67)(59,77,68)(60,78,69)(61,79,70)(62,80,71)(63,81,72),
( 1,10,19)( 2,11,20)( 3,12,21)( 4,13,22)( 5,14,23)( 6,15,24)( 7,16,25)( 8,17,26)( 9,18,27)(28,46,37)(29,47,38)(30,48,39)(31,49,40)(32,50,41)(33,51,42)(34,52,43)(35,53,44)(36,54,45)(55,64,73)(56,65,74)(57,66,75)(58,67,76)(59,68,77)(60,69,78)(61,70,79)(62,71,80)(63,72,81),
( 1,19,10)( 2,20,11)( 3,21,12)( 4,22,13)( 5,23,14)( 6,24,15)( 7,25,16)( 8,26,17)( 9,27,18)(28,37,46)(29,38,47)(30,39,48)(31,40,49)(32,41,50)(33,42,51)(34,43,52)(35,44,53)(36,45,54)(55,73,64)(56,74,65)(57,75,66)(58,76,67)(59,77,68)(60,78,69)(61,79,70)(62,80,71)(63,81,72),
( 1,19,10)( 2,20,11)( 3,21,12)( 4,22,13)( 5,23,14)( 6,24,15)( 7,25,16)( 8,26,17)( 9,27,18)(28,37,46)(29,38,47)(30,39,48)(31,40,49)(32,41,50)(33,42,51)(34,43,52)(35,44,53)(36,45,54)(55,64,73)(56,65,74)(57,66,75)(58,67,76)(59,68,77)(60,69,78)(61,70,79)(62,71,80)(63,72,81),
( 1,19,10)( 2,20,11)( 3,21,12)( 4,22,13)( 5,23,14)( 6,24,15)( 7,25,16)( 8,26,17)( 9,27,18)(28,46,37)(29,47,38)(30,48,39)(31,49,40)(32,50,41)(33,51,42)(34,52,43)(35,53,44)(36,54,45)(55,73,64)(56,74,65)(57,75,66)(58,76,67)(59,77,68)(60,78,69)(61,79,70)(62,80,71)(63,81,72),
( 1,19,10)( 2,20,11)( 3,21,12)( 4,22,13)( 5,23,14)( 6,24,15)( 7,25,16)( 8,26,17)( 9,27,18)(28,46,37)(29,47,38)(30,48,39)(31,49,40)(32,50,41)(33,51,42)(34,52,43)(35,53,44)(36,54,45)(55,64,73)(56,65,74)(57,66,75)(58,67,76)(59,68,77)(60,69,78)(61,70,79)(62,71,80)(63,72,81)


[eleven]

Thanks, i see now.
In the first half addidtionally columns are swapped, in the second half rows.
So i think, that for SudokP's you would have to test each of them either in this class.
Or will the counts be the same ?

[Mathimagics]

Serg, I'm happy to to discuss symmetric patterns, indeed it sounds interesting, but I suggest we do so in a separate thread, which you can start, as I want to pursue our Sudoku transformations discussion with eleven here.