The New Sudoku Players' Forum

[JPF]

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

[Leren]

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

[Mathimagics]

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.

[Leren]

Withdrawn.

[Mathimagics]

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 ...

[Leren]

Withdrawn

[Mathimagics]

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

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

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 ...

[Mathimagics]

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..

[JPF]

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

I like this sense of humor

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

[Serg]

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

[Mathimagics]

.
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...


[coloin]

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]

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 ?

[JPF]

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

JPF

[m_b_metcalf]

.
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