The New Sudoku Players' Forum

[Serg]

Hi, Mathimagics!

It seems true number of p-different SudokuP solution grids should be around 214,038,113/4 = 53,509,528 (approx.)

Very close! The actual number is 53,666,689

Well done! We need some time to decide - what to do next.

I was forced to search "blunder" in Google translator

Howls of derisive laughter! I am in fact Australian, of mostly Irish/Scotttish extraction.

I feel it's time to open separate thread on this theme in "Coffee bar" section .

Serg

[Serg]

Hi, blue!
I am sorry, but I was only now able to collect my thoughts about your discovery - F-transformation.
I am very impressed. It's mathematically elegant - exchanging rows/boxes and p-sets/columns! Your observation present SudokuP puzzle as more elegant object than regular Sudoku puzzle. You saw internal structure of SudokuP/Sudoku puzzles, bravo!

Serg

[Mathimagics]

Agreed, it's hats off to Gittermeister blue ...

[Mathimagics]

I propose a simple Canonical Form algorithm for SudokuP solution grids.

It has the advantage of simplicity of implementation.

If X is the grid in question, we first convert it to gsf minlex form (eg: using Michael Deverin's function).

We then apply band2/3 and stack 2/3 permutations in a fixed order, selecting the first case that has SudokuP property. If we use the same order of test and permute operations, we will produce the same result.

Pseudo-code:

Hidden Text: Show

Code: Select all

   Minlex(X);  // convert to minlex
   
   for (b2 = 1; b2 <= 6; b2++) {
      for (b3 = 1; b3 <= 6; b3++) {
         for (s2 = 1; s2 <= 6; s2++) {
            for (s3 = 1; s3 <= 6; s3++) {
               if (IsSudokuP(X))) return;
               PermuteStack3();
               }
            PermuteStack2();
            }
         PermuteBand3();
         }
      PermuteBand2();
      }
  return;  // aagh! X has no SudokuP isotope !!
   
PermuteBand2() {
   switch (b2) {
      case 1: case 4: SwapRows(5, 6);
      case 2: case 5: SwapRows(4, 5);
      case 3: case 6: SwapRows(4, 6);
      }
   }
   
PermuteBand3() {
   switch (b3) {
      case 1: case 4: SwapRows(8, 9);
      case 2: case 5: SwapRows(7, 8);
      case 3: case 6: SwapRows(7, 9);
      }
   }
   
PermuteStack2() {
   switch (s2) {
      case 1: case 4: SwapCols(5, 6);
      case 2: case 5: SwapCols(4, 5);
      case 3: case 6: SwapCols(4, 6);
      }
   }
   
PermuteStack3() {
   switch (s3) {
      case 1: case 4: SwapCols(8, 9);
      case 2: case 5: SwapCols(7, 8);
      case 3: case 6: SwapCols(7, 9);
      }
   }
 

[Serg]

Hi, Mathimagics!
I have too many questions, as usual.

I propose a simple Canonical Form algorithm for SudokuP solution grids.
It has the advantage of simplicity of implementation, and gives a box1-normal form.

What do you mean, saying "box1-normal form"?

