SudokuP - Analysis

Everything about Sudoku that doesn't fit in one of the other sections

Re: SudokuP - Frequency Analysis

Postby Mathimagics » Sun Jan 21, 2018 7:10 pm

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 551
Joined: 27 May 2015

Re: SudokuP - Frequency Analysis

Postby Mathimagics » Sun Jan 21, 2018 7:57 pm

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 551
Joined: 27 May 2015

Re: SudokuP - Frequency Analysis

Postby Mathimagics » Sun Jan 21, 2018 8:57 pm

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 ....
User avatar
Mathimagics
2017 Supporter
 
Posts: 551
Joined: 27 May 2015

Re: SudokuP - Frequency Analysis

Postby eleven » Sun Jan 21, 2018 10:03 pm

Mathimagics wrote: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.
eleven
 
Posts: 1780
Joined: 10 February 2008

Re: SudokuP - Frequency Analysis

Postby Mathimagics » Sun Jan 21, 2018 10:17 pm

Aha! Now we're talking! 8-)

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?
User avatar
Mathimagics
2017 Supporter
 
Posts: 551
Joined: 27 May 2015

Re: SudokuP - Frequency Analysis

Postby eleven » Sun Jan 21, 2018 10:44 pm

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.
eleven
 
Posts: 1780
Joined: 10 February 2008

Re: SudokuP - Frequency Analysis

Postby Mathimagics » Sun Jan 21, 2018 11:01 pm

Good thinking!

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

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 ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 551
Joined: 27 May 2015

Re: SudokuP - Frequency Analysis

Postby Mathimagics » Sun Jan 21, 2018 11:02 pm

Feel free to take a break, catch up tomorrow. I have something to go on with, thanks!
User avatar
Mathimagics
2017 Supporter
 
Posts: 551
Joined: 27 May 2015

Re: SudokuP - Frequency Analysis

Postby dobrichev » Mon Jan 22, 2018 5:42 am

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.
dobrichev
2016 Supporter
 
Posts: 1558
Joined: 24 May 2010

Re: SudokuP - Frequency Analysis

Postby eleven » Mon Jan 22, 2018 7:25 am

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."
eleven
 
Posts: 1780
Joined: 10 February 2008

Re: SudokuP - Frequency Analysis

Postby Mathimagics » Mon Jan 22, 2018 2:43 pm

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

Which set of equivalence classes was used in this experiment?
User avatar
Mathimagics
2017 Supporter
 
Posts: 551
Joined: 27 May 2015

Essentially Different SudokuP's - Progress

Postby Mathimagics » Fri Jan 26, 2018 1:06 am

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]).
User avatar
Mathimagics
2017 Supporter
 
Posts: 551
Joined: 27 May 2015

Almost exact number of e-d SudokuP grids!

Postby Mathimagics » Sat Jan 27, 2018 5:10 am

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 ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 551
Joined: 27 May 2015

Re: SudokuP - Frequency Analysis

Postby Mathimagics » Tue Jan 30, 2018 8:31 am

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) ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 551
Joined: 27 May 2015

Re: SudokuP - Frequency Analysis

Postby coloin » Fri Feb 02, 2018 3:42 pm

coloin wrote:.....
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 ?
coloin
 
Posts: 1702
Joined: 05 May 2005

PreviousNext

Return to General