SudokuP - Analysis

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

Re: SudokuP - Frequency Analysis

Postby Mathimagics » Wed Jan 17, 2018 2:40 pm

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


I meant the same 5 grid operations that you listed in your "computational approach" description above. It just happens that these can be defined with exactly 5 transformations (permutations), 1 for transposition, 2 for band permutations, and 2 for rows within 3 bands. That is, the SudokuP symmetry group G is completely generated by just 5 permutations:

  • transposition
  • swap bands 1 and 2
  • swap bands 2 and 3
  • swap rows (1,2) + (4,5) + (7,8)
  • swap rows (2,3) + (5,6) + (8,9)

All required SudokuP-preserving grid permutations can be made with combinations of these.

By "exist" I just meant to say "defined by the allowable transformations". Just another way of saying that if isomorphism is based on these group permutations, then the orbit problem doesn't apply.

And that seems to be the key point, I just naturally assumed that if we define a group with specific set of SudokuP transformations, then we automatically define isomorphism as equivalence under those transformations, not the full set of Sudoku transformations.

I think we all agree that under this definition, the symmetry group is well-defined, orbits don't intersect, Burnside's Lemma applies, and all is right in the universe! 8-)

But if we define isomorphism as equivalent under Sudoku transformations, we definitely have orbits that intersect, and our universe is chaotic (and, alas, no Burnside!).

But the ordered universe, you say, is less interesting! In any case we clearly need to distinguish between these 2 isomorphism definitions, and I suggest we use p-isomorphism for the restricted (but uninteresting) case, and where necessary s-isomorphism for standard Sudoku isomorphism. "Isomorphism" unqualified will be assumed to be "s-isomorphism".

So the debate really boils down to this question:
  • Should we define "essentially different" SudokuP grids in terms of p-isomorphism or not? (discuss)
8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 551
Joined: 27 May 2015

Re: SudokuP - Frequency Analysis

Postby Mathimagics » Wed Jan 17, 2018 2:50 pm

coloin wrote:Has anyone got a batch of random grids for study ?


Yes, I actually have a complete catalog from which I can quickly produce random samples. If you like I can send you some sample batches of 1,000 or 10,000 (PM me with email address).

You can always use a random Sudoku grid generator of course, like Red Ed's, but you have to filter them, and SudokuP's only occur 1 in every 33172, so at 7K grids/second that only produces one every 5 seconds on my 2.7Gh box.

I can also provide a (Win32) program that will build the complete catalog (235Gb) if anybody wants to get serious!
User avatar
Mathimagics
2017 Supporter
 
Posts: 551
Joined: 27 May 2015

SudokuP - Automorphism Enumeration

Postby Mathimagics » Wed Jan 17, 2018 3:32 pm

Mathimagics wrote:But we can still count the number of automorphic SudokuP grids, and do so very quickly (< 2 minutes). That turns out to be 78,257,944 (ignoring relabelling).

These occur in just 2 types of transformations (ie in just 2 of 54 conjugacy classes).


In all the cut-and-thrust of the debate over the group-theoretic issues, I forgot my suspicions over this result, which on inspection turned out to be well founded!

I had simply stuffed up the batch control, which selected which classes to check, in order to run the job in 4 parallel batches.

It seems that 19 of the 54 classes yield automorphism cases, with a revised total of approx 595 million, and job time of 30 minutes.
User avatar
Mathimagics
2017 Supporter
 
Posts: 551
Joined: 27 May 2015

Re: SudokuP - Frequency Analysis

Postby eleven » Wed Jan 17, 2018 6:07 pm

Ah fine. Could you provide a sample for each class ?
eleven
 
Posts: 1780
Joined: 10 February 2008

Re: SudokuP - Frequency Analysis

Postby Mathimagics » Wed Jan 17, 2018 6:35 pm

