MinLex Puzzles

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

Re: MinLex Puzzles

Postby JPF » Thu Feb 04, 2021 10:49 pm

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.7
Gridchecker      1106.0
gsf              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

Postby champagne » Fri Feb 05, 2021 8:37 am

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

Postby Mathimagics » Fri Feb 05, 2021 8:51 am

I think he means the minlexing of Puzzle-only (Pattern only) forms (ie. without reference to a solution grid)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1829
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby JPF » Fri Feb 05, 2021 10:17 am

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
003195329531437918877070817926625631136964997876804980377882615741485757087268715
268261042050737255219334240066880947143419936281503711125758373130829310325633378
723817951694116970628976526980432981379045310795598334875127824724030567308657391
101001111000100010011101110010100000011100111000100000000011010001110000100000010
101111111010111110100000101010101111110100111101001001101100110011110010100110110
010001110110001011110000110010111010100000000000101100010011001111010110001010001

MinLex
Code: Select all
001112123345060567816634253272116493729210413842831114280192052589693155947795396
001112334256072474289270269099375808268663140647945756412834944604064852612434381
001234256256107891283726437278231869588594029592537536341970879604129081769296411
000000001000001001111011001000010011001000110001100000001000001011011101111110100
000001011111010101111101111001011111010101010011010111001101101101001101101110100
000000001001011000010111010011000011011001010110001011011100111100100100100101010

JPF
JPF
2017 Supporter
 
Posts: 5414
Joined: 06 December 2005
Location: Paris, France

Re: MinLex Puzzles

Postby Mathimagics » Fri Feb 05, 2021 11:03 am

JPF wrote:With 300,000 random sudoku grids I got the following results on my laptop in seconds:
Code: Select all
Mathimagics         1.7
Gridchecker      1106.0
gsf              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.611
GridChecker        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) ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1829
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby JPF » Fri Feb 05, 2021 12:29 pm

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

Postby Mathimagics » Fri Feb 05, 2021 1:50 pm

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

Re: MinLex Puzzles

Postby dobrichev » Fri Feb 05, 2021 6:34 pm

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

Postby JPF » Wed Feb 17, 2021 11:10 am

Thanks Mladen!
JPF
JPF
2017 Supporter
 
Posts: 5414
Joined: 06 December 2005
Location: Paris, France

Re: MinLex Puzzles

Postby JPF » Wed Feb 17, 2021 11:12 am

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=1
r4c4=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

Postby Mathimagics » Wed Feb 17, 2021 3:27 pm

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..........................................
123456789456789123798213564234175896561928437879364215342591678615837942987642351
123456789456789123798213564234175698561928347879364215342591876615847932987632451
123456789456789123798213564234175896561928347879364215342591678615847932987632451
123456789456789123798213564234175698561928347879634215342591876615847932987362451
123456789456789123798213564234175896561928347879634215342561978615897432987342651
123456789456789123798213564234175896561928347879634215342591678615847932987362451
123456789456789123798213564234175698561938247879624315342591876615847932987362451
123456789456789123798213564234175896561938247879624315342561978615897432987342651
123456789456789123798213564234175896561938247879624315342591678615847932987362451
User avatar
Mathimagics
2017 Supporter
 
Posts: 1829
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby JPF » Thu Feb 18, 2021 9:55 am

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

Postby Mathimagics » Thu Feb 18, 2021 11:07 am

Excellent, well done! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1829
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby JPF » Fri Feb 19, 2021 4:13 pm

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

Postby Mathimagics » Sat Feb 20, 2021 12:36 pm

Thanks, JPF, nice to have that figure confirmed. Do you intend to count the 3-clue minimals also?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1829
Joined: 27 May 2015
Location: Canberra

PreviousNext

Return to General