SudokuP - Analysis

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

Re: SudokuP - Analysis

Postby Serg » Sat Feb 10, 2018 9:08 pm

Hi, Mathimagics!
Mathimagics wrote:
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.
Mathimagics wrote:
Serg wrote:I was forced to search "blunder" in Google translator

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

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

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

Re: SudokuP - Analysis

Postby Serg » Sat Feb 10, 2018 9:25 pm

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
Serg
2018 Supporter
 
Posts: 563
Joined: 01 June 2010
Location: Russia

Re: SudokuP - Analysis

Postby Mathimagics » Sun Feb 11, 2018 1:32 am

Agreed, it's hats off to Gittermeister blue ... 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 493
Joined: 27 May 2015

SudokuP - Canonical Form

Postby Mathimagics » Sun Feb 11, 2018 2:51 am

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);
      }
   }
 
Last edited by Mathimagics on Mon Feb 12, 2018 3:49 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 493
Joined: 27 May 2015

Re: SudokuP - Canonical Form

Postby Serg » Sun Feb 11, 2018 7:26 pm

Hi, Mathimagics!
I have too many questions, as usual.
Mathimagics wrote: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"?
Mathimagics wrote: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?
Mathimagics wrote: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).]
Last edited by Serg on Mon Feb 12, 2018 9:06 pm, edited 2 times in total.
Serg
2018 Supporter
 
Posts: 563
Joined: 01 June 2010
Location: Russia

Re: SudokuP - Analysis

Postby Mathimagics » Mon Feb 12, 2018 4:37 am

Hi Serg,

serg wrote: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.

Serg wrote: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.


Serg wrote: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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 493
Joined: 27 May 2015

Re: SudokuP - Analysis

Postby Mathimagics » Tue Feb 13, 2018 3:33 pm

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 493
Joined: 27 May 2015

Re: SudokuP - Analysis

Postby Mathimagics » Thu Feb 15, 2018 6:14 pm

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".
Last edited by Mathimagics on Fri Feb 16, 2018 4:20 am, edited 2 times in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 493
Joined: 27 May 2015

Re: SudokuP - Analysis

Postby Mathimagics » Thu Feb 15, 2018 6:43 pm

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
Last edited by Mathimagics on Fri Feb 16, 2018 4:06 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 493
Joined: 27 May 2015

Re: SudokuP - Analysis

Postby Serg » Thu Feb 15, 2018 11:45 pm

Hi, Mathimagics!
Here is your description of F-different SudokuP grids
Mathimagics wrote: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?
Serg wrote: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:
Mathimagics wrote:
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:
Mathimagics wrote: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?
Serg wrote: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
Last edited by Serg on Fri Feb 16, 2018 8:54 pm, edited 1 time in total.
Serg
2018 Supporter
 
Posts: 563
Joined: 01 June 2010
Location: Russia

Re: SudokuP - Analysis

Postby Mathimagics » Fri Feb 16, 2018 5:01 am

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
User avatar
Mathimagics
2017 Supporter
 
Posts: 493
Joined: 27 May 2015

Re: SudokuP - Analysis

Postby Serg » Fri Feb 16, 2018 9:06 pm

Hi, Mathimagics!
Mathimagics wrote:number of SF-different SudokuP grids = 30,603,892

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

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

Re: SudokuP - Analysis

Postby Mathimagics » Fri Feb 16, 2018 10:30 pm

Serg wrote:I am planning to crosscheck it.


Ok, I will keep my fingers crossed! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 493
Joined: 27 May 2015

Previous

Return to General