Sure, here we go (C# is class #):
Hidden Text: Show
Code: Select all
C02: 123456789789123456456789123314267598278591634695834217931645872847312965562978341
C03: 123456789789123456456789123912648375678315942345972618261594837837261594594837261
C04: 123456789578139264469278153217694538985321647634587921341962875852713496796845312
C05: 123456789897123564645879123318564297279318645456792318931645872782931456564287931
C06: 123456789759183426486729153814597362392864517567312894935271648678945231241638975
C07: 123456789978123456546789123312645897789312645465897312231564978897231564654978231
C08: 123456789794128356586379124378241965469835271251967438637594812912683547845712693
C09: 123456789476189253859723146312847695647915832985632417231574968764398521598261374
C10: 123456789789123465456897123312564897897312654564978312231645978978231546645789231
C11: 123456789598127643746398125817632594259714836634589217361245978485971362972863451
C12: 123456789857329146469187352341978265582614973796235814614892537235761498978543621
C13: 123456789486179253759823416218964537634517928597238164342691875861745392975382641
C14: 123456789589127436476389125314695278258714693697238514931562847845971362762843951
C21: 123456789789123456456789123312648975975312648648975312231594867867231594594867231
C26: 123456789469781253758329416372615948645978132981243675234567891516894327897132564
C27: 123456789789123456456789123312567894897214365564398217231945678978631542645872931
C28: 123456789789123456456789123897312564231564978564978312978231645312645897645897231
C29: 123456789965187423487932156534261897716598234298743561642315978851679342379824615
C30: 123456789857193642496827153312645978785319264649782315231564897578931426964278531
User avatar
Mathimagics
2017 Supporter
 
Posts: 551
Joined: 27 May 2015

Re: SudokuP - Frequency Analysis

Postby eleven » Wed Jan 17, 2018 8:45 pm

Mathimagics,

please can you check your outputs again.

You talked of 54 classes, but your transformations list only has 53 lines (you left out the identity ? Did you count it ?).
The first transformation (C02, line 2) is mini-colums as the puzzle, but for the next 4 (C03-C06) i can't find the class symmetry in your puzzles, your sample for C05 has a different symmetry, for the others i don't know.
Since i have to do all that manually, it is too time consuming that way.

Hidden Text: Show
Code: Select all
C02: 123456789789123456456789123314267598278591634695834217931645872847312965562978341 Mini-Colums  (174)(285)(396)
C03: 123456789789123456456789123912648375678315942345972618261594837837261594594837261 Jumping-Diagonals       ???
C04: 123456789578139264469278153217694538985321647634587921341962875852713496796845312 Jumping-Diagonals + RC  ???
C05: 123456789897123564645879123318564297279318645456792318931645872782931456564287931 Jumping-Diagonals - R, but puzzle is Gliding rows
C06: 123456789759183426486729153814597362392864517567312894935271648678945231241638975 Jumping Rows            ???
eleven
 
Posts: 1780
Joined: 10 February 2008

Re: SudokuP - Frequency Analysis

Postby Mathimagics » Wed Jan 17, 2018 9:34 pm

The invariant grid count for the identity mapping is just the total number of different grids, a value which we already know, so this process is just about checking the other 53 classes.

Thanks for spotting those anomalies, I will look into them.

I am working on a method that should let me verify a mapping from SudokuP class #'s to Sudoku class #'s (Ed's list), each one should be found in there somewhere. That will hopefully identify any problems.
User avatar
Mathimagics
2017 Supporter
 
Posts: 551
Joined: 27 May 2015

Re: SudokuP - Frequency Analysis

Postby eleven » Wed Jan 17, 2018 9:57 pm

Ok, the numbering was the main problem (line 1 is C02, etc)
That's better now for the first 6 ones:
Code: Select all
C02: 123456789789123456456789123314267598278591634695834217931645872847312965562978341 Mini-Diagonal (186)(294)(375)
C03: 123456789789123456456789123912648375678315942345972618261594837837261594594837261 Mini-Columns (147)(258)(369)
C04: 123456789578139264469278153217694538985321647634587921341962875852713496796845312 Jumping-Diagonals (168)(297)(345)
C05: 123456789897123564645879123318564297279318645456792318931645872782931456564287931 Jumping-Diagonals + RC (1)(289)(3)(4)(5)(6)(7)
C06: 123456789759183426486729153814597362392864517567312894935271648678945231241638975 Jumping Diagonals - R (132)(486)(597)
C07: 123456789978123456546789123312645897789312645465897312231564978897231564654978231 Jumping Rows + R (176)(258)(349)

You will not find some classes in Red Ed's list, there are extra classes needed because of the restricted equivalences.

[Edit: corrected description of C06]
Last edited by eleven on Sat Jan 20, 2018 2:54 pm, edited 1 time in total.
eleven
 
Posts: 1780
Joined: 10 February 2008

Re: SudokuP - Frequency Analysis

Postby Mathimagics » Wed Jan 17, 2018 10:38 pm

Oh, I'm sorry about that line numbering. My bad! :?

The elements of the SudokuP symmetry group should be a subset of the elements of the Sudoku symmetry group, or all is lost!

So I should be able to find every one ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 551
Joined: 27 May 2015

Re: SudokuP - Frequency Analysis

Postby eleven » Wed Jan 17, 2018 10:56 pm

Mathimagics wrote:The elements of the SudokuP symmetry group should be a subset of the elements of the Sudoku symmetry group, or all is lost!.

I don't think so. Or yes, but in different classes.
The puzzles of Sudoku Jumping rows are equivalent to both PSudoku Jumping Rows (band down, stack right) and PSudoku Jumping Rows +RC (with an additional row down and column right). If in the latter you move the rows/columns of bands/stacks 2 and 3, you would get a normal Jumping rows symmetry. But this is not allowed in SudokuP.
eleven
 
Posts: 1780
Joined: 10 February 2008

Re: SudokuP - Frequency Analysis

Postby Serg » Wed Jan 17, 2018 11:10 pm

Hi, eleven, Mathimagics!
Serg wrote: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!

Let's consider rather similar problem of enumerating fully symmetrical patterns.

Comment for Mathimagics. Pattern is 9x9 binary matrix (i.e. containing "0" or "1" in each cell). Cell containg "1" means that sudoku puzzle, constructed on the base of this pattern must have clue in this cell. Cell containg "0" means that sudoku puzzle, constructed on the base of this pattern must not have clue in this cell. So, pattern defines a family of sudoku puzzles. These puzzles may have equal or different digits in the same cells, but all these puzzles have the same structure (the same pattern of clues). Here is an example of (fully symmetrical) pattern.
Code: Select all
1 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 1 0
0 0 1 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 0
0 1 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 1

Very often cells containing clues are marked by "x", but cells not containing clues are marked by "." End of comment.

Total number of fully symmetrical patterns (i.e. patterns having vertical, horizontal, diagonal and antidiagonal symmetries simultaneously) is 2^15 or 32768 (not so many patterns). But how many are there essentially different patterns?

It is rather evident, that there are 6 "universal" isomorphic transformations, which transform any fully symmetrical patterns to other fully symmetrical patterns, all transformation having similar type: permutation of rows in B123 band AND the same permutation of columns in B147 stack AND "mirrored" permutation of rows in B789 band AND the same "mirrored" permutation of columns in B369 stack. "Mirrored" permutation means that r1/r2 permutation must be supplemented by r8/r9 permutation, left cyclical shift of columns c1-c3 must be supplemented by right cyclical shift of columns c7-c9, etc.

Besides those "universal" isomorphic transformations, there are "non-universal" transformations, which transform some fully symmetrical patterns to other fully symmetrical patterns, but drop fully symmetry for certain fully symmetrical patterns. So, you can see that situation is rather similar to SudokuP solution grids.

First we can get rough estimate of numbers of essentially different fully symmetrical patterns. We can divide "number of fully symmetrical patterns" by "number of isomorphic transformation" and we'll get 32768/6 = 5461 essentially different fully symmetrical patterns (approx.).

Then we can calculate conjugacy classes for those 6 transformations:
1. "Do nothing".
2. Swap r1/r2 rows.
3. Swap r1/r3 rows.
4. Swap r2/r3 rows.
5. Left cyclic shift of r1-r3 rows.
6. Right cyclic shift of r1-r3 rows.

It turns out, that there are 3 conjugacy classes - first class contains alone transformation "Do nothing", the second class contains 3 pairwise swappings, the third class contains both shifts. Calculations involving Burnside's Lemma gives 6528 essentially different patterns. (This number can be easily obtained without Burnside's Lemma by "brute force" patterns scanning because of relatively small number of patterns.) But this number don't take into account orbit connections. If we'll take into account orbit connections, we'll get 6016 essentially different patterns.

