MinLex Puzzles

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

MinLex Puzzles

Postby JPF » Fri Jan 22, 2021 10:16 pm

A MinLex grid is a sudoku grid G such that G=MinLex(G). There are 5,472,730,538 MinLex grids.
A MinLex puzzle is a MinLex subgrid having only one MinLex grid solution.

Here is a MinLex puzzle:
Code: Select all
 . . . | . . . | . . .
 . . . | . . 9 | . . .
 . 8 . | . . . | . . .
-------+-------+-------
 . . . | 7 9 . | . . .
 7 . . | . . 2 | . . .
 . 1 8 | . . . | . . .
-------+-------+-------
 . . . | 5 4 . | . . 8
 . 4 2 | . 3 . | . . .
 . . . | . . . | 5 . .   

Can you solve the puzzle?
The puzzle has 15 clues. What is the minimum number of clues of a MinLex puzzle?

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

Re: MinLex Puzzles

Postby Leren » Sat Jan 23, 2021 12:48 am

Code: Select all
*-----------------------*
| 1 2 3 | 4 5 6 | 7 8 9 |
| 4 5 6 | 8 7 9 | 1 2 3 |
| 9 8 7 | 2 1 3 | 4 5 6 |
|-------+-------+-------|
| 3 6 5 | 7 9 4 | 8 1 2 |
| 7 9 4 | 1 8 2 | 3 6 5 |
| 2 1 8 | 3 6 5 | 9 4 7 |
|-------+-------+-------|
| 6 3 1 | 5 4 7 | 2 9 8 |
| 5 4 2 | 9 3 8 | 6 7 1 |
| 8 7 9 | 6 2 1 | 5 3 4 |
*-----------------------*

Is this right ? Leren
Leren
 
Posts: 4031
Joined: 03 June 2012

Re: MinLex Puzzles

Postby Mathimagics » Sat Jan 23, 2021 5:06 am

Leren, that solution cannot be minlex. One property of minlex grids is that (r4c1 < r5c1 < r6c1), (r7c1 < r8c1 < r9c1), and (r4c1 < r7c1). Thus there are 5 implied Futoshiki clues. So, with r5c1 = 7 in this puzzle, that means that r6c1 = 9.

JPF, minlex grids have fixed value in the first 11 cells, that is r1 = {123456789} and r2c12 = {45}. So is this a 15 clue puzzle, or is it really a 26 clue puzzle? :?

That semantic quibble aside, "how many additional clues are the minimum necessary?" is still a very interesting question, I think. 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby Leren » Sat Jan 23, 2021 6:13 am

Withdrawn.
Last edited by Leren on Sat Jan 23, 2021 9:33 am, edited 1 time in total.
Leren
 
Posts: 4031
Joined: 03 June 2012

Re: MinLex Puzzles

Postby Mathimagics » Sat Jan 23, 2021 7:21 am

Hmmm ... it could be that JPS's puzzle is in fact invalid!

[ EDIT ] rubbish, see post below ...

I added the 11 givens to it, and fed that into a normal Sudoku solver:
Code: Select all
12345678945...9....8..........79....7....2....18.........54...8.42.3..........5.. # NS = 463

I then checked those 463 solutions, and there was no solution S that satisified Minlex(S) = S ... :?
Last edited by Mathimagics on Mon Jan 25, 2021 3:36 pm, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby Leren » Sat Jan 23, 2021 7:26 am

Withdrawn
Last edited by Leren on Sat Jan 23, 2021 9:04 am, edited 1 time in total.
Leren
 
Posts: 4031
Joined: 03 June 2012

Re: MinLex Puzzles

Postby Mathimagics » Sat Jan 23, 2021 8:49 am

Mathimagics wrote:Hmmm ... it could be that JPS's puzzle is in fact invalid!


Apologies to JPF, the only invalid here is me ... :oops:

The puzzle is valid, the requirements are clear, and the solution is:

Solution: Show
Code: Select all
 +-------+-------+-------+
 | 1 2 3 | 4 5 6 | 7 8 9 |
 | 4 5 7 | 1 8 9 | 2 3 6 |
 | 6 8 9 | 2 7 3 | 1 5 4 |
 +-------+-------+-------+
 | 2 3 5 | 7 9 4 | 8 6 1 |
 | 7 6 4 | 8 1 2 | 3 9 5 |
 | 9 1 8 | 3 6 5 | 4 7 2 |
 +-------+-------+-------+
 | 3 9 1 | 5 4 7 | 6 2 8 |
 | 5 4 2 | 6 3 8 | 9 1 7 |
 | 8 7 6 | 9 2 1 | 5 4 3 |
 +-------+-------+-------+


