## MinLex Puzzles

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

### Re: MinLex Puzzles

Mathimagics wrote:I have posted the code in the Software area ... have fun!

I finally had time to test the performance of your MinLex program.
Its speed is impressive. Congratulations!
With 300,000 random sudoku grids I got the following results on my laptop in seconds:

Code: Select all
`Mathimagics         1.7Gridchecker      1106.0gsf              3501.0`

On the other hand, gridchecker is the only one that efficiently determines MinLex from any sequence of digits.

JPF
JPF
2017 Supporter

Posts: 5414
Joined: 06 December 2005
Location: Paris, France

### Re: MinLex Puzzles

JPF wrote:On the other hand, gridchecker is the only one that efficiently determines MinLex from any sequence of digits.
JPF

Hi JPF,

what do you mean precisely?
champagne
2017 Supporter

Posts: 7204
Joined: 02 August 2007
Location: France Brittany

### Re: MinLex Puzzles

I think he means the minlexing of Puzzle-only (Pattern only) forms (ie. without reference to a solution grid)

Mathimagics
2017 Supporter

Posts: 1829
Joined: 27 May 2015
Location: Canberra

### Re: MinLex Puzzles

champagne wrote:
JPF wrote:On the other hand, gridchecker is the only one that efficiently determines MinLex from any sequence of digits.
...what do you mean precisely?

Mathimagics wrote:I think he means the minlexing of Puzzle-only (Pattern only) forms (ie. without reference to a solution grid)

Yes, Mathimagics is right.
In a more formal way:
For any sequence of 81 digits SQ=(x1,x2,...,x81) with 0≤xi≤9, gridchecker is able to find MinLex(SQ) which is defined by
the sequence (f(x1),f(x2),...,f(xn)) such that f(x1).10^80 + f(x2).10^79 + ... + f(x81) is the minimum for all f of the group S9xG

S9 is the symmetric group S9 ; |S9|=9!
G is the group of geometric transformations (VPT) ; |G|=2 x 6^8=3359232

Then, gridchecker can be used for different purposes, like minlexing patterns (xi=0 or xi=1), minlexing solution grids, minlexing valid or invalid puzzles...

Here are some examples:
Code: Select all
`003195329531437918877070817926625631136964997876804980377882615741485757087268715268261042050737255219334240066880947143419936281503711125758373130829310325633378723817951694116970628976526980432981379045310795598334875127824724030567308657391101001111000100010011101110010100000011100111000100000000011010001110000100000010101111111010111110100000101010101111110100111101001001101100110011110010100110110010001110110001011110000110010111010100000000000101100010011001111010110001010001`

MinLex
Code: Select all
`001112123345060567816634253272116493729210413842831114280192052589693155947795396001112334256072474289270269099375808268663140647945756412834944604064852612434381001234256256107891283726437278231869588594029592537536341970879604129081769296411000000001000001001111011001000010011001000110001100000001000001011011101111110100000001011111010101111101111001011111010101010011010111001101101101001101101110100000000001001011000010111010011000011011001010110001011011100111100100100100101010`

JPF
JPF
2017 Supporter

Posts: 5414
Joined: 06 December 2005
Location: Paris, France

### Re: MinLex Puzzles

JPF wrote:With 300,000 random sudoku grids I got the following results on my laptop in seconds:
Code: Select all
`Mathimagics         1.7Gridchecker      1106.0gsf              3501.0`

Just to put these superficially dazzling results in perspective, the grid-minlex function of GridChecker is quite good (and we have all been using it for some time, I think). Although my grid-minlex function is around 10 times faster, it is certainly not 650 times faster!

Here are my results for 300,000 grids:

Code: Select all
`Mathimagics        0.611GridChecker        6.395 (*)gsf              824.773`

My "GridChecker" test (*) is the result of calling its grid-minlex function directly, not actually running the GridChecker program.

More difficult to explain is the poor performance by gsf's program. No doubt there is some magic option which we need to add (in addition to -f%#mc) ...

Mathimagics
2017 Supporter

Posts: 1829
Joined: 27 May 2015
Location: Canberra

### Re: MinLex Puzzles

I agree with you : GridChecker is a great program!

I am using GridChecker v1.23 with this command line :
Code: Select all
`gridchecker --similar --subcanon < in.txt > out.txt`

My laptop:
Intel(R) Core(TM)i5-8265U CPU @ 1.60GHz 1.80GHz
64 bits ; Processor x64
Windows 10 Family

