MinLex Routine

Programs which generate, solve, and analyze Sudoku puzzles

MinLex Routine

Postby swb01 » Wed Aug 04, 2021 2:45 pm

Update, 2021_08_17: I 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
Last edited by swb01 on Tue Aug 17, 2021 4:22 pm, edited 1 time in total.
swb01
 
Posts: 28
Joined: 07 March 2021
Location: Potomac, Maryland

Re: MinLex Routine

Postby creint » Wed Aug 04, 2021 7:12 pm

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"
creint
 
Posts: 322
Joined: 20 January 2018

Re: MinLex Routine

Postby swb01 » Wed Aug 04, 2021 8:42 pm

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?
swb01
 
Posts: 28
Joined: 07 March 2021
Location: Potomac, Maryland

Re: MinLex Routine

Postby creint » Wed Aug 04, 2021 10:07 pm

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


Visual studio
Test Explorer
Analyse Code Coverage for Selected Tests
creint
 
Posts: 322
Joined: 20 January 2018

Re: MinLex Routine

Postby JPF » Wed Aug 04, 2021 10:50 pm

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
JPF
2017 Supporter
 
Posts: 5297
Joined: 06 December 2005
Location: Paris, France

Re: MinLex Routine

Postby swb01 » Thu Aug 05, 2021 1:45 pm

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
swb01
 
Posts: 28
Joined: 07 March 2021
Location: Potomac, Maryland

Re: MinLex Routine

Postby JPF » Thu Aug 05, 2021 8:19 pm

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
JPF
2017 Supporter
 
Posts: 5297
Joined: 06 December 2005
Location: Paris, France

Re: MinLex Routine

Postby swb01 » Fri Aug 06, 2021 12:07 am

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
Last edited by swb01 on Fri Aug 06, 2021 12:54 pm, edited 1 time in total.
swb01
 
Posts: 28
Joined: 07 March 2021
Location: Potomac, Maryland

Re: MinLex Routine

Postby JPF » Fri Aug 06, 2021 9:58 am

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
JPF
2017 Supporter
 
Posts: 5297
Joined: 06 December 2005
Location: Paris, France

Re: MinLex Routine

Postby Serg » Fri Aug 06, 2021 3:23 pm

Hi, JPF!
JPF wrote: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
Serg
2018 Supporter
 
Posts: 768
Joined: 01 June 2010
Location: Ukraine

Re: MinLex Routine

Postby swb01 » Tue Aug 17, 2021 4:33 pm

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
 
Posts: 28
Joined: 07 March 2021
Location: Potomac, Maryland


Return to Software