The New Sudoku Players' Forum

[Sojourner9]

I just posted the MinLex416 Subgroups

[Sojourner9]

Hi Blue,

Hi Sojourner9,

Second part first: I know the ones you're talking about, although I hadn't realized that some (minlex) bands have the same (non-trivial) automorphism group
There are 84 distinct groups, as you say ... not (416-279)+1 = 138 !

The column/stack order for each of the 416 is kind of random, just whatever gets the lowest representative.
I've noticed they act like triangles, some equilateral, some isosceles, and some scaler. For the ones that have one box different, it varies which one it is.
So if I could swap them around I might even have less subgroups, but alas I can't. The only real point is saving memory.

Trivia, there are 66 conjugacy classes for bands.

For the first part: The only ones I actually use, are the band automorphisms.
At the end of this post I mentioned a way of counting automorphisms.
There, I meant automorphisms for the full grid ... which puts them in the union of the 27 relevant conjugacy classes.

How do you use band automorphisms, like how I described or is there another use?

I saw that you keep a count of the times you see the minLex grid.
My program returns the reorderings so I get the count as the length of my list.

My understanding of group theory is sophomoric and I don't want to come off as not knowing what I'm talking about.
Like I said, it took a long time before I understood what an automorphism was, and I am still not sure I got the terminology right.

Is automorphism the correct term to use here?
Do you mean seeing the same result as an automorphism or is it the reordering to get the same result?
Seems to me, the grid is automorphic because it can be seen as the same multiple times.
The reorderings is a subgroup that represents the symmetries of the grid or band.

I guess anyone could pipe in if they have an opinion.

[coloin]

Indeed..... perhaps we need to discuss particular grids to demonstrate what we are discussing

I wonder which conjugacy class the first grid is ?
It has 2 automorphisms

Code: Select all

12498 123456789456789231789132546268573914374961825915824673537618492691247358842395167 count 2      old416bands : 28 33 33 , 334 334 315
Automorphic puzzles in this grid
12498 .2.4.......6....3....1..5.........14....6....9.5.2..........4.2.........8..39....
12498 1......8......92..7...3....26.5.....................73.3.6.8....9.............1.7

There are 9 crossing bands [B12347 Equivalents] combinations
28/334, 28/334, 28/315, 33/334, 33/334, 33/334,33/334,33/315, 33/315
There are 4 which are "similar" 33/334
and only one which is unique - The 28/315 [box 3 crossing band] is reference box in the grid

Interestingly they [ 33/334 ] are the same bands numerically but not identical bands !

Code: Select all

123456...456789...789132...268573...374961...915824...537618...691247...842395...
...........................268573914374961825915824673537618492691247358842395167

000000000000000000000000000123456789457189623698732541379548216542361897816297435
000000000000000000000000000123456789457189236689273541572634198831927465964518372 

So the automorphism is therefore
2/3 band swop, 1/2 shute swap
plus the required row and column swaps
plus the required clue swaps.

I guess having and keeping the grid in minlex form helps in programming it - but it is not an absolute requirement. An automorphic grid is one where after a specified number of transforms one ends up with the exact same solution grid.

I managed to find these posts....
here

Code: Select all


   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

here

Code: Select all

N   | Classes [G] where #K(G)=N
    +-------------+------------
    | not trans.- | transpose-
    | invariant   | invariant
----+-------------+------------
  1 | 10944340774 | 23201
  2 |     1050496 |   637
  3 |       14672 |    36
  4 |        4378 |    29
  6 |        2442 |     6
  9 |          84 |     1
 12 |         172 |     0
 18 |         168 |     4
 27 |           4 |     1
 36 |          22 |     2
 54 |          20 |     1
108 |           4 |     0
162 |           2 |     0
324 |           0 |     1   

[Sojourner9]

Hi coloin,
I understand now what you mean by 9 crossing bands.
Other than our current discussion have you had any success using this methodology? What is your goal?
There is a lot I can say as way of digression but that might be a topic all it's own.
I remember reading that dusoku said that the six band/stack indexes is insufficient to describe the grid.

Indeed..... perhaps we need to discuss particular grids to demonstrate what we are discussing

I wonder which conjugacy class the first grid is ?
It has 2 automorphisms

Code: Select all