This problem was discussed in the thread "Fully symmetrical puzzles" (see, for example, gfroyle's post here and JPF's post here). Unfortunately this enumeration was too briefly described, but you can see that thread's participants took into account "non-universal" transformations without any doubt and got "6016" number, that no one disputes.

Serg
Serg
2018 Supporter
 
Posts: 573
Joined: 01 June 2010
Location: Russia

Re: SudokuP - Frequency Analysis

Postby Mathimagics » Wed Jan 17, 2018 11:22 pm

Hi Serg

That looks interesting! Give me some time to absorb all that ... I've got a few things going on here! 8-)

eleven:

I made a GAP script to cross-reference PCC (SudP Conj Class) numbers to SCC (Sud Conj Class), and all correspond (sighs of relief all round!):

Hidden Text: Show
Code: Select all
gap> Read("C:/Gap/CC-Match.txt");

PCC  #2 = SCC 10
PCC  #3 = SCC 8
PCC  #4 = SCC 22
PCC  #5 = SCC 22
PCC  #6 = SCC 22
PCC  #7 = SCC 25
PCC  #8 = SCC 32
PCC  #9 = SCC 25
PCC #10 = SCC 32
PCC #11 = SCC 37
PCC #12 = SCC 40
PCC #13 = SCC 43
PCC #14 = SCC 43
PCC #15 = SCC 60
PCC #16 = SCC 69
PCC #17 = SCC 66
PCC #18 = SCC 54
PCC #19 = SCC 55
PCC #20 = SCC 59
PCC #21 = SCC 79
PCC #22 = SCC 93
PCC #23 = SCC 96
PCC #24 = SCC 116
PCC #25 = SCC 116
PCC #26 = SCC 86
PCC #27 = SCC 134
PCC #28 = SCC 135
PCC #29 = SCC 145
PCC #30 = SCC 142
PCC #31 = SCC 227
PCC #32 = SCC 236
PCC #33 = SCC 235
PCC #34 = SCC 228
PCC #35 = SCC 253
PCC #36 = SCC 248
PCC #37 = SCC 248
PCC #38 = SCC 253
PCC #39 = SCC 212
PCC #40 = SCC 213
PCC #41 = SCC 270
PCC #42 = SCC 275
PCC #43 = SCC 164
PCC #44 = SCC 167
PCC #45 = SCC 170
PCC #46 = SCC 170
PCC #47 = SCC 172
PCC #48 = SCC 175
PCC #49 = SCC 184
PCC #50 = SCC 184
PCC #51 = SCC 189
PCC #52 = SCC 190
PCC #53 = SCC 201
PCC #54 = SCC 208
gap>
User avatar
Mathimagics
2017 Supporter
 
