The New Sudoku Players' Forum

[Mathimagics]

.
For champagne,

I can't take a trick today, it seems. Now I am getting false positives!

[ EDIT ] Success! Sorted out a few wrinkles, and now it looks good. I'll need to do some thorough road testing, then look at table-driven version for speed.

[Serg]

Hi, Mathimagics!

For the record, it was Serg, if I recall correctly, who explained to me in great detail why he thought he number of ED (aka S-different) SudokuP grids could not be established using Burnsides' Lemma counting method because there are S-transformations that produce SudokuP grids from non-SudokuP grids, and vice-versa.

I am very sorry. Yes, it was me who stated that Burnsides' Lemma was not applicable for SudokuP solution grids enumeration. But later I changed my mind. I published a post in the thread SudokuP - Analysis, where I declared changing of my position:

I have to make a surprise announcement.
I came to a conclusion, that it's not necessary to account for classical 3359232 VPT-transformations while counting essentially different SudokuP solution grids. So, 53,666,689 PF-different SudokuP solution grids is the number of essentially different SudokuP solution grids. It's not necessary to count connected orbits, etc. to refine this result.

You calculated "Number of PF-different SudokuP solution grids" using Burnside's Lemma, aren't you?
Because I treated number of PF-different SudokuP solution grids as the number of essentially different SudokuP solution grids and said that it's not necessary to count connected orbits it should be clear (as I thought) that I withdraw my objections to the application of Burnside's Lemma for ED SudokuP solution grids enumeration. You replied to this my post, and I thought you accepted change of my position ...

That time I used concepts of "content-independent" and "content-dependent" VPT. Now I have much more stronger arguments, why it's not necessary to account for classical 3359232 VPT-transformations while counting essentially different SudokuP (and X-sudoku) solution grids.

What is isomorphic transformation? It is transformation, which doesn't change essence of transformed object. Some external changes of transformed object can be accounted for by simple rules, such as relabelling, changing row/column numbers etc. But internal structure (essence) of the object must not be changed.

What is the essence of SudokuP (traditional Sudoku, X-sudoku, etc.) solution grid? I propose several variants of definitions. Choose definition you like.

1. The essence of SudokuP solution grid is a set of SudokuP (not necessary valid) puzzles, which has given solution grid as one of its solutions. One can consider distribution (histogram) of number of clues by number of puzzles as invariant, which must not be changed under isomorphic transformation.

2. The essence of SudokuP solution grid is a set of SudokuP minimal valid puzzles, having given solution grid as its solution. One can consider distribution (histogram) of number of clues by number of puzzles as invariant, which must not be changed under isomorphic transformation. Another possible invariant - list of MinClues for 3 bands, 3 stacks, 3 P-bands and 3 P-stacks (12 numbers). Numbers in MinClues list may be permuted, but according to some rules. These numbers may not disappear and may not appear from nowhere during transformations.

3. The essence of SudokuP solution grid is a set of grid's unavoidable sets. One can consider distribution (histogram) of UA sizes by number of UA sets as invariant, which must not be changed under isomorphic transformation.

When I objected to the application of Burnside's Lemma for ED SudokuP solution grids, I posted an example - MC grid (being valid SudokuP solution grid) can be transformed to another valid SudokuP solution grid by swapping rows r2/r3 only. I insisted that such transformation should be treated as isomorphic, because it transforms one SudokuP solution grid to another. But it turns out this transformation (swapping r2/r3) is not isomorphic!

Code: Select all

           MinClues:
           MC grid  Transformed grid
Band 1     6        6
Band 2     6        6
Band 3     6        6
Stack 1    6        4
Stack 2    6        4
Stack 3    6        4
P-band 1   6        6
P-band 2   6        3
P-band 3   6        3
P-stack 1  6        6
P-stack 2  6        6
P-stack 3  6        6

You can see that swapping rows r2/r3 is not isomorphic, because it changes internal structure (essence) of the MC grid.

Note. Typical UA set's permutation changes internal structure (essence) of the SudokuP (traditional Sudoku, X-sudoku, etc.) solution grid.

We should change terminology. When we consider solution grids we should say isomorphic Structure Preserving Transformations, not Validity Preserving Transformations.

Serg

[Serg]

Hi, Mathimagics!

I'm not sure exactly what you would like to see. In my discussion with champagne above, you will find an example of non-SudokuX to SudokuX transformation, and I can provide that specific transformation, if that's what you want?

Sorry, but I didn't manage follow your discussion. I'd like to see description of transformation, which preserves validity of some X-sudoku solution grid, but destroy validity of another X-sudoku solution grid (and examples of both types of X-sudoku solution grids).