12498 123456789456789231789132546268573914374961825915824673537618492691247358842395167 count 2      old416bands : 28 33 33 , 334 334 315
Automorphic puzzles in this grid
12498 .2.4.......6....3....1..5.........14....6....9.5.2..........4.2.........8..39....
12498 1......8......92..7...3....26.5.....................73.3.6.8....9.............1.7

I have not used the grid conjugacy classes for anything but the Burnside's calculation of Nmin using templates.
BTW: Did mathimagics ever get this working, I asked but got no reply? I can explain how I did it.

There are 9 [Nine] crossing bands [B12347 Equivalents] combinations
28/334, 28/334, 28/315, 33/334, 33/334, 33/334,33/334,33/315, 33/315
There are 4 which are "similar" 33/334
and only one which is unique - The 28/315 [box 3 crossing band] is reference box in the grid

Interestingly they [ 33/334 ] are the same bands numerically but not identical bands !

Code: Select all

123456...456789...789132...268573...374961...915824...537618...691247...842395...
...........................268573914374961825915824673537618492691247358842395167

000000000000000000000000000123456789457189623698732541379548216542361897816297435
000000000000000000000000000123456789457189236689273541572634198831927465964518372 

So the automorphism is therefore
2/3 band swop, 1/2 shute swap
plus the required row and column swaps
plus the required clue swaps.

I'll have to take your word on this as I haven't tried this methodology.
Question, how may different representatives for B12347 do you have? Is this like 8000 something?
I have my own way of looking at sudoku grids and I ended up with 18,296,007 representatives.
I eventually got in down to ~10 million before I filled in B5689.
So getting down to 8000 would be great, as long as I could make it work with my methodology.

Say I wanted to construct a grid, given six band indexes.
I could put band 1 together but band 2 has a max of 7776 different ways it can be constructed and still be the same band index.
This number might be divided by the AMC counts for band 1 and 2. Now add the same problem for band 3.
Then trying to restrict these according to stacks 1, 2, and 3 and I am at a loss for how to do this.
I could do the math maybe, but I don't think there are 416 choose 6, with repeat, ways to build a grid is less than the number of Nmin grids.
Some must not be possible because of some structural constraint.

Here are the two "automorphisms" for this grid. It might take some decryption to be usable.
To go from the wild solution grid to the two occurrences of the minLex solution grid the reorderings are:

Code: Select all

987456213,312564879,428391657
789312654,564312789,735261984

if you want to start with the minLex solution just multiply both by the inverse of the first.
That should set the first to 123456789,123456789,123456789 and the second should be a 2-cycle to go back and forth between them.
Bonus Problem: Use the inverse of the second instead. Hint: you should get the same result.
I haven't done this yet. Spending too much time on the forum.

I published the minLex subgroups. And if you want I can publish the 66 band conjugacy classes but I can not attest to there validity.
But in the minLex subgroups you can see the multiplication of several smaller subgroups.

I guess having and keeping the grid in minlex form helps a lot but it is not an absolute requirement

I managed to find these posts....
here

Code: Select all


   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

here

Code: Select all

N   | Classes [G] where #K(G)=N
    +-------------+------------
    | not trans.- | transpose-
    | invariant   | invariant
----+-------------+------------
  1 | 10944340774 | 23201
  2 |     1050496 |   637
  3 |       14672 |    36
  4 |        4378 |    29
  6 |        2442 |     6
  9 |          84 |     1
 12 |         172 |     0
 18 |         168 |     4
 27 |           4 |     1
 36 |          22 |     2
 54 |          20 |     1
108 |           4 |     0
162 |           2 |     0
324 |           0 |     1   

So the first of these lists was derived by gsf when he enumerated Nmin as he was able to pull them out during enumeration.
I think we could get the reordering subgroups for all the automorphic grids as it might be interesting study.

The second list was produced by kjellg a year before gsf did his Nmin enumeration and they had a discussion about it.
My question is how did Pettersen get these numbers without enumerating Nmin?
Looking at what he was doing at the time, he just popped out the answer over a weekend and promptly forgot how he did it.
I have studied group theory up thru cosets. Just after this they talk about normal subgroups and guotient group and factor groups and just throw out the automorphism group like it can be calculated.
Maybe he did a Burnside's calculation. I will have to go back through my calculations and see if it gives me Aut().

My list of this is a spread sheet but I confirm the same counts and AMC numbers.
Has anyone noticed the ration 1:6:2 coming up in there calculations?
How about 1:27:54:162:36. I know the answer just asking.
Also, since you are into looking at conjugacy classes.
Based upon my methodology, I would expect that any conjugacy class that only moves the columns or rows around within their stacks/bands will not cause an automorphic grid.
But I just don't want to spend the time to confirm it. I could be wrong, maybe swaps in band 1 might.

