The New Sudoku Players' Forum

[StrmCkr]

http://forum.enjoysudoku.com/about-red-ed-s-sudoku-symmetry-group-t6526.html

starting grid
apply these transformations specifically. { p.s include a transpose on the grid for completion}

coupled with the 9! digit re-swap the new grid then checking start grid to transformed grid for a 1:1 mapping = automorphic grid.

[Sojourner9]

Realized I just needed to check the 416 and No it is not a general rule that 7189 appears in all. So there are still 36 gyrations.
Sorry for so much thinking out loud.

[Sojourner9]

Preliminaries ...
1) set up a "best case" (result) grid that r4c1 set to 10, the best band result in band 1, and garbage everywhere else.
2) look up the "one of 416" index for the best case band 1, and use it to look up a list of band 1 automorphisms
The automorphism list should include the identity transformation.

I like that you mentioned the automorphisms and including the identity. I would be interested in seeing what a list of automorphisms looks like, even if it is just in a PM.
...
I don't think I would know if the solution grid was automorphic by rotation for example.
All I know is when swapping the columns and relabeling, results in the same band2 and band3.

Hi, I had hoped to hear back on band 1 automorphisms and how they are represented, but I went off and looked at on my own.
Originally was using a structure that I had to update anytime I swapped a row, band, column, stack or transposed. The output looked something like:

Code: Select all

    //   TR   Bnds Stks Bnd1 Bnd2 Bnd3 Stk1 Stk2 Stk3 Relabel
    ( 23, 123456789, 456789132, 789213654,   2, [
        (.id ,.id ,.id ,.id ,.id ,.id ,.id ,.id ,.id ,123456789),
        (.id ,.id ,.AB ,.AC ,.id ,.id ,.id ,.id ,.AC ,213789456)
    ]),


Here the columns are Transposition, Bands, Stacks, Band1, Band2, Band3, Stack1, Stack2, Stack3, Relabel.

Over time I got smarter about it and just created a rowMap, columnMap, and relabelMap using integers because it is easier to store in the code.
Now the same thing looks like:

Code: Select all

    { 23, 123456789, 456789132, 789213654,   2, 34 },
...
    (Reorder[]) { // 34
        { 123456789, 123456789, 123456789 },
        { 321456789, 456123987, 213789456 }
    },


You can see they do the same thing.

So any of the 3,359,232 reordering can be represented using a rowMap and a ColumnMap. To document transposition I add a minus sign to the columnMap if it is transposed.
This is like an S9 group that has 9! permutations except it has the added restriction that the numbers 123, 456, and 789 each have move together cross bands and stacks.
The relabelMap is included because the 416 is deterministic so we always get the same relabels.

So now I never swap any data in the grid. I just de-reference it through the maps and do the swaps in the maps.

Each of the 416 has an automorphism count or AMC for short, and a reorder subgroup, which I think is what you are calling automorphisms.
So if the AMC = 1 then the subgroup is the identity transformation or reordering. The distribution or the AMC is:

Code: Select all

AMC = [1: 279, 2: 106, 3: 2, 4: 1, 6: 18, 12: 2, 18: 6, 54: 1, 108: 1] = 416


So 279 of 416 are AMC 1 which means they are not automorphic.
There are 84 different subgroups that range from the trivial, AMC 1, to the redundent, AMC 108.
The last four 413, 414, 415, and 416 have unique subgroups and double in size if we include both cases for columns 8 and 9. They are never used because no grid ever uses them as the band 1 winner.

Using this knowledge, I created a C program, gridMinLex, that can convert wild grids to their gridMinLex at a rate of 150000 to 200000 grids/sec.
It returns the minLex grid and the reordering it took to get there. So for the six AMC 2 automorphic grids in the 49158 17 clue puzzles it returns two reorders.
I have analyzed the six automorphic grids from the 17 clue puzzle list using this code. Which I will present as a separate post.
I am pretty sure I can detect all grids that are automorphic by rotation and transposed. I will look at the set of all automorphic grids at some point.
My original analysis took 812 seconds or 13m 32s to read in 48159 minLex puzzles, solve them, grid minLex the results, then reorder the puzzles using grid minLex reordering, and report the results.
Now it takes 6.229s.

So is 200000 grids/sec. Is that fast?

[blue]

Hi Sojourner9,

Hi, I had hoped to hear back on band 1 automorphisms and how they are represented, but I went off and looked at on my own.

Sorry I didn't get back to you on this.
One person's "right answer" might not match the next, depending on how you want to use them.

I do something like this:

Code: Select all

struct BandTForm {
    unsigned char r_order[3];
    unsigned char c_order[9];
    unsigned char map[10];
};

