The New Sudoku Players' Forum

[Mathimagics]

eleven,

You've noticed something about class 8 which I have also done, and they are definitely related to same thing.

The 16 permutations are indeed split into two "halves", elements 1 to 8 all have inverses in 1-8, and same for 9-16, which corresponds (I think) with your observation.

That makes sense, as all symmetries have transpositions with same property. I expect that every class will exhibit this property.

Nice observation!

BTW, let's put aside the question of which transforms apply to SudokuP, just for the moment, and focus on the general case.

Given a grid A which is invariant under T(8,1) = 1st transformation of class 8, how do we generate 15 grids that are invariant under T(8, 2), T(8, 3) etc

And will this method generate a distinct set for every A with given property? That would mean a complete set of invariants for class 8 can be generated from the base set of all A with T(8,1)(A) = A.

[Mathimagics]

eleven: I do hope that I'm not on a wild goose chase here, and dragging you along!

It's entirely possible that the correspondence is a combinatorial one only, and not directly related to the group properties.

In other words the "magic" transformation need not exist at all. In fact if it DID exist, and was just a composition of T's in the same class, then that would imply that all 16 sets of invariant grids would be isomorphic to each other, and I'm not sure that is possible.

[Mathimagics]

A random thought: would my "magic morph" function have something in common with your "normalisation" process?

That sounded to me like a process that mapped between members of the same conjugacy class ....

[eleven]

Given a grid A which is invariant under T(8,1) = 1st transformation of class 8, how do we generate 15 grids that are invariant under T(8, 2), T(8, 3) etc

And will this method generate a distinct set for every A with given property? That would mean a complete set of invariants for class 8 can be generated from the base set of all A with T(8,1)(A) = A.

The problem is, that this is not a PSudoku transformation. In S-Sudoku just swap two colums or rows to get from one to the next (S-equivalent) grid.
I learned that from you.

[Mathimagics]

Aha! Now we're talking!

You can tell I have no visual acuity for these transformations ....

While I do some experimenting with that nugget of information, and ignoring the validity or otherwise wrt SudokuP, is there a similar transform for class 7, say?

[eleven]

I wonder, which additional transformations will be there (96/16=6). I guess band changes (4) and reflections (both SudokuP transformations).
Or just band swaps. Too tired now.

[Mathimagics]

Good thinking!

I am, alas, a novice in Group Theory, whereas you are a veritable Swami of Symmetry!

That class 8 trick seems to be just what I'm looking for, for the first time I have been able to turn my A into a B with different invariant mapping. Maybe there is a generator method after all ...

[Mathimagics]

Feel free to take a break, catch up tomorrow. I have something to go on with, thanks!

[dobrichev]

Hi,

In continuation to this work I applied coloring on the eqivalence classes that happened to be useless for counting, and found this well known result

Putty. Putty. Putty.
Green Putty - Grutty Peen.
Grarmpitutty - Morning!
Pridsummer - Grorning Utty!
Discovery..... Oh.
Putty?..... Armpit?
Armpit..... Putty.
Not even a particularly
Nice shade of green.
As I lick my armpit and shall agree,
That this putty is very well green.

[eleven]

Be careful.
"During a reading of the poem, 4 of his audience died of internal hemorrhaging and the president of the Mid-Galactic Arts Nobbling Council survived by gnawing one of his own legs off."

[Mathimagics]

I can see you guys have been busy while I took a well-earned kip!

Which set of equivalence classes was used in this experiment?

[Mathimagics]

Just an update on progress with the counting of essentially different SudokuP grids.

• my brute-force class expansion, as predicted, is taking a very, very long time to complete. Most S-classes were done in a day or 2, but the monster classes 79 and 134 are slow. C79 is now complete, it took 4 x parallel jobs 80 hours to complete! Cranking up C134 now

• my idea for a per-class expansion method as an alternative to the brute-force approach is coming along nicely, thanks to eleven for his contribution!

Example of the invariant-enumeration method for Class 8, we start with a set A(1) of known invariant grids under T[1] :

• There are 16 members of conjugacy class 8

• Every member transformation T[k] has a corresponding transposition form X[k]

• Every member transformation has a corresponding inverse U[k]

This reduces the problem to finding just the mapping transformations that turn each invariant grid in A(1) into corresponding grids for A(2), A(3) and A(4). One such mapping set is:

• A(2): swap {r78, c78}

• A(3): swap {r45, c45}

• A(4): swap {r12, c12}

The transposition forms apply to all classes, but not every class has distinct inverses (for some classes T[k] = U[k]).

[Mathimagics]

The job of counting SudokuP invariant grids has finished finally, and oh, we came so close ....

Code: Select all

 Class   Invariants 
 ------------------
   1   554191840696
   7         580608
   8       16135168
   9         245376
  10         515440
  22        2527920
  23          10368
  24         171072
  25        8337120
  26           5184
  27          41472
  28        3005856
  29              0
  30         873504
  31          54432
  32       94740960
  37        1711296
  40          87120
  43          62640
  79      172868904
  86         519696
 134      638043984
 135        1233504
 142        4794624
 143         135648
 144         293760
 145        1143648
-------------------
Total  555139980000
-------------------


Sadly that total is almost, but not quite, divisible by 3,359,232.

555,139,980,000 / 3,359,232 = 165,258.00540123....

That's very close to the prediction estimate (# of essentially different Sudoku grids divided by 33171 ~= 165000) .

I've run an audit of all the data (I wrote all invariants to disk) and everything appears to be in order. So I've either double counted 18144 (the excess mod 3359232), or have somehow missed out some ...

[Mathimagics]

Doh!

Because Burnside's Lemma is not applicable here, for reasons explained by Serg above, we are highly unlikely to get an exactly divisible result, and even if we did, it would still be of dubious providence.

In fact, the exact number of essentially different SudokuP's may well be an intractable problem, and we will have to be content with the result above as the "best estimate" available. It certainly serves as an upper-bound, and looks on the surface to be a fairly tight one.

Perhaps it can be reduced, by finding hitherto unrevealed "orbit connections" (wrt S-equivalence) ...

[coloin]

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


so how many of the 6 ^ 8 * 2 = 3,359,232 ways to protray the mc grid are sudoku-p,
a single row swop in the above mcgrid maintains it -
if each orbit has 6^4 * 2 "different" grids .... that doesnt really add up or does it ?