The New Sudoku Players' Forum

[swb01]

Update, 2022_05_23: Posted release 4: added pattern processing and self-contained executables.
Update, 2022_04_01: Added to release 3, executables with command line execution instructions.
Update, 2022_03_30: Posted release 3 to the google drive. It has three process modes: 1) Minlex, sort and remove duplicates; 2) Minlex and leave in original order; and 3) Minlex, sort, remove duplicates, compare and add new to a "Master" file. Performance times are in the neighborhood of gridchecker.
Update, 2021_08_17: Posted release 2 of my minlex routine today with a release2 readme file. One bug was fixed and changes were made to comment out some code that was not reachable (thanks creint for your help.)
Original post:
I've been working on my MinLex routine and can't think of anything else to do to it to speed it up. I think it works, but I could use additional test cases to verify its logic such as large sets of 18 clue puzzles, symmetric puzzles, and other puzzles with unusual characteristics. On my 2.8 Ghz laptop it minlexes at approximately 60,000 per second after subtracting I/O time. I would like to thank Denis Berthier for providing his “Controlled-bias generator and collection” forum entry. I used the 511,215 puzzles in his Part12 file as general test cases.
A ReadMe file provides an introduction. It was developed in Visual Basic and an automatically generated C# version is also provided. You can view the source code and test files at:

Code: Select all

https://drive.google.com/drive/folders/1WpEwW1RUYIly_oCLsmBo-wyU_bvmfpNN?usp=sharing

[creint]

Both testfiles don't cover all codepaths, can you provide more?

Following are not triggered by testfiles:

Code: Select all

StoppedJustifyingRow = 1


Code: Select all

Row2StackPermutationCode = 0
Row2ColumnPermutationCode = 0


Code: Select all

SwitchStacks(0, TestGridBand2Rows, PermutationStackX(Row5StackPermutationCode)(row5stackpermutationix), PermutationStackY(Row5StackPermutationCode)(row5stackpermutationix))


Code: Select all

SwitchStacks(0, TestGridBand2Rows, PermutationStackX(Row6StackPermutationCode)(row6stackpermutationix), PermutationStackY(Row6StackPermutationCode)(row6stackpermutationix))

Code: Select all

SwitchStacks(0, TestGridBand3Rows, PermutationStackX(Row7StackPermutationCode)(row7stackpermutationix), PermutationStackY(Row7StackPermutationCode)(row7stackpermutationix))

Code: Select all

SwitchStacks(0, TestGridBand3Rows, PermutationStackX(Row8StackPermutationCode)(row8stackpermutationix), PermutationStackY(Row8StackPermutationCode)(row8stackpermutationix))

Code: Select all

Array.ConstrainedCopy(Row8FixedColumnsAndStacks, 0, FixedColumnsAndStacks, 0, 12)                  ' Reset FixedColumnsAndStacks to after Row8 setting.

Code: Select all

SwitchStacks(0, TestGridBand3Rows, PermutationStackX(Row9StackPermutationCode)(row9stackpermutationix), PermutationStackY(Row9StackPermutationCode)(row9stackpermutationix))

Code: Select all

MinimalHitCount += 1                        ' then the puzzle has multiple transformation paths that produce the minimal, thus the puzzle and its grid are automorphic.
MinimalCandidateSw = False

Code: Select all

Select Case MiniRow1PatternCode(Row1CalcMiniRowCodeMinimum)
Case 1                  '     MiniRow1PatternCode = "001"
Case 2                  '     MiniRow1PatternCode = "011"

Code: Select all

Select Case MiniRow2PatternCode(Row1CalcMiniRowCodeMinimum)
Case 1                  '     MiniRow1PatternCode = "001"
Case 2                  '     MiniRow1PatternCode = "011"

[swb01]

Thank you creint for your code review. I didn't include a test to verify that all code paths were reached.

creint wrote: Both testfiles don't cover all codepaths, can you provide more?

As I noted in my post and in the ReadMe file, I could use additional test cases to verify correct processing of this routine. Also, some code paths are probably not achievable with valid SuDoKu puzzles (single solution). For example, in order to hit

Code: Select all

SwitchStacks(0, TestGridBand3Rows, PermutationStackX(Row9StackPermutationCode)(row9stackpermutationix), PermutationStackY(Row9StackPermutationCode)(row9stackpermutationix))

, a puzzle with the following pattern would be needed.

Code: Select all

+---+---+---+
|...|...|..x|
|...|...|..x|
|...|...|..x|
+---+---+---+
|...|...|..x|
|...|...|..x|
|...|...|..x|
+---+---+---+
|...|...|xxx|
|...|...|xxx|
|xxx|xxx|xxx|
+---+---+---+


So, give me a little time and I will prepare another test file to hit these code paths.
What tool did you use to track the code execution paths?

[creint]

What tool did you use to track the code execution paths?

Visual studio
Test Explorer
Analyse Code Coverage for Selected Tests

[JPF]

swb01,

