The New Sudoku Players' Forum

[champagne]

As said in another thread, I open this thread to release a clean version of my code finding the min lexical morph of a grid.

In fact, having the DLL giving the min lexical mapping of a band, finding the min lexical grid is not hard, and doing this, we have to look at all auto morphs of the min lexical grid, so it was clear to me that the results should include the count of auto morphs.

I don’t know what is the agreed way to express this count, and I’ll use the last grid of the catalog to show how I see the count.

As the code to add to the band minlexing DLL is small, I intend at the end to add this as an entry of the recently released band mapping DLL.

[champagne]

Last min lexical grid analysis

The last grid of the catalog is

123 456 789
457 893 612
986 217 354

274 538 196
531 964 827
698 721 435

342 685 971
715 349 268
869 172 543

In this solution grid, each band and each stack must have the index 415. Any other possibility would give a lower solution grid using the corresponding band as start.

As we have only one min lexical solution grid with the index 415, each solution grid could have a corresponding main diagonal symmetry after mapping and a corresponding solution using any band or stack as first band.

If my code is correct, this happens for any band/stack used as first band. Generally speaking,

if I am right again, as soon as you get a main diagonal symmetry after mapping, each minimal morph of the min lexical grid in bands has a corresponding morph with the diagonal symmetry. (what I see in the code here)

But with this band 1, we have also 12 auto morphs. Any auto morph of the band 1 can delivers an auto morph of the entire grid, and here, again, if my draft of the code is right, each morph of the band 1 ends with the original solution grid after reordering and digit mapping.

If all this is true for the min lexical solution grid, this will be true for any morph of it.

At the end, I would say that this minimal solution grid has

3 vertical auto morphs (any band as first band)
X 12 " band 1" auto morphs equivalences
X 2 due to the diagonal symmetry

This is 72 auto morphs of the grid expressed through 3 factors.

Without external contribution, this is the way I intend to give the result

[champagne]

Just to give an idea, this is the status of my draft to find the min lexical grid ant the auto morphisms.
As I just started the debugging, the final code could be slightly different,
and some code is missing

Hidden Text: Show

Code: Select all


int gd[81],  n_auto_b1;
int b1min[27], b2min[27], b3min[27];

int ngauto , ngvert;
BANDPERM* t_auto_b1;
GRIDPERM gperm_min;
int SeeNewMin(BANDPERM& p, int* wb2, int* wb3,int isd);
void SkbsGetMin(int* g, int* g81min) {
   int minindex, ii; // diagonal symmetry
   BANDPERM pg[3], pd[3];
   memset(b2min, 9, sizeof b2min);
   for (int i = 0; i < 81; i++)   gd[i] = g[C_transpose_d[i]];
   // Getindex band/stack and min index
   SkbGetMappingInt(g, &pg[0]); minindex = pg[0].i416;
   SkbGetMappingInt(&g[27], &pg[1]); ii = pg[1].i416;
   if (ii < minindex)minindex = ii;
   SkbGetMappingInt(&g[54], &pg[2]); ii = pg[2].i416;
   if (ii < minindex)minindex = ii;
   SkbGetMappingInt(gd, &pd[0]); ii = pd[0].i416;
   if (ii < minindex)minindex = ii;
   SkbGetMappingInt(&gd[27], &pd[1]); ii = pd[1].i416;
   if (ii < minindex)minindex = ii;
   SkbGetMappingInt(&gd[54], &pd[2]); ii = pd[2].i416;
   if (ii < minindex)minindex = ii;
   // get the first band min lex and the auto morphs
   char b1char[27];
   SkbGetBandChar(minindex, b1char);
   n_auto_b1 = SkbGetAutoMorphs(minindex, &t_auto_b1);
   for (int i = 0; i < 27; i++)   b1min[i] = b1char[i] - '1';
   
   // try each start equal to min index
   int* bx[3] = { g,&g[27] , & g[54]};
   int* bxd[3] = { gd,&gd[27] , &gd[54] };
   for (int ip = 0; ip < 3; ip++) {
      int* p = tperm3[ip];
      if (pg[p[0]].i416 == minindex)
         if (SeeNewMin(pg[p[0]], bx[p[1]], bx[p[2]], 0)) {
// code to finish
         }
      if (pd[p[0]].i416 == minindex)
         if (SeeNewMin(pd[p[0]], bxd[p[1]], bxd[p[2]], 1)) {
// code to finish
         }
   }

}