JPF
JPF
2017 Supporter

Posts: 5414
Joined: 06 December 2005
Location: Paris, France

### Re: MinLex Puzzles

So what you are doing there is invoking GridChecker's puzzle/pattern minlex function (subcanon), but giving it full solution grids to work on.

The results are correct, but that is not what that particular function is designed for, and that's why it is so slow ...

Mathimagics
2017 Supporter

Posts: 1829
Joined: 27 May 2015
Location: Canberra

### Re: MinLex Puzzles

Hi JPF,

As Mathimagics said

subcanon canonicalizes subgrid, i.e. puzzle, unavoidable set, etc. It is optimized by Michael Deverin for subgrids with many non-givens since in minlex the non-givens are moved to top left.

rowminlex canonicalizes full valid grids. It was optimized by Glenn Fowler for fast grid processing.

I can add only that I found a command in gridchecker that uses Glenn's canonicalization.

Code: Select all
`gridchecker --similar --subcanon < 17grids46300.txt | wc -l  162.967 seconds, uses subgrid canonicalization which is inefficient for full grids.gridchecker --solve --groupbygrid --gridsonly < 17grids46300.txt | wc -l  0.944 seconds, uses grid canonicalization. It also "solves" the grids as a bonus when full grids are given on input.`

I tried the second syntax with and without --gridsonly option on your puzzles from this post and the tool reported all but the first as "Duplicate puzzle".
dobrichev
2016 Supporter

Posts: 1816
Joined: 24 May 2010

### Re: MinLex Puzzles

JPF
JPF
2017 Supporter

Posts: 5414
Joined: 06 December 2005
Location: Paris, France

### Re: MinLex Puzzles

Hi Mathimagics!
you wrote:1-clue puzzles

Band 416 is the only grid with 1-clue puzzles. There are 5 cells with values that do NOT occur in any other ED (Minlex) grid, so there are 5 puzzles with unique solutions for just the 1 clue:

Code: Select all
` r2c4 = 8 r2c5 = 9 r2c6 = 3 r7c5 = 8 r8c6 = 9`

...

Well, I got 21 1-clue puzzles...
Here is a puzzleM and a solution:
Code: Select all
`r4c4=1r4c4=1:  123456789457389621896217354268174593745938162931562847382641975574893216619725438  bnd (411)`

Could you give me an other solution?
I wonder if my catalog is corrupted or something else...

JPF
JPF
2017 Supporter

Posts: 5414
Joined: 06 December 2005
Location: Paris, France

### Re: MinLex Puzzles

Something is up, that's for sure!

These solutions are all in band 12 (but I only printed the first 10 solutions found).
Code: Select all
`......................................1..........................................123456789456789123798213564234175896561928437879364215342591678615837942987642351123456789456789123798213564234175698561928347879364215342591876615847932987632451123456789456789123798213564234175896561928347879364215342591678615847932987632451123456789456789123798213564234175698561928347879634215342591876615847932987362451123456789456789123798213564234175896561928347879634215342561978615897432987342651123456789456789123798213564234175896561928347879634215342591678615847932987362451123456789456789123798213564234175698561938247879624315342591876615847932987362451123456789456789123798213564234175896561938247879624315342561978615897432987342651123456789456789123798213564234175896561938247879624315342591678615847932987362451`

Mathimagics
2017 Supporter

Posts: 1829
Joined: 27 May 2015
Location: Canberra

### Re: MinLex Puzzles

Thank you for your moral support!
After three weeks of trial and error, I finally have a correct catalog and ... I am able to confirm your list of five 1-clue puzzles...

JPF
JPF
2017 Supporter

Posts: 5414
Joined: 06 December 2005
Location: Paris, France

### Re: MinLex Puzzles

Excellent, well done!

Mathimagics
2017 Supporter

Posts: 1829
Joined: 27 May 2015
Location: Canberra

### Re: MinLex Puzzles

Mathimagics wrote:2-clue SudokuM Puzzles
If my scan was done correctly, there are 80 minimal 2-clue puzzles.

Confirmed!
There are 420 2-clue valid SudokuM puzzles but only 80 are minimal.

JPF
JPF
2017 Supporter

Posts: 5414
Joined: 06 December 2005
Location: Paris, France

### Re: MinLex Puzzles

Thanks, JPF, nice to have that figure confirmed. Do you intend to count the 3-clue minimals also?

Mathimagics
2017 Supporter

Posts: 1829
Joined: 27 May 2015
Location: Canberra

PreviousNext