If X is the grid in question, we first convert it to gsf minlex form (eg: using Michael Deverin's function).

For what purpose do you convert given SudokuP solution grid to minlex form?

We then apply band2/3 and stack 2/3 permutations in a fixed order, selecting the first case that has SudokuP property. If we use the same order of test and permute operations, we will produce the same result.

Is this coset representative transformations set (mentioned earlier 1296 transformations)?
Why don't you account for F/G-transformations?


I have a counter proposal.
I pondered about necessary modification of your method to count naturally different SudokuP (valid) solution grids. Here is verbal description of the algorithm.

1. Initially we have the list of all essentially different regular sudoku solution grids (5472730538 solution grids).

2. Using 1296 coset representative transformations, we check images of all these representative transformations (transformations are repeatedly applied to given regular sudoku solution grid).

3. If an image of representative transformation is valid SudokuP solution grid, we produce "brother" SudokuP solution grids, applying set of 4 F/G-transformations (10368/2592). So, at the end of this procedure we have 4 "brother" SudokuP solution grids, including starting image of applying
representative transformation (result of applying transformation "Do nothing", participating F/G-transformations group).

4. New found 3 "brother" SudokuP solution grids are reduced to minlex form. (Minlex form of starting image of applying representative transformation is already known).

5. Different minlex forms (among 4 "brother" SudokuP solution grids) are added to set of "brother" minlex forms.

6. Count (different) minlex forms in the set of "brother" minlex forms after cycle done by 1296 coset representative transformations. Now we have N - number of interconnected sudoku solution grid's orbits for given sudoku solution grid (one of 5472730538 solution grids).

7. We must increase resulting number of naturally different SudokuP solution grids by fraction 1/N.

8. After processing of all essentially different sudoku solution grids (5472730538 grids) we'll get number of naturally different SudokuP solution grids.

Sum of fractions looks like very strange, but it should work.

Serg

[Edited. I corrected an error - F/G-transformations group contains 8 elements, not 4 elements, as was written earlier.]
[Edited 2. I was wrong again - we need no overall F/G-transformations group (containing 8 elements), it is sufficient to consider 4 elements only (representatives for partitioning PVP Group to cosets by 2592-elements subgroup).]

[Mathimagics]

Hi Serg,

What do you mean, saying "box1-normal form"?

Box 1 is {r123, c123} = 123/456/789. I thought that Minlex CF always has this property, but I was wrong (again! ) and have corrected the post to remove this blunder (!).

Why don't you account for F/G-transformations?

I have specifically excluded consideration of F transformation here. I want a SPCF (SudokuP Canonical Form) that is simple and easy to implement, and which serves the purpose of providing a CF that is of general use.

The SPCF suffices to provide a unique CF among all the conventional Sudoku isomorphisms, and thus provide a basis for comparing grids for conventional P-equivalence. This is the primary function of any CF algorithm.

If we wish to compare grids for PF-equivalence (P + F), then I believe this method will still be useful. One simply makes a list of the 8 possible CF's for each grid under the F-group and compares the two lists.

For what purpose do you convert given SudokuP solution grid to minlex form?

Simply to ensure that the algorithm is deterministic. Given X is a SudokuP grid, we want the same CF(X) result for any P-isotope of X. Starting from minlex(X) then applying permutations in same sequence does just this.

Is this coset representative transformations set (mentioned earlier 1296 transformations)?

It is an equivalent set. If we choose ANY box N, we can define a subgroup B(N) of 1296 elements based on row-pair swaps + col-pair swaps.

Any one of these will qualify as a complement under S (full Sudoku group) for the 2592 P transformations (P being the standard set, not including F). That is B x P = S.

As I understand it, there may well be other choices for group(S, P) complement, but these ones are particularly convenient computationally.

[Mathimagics]

Serg, I forgot to add, that I am definitely looking to count the "brother" orbit connections, but I'm configuring a new desktop PC which has just arrived, so I have been tied up with that.

[Mathimagics]

Ok, we are off and running in pursuit of the answer to the question, "how many SF-different SudokuP grids are there?"

Two SudokuP grids X and Y are SF-different if X and Y are neither S-equivalent nor F-equivalent. S-equivalence is normal Sudoku isomorphism , F-equivalence is isomorphism under {E, F, G} transformations identified by blue above.

I considered the approaches to this problem outlined by Seg and dobrichev above, but settled on a third option, which I outline here. It exploits the fact that we know the exact number (171,677,353) of Suduku grids that have one or more P-isomorphism, so we don't need to re-test the full set of 5,472,170,387.

And since my new PC is equipped with plentiful RAM (32Gb), it is quite easy to load this entire set of grids into memory and manipulate them, which makes a combinatorial solution feasible.

The job is done in two stages. The first stage is to identify the set of "brothers" (to use Serg's term).

Stage 1 (Build brother list):

• for each grid X, we enumerate the P-isotopes. These are the SudokuP grids we can obtain by any of the 1296 band/stack transformations described above. (Each P-isotope represents a set of 2592 different SudokuP grids, all of which are S-isomorphic to X)

• we reduce time here because we know already exactly which X have P-isotopes

• for each P-isotope, we apply the 4 F-transformations, get their minlex forms, remove duplicates, thereby producing a "brother" set of grids. Each brother represents an orbit connection between this grid X and brother grids Y1 .. Yn

This job took about 6 hours (using 6 parallel processes), but this was totally sub-optimal. I didn't write it in C, it was simpler to use existing VB6 test rig to generate the brother data, and work on the Stage 2 algorithm while that was running. In the end it finished well in advance of Stage 2 being ready!

The result was a brother list of some 600 million entries.

Stage 2 is simply the partitioning of the set {X} into the desired equivalence classes:

Stage 2 (Partitioning):

• Load the 171,677,353 grid representatives (all in minlex form) into a table

• Use a simple doubly-linked list structure to join together those grids that are related by brother linkage

• For each brother-pair {X, Y}, we locate X and its brother Y in our table, link them together, along with any chains they belong to

This method, while not decomposable (for parallel processing), does have the advantage of producing the equivalence classes explicitly, so the results can be analysed and verified. It's also quite fast, taking just 2h 20m to process all 600 million "brothers".

[Mathimagics]

Ok, by the method described above, my result is:

• the number of F-different SudokuP grids is 30,603,892

• the equivalence class sizes range from 1 to 33,753

There is only one case of class-size = 33,753. Here is one member:

Code: Select all

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


At the other extreme, there are just 3152 cases of one-member classes. These have the quite unusual property that applying any of blue's transformations results in an isomorphism (in the Sudoku sense) of that grid. So there are no orbit connections provided by these transformations. That makes these cases particularly interesting.

Here is an example, with its 3 F-group transformations:

Code: Select all

             X                     F(X)                      G(X)                      E(X)
 1 2 3 | 4 6 5 | 7 9 8     1 2 3 | 4 5 6 | 7 8 9     1 6 9 | 4 2 5 | 7 8 3     1 4 7 | 2 6 9 | 3 5 8
 4 5 6 | 7 9 8 | 1 3 2     4 6 5 | 7 9 8 | 1 3 2     4 2 5 | 7 3 8 | 1 9 6     6 2 8 | 3 5 1 | 7 9 4
 7 8 9 | 1 3 2 | 4 5 6     7 9 8 | 1 3 2 | 4 5 6     7 8 3 | 1 6 9 | 4 5 2     9 5 3 | 4 7 8 | 2 6 1
 ---------------------     ---------------------     ---------------------     ---------------------
 6 3 7 | 2 5 9 | 8 1 4     6 3 7 | 2 1 5 | 8 9 4     2 3 4 | 6 5 7 | 9 1 8     4 7 1 | 5 9 3 | 6 8 2
 2 1 5 | 3 8 4 | 9 6 7     2 5 9 | 3 8 4 | 6 1 7     5 1 7 | 9 8 2 | 3 6 4     2 3 9 | 1 8 6 | 5 4 7
 8 9 4 | 6 1 7 | 5 2 3     8 1 4 | 9 6 7 | 5 2 3     8 9 6 | 3 1 4 | 5 2 7     5 8 6 | 7 2 4 | 1 3 9
 ---------------------     ---------------------     ---------------------     ---------------------
 9 4 2 | 5 7 6 | 3 8 1     9 4 2 | 5 7 1 | 3 6 8     3 7 2 | 5 9 6 | 8 4 1     7 1 4 | 8 3 5 | 9 2 6
 5 7 1 | 8 2 3 | 6 4 9     5 7 6 | 8 2 3 | 9 4 1     6 5 1 | 8 4 3 | 2 7 9     8 6 5 | 9 1 2 | 4 7 3
 3 6 8 | 9 4 1 | 2 7 5     3 8 1 | 6 4 9 | 2 7 5     9 4 8 | 2 7 1 | 6 3 5     3 9 2 | 6 4 7 | 8 1 5


[Serg]

Hi, Mathimagics!
Here is your description of F-different SudokuP grids

Two SudokuP grids X and Y are F-different if X can't be transformed into Y by any combination of the 2592 P-transformations plus the 3 F-transformations {E, F, G} identified by blue above (total = 4 x 2592 = 10368 transformations).

Isn't it equal to my last definition of p-different SudokuP grids?

Definition (corrected)
SudokuP Validity Preserving Group or PVP Group is group of transformations preserving validity of any valid SudokuP puzzle or solution grid. This group is generated by following set of transformations.

1. Transposing.
2. Permutations of 3 bands.
3. Permutations of 3 stacks.
4. The same permutations of rows in every band.
5. The same permutations of columns in every stack.
6. F-transformation (permutations of minirows in each band).
7. G-transformation (permutations of minicolumns in each stack).

Totally we have 8 x 6^4 = 10368 isomorphic transformations.

You calculated earlier number of p-different transformations:

It seems true number of p-different SudokuP solution grids should be around 214,038,113/4 = 53,509,528 (approx.)

Very close! The actual number is 53,666,689

Now you are presenting another number:

Ok, by the method described above, my result is:

• the number of F-different SudokuP grids is 30,603,892

What is the difference between p-different (see my definition above) and F-different SudokuP grids? Do you mean naturally-different SudokuP grids?

Definition
Two SudokuP puzzles/grids/patterns are naturally the same if there is VPT or PVP transformation transforming one puzzle/grid/patterns to another. Otherwise these puzzles/grids/patterns are naturally different or nd-different.

Serg

[Mathimagics]

Hi Serg,

Sorry for the confusion! I was up quite late working on the Stage 2 algorithm and got my definitions quite mixed up ..

I am indeed counting what Serg has called "naturally different" SudokuP grids. I'm not entirely comfortable with that term, so I have used SF-different instead. Here we are counting SudokuP grids that are neither S-equivalent nor F-equivalent.

I have corrected the post above to reflect this (and have relabelled the E and G cases in the example following).

Summarising the state of play, we have identified 4 categories of equivalence for comparing SudokuP grids:

• P-equivalence under the 2592 P-preserving transformations. We used Burnside's Lemma to count the number of P-different SudokuP grids = 214,038,113

• S-equivalence is normal Sudoku-equivalence. Burnside's Lemma does not apply here, so we used an "orbit connection" method to count the number of S-different SudokuP grids = 171,677,353

• PF-equivalence extends P-equivalence to include blue's F-transformations. There are 4 x 2592 = 10368 transformations in this group. Burnside's Lemma applies and we used that to count the number of PF-different SudokuP grids = 53,666,689

• SF-equivalence extends S-equivalence in the same way. Again, Burnsides's Lemma does not apply, and so we used an "orbit connection" method to count the number of SF-different SudokuP grids = 30,603,892

[Serg]

Hi, Mathimagics!

number of SF-different SudokuP grids = 30,603,892

Congratulations on the result!
I am planning to crosscheck it.

Serg

[Mathimagics]

I am planning to crosscheck it.

Ok, I will keep my fingers crossed!

[blue]

Hi, blue!
I am sorry, but I was only now able to collect my thoughts about your discovery - F-transformation.
I am very impressed. It's mathematically elegant - exchanging rows/boxes and p-sets/columns! Your observation present SudokuP puzzle as more elegant object than regular Sudoku puzzle. You saw internal structure of SudokuP/Sudoku puzzles, bravo!

Agreed, it's hats off to Gittermeister blue ...

Thank you for the complements.
I see (today), that this was (first?) seen in 2005. Well done, Dan Hoey

[ The example that he gives, is for what I called the "G" transformation. ]

[Serg]

Hi, Mathimagics!

• P-equivalence under the 2592 P-preserving transformations. We used Burnside's Lemma to count the number of P-different SudokuP grids = 214,038,113

I confirm this result. I didn't enumerate SudokuP grids, but counted them by generation grids for 11 Red Ed's equivalence classes for SudokuP solution grids (originally - Sudoku DG solution grids). Computation took 20 hours of my notebook's CPU time. The next my goal - to confirm 53,666,689 PF-different SudokuP solution grids.

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.

Here are my considerations.
We are considering validity preserving transformations, i.e. transformations of puzzles, which don't change the number of puzzles solutions. Puzzle having 0 solutions should be transformed to another puzzle with 0 solutions. Puzzle having unique solution should be transformed to another puzzle with unique solution. Puzzle having N solutions should be transformed to another puzzle with N solutions. Such isomorphic transformations are some kinds of permutations, permuting contents of several cells of solution grid or permuting labels (relabeling). Isomorphic transformations are content-independent (universal) or content-dependent (not universal). Content-independent transformation acts on cells or labels (digits) in predefined order, not affected by cells contents or by location of relabeled digits. An example of content-independent isomorphic transformation - swapping B123/B456 bands. An example of content-dependent isomorphic transformation - permutation of strongly minimal UA set. Such UA set requires 1 clue cell only to be hitted or broken.

An equivalence based on content-independent isomorphic transformations is very useful. Solution path of a puzzle can be transformed to solution path of an equivalent puzzle by some isomorphic transformation. So, we do not need to solve an equivalent puzzle. Check for equivalence can be done by relatively simple procedure, not depending on cells content. And puzzles do not need solving to be checked for equivalence. On the contrary, checking for equivalence by content-dependent isomorphic transformation needs (typically) puzzle's solving and can hardly be applied to known puzzle's solution path. So, when people say about essentially the same (or equivalent) puzzles, they usually mean that one puzzle can be transformed to another by some content-independent isomorphic transformation.

Further considerations depend on the type of puzzle.

Regular Sudoku puzzles.
There are well known 3359232 VPT-transformations, forming VPT Group. These transformations and relabeling are content-independent. Strongly minimal UA sets are examples of content-dependent isomorphic transformations.

SudokuP puzzles.
Group of 10368 content-independent isomorphic transformations is known providing PF-equivalence relation. Because we know no other content-independent isomorphic transformations for SudokuP puzzles, this group of transformations should be used to check - are 2 given SudokuP puzzles essentially the same or essentially different. It sounds strange, but most of VPT-transformations (like "swapping r1/r2 rows") are content-dependent, like UA sets, and should not be used in puzzles equivalence checking procedure.

Maybe these considerations look strange, because it was I who insisted on accounting for VPT-transformations during SudokuP solution grids enumeration. But now I changed my mind.

Serg