int SeeNewMin(BANDPERM & p, int * wb2, int * wb3,int isd) {
   int b2n[27], b3n[27],temp[27];
   // find first min see if it is a new min
   p.MorphOrdered(wb2, b2n);
   p.MorphOrdered(wb3, b3n);
   if (b2n[0] > b3n[0]) {// exchange b2 b3
      memcpy(temp, b2n, 4 * 27);
      memcpy(b2n, b3n, 4 * 27);
      memcpy( b3n,temp, 4 * 27);
   }

   int ir2 = BandCompare(b2n, b2min);
   if (ir2 > 0) return 0;
   if (ir2 < 0) {
      cout << "new band2" << endl;
      memcpy(b2min, b2n, 4 * 27);
      memcpy(b3min, b3n, 4 * 27);
      ngvert = 1;
   }
   else {   // now same band 2 see band 3
      int ir3 = BandCompare(b3n, b3min);
      if (ir3 > 0) return 0;
      if (ir3 == 0) { // same; count auto morphs and back
         ngvert++;
         return 0;
      }
      cout << "new band3" << endl;
      // now ir3<0  new min through b3
      memcpy(b3min, b3n, 4 * 27);
      ngvert = 1;
   }
   cout << "new min find ngauto" << endl;
   // if a new min  see if auto morphs are <=
   ngauto = 1;
   for (int i = 0; i < n_auto_b1; i++) {
      BANDPERM & p2 = t_auto_b1[i];
      int b2n2[27], b3n2[27];
      p2.MorphOrdered(b2n, b2n2);
      p2.MorphOrdered(b3n, b3n2);
      if (b2n2[0] > b3n2[0]) {// exchange b2 b3
         memcpy(temp, b2n2, 4 * 27);
         memcpy(b2n2, b3n2, 4 * 27);
         memcpy(b3n2, temp, 4 * 27);
      }
      int ir2 = BandCompare(b2n2, b2min);
      if (ir2 > 0) continue;;
      if (ir2 < 0) {
         memcpy(b2min, b2n2, 4 * 27);
         memcpy(b3min, b3n2, 4 * 27);
         ngvert = ngauto=1;
      }
      else {   // now same band 2 see band 3
         int ir3 = BandCompare(b3n2, b3min);
         if (ir3 > 0) continue;
         if (ir3 == 0) { // same; count auto morphs and back
            ngauto++;   continue;   }
         // now ir3<0  new min through b3
         memcpy(b3min, b3n2, 4 * 27);
         ngvert = ngauto = 1;
      }

   }
   return 1;
}

[champagne]

Night thoughts.

I am not clear on how to show “solution grid auto morphisms”. This night, I remembered an old problem raised during my work on the project of "Mathimagics"

Here is part of a pm sent in April 2023 to “blue”

Hidden Text: Show

To give you the context, we are using the DLL to produce sample files in validation tests of my new code . These tests take place in an area where we have many valid bands 1+2 and often many 18s produced on both side in different conditions. We had difficulty to match the files, so at the end I morphed them to a canonical form.

Big surprise, The DLL output contained plenty of redundant puzzles;

Working on the band index 390 (number 357 in the min lexical order), I had 31 solution grids to study (what comes in the pass 2 , printed here below).
The DLL output for these 31 grids gives 4758 18s, but only 3887 ED puzzles. 652 puzzles have one or more morphs.

As far as I can see, it's not a question of "transpose". My new scan does not work on stacks, and I have a similar redundancy.
It seems to me that most of them appear when we have twice the same band index in bands i&2.
Then we can produce the same puzzles for example in a distribution 747 or 477 (or 666 and 666)

This has been a source of trouble, just because we were looking for other reasons in the matching problems, and I am sure that you did not expect this. The redundancy was expected in the scan, but on my side, this situation was not clearly identified as source of redundancy

these 31 grids

