The New Sudoku Players' Forum

[eleven]

Mathimagics,

ok, your second transformation is a 180 degree rotation. It is hard to spot in this form. If you bring the puzzle into "normal form" with the fixed cell in the center, it does not have the SudkuP property.
You should explicitly say, what an automorphism for the SudokuP grids is for you.
E.g. a SudokuP grid with mini-row symmetry can have a classical morph to another SudokuP grid, i.e. they are classical equivalent. But i guess, that they are essential different SudokuP grids, if one cannot be morphed to the other inside the SudokuP space, i.e. using only the 2*6^4 SudokuP transformations.

[Mathimagics]

But i guess, that they are essentially different SudokuP grids, if one cannot be morphed to the other inside the SudokuP space, i.e. using only the 2*6^4 SudokuP transformations.

Indeed! I'm sorry that I didn't make that clear.

ok, your second transformation is a 180 degree rotation. It is hard to spot in this form. If you bring the puzzle into "normal form" with the fixed cell in the center, it does not have the SudkuP property.

Are you referring to T2 above? That permutes both rows and columns using pattern 132798465. How is that any kind of rotation?

What is "normal form"?

[eleven]

The normal form is a "user-defined" morph, where the symmetry can be easiliy seen.
For your last example it is

Code: Select all

     1 6 4 | 5 7 3 | 8 2 9
     9 8 3 | 6 2 1 | 5 4 7
     2 5 7 | 8 9 4 | 1 3 6
     ------------------- --
     6 4 5 | 9 8 7 | 3 1 2
     7 9 8 | 3 1 2 | 6 5 4 
     3 1 2 | 4 6 5 | 9 7 8
     ------------------- --
     8 2 1 | 7 5 6 | 4 9 3
     4 7 9 | 1 3 8 | 2 6 5
     5 3 6 | 2 4 9 | 7 8 1

Now the fixed cell (was r1c1) is in the center, and if you rotate it by 180 degree (or apply reflection by both diagonals) you get a morph, which transforms to the same grid with the number cycles (1)(23)(47)(68)(59).
This can be easiliy seen, because each cell row n,column m has the relabel digit in the "opposite" cell row (10-m), column (10-n) (e.g. 5r3c2/9r7c8).

Back to your transformations.
This grid

Code: Select all

 +-------+-------+-------+
 | 8 3 2 | 1 7 9 | 6 4 5 |
 | 1 7 6 | 5 4 8 | 3 2 9 |
 | 9 4 5 | 6 3 2 | 1 8 7 |
 +-------+-------+-------+
 | 2 5 3 | 4 9 6 | 7 1 8 |
 | 6 9 4 | 8 1 7 | 2 5 3 |
 | 7 1 8 | 2 5 3 | 4 9 6 |
 +-------+-------+-------+
 | 3 2 7 | 9 8 1 | 5 6 4 |
 | 4 8 1 | 7 6 5 | 9 3 2 |
 | 5 6 9 | 3 2 4 | 8 7 1 |
 +-------+-------+-------+

is a sudokuP with (only) a stick symmetry (in normal form). In the middle mini-columns of band 2 you have the 9 fixed cells with digits 159. The mini-columns left and right of them are exchanged by the transformation. The left mini-columns of band 1 go to the right of band 3 in the same stack and vice versa. And the middle of band 1 change with the middle of band 3.
The transformation can be performed by swapping bands 13 and columns 13,46 and 79. So it keeps the SudokuP property. The number cycles are (1)(5)(9)(23)(46)(78).

Code: Select all

 +-------+-------+-------+
 | 7 2 3 | 1 8 9 | 4 6 5 |
 | 1 8 4 | 5 6 7 | 2 3 9 |
 | 9 6 5 | 4 2 3 | 1 7 8 |
 +-------+-------+-------+
 | 3 5 2 | 6 9 4 | 8 1 7 |
 | 4 9 6 | 7 1 8 | 3 5 2 |
 | 8 1 7 | 3 5 2 | 6 9 4 |
 +-------+-------+-------+
 | 2 3 8 | 9 7 1 | 5 4 6 |
 | 6 7 1 | 8 4 5 | 9 2 3 |
 | 5 4 9 | 2 3 6 | 7 8 1 |
 +-------+-------+-------+

