MinLex Puzzles

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

Re: MinLex Puzzles

Postby dobrichev » Wed Jan 27, 2021 2:17 pm

Paid version of GridChecker has some functions unlocked :) :) :)
dobrichev
2016 Supporter
 
Posts: 1807
Joined: 24 May 2010

Re: MinLex Puzzles

Postby Mathimagics » Wed Jan 27, 2021 3:06 pm

Hmmm ... that looks eerily familiar!

:lol:
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby Mathimagics » Fri Jan 29, 2021 5:47 am

.
SudokuM 3-clue Puzzles

The catalog scan found 12,983 minimal 3-clue puzzles. Like the 2-clue puzzles listed above, the band range is 348 to 416, with a small number (12) of notable exceptions. Surprisingly, there were 12 puzzles found for bands 29,30,31: :o

3-clue puzzles (Bands 29-31): Show
Code: Select all
r3c8=6 r4c2=6 r9c7=1: 123456789456789231789231564267148395348592617915673428591367842672814953834925176 (bn  29)
r4c2=6 r5c4=2 r9c4=1: 123456789456789231789312456264571398375298614891634527517843962638927145942165873 (bn  30)
r4c2=7 r4c4=1 r7c4=2: 123456789456789231789312456274195863538627194961843527395274618617538942842961375 (bn  30)
r3c5=1 r4c2=7 r5c4=2: 123456789456789231789312456274861395538294617961537842395628174617943528842175963 (bn  30)
r3c6=2 r4c2=7 r9c4=1: 123456789456789231789312456274861395538294617961537842395628174617943528842175963 (bn  30)
r4c2=7 r5c4=2 r9c4=1: 123456789456789231789312456274861395538294617961537842395628174617943528842175963 (bn  30)
r3c6=2 r4c2=7 r8c4=1: 123456789456789231789312456274963518395841627861527394518274963637195842942638175 (bn  30)
r4c2=7 r7c4=2 r8c4=1: 123456789456789231789312456274963518395841627861527394518274963637195842942638175 (bn  30)
r4c2=9 r6c4=2 r7c4=1: 123456789456789231789312456294863517375941628618275943537194862861527394942638175 (bn  30)
r2c9=1 r4c2=9 r7c5=3: 123456789456789231789312456294873165365194872871265394542638917618927543937541628 (bn  30)
r4c2=8 r5c3=7 r5c7=1: 123456789456789231798213645284361957537942168619875324372594816865137492941628573 (bn  31)
r4c2=8 r4c3=7 r5c7=1: 123456789456789231798213645287641953349875162615932874532167498871594326964328517 (bn  31)


Minimal Puzzle Generation

We can take any valid Sudoku puzzle (SP), convert it to canonical puzzle form (CP, so it solves to a minlex grid), and then enumerate all the minimal SudokuM puzzles that can be derived from that CP. Typically we find puzzles with 9, 10, or 11 clues. These examples show only the least-clue puzzles:

Example 1: Show
Code: Select all
..9...2...8.5...1.7.......6..6.9.....5.8..3..4....7........4..9.3..1..8....2..5.. #  SP
1...5...9..6...2...8.....4...76.....5...1.3...4...8...3..9....5....2.1.......7.6. #  CP
.............................76.........1.....4...............5....2.1.......7.6. #  9C
.............................76.........1.3..............9....5......1.......7.6. #  9C


Example 2: Show
Code: Select all
8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4.. #  SP
1.....7...5...9....98.....5....1.36......2..89...6.1..3...7.......6.......2..5..4 #  CP
....................8..........1.36......2...9...6.1......7..................5..4 # 11C
...................9...........1.36......2...9...6.1......7..................5..4 # 11C


Example 3: Show
Code: Select all
........1....23.....45...6...57...4...62.8.7..9......8..7..2...46.....2.5..6..7.. #  SP
.....6..9..6...12..9.2..5....19....5..96.8..28......7.3..........25....1....64... #  CP
.....................2.......19....5.....8..2.......7.............5....1....64... # 11C
.....................2.......19....5..9..8..........7............25....1.....4... # 11C
.....................2.......19....5..96.8..........7.............5....1.....4... # 11C
................2....2........9....5..96.8..........7.............5....1.....4... # 11C
...............1.....2........9....5..96.8..........7.............5....1.....4... # 11C
...........6.........2........9....5..96.8..........7.............5....1.....4... # 11C