Solution Info: Show
Code: Select all
123456789457189236689273154235794861764812395918365472391547628542638917876921543

This minlex grid is in Band  39, at grid#  17,514,110  (the full ED catalog index is 1,561,664,895)


I did at least get the normal Sudoku solution count (463) correct, but stuffed up (royally) the testing of those solutions ... :?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby Mathimagics » Sat Jan 23, 2021 10:16 am

JPF's original 15-clue has some redundancy, here is a minimal 11-clue form:

Code: Select all
..............................7.....7....2....18.........54...8..2.3..........5..
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby JPF » Sat Jan 23, 2021 10:44 am

Mathimagics wrote:Apologies to JPF, the only invalid here is me ... :oops:
I like this sense of humor :D

and yes, your solution is correct. It's easy to verify.
Just a hint : r4c1=2 see here. It gives 83 grid-candidates instead of 463.

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

Re: MinLex Puzzles

Postby Serg » Sat Jan 23, 2021 10:47 am

Hi, JPF!
Thank you for interesting puzzle!
Solving it manually (using minlex form's properties), I came to the puzzle with 2 solutions, solved it by computer solver and choose solution with less minlex metric.

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

Re: MinLex Puzzles

Postby Mathimagics » Sat Jan 23, 2021 1:29 pm

.
Ok, boys and girls, try this one, 7 clues, one minlex solution:

Code: Select all
 +-------+-------+-------+
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 +-------+-------+-------+
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | 6 . . | . . . | . 3 . |
 +-------+-------+-------+
 | . . . | . 8 . | . . . |
 | . . 5 | . . . | . . . |
 | . . 9 | . 7 2 | . . . |
 +-------+-------+-------+

.............................................6......3.....8......5........9.72...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1644
Joined: 27 May 2015
Location: Canberra

Re: MinLex Puzzles

Postby coloin » Sat Jan 23, 2021 3:25 pm

Are we allowed to expand it to -
Code: Select all
+---+---+---+
|123|456|789|
|45.|...|...|
|...|...|...|
+---+---+---+
|2..|...|...|
|...|...|...|
|6..|...|.3.|
+---+---+---+
|...|.8.|...|
|..5|...|...|
|..9|.72|...|
+---+---+---+
hmmm but still has multi solutions .......
coloin
 
Posts: 1982
Joined: 05 May 2005

Re: MinLex Puzzles

Postby coloin » Sat Jan 23, 2021 3:33 pm

Adding a few clues..... and that r3c1 is a 9 therefore r2c3 has to be a 7 ?
Code: Select all
+---+---+---+
|123|456|789|
|457|...|...|
|986|...|...|
+---+---+---+
|2..|...|...|
|5..|...|...|
|6..|...|.3.|
+---+---+---+
|..2|.8.|...|
|..5|...|...|
|..9|.72|...|
+---+---+---+
now i wonder which band it is 30-416 ?
coloin
 
Posts: 1982
Joined: 05 May 2005

Re: MinLex Puzzles

Postby JPF » Sat Jan 23, 2021 3:35 pm

of course, but one and only one solution S has to be such that S = MinLex(S)

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

Re: MinLex Puzzles

Postby m_b_metcalf » Sat Jan 23, 2021 7:03 pm

Mathimagics wrote:.
Ok, boys and girls, try this one, 7 clues, one minlex solution:


Maybe this solution, one of 229,603,014, is near:

Code: Select all
  1  2  3  4  5  6  7  8  9
  4  5  6  7  9  8  1  2  3
  9  7  8  1  2  3  4  5  6
  2  3  1  5  6  4  9  7  8
  5  9  4  8  3  7  2  6  1
  6  8  7  2  1  9  5  3  4
  3  4  2  9  8  5  6  1  7
  7  6  5  3  4  1  8  9  2
  8  1  9  6  7  2  3  4  5
Last edited by m_b_metcalf on Sat Jan 23, 2021 7:26 pm, edited 1 time in total.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 11567
Joined: 15 May 2006
Location: Berlin

Next

Return to General