123456789457289163869731524278314956395867412641592378534678291716923845982145637
123456789457289163869731524285673491394128675671945832536894217748312956912567348
123456789457289163869731524518924637736518492942367815271843956384695271695172348
123456789457289163869731524536194278782563491941872635295618347374925816618347952
123456789457289163869731524295673841318524697746918235534867912671392458982145376
123456789457289163869731524295348671314672958786915432538164297642897315971523846
123456789457289163869731524274695831315847296986312457538164972642978315791523648
123456789457289163869731524594163278638572491712894635246918357385647912971325846
123456789457289163869731524238597416594618237671324958345872691712963845986145372
123456789457289163869731524271345896538697412694128357316572948782914635945863271
123456789457289163869731524278643915531978246694125837386592471715864392942317658
123456789457289163869731524291673845534128697678945231382597416746312958915864372
123456789457289163869731524294675318531928476678143952382597641746312895915864237
123456789457289163869731524291564837578392416634817952345678291716925348982143675
123456789457289163869731524345128976786945312912673458234567891598312647671894235
123456789457289163869731524345812976786594312912367458294178635578643291631925847
123456789457289163869731524238564971516897432974123856395618247642975318781342695
123456789457289163869731524276814935518397246934562817382675491695148372741923658
123456789457289163869731524276915348518643972934872651382597416695124837741368295
123456789457289163869731524392678451614592378785143692246817935538964217971325846
123456789457289163869731524395678241641925837782143695236597418518364972974812356
123456789457289163869731524395812476642597318781364952278143695536978241914625837
123456789457289163869731524235874691694512378781693452378125946516948237942367815
123456789457289163869731524284617395635948217791523648372864951518392476946175832
123456789457289163869731524238567491716924835945318672384172956571693248692845317
123456789457289163869731524234178695786945231915623847348567912592814376671392458
123456789457289163869731524235817946781964235946325817392678451578143692614592378
123456789457289163869731524235914678786325941941678235394567812578142396612893457
123456789457289163869731524281945637746123895935678241314867952578392416692514378
123456789457289163869731524378524691592163847641978235234815976716392458985647312
123456789457289163869731524384915672591672348672843951238597416716324895945168237

The band index 357 has no auto morphs, so here we can only have a “vertical” or a “main diagonal symmetry” auto morphism of the solution grid.
note: the 31 grids are likely not in min lexical status, they are in the canonical status of the 17/18 clues scan done.

The good way to avoid the redundancy is surely not to use the canonical (minlex or maxlex) filter;
Instead, we should do the following:
Define as ED puzzle the puzzle having the lowest 81 bit pattern (or any other canonical morph)
Have a list of the auto morphs of the solution grid
Check whether the given puzzle is an ED morph

This pushes in the direction of a permutation descriptor made of the 81 cells mapping and of the digit mapping.
A small problem here is that the cells mapping is not so easy to follow, so the alternative good descriptor giving the transpose status, the rows mapping and the cells mapping will be useful to understand how came the cells mapping

And this gives a good way to filter ED puzzles in a data base of the 18 clues puzzles made of
solution grid rank + 81 bits field

[champagne]

some corollary effect of the above post.

I have for long in mind that for huge data bases of puzzles, the canonical form could be

min lexical rank of the solution
81 bit field pattern of the puzzle in the solution

just to solve the potential redundancy of the solution grid auto morphs, it should be

min lexical rank of the solution
ED 81 bit field pattern of the puzzle in the solution.

In binary mode, this is around 33+81 bits = 15 bytes
my experience with mathimagics tells me that a text mode is useful.

this could be something as

10 bytes for the rank of the solution grid
a sequence of 14 printable characters to show the 81 bits.

I would use "0123456789abcdefghijklmnopqrstuvxyzABCDEFGHIKLMNOPQRSTUVWXYZ%&"
or anything else for the 2 last characters.
as table of 6 bits equivalence

Normally, at the end of the current work, all the tools needed to handle such a design should be available.

[champagne]

I started investigations to see what can be the highest number of auto morphs for a grid.
Having found 72 auto morphs for the last min lexical solution grid, this gives not so many first band to check.
Already, we know that only bands1 having 12 auto morphs or more can pass this.

competitors are the following (band index, count of auto morphs)

Code: Select all

  0 108
 15  54