Example 4: Show
Code: Select all
........1.....2.3...4.5.6....6....1..4.7....38...9.4....85......6..8..949.5...... #  SP
1.......9..6....2.89.2..6.......5....8.....7...98....1...6....2..2.4..3...1..34.. #  CP
................................5....8.....7...9.....1........2....4..3...1...4.. # 10C
........................6............8.........9.....1........2....4..3...1..34.. # 10C
..................8..................8.....7...9..............2....4..3...1..34.. # 10C
..................8..................8.....7...9.....1........2....4..3...1..3... # 10C
..................8.............5....8.........9.....1...........2.4..3...1...4.. # 10C
..................8.............5....8.........9.....1........2....4..3...1...4.. # 10C
..................8.............5....8.....7.............6....2....4..3...1...4.. # 10C
..................8.............5....8.....7.........1........2....4..3...1...4.. # 10C
..................8.............5....8.....7.........1...6....2.......3...1...4.. # 10C
..................8.............5....8.....7.........1...6....2....4..3...1...... # 10C
..................8.............5....8.....7...9.....1...6....2.......3...1...... # 10C
..................8.....6.......5....8.....7..................2....4..3...1...4.. # 10C
..................8.....6.......5....8.....7.............6....2....4..3...1...... # 10C
...........6......8.............5....8.....7..................2....4..3...1...4.. # 10C
...........6......8.............5....8.....7.............6....2....4..3...1...... # 10C
Last edited by Mathimagics on Sat Jan 30, 2021 4:08 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby JPF » Fri Jan 29, 2021 8:48 pm

Hi Mathimagics!

Impressive results for the exhaustive list of 3-clue puzzles!
now you practically have to figure out the list of all the minimal puzzles :D

Concerning the minimal puzzleM generation, I have two questions:
Is there somewhere a definition of what you call canonical form CF of the puzzle SP?

My guess is: if S is the solution of SP and if MLS is its minlex equivalent, then there exists a transformation f such that MLS=f(S)
A canonical form CF is f(SP).
CF is not unique if S has more than one automorphism, say n>1.
Actually, there are n different CF.

You wrote:...and then enumerate all the minimal SudokuM puzzles that can be derived from that CF.
What does it mean and how do you do that?

Thanks!

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

Re: MinLex Puzzles

Postby coloin » Fri Jan 29, 2021 9:56 pm

Very impressive 1,2 and 3 clue puzzles .....

Heres a project !!!