Red Ed's class for that is number 134.

[eleven]

This is a puzzle with (only) diagonal symmetry with a SudokuP automorph.

Code: Select all

 +-------+-------+-------+
 | 1 4 8 | 7 3 2 | 5 9 6 |
 | 5 3 6 | 4 9 8 | 1 7 2 |
 | 9 7 2 | 5 1 6 | 4 3 8 |
 +-------+-------+-------+
 | 6 5 4 | 3 7 9 | 8 2 1 |
 | 3 8 1 | 6 2 4 | 7 5 9 |
 | 2 9 7 | 8 5 1 | 3 6 4 |
 +-------+-------+-------+
 | 4 1 5 | 9 6 3 | 2 8 7 |
 | 8 6 3 | 2 4 7 | 9 1 5 |
 | 7 2 9 | 1 8 5 | 6 4 3 |
 +-------+-------+-------+

It should be this class in your transformations.
(2,10)(3,19)(4,28)(5,37)(6,46)(7,55)(8,64)(9,73)(12,20)(13,29)(14,38)(15,47)(16,56)(17,65)(18,74)(22,30)(23,39)(24,48)(25,57)(26,66)(27,75)(32,40)(33,49)(34,58)(35,67)(36,76)(42,50)(43,59)(44,68)(45,77)(52,60)(53,69)(54,78)(62,70)(63,79)(72,80)
Coud not find a sticks symmetry there.

[Mathimagics]

There certainly is something about Conjugacy Class #134 that is unusual.

Looking at the Russell & Jarvis table of classes and automorphism counts (aka "# of invariant grids"), it has the most (449,445,888).

So for my automorphism enumerator, it should take the longest. But I notice that for every digit template based on cell (1,1) the count is exactly the same. I haven't found any other class (yet) that exhibits this behaviour.

I'm still trying to wrap my brain around this. Can you give a link to where "normal form" is defined?

[Mathimagics]

It should be this class in your transformations.

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

Actually it isn't! It's one of the operators in the Sudoku group definition.

[eleven]

Can you give a link to where "normal form" is defined?

See here.

[Mathimagics]

Ok, I'm getting there, slowly ...

Please bear with me as I have no background in Group Theory (obviously!)

Wrt the "standard Sudoku" symmetry group G, we have 275 conjugacy classes, C(n), only 26 of which support automorphisms. Each class is a set {T(n)} of "equivalent" transformations.

If a grid X has a symmetry property (automorphism) for a given class (ie. T(X) => X for some T in {T(n)}), then for each T in {T(n)} there is some "mapping morph" t such that t(X) is automorphic under T.

For each class there is a preferred choice of T that best demonstrates the symmetry for that class, and any grid X that is automorphic under this T is called a normalised form.

Assuming I have that right, how do we determine the mapping transformation t? That is, if Ta and Tb are transformations in the same class, and Ta(X) => X, how do we transform X into Y so that Tb(Y) => Y?

[EDIT] Aha, it looks like t = Ta ^ Tb, where ^ is conjugation, right?

[EDIT] And yes, I now see that T2 is essentially 180-degree rotation! Phew ...

[eleven]

Think you already found that out.