412  36
  7  18
 26  18
 28  18
 29  18
347  18
  3  12
  8  12
414  12
415  12 done

in fact, for competitors with 12 auto morphs, the only way to reach 72 is to have 3 bands and 3 stack with the same Index


but my bet is that 72 will be the highest count after the following tests
(all this subject to ...)

first test
I checked all solution grids with 3 times the same band index (index 353 and over).
Only one band (out of the last one) had the same index in stacks.

123456789457289631869713245236594817578162394914378526345927168691835472782641953
with 2 auto morphs for the band and 12 auto morphs for the grid, we reach, as in the last solution grid, the maximum of possible auto morphs for the grid.

second test :
With the band 0 as first band, I find 1592 solution grids having 3 times index 0 in bands. This pushes to think that, in most cases, the 108 auto morphs of the first band will not deliver an auto morph for the solution grid

I checked the first 50 solution grids and got 3 auto morphs for the grids for all of them except this one

123456789456789123789123456214367598367598214598214367632941875875632941941875632
total auto morphs 6

In the first test, I had solution grids with no auto morphs for the first band.
For this one, the solution grid has 3 auto morphs, another expected possible result
123456789457289163896317245271643958685192374934875621368521497519764832742938516
index 357 357 357 d 370 370 370
total auto morphs 3

Assuming that the used part of the code is correct, this pushes to think that a maximum of 72 auto morphs is highly probable.
I'll do a full test of the 12 possible first band to verify it;

[champagne]

I lost the bet, I had, in my file to test, the worst case

123456789456789123789123456231564897564897231897231564312645978645978312978312645 ;964550

This is the min lexical solution grid of rank 964550.
All bands and stacks are morphs of the band index 0, giving a potential of 6 x 108 auto morphs for the solution grid.

Still subject to...my code finds the 648 auto morphs for the solution grid.
This case is unique and no other first band can compete..

[champagne]

I started investigations to see what can be the highest number of auto morphs for a grid.
Having found 72 auto morphs for the last min lexical solution grid, this gives not so many first band to check.
Already, we know that only bands1 having 12 auto morphs or more can pass this.

competitors are the following (band index, count of auto morphs)

Code: Select all

  0 108
 15  54
412  36
  7  18
....
414  12
415  12 done

in fact, for competitors with 12 auto morphs, the only way to reach 72 is to have 3 bands and 3 stack with the same Index

Another trivial condition : if we have a grid auto morph in bands, we have the same grid auto morph in stacks,
So, the stack indexes status can tell us that we have no auto morph or can put another limit.

A scan of the band 15 min lexical solution grids gives me as best case this one
123456789456789123897231564231564978564978231789312645312645897645897312978123456
three times index 15 in bands, 3 times index 412 in stacks. 54 auto morphs.
here the maximum expected would have been 3 x 36 = 108.
we have only 3 x 18 auto morphs;

i checked also the 31 solution grids of the fourth post. I get auto morphs with four of them (grid followed by indexes)
123456789457289163869731524285673491394128675671945832536894217748312956912567348 356 356 351/350 28 350
123456789457289163869731524291673845534128697678945231382597416746312958915864372 356 356 351/24 24 24
123456789457289163869731524345812976786594312912367458294178635578643291631925847 356 356 352 /24 28 24
123456789457289163869731524238567491716924835945318672384172956571693248692845317 356 365 382 /382 365 356

In all cases, I find 2 auto morphs, a transpose auto morph for the last one

[champagne]

as nobody came to suggest something, I had to define how to deliver auto morphisms of a solution grid.
This will come as response to a given solution grid (valid, the code assumes a valid solution grid) , in parallel to the min lexical morph of the given.

The list of auto morphs will describe all ways to go from the given to the min lexical;
I looked for a readable and short way to do this.
As the min lexical morph has the first row 123456789, the digit map is somehow redundant.

So my proposal is a char[19] sequence
first character 1 if transpose is first needed (main diagonal symmetry)
9 digits 0-8 to reorder the rows
9 digits 0-8 to reorder the columns.

so, if the given is minimal with no auto morph, the only item will be
"0012345678012345678"