[coloin]

Unfortunately Jim [Mathimagics] passed away a few months ago, he surely would have a contribution here as he investigated all this with regard to SudokuP

I think we were eventually able to find duplicates in the 6 band indicies, however convenient that would have been, although it did usefully differentiate between different grids. !

blue kindly elucidated the B12347 counts, and you have confirmed his work.

Code: Select all

B12347               18,296,007              2865 classes                                          CrossingBand

I think the reduction to 2865 [crossing gangsters] is the way kjellfp calculated the big number. I believe the 2865 all have different solution counts.

Over the years i think we have ignored the automorphic problem as a nuisance ... !

Most of the automorphic grids are x2 and i guess this probably represents an automorphic process as found in that first 17C

The higher automorphic grids are probably going to have the same triple band stucture.
I am guessing that the transpose invarients have each 3 crossing bands of which each have the same 2 bands .

Hopefully , as I fail to understand the 275 conjugacy classes as presented, we will have some clarity and simplification !

Edit
These are dukusos final numbers from here

walking throught the 11555445688 sudokus from the 306993 G-classes,
which by design should intersect each S-class at least once, I found indeed
23919 different S-classes which are T-equivalent to their transpose.
The list is here:
http://magictour.free.fr/t-invar.gz
I found 26641 S-classes where the 3*9-horizontal bands
are pairwise isomorphic to the vertical 9*3-stacks.

edited 17.Oct. My earlier calculation of 819 t-invariant classes
was wrong.

this indirectly confirms Frazer's and RedEd's numbers of
S-classes, T-classes and T-invariants.

[Sojourner9]

I was thinking about the output I get from gridMinLex and realized there were other things that could be returned/reported.
I give gridMinLex the input grid, which is what I call wild, which is anything other than the minLex grid.
It returns the minLex grid along with the reorders to go from wild to minLex.

This is good if I want to bring something else forward into the minLex reordering, like I did with the puzzle minLex puzzles.

For debug I created a couple of routines to modify the reorder data.
The first just inverts the data. So now I supply the minLex grid and it shows how to get back to the wild grid.
So any puzzle could be stored, say in an Internet Sudoku Data Base, in the grid minLex form along with the reordering to get it back to original puzzle ordering.
Duplicate puzzles with different reorders would mean someone is cheating somewhere, reusing old puzzles in a new way.

The second routine took one of the wild to minLex reorders and reversed it and then composed it with all the other reorders.
This has the curious effect of telling me what the symmetries are of the original wild grid.

I took this puzzle:

Code: Select all

124567893378294516659831742987123465231456978546789321863972154495618237712345689

Which is from the Ed Russell/Frazer Jarvis paper and is listed as being symmetric by a quarter turn.
Let's assume we don't know it is symmetrical. I run it thru gridMinLex and get the following reorders:

Code: Select all

          465879231  213798645 897456312
          645231879  897312465 213654798
          645231879 -213798645 348159267
          465879231 -897312465 762951843


So we know it is AMC 4, because I got four results.
I run it through the second routine and get this result:

Code: Select all

          123456789  123456789 123456789
          987654321  987654321 987654321
          987654321 -123456789 741852963
          123456789 -987654321 369258147


A keen eye will notice that rowMap/colMap show four quarter turns of the gird.
The way gridMinLex works it lists those on the row axis first, so 0 and 180 degrees first.

Notice on the third row the relabel map 741852963, is 1->3->9->7->1 and 2->6->8->4->2, just like the paper says.

This would be hard to find, going through all the permutations of the grid. With gridMinLex it come out quickly.

On a lark I swapped row 4 and 5 of this puzzle and I get the same minLex grid with this as the reorderings.

Code: Select all

          123456789  123456789 123456789
          987465321  987654321 987654321
          987564321 -123546789 741852963
          123546789 -987645321 369258147


You can see the slight eccentricity of the rotation here.

Anyone want team up on a Internet Sudoku Data Base?
Save off N, sumX, and sumX^2 to calculate Mean and SD of the solving times so people can see where they rank, time wise.
Maybe do some postmortem on how people solve puzzles to make sure they are not machines, etc.
At some point setup on-line tournaments, etc.