Serg

[Mathimagics]

Because I treated number of PF-different SudokuP solution grids as the number of essentially different SudokuP solution grids and said that it's not necessary to count connected orbits it should be clear (as I thought) that I withdraw my objections to the application of Burnside's Lemma for ED SudokuP solution grids enumeration.

You replied to this my post, and I thought you accepted change of my position ...

What can I say? The evidence is there for all to see, you are absolutely right! I had conveniently forgotten about that ...

Tarnation, it looks like blue gets to have his way, go^%&^damm it!

Let ED hereafter refer to equivalence according to the Sudoku variant type ... I surrender ...

But I will proceed with the counting of the of the S-different grids anyway, that's just the kind of obsessive-compulsive guy I am ...

It will at least provide independent confirmation of blue's results, and get me an X-catalog ... very hard to get grid catalog from Burnside method (I know, I tried to do it for SudokuP).

[champagne]

.
Here is one solution

Code: Select all

 6 8 3 | 4 2 7 | 1 9 5
 7 9 2 | 3 1 5 | 6 8 4
 5 4 1 | 9 8 6 | 2 7 3
 ------+-------+------
 2 3 6 | 5 7 4 | 8 1 9
 8 7 9 | 2 3 1 | 5 4 6
 1 5 4 | 6 9 8 | 7 3 2
 ------+-------+------
 3 2 7 | 8 5 9 | 4 6 1
 4 1 5 | 7 6 3 | 9 2 8
 9 6 8 | 1 4 2 | 3 5 7


It's a standard corner pattern with box 1 moving to the center, but it seems to have different row/col permutations in bands ,3 and stacks 1,3

So it looks like we need to test all 36^2 = 1296 such permutations for the corner box diagonals it seems ...

Hi Mathimagics,

Good news, it is one of my 2 possibilities.

Let me describe how very simply I came to this

Code: Select all

  +-------+-------+-------+
  | 1 2 3 | 4 5 6 | 7 8 9 |
  | 4 5 7 | 1 8 9 | 3 2 6 |
  | 8 6 9 | 3 7 2 | 5 1 4 |
  +-------+-------+-------+
  | 2 1 4 | 5 3 7 | 6 9 8 |
  | 3 7 6 | 2 9 8 | 1 4 5 |
  | 9 8 5 | 6 4 1 | 2 3 7 |
  +-------+-------+-------+
  | 5 3 1 | 8 6 4 | 9 7 2 |
  | 6 9 8 | 7 2 3 | 4 5 1 |
  | 7 4 2 | 9 1 5 | 8 6 3 |
  +-------+-------+-------+

your starting solution grid

In each box, the possible diagonal triplets

Code: Select all

box1 159 278 346      167 249 358
box2 248 167 359      479 125 368
box3 247 568 139      259 167 348
box4 257 169 348      479 135 268
box5 159 247 368      679 123 458
box6 467 138 259      248 356 179
box7 259 378 146      179 236 458
box8 258 147 369      249 567 138
box9 359 246 178      258 347 169

For the six possible diagonal (3 boxes not in the same band/stack), the valid 9 digits possibilities

Code: Select all

boxes 159     358 247 169
boxes 168   346 179 258      249 138 567
boxes 267   248 356 179       
boxes 249  empty
boxes 348  empty
boxes 357  empty

only possibilities to have a valid status in the central box

Code: Select all

boxes 159   358 247 169
boxes 168   346 179 258   

central box is box 1 central digit is digit 3 (your solution)

Code: Select all

boxes 168   249 138 567
boxes 267   248 356 179      

central box is box 6 central digit is "3"

From here, we know that band 1 stack 1 has to be morphed to the right diagonal pattern, then box1 moved to the central box, but this plays no role in the final check.

In fact, we have to check that we have a valid status in the four corners.

I did not check in details, but the process could be

Morph 1 of the four corners to have the right diagonal status
Check if it is still possible to morph the seen corners in the right way
and see if the fourth corner is ok

This is easy with the computer, but boring and subject to errors by hand

I restart with the full post, too many things in between

As I prefer a process easy to check, from here I would do the following for the 4 corner boxes

Morph the upper left box to main diagonal (0 to 2 rows permutations)
Morph the bottom left box to antidiagonal (again 0 to 2 rows permutations)

then the three columns must be visible in the rigth stack. For the computer, 0 to 2 columns permutations can do the job.

Nothing to do anyway with the 1196 permutations

EDIT and apparently, this solution grid has only one X sudoku, the check fails for me with the second possibility