If a grid a is automorph with a transformation T, T(a)=a, and b is a morph of a, i.e. there is a transformation U(b)=a, then (with U' being the inverse transformation U'(a)=b), UTU' is an automorph transformation for b:
UTU'(b) = U'(T(U(b)) = U'(T(a))=U'(a)=b
In words: transform it to a, make the automorph transformation, you get a again, and transform it back to b.
(So UTU' is in the same class.)

[Serg]

Hi, Mathimagics!
Last days I pondered mathematical ways to enumerate essentially different P-Sudoku solution grids. But I didn't invent anything. So, I am forced to consider computational approach. No Group Theory, conjugacy classes, etc.

Approx. number of essentially different P-Sudoku solution grids must be equal to "Number of different P-Sudokus sol. grids"/"Number of permitted isomorphic transformations". For this estimation we can consider isomorphic transformations, which transform any valid P-Sudoku solution grid to another valid P-Sudoku solution grid. So, we should consider following (group of) P-Sudoku 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.

Therefore, there must exist around (201,105,135,151,764,480/9!)/2,592 = 213,808,581 essentially different P-Sudoku solution grids (approx.). Then we must take into account automorphisms and connecting orbits to get exact number.

First, I am going to define "P-Sudoku metric". This is ordered set of numbers, defining any P-Sudoku solution grid in unique way, i.e. different P-Sudoku solution grids must have different metrics. Such metric should be compatible with mentioned above "P-Sudoku solution grid equivalence classes" (11 classes) to use results of the "all-different" P-Sudoku solution grids enumeration. Here is my P-Sudoku metric definition.

1. We must reduce P-Sudoku solution grid to canonical view, i.e. we must relabel B1 box to provide "right" numeration (r1: "1","2","3"; r2: "4","5","6"; r3: "7","8","9").
2. Then we should swap or not stacks B258 and B369 to provide location of digits "1" in row r2 of B2 box and in row r3 of B3 box (similarly to P-Sudoku solution grid equivalence classes). Swapping or not bands B456 and B789 must provide location of digits "1" in column c2 of B4 box and in column c3 of B7 box.
3. Now we are ready to calculate metric. First part of the metric - list of column numbers of digits "1" in a grid (row may have numbers 0,1,...,8). For example, grid's fragment

Code: Select all

 1 2 3 . . . . . .
 4 5 6 1 . . . . .
 7 8 9 . . . 1 . .
 . 1 . . . . . . .
 . . . . 1 . . . .
 . . . . . . . 1 .
 . . 1 . . . . . .
 . . . . . 1 . . .
 . . . . . . . . 1

has "one's list" - (0,3,1,4,7,2,5,8).
4. In similar manner we should calculate lists for "2","3",... "9" digits. At the end we'll get 9 lists of numbers (each list contains 9 numbers).

When we compare 2 metrics (for 2 P-Sudoku solution grids) we must compare first one's lists, number by number. If a metric has higher number in the same position of the list, this metric is higher. If one's lists contain the same numbers in the same positions, we must process list for "2" digit, and so on.

Now we are ready to define "minimal form" of P-Sudoku solution grid. It is P-Sudoku with minimal metric among 2592 isomorhic images of the given P-Sudoku solution grid. We should count all P-Sudoku solution grid, having minimal form.

It turns out, that we need only to count P-Sudoku solution grid with minimal form among P-Sudoku solution grid, produced for 11 equivalence classes as it was done during all different P-Sudoku solution grid counting. Practically it means that each P-Sudoku solution grid, produced for an equivalence class, must be checked for form's minimality. If processed P-Sudoku solution grid has minimal form, we should increase "essentially different P-Sudoku solution grid's" counter and store grid for further needs. At the end we should get number slightly higher than 213,808,581. At this moment all grid's automorphisms will be taken into account.

Now we should take into account connections between orbits. We should check transformation, not belonging to P-Sudoku isomorphic transformations group. For example, we may check swapping rows in the alone band only. If such transformation gives us valid P-Sudoku grid, then we find orbit connection. We must count connected orbits as one orbit, so "essentially different P-Sudoku solution grid's" counter, calculated at previous stage, must be decreased to account for connections. Exact set of transformation for checking connections contains 3359232/2592 = 1296 transformations. (I'll write about these transformations later.)

Finally we should get exact number of essentially different P-Sudoku solution grids.

BTW. I've just found in the thread "Su-Doku's maths" description of essentially different sudoku counting method without Group Theory, conjugacy classes, etc. (see post of PatmaxDaddy here, dated by October 24, 2005, some his previous posts and following his discussion with dukuso). But description is not transparent and I doubt that anyone can repeat PatmaxDaddy's calculations.

Serg

[Mathimagics]

Hi Serg!

Happy to see you have not been idle!

Look forward to seeing the results.

Meanwhile, I'd like to revisit the issue of intersecting orbits and invite eleven to comment on the following.

We discussed this issue in the "Unique Sudokus" thread, but it's really an issue specifically related to SudokuP.

you should understand, that possible isomorphic transformations for SudokuP grids don't form group. I mean that there are "universal" isomorphic transformations which transform any SudokuP grid to other SudokuP grid, and there are "non-universal" isomorphic transformations which transform some SudokuP grids to other SudokuP grids, but they transform the rest SudokuP grids to non-SudokuP grids. I.e some isomorphic transformations are not universal. This means that Burnside's Lemma used for essentially different sudoku grids enumeration by Red Ed is not applicable here.

That still troubles me, and here is why:

• You say that the 5 transformations above don't form a group, because some transformations are not universal. But this implies that you allow these transformations to exist in the first place!

• By specifying precisely those universal transformations only when defining the group, eg: perms of rows within all bands rather than any band, we explicitly exclude the problem of intersecting orbits, don't we?

• GAP agrees that this is a valid group, a valid permutation group, has the correct order, and has generators that are just those transformations we defined

.

I just don't see how any orbits can intersect with this group, unless they come from transformations outside the group.

I think what I'm saying is, can't we just define grid isomorphism for SudokuP in the same way we define the cell transformations?

[eleven]

... invite eleven to comment on the following.

Don't ask me about group theory, i am all but an expert and it is full of pitfalls.
But my thinking was the same as yours. As long as we don't mix classic and SudokuP equivalence, why should there be a problem ?

[Serg]

Hi, Mathimagics!

• You say that the 5 transformations above don't form a group, because some transformations are not universal. But this implies that you allow these transformations to exist in the first place!

What "5 transformations above" do you mean? What do you mean saying "these transformations to exist in the first place"?

• By specifying precisely those universal transformations only when defining the group, eg: perms of rows within all bands rather than any band, we explicitly exclude the problem of intersecting orbits, don't we?

Yes, but in this case you must say "this is the number of essentially different SudokuP provided that isomorphic transformations are the following ...". I.e. you consider essentially different SudokuP within group of 2592 transformations, not within commonly used 3359232 isomorphic transformations. So, such result would be very special and not interesting, to my mind.

• GAP agrees that this is a valid group, a valid permutation group, has the correct order, and has generators that are just those transformations we defined.

Yes.

I just don't see how any orbits can intersect with this group, unless they come from transformations outside the group.

You are right.

I think what I'm saying is, can't we just define grid isomorphism for SudokuP in the same way we define the cell transformations?

Yes, it is possible, but result would be of limited interest, as I was saying it above.

MC grid is evident example of SudokuP. If we swap rows r1/r2 (only r1 and r2 rows, without swapping r4,r5,r7,r8 rows), we'll get another valid SudokuP. (This is an example of orbits connection.) If you use group of 2592 isomorphic transformations, you should treat MC grid and resulting grid as essentially different. But they are not essentially different!

Serg

[eleven]

If you swap the digits of a U4 in a classical sudoku, you get a valid one.
But it is not equivalent.

btw class 26 has the sticks symmetry.

[coloin]

Thanks Mathimagics and Serg


the mc grid - or any grid with a band with repeating minirows - maintains sudoku-p with a single row swap
looks like there might be 36 different "orbits" then in the mc ?

Code: Select all

+---+---+---+
|123|456|789|
|456|789|123|
|789|123|456|
+---+---+---+
|231|564|897|
|564|897|231|
|897|231|564|
+---+---+---+
|312|645|978|
|645|978|312|
|978|312|645|
+---+---+---+


this partial grid with this stack

Code: Select all

+---+---+---+
|396|...|...|
|174|...|...|
|528|...|...|
+---+---+---+
|963|...|...|
|417|...|...|
|852|...|...|
+---+---+---+
|639|...|...|
|741|...|...|
|285|...|...|
+---+---+---+


will also maintain sudoku-p with single column swaps .... this has the same gangster as the mc

This sudoku-p grid has a few U4s - and i get the feeling that they are under represented

Code: Select all

+---+---+---+
|932|615|874|
|584|327|916|
|167|984|532|
+---+---+---+
|729|458|361|
|645|132|798|
|813|796|425|
+---+---+---+
|296|543|187|
|471|869|253|
|358|271|649|
+---+---+---+


Code: Select all

23,26,33,36
28,29,48,49
65,66,75,76
74,78,84,88

however looking all the 2-templates in random sudoku-dg solution grids all 181 of the 181 2-templates were found.