Sudoku Players' Forum (clone)

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!

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)

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!

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.

Ah fine. Could you provide a sample for each class ?

Sure, here we go (C# is class #):

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.

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.

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]

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

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.

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

Hi Serg

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

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!):

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 ?

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.

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!