I have not yet finished the coding of the morphs; Is missing the code linked to the first band auto morphs.
Then, I'll have to run many tests, but I'll release the draft;

[champagne]

here, grid auto morphs appear as a co product of the grid minlexing.
Generally speaking, as corollary of the trivial remark that if a grid has auto morphs, then the transposed grid has the same, in a direct search of grids having a potential for auto morphs, we have a quick filter.

Just considering these grids in the top part of the min lex catalog
123456789456789123789123456214365897365897214897214365531642978648971532972538641 0 0 412 \ 245 150 224
123456789456789123789123456214365897365897214897214365531642978672938541948571632 0 0 412 \ 313 148 223

each grid is followed by the band/stack indexes.
Both have in bands a high potential for auto morphs.
In stacks, we have three different indexes, and at least one of the three stacks has no auto morphs.
Such solution grids can't produce auto morphs.

But implementing a code optimizing the process is of null interest here. The first target is to find the min lexical morph of the given.

EDIT: but if one wants to get auto morphs on a slice of the catalog, this quick filter can be applied.

[coloin]

Yes.... a few years ago red ed gave the list of "isohex" grids with the same 6 bands.....Canonical form
The MC grid has long been known to have the 648 isomorphs !

and a little bit furthur down a gem of a question back in 2007 !!

Now, the 1M$ question:)
Given a number x [1<= x <= 5472730538], how to find easily the x(th) min-lex grid.
Alternatively, let g be a min-lex grid g=12345678945...
What is it's ranking x ?JPF

In the thread gsf was getting to grips with generating the catalogue and concluding that the 6-tuple classifier wasnt going to do the job !!

[champagne]

Yes.... a few years ago red ed gave the list of "isohex" grids with the same 6 bands.....Canonical form
The MC grid has long been known to have the 648 isomorphs !

and a little bit furthur down a gem of a question back in 2007 !!

Now, the 1M$ question:)
Given a number x [1<= x <= 5472730538], how to find easily the x(th) min-lex grid.
Alternatively, let g be a min-lex grid g=12345678945...
What is it's ranking x ?JPF

In the thread gsf was getting to grips with generating the catalogue and concluding that the 6-tuple classifier wasnt going to do the job !!

Interesting, and yes what I am doing is one response to the question raised by "JPF" years ago .
Here the first post in your link

The non-uniqueness of the index416-coding on those "70,70,70,70,70,70" grids isn't just because the chute indices were all the same. I wrote a program to find all grids (up to isomorphism) with user-specified chute indices. After setting it to work finding the (fairly short) catalogue of all "isohex" grids, I decided to ask it to produce solutions with chutes matching the SF grid -- and it found four:
....
I can post the "isohex" catalogue if anyone wants it. But first we need to think of a better name than "isohex":)

I had a look to the list of min lexical bands with the band index 0 as first band. Looking for a quick filter, It appears clearly that the "transpose constraint" reduces sharply the number of grids having a potential for an auto morph.

And the wording of the post let think that "the catalogue of all "isohex" grids", is small.
Do you have a copy of the results or a pointer still valid to load it??

I'll give in a separate post, in the format described above, the table of auto morphs for the last solution grid (72) with the way to use it (the code I use to check the validity of the process). I should have time enough to-day to run and check it.
I should be in a position to deliver the DLL for this part of the code this week, then I'll have to make the final touch to the virtual catalog and build the DLL.
The services to offer in the virtual catalog DLL are not yet quite clear in my mind, but I think necessary to have a possibility for the user to get in sequence a slice of the catalog to work on each item.

EDIT I just see that the reference is limited to solution grids having six times the same index in bands and stacks.
Then, yes, the file can be very small. I'll work out later a ratio of solution grids having auto morphs.

[champagne]

As example of the grid auto morphs description,
the list of the 72 grid auto morphs for the last grid of the min lexical catalog
and the way it it used in my code to check the validity

123456789457893612986217354274538196531964827698721435342685971715349268869172543; 5472730538; 415 415 415

int the code, this solution grid is seen as
int g0[81] where each character is changed to a digit 0-8

the 72 permutations as stored in my code as a 19 characters field
0/1 1 if transpose is needed first
9 digits 1-9 giving the rows order
9 digits 1-9 giving the columns order