// example:
//
// BandTForm t = {
//     { 1, 0, 2, },                     // r_order[]
//     { 3, 4, 5, 0, 1, 2, 6, 7, 8, },   // c_order[]
//     { 0, 7, 8, 9, 4, 5, 6, 1, 2, 3 }, // map[]
// };
//
// usage:
//
// for (int r = 0; r < 3; r++)
// for (int c = 0; c < 9; c++)
//     band_out[r][c] = t.map[ band_in[ t.r_order[r] ][ t.c_order[c] ] ];

So is 200000 grids/sec. Is that fast?

Some others may like to comment, but I think it's quite good.
Congratulations !

Blue.

[Sojourner9]

Thanks Blue,

My rowMap maintains a constant 456789 until I call sort rows to set the order for bands 2 and 3.
Do you have may places where you use a literal array, other than {0,1,2,3,4,5,6,7,8}?
I think I tried expressing the maps as arrays but it took longer to copy the array than to convert it from an integer.
I used two little recursive routine to convert the integer to an array.

Code: Select all

void int2a1(int * ptr, int input) {
    *ptr = input % 10;
    if (input < 10) return;
    int2a1(ptr-1,input/10);
}

void int2a0(int * ptr, int input) {
    *ptr = input % 10 - 1;
    if (input < 10) return;
    int2a0(ptr-1,input/10);
}
// Usage     int2a0(&colMap[8],123456789);
// Faster than for (i = 0;i<9;i++) colMap[i] = i;


I just point it at the end of the array and it moves backwards because that's how I decompose the integer.
I base 1 the numbers so I don't loose a leading zero then subtract 1 when I convert else I use the first routine that does not subtract 1.

I needed to use JCZSolver in my Swift code but had problems having duplicate "main" routines.
So I separated the command line interface from the body of the code and put it into a file called JCZSolve.c and created a .h file.
Now I can call it from XCode without the main, but still execute it from the command line.

I fixed the index416 program to make it return 416 numbers in minLex order, I call it minLexML.
I only fixed the 416 index returns not the 44 as I am not sure what counts as the standard order there.
I think the translation tables were made by dusoku and the body code was by kjellg.
I had the same problem with duplicate mains and index416 was dumb because it could only read grids from a file.
So again I moved the body to a separate file called index416ML.c and created a .h file and can call it from my Swift programs.
I had to create the index416ML(const char *grid,int *result) and pass it a grid string and a pointer to the results.
I do the initialization once and have confirmed that it stays resident and initialized between calls.
Like I said the command line interface was dumb.
So I borrowed the main from JCZSolver and renamed the call index416ML.
So now you can pass grids as stdin and it will work, or read them from a file and get a report on how many grids/sec it can do.
But the output of index416ML is just further input in the code so there is never a need to read from a file, etc.

So of course when I created gridMinLex i borrowed the main from JCZSolver and I have a file called gridMinLex.c with a .h file that I can call.
I wish I could use this idea of separating the body from the CLI with gsf's code.

I hope I am not violating any ones Usage Agreement, I suppose the moderator might have a say, since I think he is the author. Jason?

Anyway I really should have written more about the subgroups than software because that is the star here as it shows the symmetries of the bands and grids.

[coloin]

I fixed the index416 program to make it return 416 numbers in minLex order, I call it minLexML.
I only fixed the 416 index returns not the 44 as I am not sure what counts as the standard order there.

Very good that you have addressed this .... !
I think the minlex 44 is the most logical way too

On the back of your discovery of the automorphic 17s, puzzle transformations similar to what you have done was thrashed out Grid Transformations
In that thread we were discussing the transformations to go from one isomorphic puzzle to another.
Here we are going from one solution grid ending up with the same solution grid which is similar but still boggling [for me] !

[champagne]

I needed to use JCZSolver in my Swift code but had problems having duplicate "main" routines.
So I separated the command line interface from the body of the code and put it into a file called JCZSolve.c and created a .h file.
...
So I borrowed the main from JCZSolver and renamed the call index416ML.
...
I hope I am not violating any ones Usage Agreement, I suppose the moderator might have a say, since I think he is the author. Jason?

Hi,

I did not follow all the content of the thread, but a comment on the "potential rights " on JCZSolver.

The original idea is from zhouyundong_2012.
I made and uses several variants of this first shot and one of them has been used by "Jasonlion" to publish JCZSolver where if I am right

J is for Jasonlion
C is for Champagne
Z is for zhouyundong_2012

If you used any of my variants of zhouyundong_2012' code, it starts by something as .

ZhouSolver.h
Based on code posted to <http://forum.enjoysudoku.com/3-77us-solver-2-8g-cpu-testcase-17sodoku-t30470.html>
by user zhouyundong_2012.
The copyright is not specified.

