## SudokuP - Analysis

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Re: SudokuP - Frequency Analysis

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
2017 Supporter

Posts: 737
Joined: 27 May 2015

### Re: SudokuP - Frequency Analysis

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
2017 Supporter

Posts: 737
Joined: 27 May 2015

### Re: SudokuP - Frequency Analysis

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

Mathimagics
2017 Supporter

Posts: 737
Joined: 27 May 2015

### Re: SudokuP - Frequency Analysis

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: 1846
Joined: 10 February 2008

### Re: SudokuP - Frequency Analysis

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?

Mathimagics
2017 Supporter

Posts: 737
Joined: 27 May 2015

### Re: SudokuP - Frequency Analysis

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: 1846
Joined: 10 February 2008

### Re: SudokuP - Frequency Analysis

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
2017 Supporter

Posts: 737
Joined: 27 May 2015

### Re: SudokuP - Frequency Analysis

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

Mathimagics
2017 Supporter

Posts: 737
Joined: 27 May 2015

### Re: SudokuP - Frequency Analysis

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
As I lick my armpit and shall agree,
That this putty is very well green.
dobrichev
2016 Supporter

Posts: 1612
Joined: 24 May 2010

### Re: SudokuP - Frequency Analysis

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: 1846
Joined: 10 February 2008

### Re: SudokuP - Frequency Analysis

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
2017 Supporter

Posts: 737
Joined: 27 May 2015

### Essentially Different SudokuP's - Progress

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
2017 Supporter

Posts: 737
Joined: 27 May 2015

### Almost exact number of e-d SudokuP grids!

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
2017 Supporter

Posts: 737
Joined: 27 May 2015

### Re: SudokuP - Frequency Analysis

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

Mathimagics
2017 Supporter

Posts: 737
Joined: 27 May 2015

### Re: SudokuP - Frequency Analysis

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: 1727
Joined: 05 May 2005

PreviousNext