[dobrichev]

What is isomorphic transformation? It is transformation, which doesn't change essence of transformed object. Some external changes of transformed object can be accounted for by simple rules, such as relabelling, changing row/column numbers etc. But internal structure (essence) of the object must not be changed.

What is the essence of SudokuP (traditional Sudoku, X-sudoku, etc.) solution grid? I propose several variants of definitions. Choose definition you like.

1. The essence of SudokuP solution grid is a set of SudokuP (not necessary valid) puzzles, which has given solution grid as one of its solutions. One can consider distribution (histogram) of number of clues by number of puzzles as invariant, which must not be changed under isomorphic transformation.

2. The essence of SudokuP solution grid is a set of SudokuP minimal valid puzzles, having given solution grid as its solution. One can consider distribution (histogram) of number of clues by number of puzzles as invariant, which must not be changed under isomorphic transformation. Another possible invariant - list of MinClues for 3 bands, 3 stacks, 3 P-bands and 3 P-stacks (12 numbers). Numbers in MinClues list may be permuted, but according to some rules. These numbers may not disappear and may not appear from nowhere during transformations.

3. The essence of SudokuP solution grid is a set of grid's unavoidable sets. One can consider distribution (histogram) of UA sizes by number of UA sets as invariant, which must not be changed under isomorphic transformation.

The proposed definitions are kind of hashing (many-to-one transformation) and are useful for classification but not for identification. Classification is considering particular criteria and we are back in the beginning of the definition loop.
Isn't it better to accept the popular terminology with all its uncertainties and always underline the context specific additional assumptions? This always works.
Popular terms such as VPT have passed the filter (many minds) X (many years). This usually isn't pure chance and should be respected.

[Mathimagics]

.
Why has this thread been shifted from "General" to "Variants" section, but not the others (SudokuP, SudokuPX, etc?) ??

I have no issue being here rather than in "General" section, but it would make more sense if they were all in the same place ...

While I'm on this subject, "Sudoku Variants" should be moved to the main "Sudoku - the Puzzle" section, IMHO

[Mathimagics]

.
For champagne:

Yes that puzzle had only one X-set.

As to the algorithm, what I did in the end was:

• I generated ALL possible "12-cell diagonal" sets, covering all the possible corner box permutations, then I sorted them and removed duplicates, which produced 1944 distinct cases.

• made that list into a header file

• the MorphableX function simply passes through this table, testing each 12-cell set for distinct values wrt to the grid being tested. If that is satisfied, then it investigates whether the center box and center-cell (implied by the context) allows for completion of the diagonals.

I'm happy to say it performs very well indeed, and I'm getting about 50,000 grids/second with it. That's about 20,000 times better than what I was getting before with the brute-force TransformableX function, so thank you, job well done!

Cheers!

[blue]

Here are a couple grids of test your code.

The first one generates 85 ED SudokuX grids.
The second one has two S-automorphisms, and generates 57 ED SudokuX grids ... 12 with two SX-automorphisms, the rest with one.

Code: Select all

123456789456789123798132564241975836837624915965318472372541698519863247684297351
123456789456789123897231564231597648564318297789642315315864972642975831978123456

[champagne]

. That's about 20,000 times better than what I was getting before with the brute-force TransformableX function,

In my industrial carrier, this would have been qualified as an acceptable Return On Investment

I am glad to have contributed positively to your project

[Mathimagics]

The first one generates 85 ED SudokuX grids.
The second one has two S-automorphisms, and generates 57 ED SudokuX grids ... 12 with two SX-automorphisms, the rest with one.

Confirmed first grid having 85. For the second, I don't have automorphism checking code in place, but I get 102 ED SudokuX grids.

That's 2 x 57 - 12, so I can see a correlation, not sure about why this would be so ...

BTW, these are the biggest EDX counts I've seen by a mile ... anything special about these grids?

[blue]

Confirmed first grid having 85. For the second, I don't have automorphism checking code in place, but I get 102 ED SudokuX grids.

The number 102, came up for me too, but after X-canonicalization, only 57 were distinct.
(My X-canonicalizer counts automorphisms, too).

That's 2 x 57 - 12, so I can see a correlation, not sure about why this would be so ...

The story seems to be this:

1. 102*96 S-transformations (not counting relabeling), produce an X-Sudoku grid
2. They come in pairs, (T, T o A), where A is the non-trivial automorphism for the input grid.
3. If the results were relabeled to have 123456789 in row 1, the number of distinct X-Sudoku grids produced, would be (102*96)/2 = 4896.
4. For the 12 canonical X-Sudoku grids with 2 automorphisms, applying X-Sudoku VPTs and relabling again, would produce (96/2) distinct grids.
5. For the remaining (57-12), 96 would be produced.
6. 12*(96/2) + (57-12)*96 = 4896 ... matching the number in (3)