All the code that I published is under he GNU GENERAL PUBLIC LICENSE which means to make it simple, as far as I know, free use but no possibility to catch the property.

I don't know if Jasonlion made more restrictions, but as long as we are considering the brute force solver, the use remains free.


and BTW, JasonLion is not anymore owner of the forum

[Serg]

Hi, Sojourner9!

I needed to use JCZSolver in my Swift code...

I've been using JCZSolver since 2016. Its performance is excellent and it doesn't use special CPU instruction sets, such as 128-bit registers etc, so it is wide portable. Solver may be called by function JCZSolver(puzzle,solutiongrid,1) - search for the first solution only (population of grid), or by function JCZSolver(puzzle,solutiongrid,2) - search for the two first solutions only (the function returns number of found solutions, if it returns "2" - you have mulisolution puzzle, if it returns "0" - the puzzle has no solutions).

You should know that "solutiongrid" array of char must have dimension of 82, because solver's code has the string "solution[81]=0;". Input array "puzzle" may have dimension of 81 ("end of string" zero byte is not required).

Serg

[Sojourner9]

I was wrong on what I said about JCZSolve.
I thought it odd that the main was called JCZSolveMain.c and thought I had changed the name.
I did not go back to the original code to check because I didn't realize there was a problem.
So I did not modify JCZSolve at all I just benefited from the fact that it was already easy to import into Xcode.

I then copied JCZSolveMain as the front end on index416ML, calling it index416MLMain.c.
I did the same thing for gridMinLex.

I was reading the thread that coloin had include on grid transformations and was surprised recent the thread was.
I assumed all of this was hashed out years ago.
But this is what I wanted to address, so that is great.

[blue]

My rowMap maintains a constant 456789 until I call sort rows to set the order for bands 2 and 3.
Do you have may places where you use a literal array, other than {0,1,2,3,4,5,6,7,8}?

None.

One person's "right answer" might not match the next, depending on how you want to use them.

I think I tried expressing the maps as arrays but it took longer to copy the array than to convert it from an integer.
I used two little recursive routine to convert the integer to an array.

Case in point.

[Sojourner9]

Blue,
When you say you are using the automorphisms, do you mean the 275, or the 27 of 275 that produce automorphic grids or what?
Do you know about the subgroups I am talking about?

[Sojourner9]

Based upon how my gridMinLex works, I analysed the six automorphic grids found in the 71clue48159.

Grid 12498

• Previously, 12498 has band/stack numbers 33 1,33 1,28 2,319 2,319 2,303 2.
• So the winning band is 28 AMC 2 with two copies of 33 AMC 1 for band 2 and 3.
• It was shown that one version of 28 picked up one of the 33 as band2.
• The other version of 28 picked up the other 33 as band2.
• It is interesting that the losing stacks were all AMC 2 and two copies of 319.

Grid 18679

• Grid 18679 has band/stack numbers 14 2,392 2,45 2,179 1,9 12,179 1.
• The winning stack is 9 AMC 12 with two copies of 179 AMC 1 for bands 2 and 3.
• This time I have 12 iterations to go through.
• Two iterations had 219 for r4c123, one from band 2 and one from band 3.

Grid 23847

• Grid 23847 has band/stack numbers 2 4,125 1,125 1,167 2,148 2,286 2.
• The winning band is 2 AMC 4 with two copies of 125 AMC 1 for bands 2 and 3.
• This time I have 4 iterations to go through.
• Again all the loosing stacks were AMC 2.
• Two iterations has 238617 for r4c123456, one from band 2 and one from band 3.

Grid 34844

• Grid 34844 has band/stack numbers 284 2,176 1,176 1,376 1,376 1,21 2.
• The winning stack is 21 AMC 2 with two copies of 376 AMC1 for bands 2 and 3.
• This time the loosing bands were not all AMC 2, but there was two copies of 176.
• Both iterations has 245 for r4c123, one from band2 and one from band 3.

Grids 35709 and 35716

• Grids 35709 has band/stack numbers 334 2,374 1,374 1,376 1,376 1,21 2.
• The winning stack is 21 AMC 2 with two copies of 376 AMC 1 for bands 2 and 3.
• Again the loosing bands had two copies of 374.
• Both iterations had 248 for r4c123, one from band 2 and one from band 3.
• Grid 35716 has band/stack numbers of 334 2,374 1,374 1,376 1,376 1,21 2.
• This wild grid was not the same as 35709, likely because band 2 and 3 were swapped.
• The intermediate grids, after the intelligent reordering but before the rows were sorted, are the same.
• This means that the intelligent reordering must have fixed the two grids.

I was anticipating that some magical bit ORing of the reorders would lead to an automorphic grid, but I now don't think that is necessary.