Minlexing the 560,151 automorphic grids could be a good chalenge:
https://drive.google.com/file/d/1QAS5B7Zt94wyODpPJ_Oi_WPDKTeG9GvM/view?usp=sharing
The list is in minlex form.

JPF

[swb01]

Hi JPF,

JPF wrote: Minlexing the 560,151 automorphic grids could be a good challenge:

Thank you for the reference. I added this file to my post with processing results. I first scrambled the grids to take them out of minlex form and then minlexed them in 41 minutes, or 231 per second, producing the same minlex results as the original. MinLex9X9SR1 is not optimized as a grid minlexer. Do you have a link for puzzles for this set of automorphic grids?
The automorphic count distribution of the test file is:

Code: Select all

Automorphic
 Count    Cases
   2     548,449
   3       7,336
   4       2,826
   6       1,257
   8          29
   9          42
  12          92
  18          85
  27           2
  36          15
  54          11
  72           2
  108          3
  162          1
  648          1
         -------
         560,151


SWB01

[JPF]

Edited
The automorphic count distribution is correct. It was first given by gsf here in 2007.

MinLex9X9SR1 is not optimized as a grid minlexer.

Actually, there are four different uses of minlexing. For:

1. solution grids
2. valid* puzzles
3. any strings of digits 0 to 9
4. 0 or 1 digits (patterns)

This point has been discussed here.
Any general algorithm able to solve 3 is less efficent than those developped for 1 or 2 which take into account the properties of a sudoku grid.
Case 4 is special case. Gridchecker works fine and is very fast.

With Mathimagics' program (for solution grids) it takes 3.3 seconds to minlex the 560,151 automorphic grids.

Do you have a link for puzzles for this set of automorphic grids?

Here is a list of 560,151 minimal valid* puzzles.
Each puzzle is a scrambled minimal valid* subgrid of an automorphic grid.

JPF
* valid = one and only one solution

[swb01]

JPF,

Thanks for the links. It's quite a history.

On specialized vs generalized minlex routines, LinLex9X9SR1 is closer to a minlexer for valid puzzles (case 2). It requires an 81 element array of digits 0 - 9 and treats the array as rows 1 to 9 of a SuDoKu puzzle placed end-to-end. It does not check for or take advantage of 1) the digits 1 - 9 not repeating in a row, column and box or 2) the provided non-zero digits resolve to a one and only one solution grid.
I can see how digits not repeating in rows, columns and boxes can be beneficial for grid minlexing, but I haven't figured out how to make use of it for a puzzle minlexer.
Also, do you happen to have a link for test sets of 18 clue puzzles?

Swb01

[JPF]

Swb01,

I seem to be locked out of the list of 560,151 minimal valid* puzzles. I've requested access.

Sorry for that. I hope it's ok now.

Also, do you happen to have a link for test sets of 18 clue puzzles?

Here is a link of 2,000,000 18-clues puzzles.
Thoses puzzles were sent to me by Mathimagics a while ago.

JPF

[Serg]

Hi, JPF!

Actually, there are four different uses of minlexing. For:

1. solution grids
2. valid* puzzles
3. any strings of digits 0 to 9
4. 0 or 1 digits (patterns)

I think, the case "valid puzzles" can be mitigated to "correct puzzles", i.e. 9 x 9 matrices with numbers 0-9, obeying Sudoku rules. (These puzzles can have solutions or not.) The constraint "correct puzzles" can simplify and fasten minlexing algorithm, but I don't see additional (to "correct puzzles" constraint) optimization ideas caused by knowledge the puzzle is valid.

Serg

[swb01]

Thanks for your help creint.

creint wrote: Both testfiles don't cover all codepaths, can you provide more?

Today I uploaded Release2 of my minlixer with one bug fix and I commented out three cases that were in fact unreachable in my code. I added a new test file of "contrived" puzzles that hit the cases you published in your comment above. The puzzles are contrived because they are highly non-minimal and unlikely to be encountered in normal SuDoKu work.
(The reason the code cases are unreachable is in order to have a second row configured to hit each case, it would then be less that the necessary row1 and therefor it would supplant the row1 as as a candidate.)

swb01

[swb01]

I posted release 3 of MinLex9X9SR1 to it’s Google drive today. It can minlex 2.5M puzzles in 10.5 seconds.

[dobrichev]

Hi swb01,

Do you think your algorithm can be extended to pencilmarks min-lexing?

[swb01]

Hi Mladen,
Thanks for the question.

Do you think your algorithm can be extended to pencilmarks min-lexing?

I haven't considered extending it, but it is very specialized to the standard 81 character puzzle so I doubt it.
swb01

[JPF]

Hi swb01,

Is there an executable, say MinLex9X9SR1.exe for Windows such that for any file A.txt of "puzzles":

MinLex9X9SR1.exe A.txt B.txt gives in B.txt the list of minLexed puzzles of A.txt?

Does your program work for any string of digits (0,1,...,9) or only for sudoku subgrids/grids?

JPF