Hidden Text: Show

0123456789123456789 __ 0
0123879546213546798 1
0213546879123897645 2
0213789456213987654 3
0123456789456897312 4
0123879546546987321 5
0213546879456123789 6
0213789456546213798 7
0123456789897123645 8
0123879546987213654 9
0213546879897456312 10
0213789456987546321 11
1123456987123456987 __ 12
1123897546213546978 13
1213546897123879645 14
1213987456213789654 15
1123456987456879312 16
1123897546546789321 17
1213546897456123987 18
1213987456546213978 19
1123456987879123645 20
1123897546789213654 21
1213546897879456312 22
1213987456789546321 23
0456879213123456789 __ 24
0456123789213546798 25
0546789123123897645 26
0546213879213987654 27
0456879213456897312 28
0456123789546987321 29
0546789123456123789 30
0546213879546213798 31
0456879213897123645 32
0456123789987213654 33
0546789123897456312 34
0546213879987546321 35
1456897213123456987 __ 36
1456123987213546978 37
1546987123123879645 38
1546213897213789654 39
1456897213456879312 40
1456123987546789321 41
1546987123456123987 42
1546213897546213978 43
1456897213879123645 44
1456123987789213654 45
1546987123879456312 46
1546213897789546321 47
0789213456123897645 __ 48
0789546123213987654 49
0879123546123456789 50
0879456213213546798 51
0789213456897456312 52
0789546123987546321 53
0879123546897123645 54
0879456213987213654 55
0789213456456123789 56
0789546123546213798 57
0879123546456897312 58
0879456213546987321 59
1897123546123456987 __ 60
1897456213213546978 61
1987213456123879645 62
1987546123213789654 63
1897123546456879312 64
1897456213546789321 65
1987213456456123987 66
1987546123546213978 67
1897123546879123645 68
1897456213789213654 69
1987213456879456312 70
1987546123789546321 71

to check the validity the code builds the morph and compares the result to the given

Code: Select all

GRIDPERM mypr;
mypr.Import19(g0, wexp3);
mypr.Morph(g0, gout2);

are used here
the transpose table (main diagonal symmetry )

Code: Select all

int C_transpose_d[81] = {
   0, 9, 18, 27, 36, 45, 54, 63, 72, 1, 10, 19, 28, 37, 46, 55, 64, 73,
   2, 11, 20, 29, 38, 47, 56, 65, 74, 3, 12, 21, 30, 39, 48, 57, 66, 75,
   4, 13, 22, 31, 40, 49, 58, 67, 76, 5, 14, 23, 32, 41, 50, 59, 68, 77,
   6, 15, 24, 33, 42, 51, 60, 69, 78, 7, 16, 25, 34, 43, 52, 61, 70, 79,
   8, 17, 26, 35, 44, 53, 62, 71, 80,
};

A permutations handler structure

Code: Select all

struct GRIDPERM {
   int transpose;
   int rows[9], cols[9], map[9];
   void Export( char * w);
   void Import( int transp,BANDPERM & p, int* rr);
   void Import19(int *g0,char *x19);
   void Morph(int* s, int* d);
};


The first step change the 27 char field in the internal working pattern
Here the missing digit map is built using the row 1 of the morph

Code: Select all

void GRIDPERM::Import19(int* g0, char* x19) {
   transpose = x19[0] - '0';
   for (int i = 0; i < 9; i++) {
      rows[i] = x19[i + 1] - '1';
      cols[i] = x19[i + 10] - '1';
   }
   // must do the digit mapping on morphed row 1
   int w[81];
   if (transpose) {// transpose before
      for (int i = 0; i < 81; i++)w[i] = g0[C_transpose_d[i]];
   }
   else  memcpy(w, g0, sizeof w);
   // morph row 0
   register int  drows = 9 * rows[0];
   for (int icol = 0; icol < 9; icol++)
         //map[ icol] = w[drows + cols[icol]];
      map[w[drows + cols[icol]]] = icol;
}


and the next step builds the morph using the permutation parameters.
The result must be identical to the entry

Code: Select all