I've checked that reasoning for two other grids too.

Code: Select all

123456789456789123789123456231564897564897231897231564312645978645978312978312645 - MC grid, 648 automorphisms
123456789456789123789123456214635978695874312837291564341562897568947231972318645 - 4 automorphisms

For the MC grid, the "102"-like number is 243, but only two X-distinct results are produced.
One has 8 automorphisms, and the other has 4.

243*96/648 = 36 = 1*(96/8) + 1*(96/4)

For the other grid, "102"-like number is 23, and the X-distinct results are: 1 grid @ 4 automorphisms, 3 @ 2, and 4 @ 1.

23*96/4 = 552 = 1*(96/4) + 3*(96/2) + 4*96

BTW, these are the biggest EDX counts I've seen by a mile ... anything special about these grids?

Not that I know of, other than the large counts.

Edit: Corrected the "4 @ 1" count above ... thanks Mathimagics

[Mathimagics]

For the other grid, "102"-like number is 23, and the X-distinct results are: 1 grid @ 4 automorphisms, 3 @ 2, and 5 @ 1.

23*96/4 = 552 = 1*(96/4) + 3*(96/2) + 5*96

Ok, I've got an X-canonicaliser working. It generates all 96 X-transformations, normalises them and picks the smallest (is that what you do?)

I now get 57 as the EDX count for case "102", and 2 for the MC grid instead of 243.

But for the "4 automorphisms" case above, I came up with 8, as opposed to your 9 = 1 + 3 + 5.

This really had me worried until I noticed that you only get 552 if you use the split (1 + 3 + 4). That is, 552 = 24 + 3*38 + 4*96, and so the EDX count really is 8.

[Mathimagics]

I get a result of 1,596,582,158 ED grids ... in under a second, not counting the time to arrive at the "153,255,603,504" number.

Note: Here, grids A and B are "essentially distinct" (ED), if neither can be transformed to the other, using relabelling and one of the 96 "validity preserving transformations" for SudokuX (X-Sudoku).

Ok, the dog seems to have eaten my homework, but I did report that my catalog build produces an EDX count of 1,596,740,368, an excess of 158,210 over blue's count.

I have now re-processed those Sudoku grids with non-trivial automorphisms, to get revised EDX counts for those grids, using X-canonicalisation to correctly identify the X-distinct solutions. This process reports that my overall count needs to be reduced by, you guessed it, 158,210!

Never in doubt, of course, but blue's count is hereby confirmed!

Also it demonstrates the fidelity of my MorphableX function (methode champenoise) and the X-canonicaliser.

[blue]

Ok, I've got an X-canonicaliser working. It generates all 96 X-transformations, normalises them and picks the smallest (is that what you do?)

More or less. I don't actually transform the grid 96 times, but I start calculating the "would-be" transformed grid, and comparing it with a "best case" grid. Usually one or the other is seen to be smaller, "early on". If it's the "would be" grid, I restart the transformation, updating the best case, and then reset an automorphism count to one. If the comparision shows that the result would be a match, I just bump the automorphism count, and skip to the next transformation.

For the other grid, "102"-like number is 23, and the X-distinct results are: 1 grid @ 4 automorphisms, 3 @ 2, and 5 @ 1.

23*96/4 = 552 = 1*(96/4) + 3*(96/2) + 5*96

(...)
But for the "4 automorphisms" case above, I came up with 8, as opposed to your 9 = 1 + 3 + 5.

This really had me worried until I noticed that you only get 552 if you use the split (1 + 3 + 4). That is, 552 = 24 + 3*38 + 4*96, and so the EDX count really is 8.

You're right ... it was "4 @ 1". I've corrected the original post, thank you.
I had the 8 count and the "1+3" grids with automorphisms on hand, originally.
For a while I had a typo of "2 @ 2" in the works, which carried over to (8 - (1 + 2)) being 5.
When I saw the first typo, I changed it to 3, but forgot to change the 5 to match.

BTW: I saw your earlier post, with the 1223885904 and 158210 numbers ... did what you were going to do, and like you, confirmed that the "158210" was due to not X-canonicalizing at the appropriate point. I knew you'ld discover that too, so I didn't post anything.

Good job, again
Thanks for the confirmation.

In return, I can confirm your result of 1,223,885,904 S-canonical forms for the SX grids.