Posts: 551
Joined: 27 May 2015

Re: SudokuP - Frequency Analysis

Postby eleven » Wed Jan 17, 2018 11:53 pm

That's what i said.
You see, that several PCC classes "correspond" to a single SCC class. So they are not the same, and have different representative cell transformations, which you don't find there.
But a class is defined by it's transformation.

btw, did you notice, that the PCC classes you gave with the examples (those which do have valid grids), "correspond" to exactly those, i told you, i would expect here ?
eleven
 
Posts: 1780
Joined: 10 February 2008

Re: SudokuP - Frequency Analysis

Postby Mathimagics » Thu Jan 18, 2018 12:50 am

Yes, I understand now.

Ok, PCC's 4, 5 and 6 are "different" in SudokuP, but equivalent in SCC 22. But this difference is only because they can't all be conjugated using P-transforms, whereas in SCC they can because a conjugation transformation using non-P transformations links them together.

Neverthless, it seems to me that they can be still be regarded as structurally similar wrt Sudoku class 22, as those different transformations are all equivalent in Sudoku. In that sense they are proper subsets of SCC 22, just as SCC 22 itself is a subset of the "global" set of transformations corresponding to that cycle structure. So in symmetric group S81 they are in the same class.
User avatar
Mathimagics
2017 Supporter
 
Posts: 551
Joined: 27 May 2015

Re: SudokuP - Frequency Analysis

Postby Mathimagics » Thu Jan 18, 2018 6:03 am

Serg wrote: Unfortunately this enumeration was too briefly described, but you can see that thread's participants took into account "non-universal" transformations without any doubt and got "6016" number, that no one disputes.


It barely qualifies as a description!
User avatar
Mathimagics
2017 Supporter
 
Posts: 551
Joined: 27 May 2015

PreviousNext

Return to General