MinLex Routine

Programs which generate, solve, and analyze Sudoku puzzles

Re: MinLex Routine

Postby swb01 » Fri Apr 01, 2022 2:28 am

Hi JPF

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?

I just added a folder on my GDrive (link provided above) containing MinLexDriver.exe and supporting files. It requires .Net runtime, version 6. (The program doesn't even start up on my very old desktop, but it works on newer laptops.)
It prompts for a process mode and then for a file name. It looks for the provided file (e.g 17puz49158.txt) in a folder named MinLexText_Output on the user's desktop and writes a results file to the same folder. If a file already exists with the results file name, it overwrites it. Example:
Code: Select all
Select process mode:
1) Minlex file, sort and remove duplicates (default) or
2) Minlex and write results in original order or
3) Minlex and merge new with a "Master" .txt file of sorted Minlexed grids or
   sub-grids. (The "Master" file is verified as sorted, but not as Minlexed.)
1
Process Mode = 1
Enter name of .txt file of puzzles or full grids to be minlexed:
17puz49158.txt

The output file names are appended with 1) _Mls (MinLexed/Sorted); 2) _Mlus (Minlexed/Unsorted); or 3) _New.
In a few days I'll add an .exe that will process command line input with parameters.

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

It expects full grids to conform to SuDoKu rules. It does not verify this and the results may not be in MinLex form for invalid grids.
For subgrids, the only verified SuDoKu constraint is that no two rows or columns are empty (all zeros) in a band or stack. This edit means that at least 6 givens are required. Processing stops if this input error is encountered. Otherwise it will apply SuDoKu validity preserving transformations to any 81 character string of digits (0,1,...,9 or "." in place of 0).

swb01
swb01
 
Posts: 47
Joined: 07 March 2021
Location: Potomac, Maryland

Re: MinLex Routine

Postby swb01 » Fri Apr 01, 2022 11:36 pm

Added today a command line execution mode. In example, work files are in path C:\Users\UserName\Desktop\MinLexWork and executables are in path C:\Users\UserName\Decktop\MinLexWork\MinLex9X9Sr1.

C:\Users\UserName\Desktop\MinlexWork>%cd%\minlex9X9Sr1\MinlexDriver ? <-- invalid argument invokes "Help".
Invalid input arguments.
First argument must be 1, 2, or 3 to select the process mode:
1 - Minlex file, sort and remove duplicates or
2 - Minlex and write results in original order or
3 - Minlex and merge new with a "Master" .txt file of sorted Minlexed grids or sub-grids. (The "Master" file is verified as sorted, but not as Minlexed.)
Followed by <inputfilename> <outputfilename> for process mode 1 or 2, or <inputfilename> <masterfilename> <outputfilename> for mode 3.

Example: C:\Users\username\Desktop\MinLexWork\>%cd%\MinlexDriver 3 MyPuzzles.txt MyMasterFile.txt MyNewMasterFile.txt

Please provide feedback if you find this useful, have improvement recommendations, or find processing errors.
swb01
swb01
 
Posts: 47
Joined: 07 March 2021
Location: Potomac, Maryland

Re: MinLex Routine

Postby coloin » Thu Apr 28, 2022 11:52 pm

Excellent !!

it processed my first test file very quickly indeed...
a file with 81 character text string puzzles.

however with a subsequent apparently structurally similar file I got a handling error ....
"Error, Input file length not a multiple of 83 (81 characters & Carrige Return/Line Feed). Process terminated."

Cheers
coloin
 
Posts: 2502
Joined: 05 May 2005
Location: Devon

Re: MinLex Routine

Postby swb01 » Fri Apr 29, 2022 4:29 am

Hi coloin,

Thanks for trying my minlexer and providing feedback.
however with a subsequent apparently structurally similar file I got a handling error ....
"Error, Input file length not a multiple of 83 (81 characters & Carrige Return/Line Feed). Process terminated."

The program edits for an input file of 81 ASCII digit lines followed by carriage return and new line - ( a dos . txt file). It simply divides the total file length by 83 and requires the remainder to be zero. (Except it allows for the last line to be only 81 characters long in case the last line does not have a CR/LF).
Check your .txt file to verify that it is a simple .txt file of 81 ASCII character lines. One case I noticed, if you save an Excel table as Unicode Text (16 bits), it looks like Text (MS-DOS) (8-bits) in Notepad, but my program will kick it out.

I’m interested in feedback. Can you quantify “very quickly”?

