The New Sudoku Players' Forum

[JPF]

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

[champagne]

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?

[Mathimagics]

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

[JPF]

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

...what do you mean precisely?

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

[Mathimagics]

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) ...

[JPF]

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

[Mathimagics]

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 ...

[dobrichev]

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".

[JPF]

Thanks Mladen!
JPF

[JPF]

Hi Mathimagics!

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

[Mathimagics]

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


[JPF]

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

[Mathimagics]

Excellent, well done!

[JPF]

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

[Mathimagics]

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