If the intention was ever to get a SudokuM puzzle for each minlex grid ...[ eeeek] [ perhaps to potentially trim down a compressed catalogue of puzzles -> grids [? would it ]

How difficult / fast would it be to generate a nonminimal 27 plus 6 [per band] plus 6 [per band] puzzle [ or less] and end up having one for each minlex solution grid ? :geek:


EDIT its pretty quick to generate these puzzles 27 plus 6 plus 6 .... but only 1/6 of them will be able to be morphed to a minlex grid with band 1 full, ... but for every puzzle, potentially we have the 44 gangster -> 416 band expansion ...

Once we had the puzzles ....Solving would be quick .... coupled with the 27 clues [of the 416] plus the exception clues, Band choice would be from a choice of 2. ~ 1M puzzles solved per sec therefore 5000 secs 1.5 hrs only :roll:

Or do we already have a compressed file of puzzles [ 1 for each minlex grid ] with 20C ... how big is this file ?
coloin
 
Posts: 1982
Joined: 05 May 2005

Re: MinLex Puzzles

Postby Mathimagics » Sat Jan 30, 2021 4:07 am

JPF wrote:Is there somewhere a definition of what you call canonical form CF of the puzzle SP?

Not really, as far as I can tell, but it seems to me to be a fundamental concept.

On reflection, perhaps a better term would be CP, ie Canonical Puzzle.

Congratulations, JPF, your guess above is absolutely correct! If SP solves to G, and f(G) transforms G to minlex, then f(SP) is a CP. There is a CP for each automorphism of G.

I wrote:...and then enumerate all the minimal SudokuM puzzles that can be derived from that CP.

What does it mean and how do you do that?

Perhaps "derived" was misleading. I meant only the normal "reduce to minimal" algorithm, which is a standard recursion that can be applied to any puzzle, in Sudoku or any variant. Given a valid puzzle P, you can use a simple recursion to find all the valid sub-puzzles (subsets of P). The recursion is applied to each removable clue at each level. Any terminal node (no removable clues) in the search tree corresponds to a minimal puzzle.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby coloin » Sat Jan 30, 2021 12:40 pm

Mathimagics wrote:
JPF wrote:Is there somewhere a definition of what you call canonical form CF of the puzzle SP?

Using gsf's software
Code: Select all
sudoku-64 -qFN -f%#0c   prints puzzle in minlexgrid 

After all these years it must treat automorphic puzzles in a standard way - otherwise we would have encoutered duplicates w.r.t the min lex puzzle
I presume it gives us the min lex puzzle in the min lex grid !
coloin
 
Posts: 1982
Joined: 05 May 2005

Re: MinLex Puzzles

Postby JPF » Sat Jan 30, 2021 5:56 pm

wording...
Here is an example of a grid S with 6 automorphisms:
Code: Select all
   n  #automorphisms    6                                                                                                                   
  SP    Valid Puzzle    .3.89......5.....4.17....5.9......8.....76....5.12............7...5.38.2..1.6...5                                   
   S   Solution Grid    432895176895617324617432958976354281128976543354128769543281697769543812281769435                                   
                                                                                                                                           
 MLS       MinLex(S)    123456789456789123789123456231564897564897231897231564315672948672948315948315672                                   
 CP1  Canonic puzzle    .......89..67.........2.45.2....4.9.56....2.18........3....2.....2.48.......1.67.                                   
 CP2  Canonic puzzle    .....67..45.....2..89......2.156.......8......9.2....4.....2.4867.....1....3....2                                   
 CP3  Canonic puzzle    ...4.678..5.7....3...1.....2...6...........31..7...5.4.15.7.....7.9.......8...6.2                                   
 CP4  Canonic puzzle    ..3.5.7........1..78....4.6.31......5.4..7......2...6.....7.9..6.2..8.......15.7.                                   
 CP5  Canonic puzzle    .2.45........89...7.......6......8....4.9.2.....2.156..1.67......2...3...48.....2                                   
 CP6  Canonic puzzle    1........4.678....7....3.5....5.4..7.6....2......31......6.2..8.7.....159......7.                                   
                                                                                                                                           
MLSP      MinLex(SP)    ........1.....2345..1.3........436....7.......3.86.....6.1....345.7..9..9.......8   
and yes:
Code: Select all
sudoku-64 -qFN -f%#0c  SP
gives CP1=MinLex(CP1,CP2,...,CPn) which is compatible with
Code: Select all
sudoku-64 -qFN -f%#0c  S
giving MinLex(S)

but I don't know how to use gsf's program to get all the CP when S is automorphic.

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

Re: MinLex Puzzles

Postby dobrichev » Sat Jan 30, 2021 7:54 pm

Hi JPF,

See one possible implementation for listing all puzzles.
Unfortunately it is yet another hidden feature of this tool, now unused.

Firstly a mapping from original grid ( == puzzle solution) to its canonical form is produced in
void transformer::byGrid(const char* sol)

For automorphic grids all mappings are produced and the first refers to the next by the field named "next". Zero is end of the list.

Then the puzzle is transformed on the base of the collected mappings in the referred above
void transformer::transform(const char *in, char *out)

If empty cell is found, then it is a puzzle, and the procedure tries all mappings but returns only the minlex.

Just below is the procedure which adds all possible mappings to the output.
void transformer::transformAll(const char *in, char *out)

I double checked - transformAll isn't called from anywhere and isn't accessible from any command line parameters combination.
dobrichev
2016 Supporter
 
Posts: 1807
Joined: 24 May 2010

Re: MinLex Puzzles

Postby JPF » Sun Jan 31, 2021 12:12 pm

Thank you Mladen!

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

Re: MinLex Puzzles

Postby Mathimagics » Sun Jan 31, 2021 1:44 pm

Would it help if I posted my minlex code? The code is standard "C", with very fast minlexing, and includes an entrypoint for retrieving all the CP's for automorphic grids.

I was going to make it available at some point, but there seemed to be little evidence of demand, and so I never got around to it :?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby JPF » Sun Jan 31, 2021 5:01 pm

Yes please.
Either way it will be a great exercise for me to see how you coded M. Deverin's algorithm.
Thanks!

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

Re: MinLex Puzzles

Postby Mathimagics » Mon Feb 01, 2021 4:38 am

I have posted the code in the Software area ... have fun!

BTW, I didn't actually encode his algorithm, I just hammered his existing code into submission :lol:
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby Serg » Mon Feb 01, 2021 5:24 pm

Hi, Mathimagics!
Mathimagics wrote:I have posted the code in the Software area ... have fun!

BTW, I didn't actually encode his algorithm, I just hammered his existing code into submission :lol:

But Michael Deverin's code "hammered" by you runs 1.5 times faster than original code, isn't it?

Serg
Serg
2018 Supporter
 
Posts: 732
Joined: 01 June 2010
Location: Russia

Re: MinLex Puzzles

Postby Mathimagics » Tue Feb 02, 2021 5:19 am

Serg wrote:But Michael Deverin's code "hammered" by you runs 1.5 times faster than original code, isn't it?

1.45 is probably closer to the mark. Also, in addition to the hammering, there was some sawing ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra

PreviousNext

Return to General