void GRIDPERM::Morph(int* s, int* d) {
   int w[81];
   if (transpose) {// transpose before
      for (int i = 0; i < 81; i++)w[i] = s[C_transpose_d[i]];
   }
   else  memcpy(w, s, sizeof w);
   for (int irow = 0; irow < 9; irow++) {
      register int drow = 9 * irow, drows = 9 * rows[irow];
      for (int icol = 0; icol < 9; icol++)
         d[drow + icol] = map[w[drows + cols[icol]]];
   }
}



I'll give in a separate post some results of the analysis done on the auto morphs for the top part of the catalog (band index 0 as first band)

[champagne]

The MC grid has long been known to have the 648 isomorphs !

I never worked earlier on auto morphs of a grid. I just noticed that this was a co-product of the min lexical search for a given solution grid.
So in fact, I don't know what MC means;

In the min lexical catalog, the second solution grid (first with 3 times the band index 1) is

Code: Select all

123 456 789
456 789 123
789 123 456

214 365 897
365 897 214
897 214 365

531 642 978
642 978 531
978 531 642   ;1;0  0 0

the grid with the 648 auto morphs comes later with the rank 964550

Code: Select all

123 456 789
456 789 123
789 123 456

231 564 897
564 897 231
897 231 564

312 645 978
645 978 312
978 312 645   ;964550;0  0 0

Having the list of solution grids with 2 or 3 times the band index 0 in bands, I tested on this file how are coming the auto morphs for a grid.
This is partial, but as the band index 0 has 108 auto morphs, the results are interesting.
I intend later to do a comprehensive analysis of this typology when the DLL of the virtual catalog is available;

Following the process used to search he min lexical morph of a given, I split the auto morphs count in 2 terms:

n1 _ a (first) band permutation count (then, due to the constraint in the first column we have only one row order) what I call the vertical count
n2 _ a_n auto morph permutation in the first band.
the count of auto morphs for the grid is n1 x n2.

I'll show here examples of the most common cases seen and in a next post comments on other cases.

____________________________________________________________________________________

Most of the solution grids of this file having auto morphs have 3 times the same band index in stacks

one example

123456789456789123789123456214365897365897214897214365548632971632971548971548632
stacks 3 times index 47
Then, we have only one first band giving the min lexical order and 2 permutations of the band 1 giving the count 3.
As far as I can see, the 2 permutations are always the same or similar

Code: Select all

201  rows order
345678012 cols order
012345678 digit map

Code: Select all

120 rows order
678012345 cols order
012345678 digit map

here, we have the 2 auto morphs in the first band leading to a stack permutation with no digit mapping

Note : as the start is min lexical, the first min lexical comes always from the first band of the given.
_______________________________________________________________________________

Another frequent case is a final count of 2, always a first band auto morph,
In this file, this happens only with indexes 0;0;412 or 0;412;0 in bands
in stacks, the pattern is x;x;y of x;y;y

here 2 examples, in stacks 1;17;17 for the first, 17,17,1 for the second.

123456789456789123789123456231564897564897231897231564312648975675912348948375612 morph

Code: Select all

021354687 rows
012678345 cols
012678345 maps

123456789456789123789123456231564978564897312897231645315642897672918534948375261 morph

Code: Select all

021354687 rows
345012678 cols
345012678 maps

Again a swap of stacks, but needs a rows reordering and a digits mapping.

[dobrichev]

Hi Champagne,

You can find an old and working code for determining the minlexing mappings in gridchecker's rowminlex.h and rowminlex.cpp, a modification of Glenn Fowler's sudoku solver/generator code.

Example usage:

Code: Select all

char sol[81];
transformer minlexer;
minlexer.byGrid(sol);
// here you have number of automorphisms stored in aut, as well as chain of additional transformations in *next.
transformer* currentTransformation = &minlexer;
do {
   // do something with the currentTransformation members box, map, row, col. See methods transform, ransformAll, reverseTransform for usage.
  currentTransformation = currentTransformation->next;
} while (currentTransformation);


As a bonus, if you pass a puzzle over transform method, you receive the minlexed one over all solution grid automorphs - something you should do in the compressed puzzle catalog.

Initializing transformer by passing an already minlexed grid will give identity as one of the transformations, see isTransforming method. Rest of the transformations are likely these you want to investigate further.

BR,
MD