Swb01
swb01
 
Posts: 47
Joined: 07 March 2021
Location: Potomac, Maryland

Re: MinLex Routine

Postby swb01 » Fri Apr 29, 2022 4:42 am

Also, make sure the file does not contain an empty line at the end.
swb01
 
Posts: 47
Joined: 07 March 2021
Location: Potomac, Maryland

Re: MinLex Routine

Postby Hajime » Fri Apr 29, 2022 7:53 am

swb01 wrote:Also, make sure the file does not contain an empty line at the end.

Or you adapt the program:
Check lines equal/larger 81 chars
Get substring of 81 chars
Check each char is 0 to 9 or a dot
Else skip
User avatar
Hajime
 
Posts: 1385
Joined: 20 April 2018
Location: Fryslân

Re: MinLex Routine

Postby swb01 » Fri Apr 29, 2022 2:13 pm

Hajime wrote:
Or you adapt the program: Check lines equal/larger 81 chars; Get substring of 81 chars;
Check each char is 0 to 9 or a dot; Else skip


I agree my program could do a better job of locating the line with a length problem. For the digit edit, it identifies the offending line and terminate processing. However, my personal preference is to be told if my input file contains ambiguities so I can fix the input. Otherwise, I might never notice inaccurate results.
swb01
 
Posts: 47
Joined: 07 March 2021
Location: Potomac, Maryland

Re: MinLex Routine

Postby m_b_metcalf » Fri Apr 29, 2022 2:43 pm

swb01 wrote: Otherwise, I might never notice inaccurate results.

True to the old adage: Garbage in , garbage out.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13637
Joined: 15 May 2006
Location: Berlin

Re: MinLex Routine

Postby coloin » Fri Apr 29, 2022 4:44 pm

Thanks for your reply

I have an intermittent problem therefore with the line end handling of the text files

I am using a windows text editor [boxertexteditor]

A manual "select and paste" of the string allows the program to work

However a Control-A and paste gives the error

But it seems to work flawlessly with puzzles that would ordinarily have the "gsf" error and run times seemingly more efficient the greater the file size.
Code: Select all
29/04/2022 17:13:26, MinLex Out = 1,068.
Elapsed Time = 0.365 seconds
29/04/2022 16:33:25, MinLex Out = 8,759.
Elapsed Time = 0.425 seconds
coloin
 
Posts: 2502
Joined: 05 May 2005
Location: Devon

Re: MinLex Routine

Postby swb01 » Fri Apr 29, 2022 6:03 pm

coloin,
Thank you for your timing examples.
Are there any changes you recommend that would make the program more useful to your work?
swb01
swb01
 
Posts: 47
Joined: 07 March 2021
Location: Potomac, Maryland

Re: MinLex Routine

Postby coloin » Sat Apr 30, 2022 3:22 pm

Ive managed to circumvent the line entry problem by pasting into a new file from a spreadsheet
I have a separate program to verify valid grids and a proven isomorph purger - so the tool works well and very quick

Testing the remove duplicates function of your program on a large raw file of generated 27C sudoku of this shape
Code: Select all
+---+---+---+
|..1|..2|..3|
|.2.|.1.|.4.|
|4..|3..|1..|
+---+---+---+
|..2|..3|..6|
|.5.|.6.|.7.|
|8..|5..|9..|
+---+---+---+
|..7|..5|..8|
|.8.|.7.|.9.|
|9..|6..|2..|
+---+---+---+


Code: Select all
0/04/2022 16:02:34, Input = 183,982, Duplicates = 51,096, MinLex Out = 132,886.
Elapsed Time = 10.250 seconds


This is a pretty good test and the result agreed exactly with my isomorph purger.

If you wanted to expand your programs fuctionality and a challenge !! - an idea would be to morph to produce the minlex puzzle of the minlex pattern ... which isnt always the minlex puzzle [ 5-10% of the time it differs]

thanks for your help ...
coloin
 
Posts: 2502
Joined: 05 May 2005
Location: Devon

Re: MinLex Routine

Postby coloin » Tue May 03, 2022 5:15 pm

An the speed is phenomenal with large puzzle files !
it only takes 20 secs or less to process and remove duplicate of 1 million puzzles !

! actually I do have an issuea which you might be able to process furthur

The minles process gives us one minimal morph of a puzzle which has up to 6^8 * 2 * 9! VPTs for each puzzle.

It might be possible to process to an optimal morph depending on what circumstance.

