The New Sudoku Players' Forum

[champagne]

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

Hi mladen,

I have the code here and I studied, years ago, the rowminlex.cpp code. If I remember properly, the process was to run all valid permutations. It works well, but it is a slow process. I have somewhere a derived version of it without the auto morphs feature.

As I don't foresee so many solution grids having auto morphs, I'll surely try to benchmark the code against a known bug free code.
Can you give me the command to use in grid checker to process a given and get the min lex and the auto morphs.

And yes in the draft of the virtual catalog, if you call the relevant process with a given solution grid, you receive the min lexical morph (and/or it's rank).
In this project of DLL, I copied in some ways the draft but I added the mapping for all auto morphs, and tried to insert it in a cleaned version of the draft.

Best Regards

Champagne

[champagne]

More thoughts about the auto morphs in solution grids.


Here the list of solution grids having a high count of auto morphs with

band "index 0" 3 times in bands

A index of the same band index appearing 3 times in stack
B Number of auto morphs (over the base) of "B"
n1 Number of "first band" leading to auto morphs of the grid
n2 Number of auto morphs of the grid for a given band 1
nauto total number of auto morphs fro the grid.
A B n1 n2 nauto

Code: Select all

123456789456789123789123456231564897564897231897231564348672915672915348915348672 26  17  2  27  54
123456789456789123789123456231564897564897231897231564348915672672348915915672348 26  17  2  27  54
123456789456789123789123456234567891567891234891234567345678912678912345912345678 28  17  3  18  54
123456789456789123789123456234567891567891234891234567372615948615948372948372615 29  17  3  18  54
123456789456789123789123456234567891567891234891234567318642975642975318975318642 7   17  3  18  54
123456789456789123789123456235964817817235964964817235392641578578392641641578392 347 17  3  18  54
123456789456789123789123456267591348591834672834267915375618294618942537942375861 15  53  3  18  54
123456789456789123789123456267591834591834267834267591375942618618375942942618375 15  53  2  27  54

123456789456789123789123456231564978564897312897231645312978564645312897978645231 0   107 4  18  72

123456789456789123789123456231564978564978231978231564312645897645897312897312645 412 35  3  36  108
123456789456789123789123456231564897564897231897231564312978645645312978978645312 0   107 2  54  108

123456789456789123789123456267591834591834267834267591375618942618942375942375618 15  53  3  54  162

123456789456789123789123456231564897564897231897231564312645978645978312978312645 0   107 6 108  648

I have no solution grid with twice the index 0 in bands reaching such a count.
I did not search solution grids with less than twice index 0 in bands.

All seen solution grids with >= 54 auto morphs in my file have a repetitive index in stacks,
The number of auto morphs for the band is >=18 (including the base)

We have 3 solution grids with 6 times index 0, only one has the maximum expected count.
This is surely in the "Red Ed"study pointed by "coloin".

The maximum possible count with band index 15 in stacks is 3* 108. It did not show up.
Note : all bands having 18 auto morphs or more appear at least once in stack in this list;



The next maximum possible (if true, in the list of "Red Ed" ) is 6*54=324 with 6 times the band 15.


In my file, with a hand made sorting I find the following distribution with >= 9 auto morphs(nauto, n grids)

Code: Select all

9    8
12  16
18  33
27   1
36   4
54   8
72   1
108  2
162  1
648  1

we know that the band index 415 delivers a count of 72.
Each of the bands index 15,412,7,26,28,29 can do better, but it will remain a small number of solution grids.

I intend, as sample of work producing a binary property of the solution grids, to scan with the DLL the full catalog to detect all grids having auto morphs.

The results should be a 5472730538 bits field.If we want to have it as text file, I would use the 6 bit per byte design suggested earlier, around 1MB for the entire file.

Note : this has been done in 2 steps, one step building a file of solution grids with 2/3 times the band index 0, then the program testing the draft of this DLL.
The target will be to do it in one step, with a sequential access to the part of the catalog.

[dobrichev]

Can you give me the command to use in grid checker to process a given and get the min lex and the auto morphs.

No such command exists.
Also a convention for textual representation of the transformation isn't discussed/implemented.

Part of this functionality is used in grouping puzzles by solution grid and transforming them so that the solution is in its minlex form.

gridchecker --solve --groupbygrid < puzzles.txt > ordered_minlex_solutions_plus_deduplicated_transformed_pussles.txt

Surely you will achieve good performance. Deverin's minlexing approach, which I believe is the base for your DLL, is proven to work much faster than gsf's.
Nevertheless gsf's approach is very fast too.
In my practical tasks, minlexing takes a negligible amount of resources, and reducing the minlexing time from 1% to 0.001% will not improve the whole process.

[coloin]

Now there is another table, produced originally by gsf, that lists the number of essentially different grids by automorphism group:

Code: Select all

Aut#      Grids
----------------
   1 5472170387   
   2     548449       
   3       7336       
   4       2826       
   6       1257       
   8         29       
   9         42       
  12         92       
  18         85       
  27          2       
  36         15       
  54         11       
  72          2       
 108          3       
 162          1       
 648          1       
===============
     5472730538      total   
   - 5472170387   
         560151

From a post from here which leads to here which leads to Red Ed

[champagne]

Now there is another table, produced originally by gsf, that lists the number of essentially different grids by automorphism group:
...
From a post from here which leads to here which leads to Red Ed

Thanks a lot "coloin" for all these links to the past.
Happily, I see no contradiction in the bottom part of "gsf"s list and what I got with the band index 0 (except a typo for the 108 auto morphs).
This list gives me a sound basis for a validation test to run using the DLL.
I also noticed that some "potential high auto morphisms" did not show up. The 324 = 6x54 has no corresponding solution grid for example.

[champagne]

Surely you will achieve good performance. Deverin's minlexing approach, which I believe is the base for your DLL, is proven to work much faster than gsf's.
Nevertheless gsf's approach is very fast too.
In my practical tasks, minlexing takes a negligible amount of resources, and reducing the minlexing time from 1% to 0.001% will not improve the whole process.

I quite agree that in many cases, the minlexing time is not a priority, same for the list of auto morphs.
Getting a live response to have the results available as part of a wider process has a bigger interest.

I was interested by the auto morphs for the reason explained earlier in this thread. In the 18 clues search and in the DLL of "blue" analyzing a solution grid, This property is source of redundancy.
One way to clear the redundancy is to move all sudokus to a canonical form to make the clearing, This is what has been done in the 17 clues scan.
A nicer solution is to use auto morphs (if any; from gsf's table, only 1/10000 solution grids have auto morphs) to do the clearing. This DLL should help.

And The source of this DLL is not Deverin's work, but more what has been done in the 17 clues scan, but with all things shared in the forum, it's always difficult to tell what is new and what is derived from another work.

[champagne]

Tests are ongoing, but the DLL works and I loaded the stuff in the wirtual catalog repository
https://github.com/GPenet/Virtual-calatog

the files needed to use it are
skbgridmin.dll
skbgridmin.lib
skgrid_minlex_user.h

The DLL works in 2 ways :

send a solution grid, get the minimal
same plus get the auto morphs given => minlex.

In the second case, a structure is available containing

the auto morphs permutations with the count,
but also the main data that I see as necessary to work on the results.
So far, the return contains the six bands/stacks Ids plus the split of the auto morphs in bands swap and first band auto morphs


the user file has so far only the calling necessary information, I intend to add later some comments on the use of the table of auto morphs.

here is the current status of the user file

Hidden Text: Show

Code: Select all

#pragma once
//skgrid_minlex_user.h - find minlex and auto morphs of a solution gris (no validity check)


/*
this DLL uses the Band mapping DLL skbminlex

The main entry receives a valid solution grid and send back the minlex morph of the entry.
The entry can be a 81 character field
or a int x[81] where each digit is an integer 0-8 replacing the characters 1-9

If the user is interested in getting back the auto morphs permutations of the solution grid,
a first call (valid for the full run) gives the pointer to a "struct" containing
  the table of permutation giving the minlex out of the entry
  receiving the number of auto morphs
  the number of valid items
  (first is neutral if the entry is already  minlex)
Are also sent back the main component of the analysis
  bands and stacks indexes
  vertical (band wap and horizontal (first band auto morphs )count of auto morphs
   
  To get it, it must be seen as the following structure 
 
  struct TPGC { char t[648][19]; int nt,bs_id[6],nv,nh; }*p_tpgc;
 
  and the call will return the value for the pointer p_tpgc
 
//================ First call to get auto morphs
extern "C" __declspec(dllimport) TPGC * SkbsSetModeWithAutos();
 
TPGC *        return value for the pointer to the table

struct TPGC { char t[648][19]; int nt;}*p_tpgc;
p_tpgc=SkbsSetModeWithAutos();

//=============== find the min lexical
2 calls differing by the given solution grid
(not verified, unpredictable behaviour if it's not a valid entry )
   given is a classical char [81]
   given is a int[81] where each cell has a value 0-8
The min lexical morph is returned as a int [81]

char zc[81];
int zint [81],zret[81];

SkbsGetMinChar(zc, zret); or
SkbsGetMinChar(zint, zret);


*/
struct TPGC { char t[648][19]; int nt, bs_id[6], nv, nh;}*p_tpgc;

extern "C" __declspec(dllexport) void SkbsGetMin(int* g81s, int* g81min);
extern "C" __declspec(dllexport) void SkbsGetMinChar(char* g81sc, int* g81min);
extern "C" __declspec(dllexport) TPGC * SkbsSetModeWithAutos();

/* to come later use of the table of auto morphs
*/


I am not quite happy with the design started without a clear idea of the auto morphs issue, but it works.
A second version could come later, but the next step is to deliver the virtual catalog DLL

[champagne]

Just sharing here new night thoughts.

The auto morphs of a solution grid is not just an academic issue.

Seen the very low ratio of grids having auto morphs, A quick filter of such grids can simplify the design of the virtual catalog and send a quicker response. Something to consider before a release of the virtual catalog DLL