Take the largest automorphic count grid. It has band/stack numbers of 0,0,0,0,0,0 each with an AMC 108.
I go through all 108 elements of the subgroup and for each the same result, which is the minLex.
I repeat this for all 6 bands and stacks and each gets 108 of the same result.
So when I am done there are 6x108 = 648 AMC for the grid.
And my program lists out all 648 reorders.

I conjecture that if the winning band/stack has an AMC 1 then the grid can not be automorphic unless there are multiple winners.
But then the other two have to be the same, which means the bands and stacks each have the same three members of the 416.

As I said I need to check the set of all automorphic grids.

[coloin]

Im not quite sure what you mean with winning and losing bands.

There are 9 "crossing bands" in each solution grid [eg B12347]

Looking at 17puzzle #12498 in its minlex grid , Box 3 remains Box 3 in both puzzles, so band 1 and stack 3 are constant [ at box 3 intersection]
Therefore band 2 and band 3 are the same and stack 1 and stack 2 are the same [and are swappable].

There wont always be this reference Box in automorphic grids with higher orders ....eg if all the bands are the same / all the stacks are the same - as you have alluded to.

The MC grid has the 648 automorphisms you have described.

[blue]

Hi Sojourner9,

When you say you are using the automorphisms, do you mean the 275, or the 27 of 275 that produce automorphic grids or what?
Do you know about the subgroups I am talking about?

Second part first: I know the ones you're talking about, although I hadn't realized that some (minlex) bands have the same (non-trivial) automorphism group
There are 84 distinct groups, as you say ... not (416-279)+1 = 138 !

The last four 413, 414, 415, and 416 have unique subgroups and double in size if we include both cases for columns 8 and 9. They are never used because no grid ever uses them as the band 1 winner.

There is one (minlex) grid where every band/stack is is "type 416".

Code: Select all

123456789457893612986217354274538196531964827698721435342685971715349268869172543 (72 automorphisms)

Band 416 has 12 automorphisms, so the 72 automorphisms for the grid, must be 6 ways to choose a "winning" band/stack, times 12 ways to map it to the minlex form, with each case giving the same result in r456789, after column 1 is "sorted".

---------

For the first part: The only ones I actually use, are the band automorphisms.
At the end of this post I mentioned a way of counting automorphisms.
There, I meant automorphisms for the full grid ... which puts them in the union of the 27 relevant conjugacy classes.

[Sojourner9]

Im not quite sure what you mean with winning and losing bands.

There are 9 "crossing bands" in each solution grid [eg B12347]

Looking at 17puzzle #12498 in its minlex grid , Box 3 remains Box 3 in both puzzles, so band 1 and stack 3 are constant [ at box 3 intersection]
Therefore band 2 and band 3 are the same and stack 1 and stack 2 are the same [and are swappable].

There wont always be this reference Box in automorphic grids with higher orders ....eg if all the bands are the same / all the stacks are the same - as you have alluded to.

The MC grid has the 648 automorphisms you have described.

Do you really. mean 9 or 6 bands?
The next thing I was going to look at, after all this, was the B12347 method and gang of 8650? for B2 B3 columns and B4 B7 rows, that I had seen from a long time ago.
But I don't know how to talk about that yet. I think the B12347 method requires B1 relabeling where minLex requires row1 relabeling.

To answer your question, i never look at what gets moved and what does not, only what the minLex looks like and how to get there.
The winning band is the lowest band index for the six bands/stacks, because that will have to be the band index for band 1 in the minLex grid.
Some reordering is done to get the winning band/stack into band 1 and band 2 and 3 are arbitrary because they get sorted later.
Band 1 likely not in minLex order yet. If the band is AMC 6, for example, then there are six ways our of 108 or 72 to get there.
But I only need the first one I find because I can compose this with each element of the subgroup for that band index.The elements of the subgroup are reorderings.
Once band 1 is in minlex order, the columns and relabeling is fixed for the whole grid. I can just look at column 1 and sort the rows and bands to get as close to minLex as I can for that band 1.
I still have to assemble all 81 symbols into a string and keep track of which the smallest one. Each time I do this, the column 1 selected and relabeling changes.
If I keep a list of the final reordering each time I find the minLex, then I have the reorderings of the grid. Getting more than one entry means the grid is automorphic.
But these reorderings are from the original grid position to the final minLex Grid.
This is useful when converting a puzzle from puzzle minLex -> wild solution grid -> minLex solution grid, because I can now reorder the puzzle to grid minLex.
But if I want back to the original grid position I need to "multiply" each by that the inverse of the wild to minLex reordering.
But I haven't coded that up yet.

Dense read, from a dense guy, hope this helps answer your question.