In the specific case of 18C puzzles... two groups to be treated separately
puzzle in box distribution
Group A -22222222 I guess 5% of all 18C puzzles - all 6 diagonals with 6 clues in total
Group B - has 7 -13 clues in the diagonal with most clues

So the randomly displayed 18C puzzle to be morphed
Code: Select all
+---+---+---+
|.2.|.8.|1..|
|...|...|...|
|..9|...|.63|
+---+---+---+
|.8.|.1.|2..|
|...|...|...|
|..6|..7|..9|
+---+---+---+
|...|...|...|
|.1.|.4.|8..|
|..3|..6|.7.|
+---+---+---+    2132222 distribution


The easy and most necessary step is to morph the puzzle putting the most clues in a specific diagonal [ usually there will be a max, but occ there will be 2 as above]

set the diagonal boxes nominally to boxes 3,5,7

Then as an exercise in what we are dealing with locate the minlex subpuzzle of the remaining 11 clues, the 7 clues in box357 go where they are mapped to.

eg a more optimally morphed puzzle might be - and the clues are cramped together
Code: Select all
+---+---+---+         +---+---+---+
|...|...|...|         |...|...|...|
|...|..1|...|         |...|..1|.76|
|..2|.3.|...|         |..2|.3.|4..|
+---+---+---+         +---+---+---+
|..4|...|3..|         |..4|.2.|3..|
|.5.|...|.1.|   -->   |.5.|..6|.1.|
|...|...|...|         |...|...|...|
+---+---+---+         +---+---+---+
|...|.4.|2..|         |..8|.4.|2..|
|...|..7|..5|         |.6.|..7|..5|
|...|...|...|         |...|...|...|
+---+---+---+         +---+---+---+


I will see if I can improve on it....

The point of this is to standardize and optimize a search for more puzzles...... with more clues in B357 there will be less clues in B124689

The search in this case would be iterating the 7 clues { -3+3} or better in the boxes 3,5,7 ... [ not the whole grid] it would be quick and extend deeper than the present limiting logistic of a whole grid {-2+2}

The 22222222 puzzles are already mapped to the 6 diagonals ... it suffers heavily with isomorphic reductions too !
I think I could look at the incidence patterns of 12 clues and 6 clues .....hmmm
coloin
 
Posts: 2502
Joined: 05 May 2005
Location: Devon

Re: MinLex Routine

Postby m_b_metcalf » Wed May 04, 2022 3:11 pm

Recently, on the hardest sudoku thread, mith and others have been posting puzzles with extremely high ratings. I got to wonder whether there might be among them puzzles that, if suitably rearranged, would appear symmetric (or nearly so) and thus suitable for submission as patterns to the Patterns Game. So, I wrote a program to process such files in this way and, although the yield is very low, it was neverthless sufficient for me be able to submit some new patterns to the Game.

I then realised that, with a few minor tweaks, the program could be be converted into a min_lex program. This I did. It can handle puzzles, solution grids or 0/1 patterns, but it's dreadfully slow. Despite that, as a little utility program it's just fine and dandy, and gave me the proof of origin of the current Patterns Game's pattern.

Just for information.

Mike
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13637
Joined: 15 May 2006
Location: Berlin

Re: MinLex Routine

Postby swb01 » Wed May 04, 2022 10:01 pm

coloin wrote:
The easy and most necessary step is to morph the puzzle putting the most clues in a specific diagonal [ usually there will be a max, but occ there will be 2 as above]; set the diagonal boxes nominally to boxes 3,5,7; Then as an exercise in what we are dealing with locate the minlex subpuzzle of the remaining 11 clues, the 7 clues in box357 go where they are mapped to.

I'm not sure I follow. Is this close to what you are looking for?
1. Count the number of clues in each of the six diagonals of a puzzle.
2. Choose a diagonal with the most clues - the target diagonal.
3. Zero out the clues in that diagonal.
4. Minlex the resulting sub-puzzle, keeping track of the diagonal clues.
5. Return the diagonal clues to their transformed location.
6. Relabel the diagonal clues from top to bottom starting with the Minlex relabel.
7. If necessary, switch stacks to place the target diagonal into boxes 3, 5, 7.

Using your example:

Code: Select all
Starting puzzle: (max diagonal in B357)
+---+---+---+    (Ignore second max in B348)     
|.2.|.8.|1..|
|...|...|...|
|..9|...|.63|
+---+---+---+
|.8.|.1.|2..|
|...|...|...|
|..6|..7|..9|
+---+---+---+
|...|...|...|
|.1.|.4.|8..|
|..3|..6|.7.|
+---+---+---+
.2..8.1.............9....63.8..1.2.............6..7..9..........1..4.8....3..6.7.
Zero out diagonal:
+---+---+---+       
|.2.|.8.|...|
|...|...|...|
|..9|...|...|
+---+---+---+.
|.8.|...|2..|
|...|...|...|
|..6|...|..9|
+---+---+---+
|...|...|...|
|...|.4.|8..|
|...|..6|.7.|
+---+---+---+
.2..8...............9.......8....2.............6.....9.............4.8.......6.7.
MinLex sub-puzzle:
+---+---+---+       
|...|...|...|
|...|...|..1|
|...|..2|.3.|
+---+---+---+.
|...|...|...|
|..1|...|..4|
|.3.|...|.2.|
+---+---+---+
|...|...|...|
|.2.|..5|...|
|6..|.4.|...|
+---+---+---+
.................1.....2.3............1.....4.3.....2...........2...5...6...4....
Replace diaginal clues:
+---+---+---+       
|...|...|...|
|6.3|...|..1|
|.1.|..2|.3.|
+---+---+---+.
|...|...|...|
|..1|.7.|..4|
|.3.|..1|.2.|
+---+---+---+
|...|...|...|
|.2.|..5|.1.|
|6..|.4.|..3|
+---+---+---+
.........6.3.....1.1...2.3............1.7...4.3...1.2...........2...5.1.6...4...3
Relabel diaginal:
+---+---+---+       
|...|...|...|
|4.7|...|..1|
|.8.|..2|.3.|
+---+---+---+.
|...|...|...|
|..1|.6.|..4|
|.3.|..8|.2.|
+---+---+---+
|...|...|...|
|.2.|..5|.8.|
|6..|.4.|..7|
+---+---+---+
.........4.7.....1.8...2.3............1.6...4.3...8.2...........2...5.8.6...4...7
Switch stacks 1 and 3 to put target diagonal into B357:
+---+---+---+       
|...|...|...|
|..1|...|4.7|
|.3.|..2|.8.|
+---+---+---+.
|...|...|...|
|..4|.6.|..1|
|.2.|..8|.3.|
+---+---+---+
|...|...|...|
|.8.|..5|.2.|
|..7|.4.|6..|
+---+---+---+
...........1...4.7.3...2.8............4.6...1.2...8.3...........8...5.2...7.4.6..
swb01
 
Posts: 47
Joined: 07 March 2021
Location: Potomac, Maryland

Re: MinLex Routine

Postby coloin » Sat May 07, 2022 12:34 am

Yes that is the idea !!

Coincidently my first attempt was close - - two more row swaps would give this
Code: Select all
+---+---+---+
|...|...|...|
|...|..1|.76|
|..2|.3.|4..|
+---+---+---+
|...|...|...|
|..4|.2.|3..|
|.5.|..6|.1.|
+---+---+---+
|...|...|...|
|..8|.4.|2..|
|.6.|..7|..5|
+---+---+---+

Swapping bands in your last post gives this ... which somehow the 6 box region is lexographically smaller than yours .......hmmmmm
Code: Select all
+---+---+---+
|...|...|...|
|...|..1|4.7|
|..2|.3.|.8.|
+---+---+---+
|...|...|...|
|.6.|..4|..1|
|..8|.2.|.3.|
+---+---+---+
|...|...|...|
|..5|.8.|.2.|
|.4.|..7|6..|
+---+---+---+


Essentially we are minlexing a region of a puzzle - in this instance the 11 clues in B1B2B4B6B8B9 region

A little more analysis is necessary to see if this can be usefully employed !

Edit
Maybe choosing the diagonal of the 7 clues to be [B1B5B9] would be easier -then the min lex region would map better !!!!
So this is exactly what is required [your 4th puzzle]
Code: Select all
+---+---+---+       
|...|...|...|
|6.3|...|..1|
|.1.|..2|.3.|
+---+---+---+.
|...|...|...|
|..1|.7.|..4|
|.3.|..1|.2.|
+---+---+---+
|...|...|...|
|.2.|..5|.1.|
|6..|.4.|..3|
+---+---+---+
coloin
 
Posts: 2502
Joined: 05 May 2005
Location: Devon

PreviousNext

Return to Software