The New Sudoku Players' Forum

[JPF]

About this thread, there is an easy way to order the set of puzzles : consider their Lex representation.
Just to be clear, this puzzle:

Code: Select all

+---+---+---+
|...|..2|..8|
|..2|7..|1..|
|.6.|.9.|.2.|
+---+---+---+
|.1.|4..|..9|
|..9|.6.|7..|
|3..|...|.5.|
+---+---+---+
|.2.|.5.|.4.|
|..4|..8|5..|
|5..|1..|..3|
+---+---+---+

has the Lex representation:

Code: Select all

000002008002700100060090020010400009009060700300000050020050040004008500500100003

or:

Code: Select all

.....2..8..27..1...6..9..2..1.4....9..9.6.7..3......5..2..5..4...4..85..5..1....3

where . stands for 0.

What is the smallest (valid) minimal puzzle? i.e. having the minimum Lex representation?

JPF

[coloin]

quick try

Code: Select all

+---+---+---+
|...|...|...|
|...|...|..1|
|...|..2|...|
+---+---+---+
|..1|.3.|..4|
|..5|...|..6|
|.4.|7..|1.8|
+---+---+---+
|.69|..7|..5|
|.2.|..9|.8.|
|1.4|82.|.93|
+---+---+---+

Code: Select all

.................1.....2.....1.3...4..5.....6.4.7..1.8.69..7..5.2...9.8.1.482..93



[JPF]

Hi coloin,

I don't know the exact answer, but I will try to post better ones as long as I can...

Code: Select all

.................1.....2.....1.3...4..5.....6.4.7..1.8.69..7..5.2...9.8.1.482..93    coloin   
.................1.....2.....1.....3..2..3.4...4..562..1..57.8..39.84..6.47.2...9    JPF     

JPF

[Mathimagics]

What is the smallest (valid) minimal puzzle? i.e. having the minimum Lex representation?

So we are just looking at the set of all minimal puzzles in minlex form, without any requirement for them to solve to minlex grids?

[JPF]

So we are just looking at the set of all minimal puzzles in minlex form, without any requirement for them to solve to minlex grids?

right!

JPF

[Mathimagics]

Ok, how's this?

Code: Select all

.................1.....1.2...1.....3..2..4.....4..56...5..7..4..6.3..5...8.9.....

[JPF]

edited

Code: Select all

.................1.....1.2...1.....3..2..4.....4..56...5..7..4..6.3..5...8.9.....      Mathimagics
.................1.....1..2..1.3...4.5..6..7..768......18.5..2..9..8.3..5..2.361.      JPF1
.................1.....1..2..1..2..3..2....4...567.....18.23.54.24..6....3..18.96      JPF2


Code: Select all

+---+---+---+
|...|...|...|
|...|...|..1|
|...|..1|..2|
+---+---+---+
|..1|..2|..3|
|..2|...|.4.|
|..5|67.|...|
+---+---+---+
|.18|.23|.54|
|.24|..6|...|
|.3.|.18|.96|    JPF2
+---+---+---+


JPF

[JPF]

a new one:

Code: Select all

.................1.....1..2..1..2..3..2....4...3.561.7.14..3..8.25.18.7..39.2.5..


Code: Select all

+---+---+---+
|...|...|...|
|...|...|..1|
|...|..1|..2|
+---+---+---+
|..1|..2|..3|
|..2|...|.4.|
|..3|.56|1.7|
+---+---+---+
|.14|..3|..8|
|.25|.18|.7.|
|.39|.2.|5..|   JPF3
+---+---+---+


JPF

[JPF]

last improvement :

Code: Select all

.................1.....1..2..1..2..3..2....4...3.45..6.15.7..8..26.5..9..3.8.6.1.

Code: Select all

+---+---+---+
|...|...|...|
|...|...|..1|
|...|..1|..2|
+---+---+---+
|..1|..2|..3|
|..2|...|.4.|
|..3|.45|..6|
+---+---+---+
|.15|.7.|.8.|
|.26|.5.|.9.|
|.3.|8.6|.1.|    JPF4
+---+---+---+


JPF

[coloin]

Its funny - that we havent done this exercise before ....and it depends on the way you fill in the first 2 bands ...

last improvement : ....

And by that comment I thought it was definitive - and that you had done an exhaustive search after the first 12 clues.... !
Gridchecker checked ...
Maybe it is the smallest minlex puzzle in "2.55 × 10^25 non-essentially-equivalent minimal puzzles".

Code: Select all

.................1.....1..2..1..2..3..2....4...3.45..6.1...3.8..25.7..9..36.54.1.

Code: Select all

+---+---+---+
|...|...|...|
|...|...|..1|
|...|..1|..2|
+---+---+---+
|..1|..2|..3|
|..2|...|.4.|
|..3|.45|..6|
+---+---+---+
|.1.|..3|.7.|
|.25|.8.|.9.|
|.36|.54|.1.|
+---+---+---+   

[JPF]

Congratulations for your finding!

And by that comment I thought it was definitive - and that you had done an exhaustive search after the first 12 clues.... !

Actually, I did it "by hand" for all the bands.
I still don't see obvious reasons why the following patterns would be impossible:

Code: Select all

+---+---+---+   +---+---+---+
|...|...|...|   |...|...|...|
|...|...|..1|   |...|...|..1|
|...|..1|..2|   |...|..1|..2|
+---+---+---+   +---+---+---+
|...|xxx|xxx|   |..1|...|xxx|
|xxx|xxx|xxx|   |xxx|xxx|xxx|
|xxx|xxx|xxx|   |xxx|xxx|xxx|
+---+---+---+   +---+---+---+
|xxx|xxx|xxx|   |xxx|xxx|xxx|
|xxx|xxx|xxx|   |xxx|xxx|xxx|
|xxx|xxx|xxx|   |xxx|xxx|xxx|
+---+---+---+   +---+---+---+


hidden UAs ?

JPF

[Serg]

Hi, JPF!

I still don't see obvious reasons why the following patterns would be impossible:

Code: Select all

+---+---+---+   +---+---+---+
|...|...|...|   |...|...|...|
|...|...|..1|   |...|...|..1|
|...|..1|..2|   |...|..1|..2|
+---+---+---+   +---+---+---+
|...|xxx|xxx|   |..1|...|xxx|
|xxx|xxx|xxx|   |xxx|xxx|xxx|
|xxx|xxx|xxx|   |xxx|xxx|xxx|
+---+---+---+   +---+---+---+
|xxx|xxx|xxx|   |xxx|xxx|xxx|
|xxx|xxx|xxx|   |xxx|xxx|xxx|
|xxx|xxx|xxx|   |xxx|xxx|xxx|
+---+---+---+   +---+---+---+


The first pattern is subset of P123 maximal invalid pattern:

Code: Select all

        P123
+-----+-----+-----+
|. . .|. x x|x x x|
|. . .|. x x|x x x|
|. . .|. x x|x x x|
+-----+-----+-----+
|. . .|x x x|x x x|
|. . .|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
|. . .|x x x|x x x|
|. . .|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+

(See List of 40 maximal pattern.)

Serg

[coloin]

Yes ....that would explain that !!!

But a better one has emerged ...

Code: Select all

.................1.....1..2..1..2..3..2....4...3.45..6.1...3.7..25.6..8..367.4.19

Code: Select all

+---+---+---+ 
|...|...|...|       
|...|...|..1|       
|...|..1|..2|       
+---+---+---+       
|..1|..2|..3|       
|..2|...|.4.|       
|..3|.45|..6|       
+---+---+---+       
|.1.|..3|.7.|       
|.25|.6.|.8.|       
|.36|7.4|.19|       
+---+---+---+

[coloin]

From a long time ago on-the-minimum-and-maximum-minlex-minimal-sudokus-t5579.html

We already know the maximum and minimum min-lex solution grids. Finding the minimum is easier that finding the maximum.

A related question is trying to find the minimum and maximum minimal sudokus. That question is obviously harder than trying to find the minimum and maximum minlex solution grid, as there are a lot more minimal sudokus than solution grids.

My conjectures about that sudokus are the following:

Code: Select all

     Minimum?
    +-------+-------+-------+
    | . . . | . . . | . . . |
    | . . . | . . . | . . 1 |
    | . . . | . . 1 | . . 2 |
    +-------+-------+-------+
    | . . 1 | . . 2 | . . 3 |
    | . . 2 | . . . | . 4 . |
    | . . 3 | . 4 5 | . . 6 |
    +-------+-------+-------+
    | . 1 . | . . 3 | . 7 . |
    | . 2 5 | . 6 . | . 8 . |
    | . 3 6 | 7 . 4 | . 1 9 |
    +-------+-------+-------+

It seems that Mauricio thought the posted puzzle was the minimum too

It seems unlikely that there will be a puzzle with an empty space at r4c9 - as the pattern is valid but is the puzzle is lexographically larger

Code: Select all

+---+---+---+
|...|...|...|
|...|...|..1|
|...|..2|..3|
+---+---+---+
|..3|...|...|
|816|453|729|
|752|981|436|
+---+---+---+
|187|239|564|
|925|146|387|
|634|875|192|
+---+---+---+

I used gridchecker to provide the minimum puzzles from the 7 valid band 1 & band 2 fillings and removed clues from the associated band 3s

from around 2M puzzles here were the top results / number of clues/ ranking but I am not sure how Mauricio did it !!!

Code: Select all

000000000000000001000001002001002003002000040003045006010003070025060080036704019   25       1    BEST   
000000000000000001000001002001002003002000040003045006010003070025060080036704029   25       2           
000000000000000001000001002001002003002000040003045006010003070025060080036704109   25       3           
000000000000000001000001002001002003002000040003045006010003070025060080036704209   25       4           
000000000000000001000001002001002003002000040003045006010003070025060080036709014   25       5           
000000000000000001000001002001002003002000040003045006010003070025060080036709024   25       6           
000000000000000001000001002001002003002000040003045006010003070025060080036709104   25       7           
000000000000000001000001002001002003002000040003045006010003070025060080036709204   25       8           
000000000000000001000001002001002003002000040003045006010003070025060080036754010   25       9           
000000000000000001000001002001002003002000040003045006010003070025060080036754020   25      10           
000000000000000001000001002001002003002000040003045006010003070025060080800054100   23      17           
000000000000000001000001002001002003002000040003045006010003070025060080800754010   24      35           
000000000000000001000001002001002003002000040003045006010003070025060300036754028   26      55           
000000000000000001000001002001002003002000040003045006010003070025064000700050080   22      94           
000000000000000001000001002001002003002000040003045006010003070025160308036708024   27     310           
000000000000000001000001002001002003002000040003045006010003070027054308039708214   28     849           
000000000000000001000001002001002003002000040003045006010003070028700000500090080   21    1226           


Would have to explore furthur for 20C and 19C

But a little search found this 18C, i would say unlikely to be the absolute smallest ...

Code: Select all

+---+---+---+
|...|...|...|
|...|...|..1|
|...|..1|.23|
+---+---+---+
|...|...|...|
|..2|.4.|5..|
|.31|..6|...|
+---+---+---+
|...|1.3|..6|
|5.4|...|7..|
|7..|..8|...|
+---+---+---+


[JPF]

I'm not sure I understand.
That 18C is greater than Mauricio's puzzle:

Code: Select all

.................1.....1..2..1..2..3..2....4...3.45..6.1...3.7..25.6..8..367.4.19  Mauricio
.................1.....1.23...........2.4.5...31..6......1.3..65.4...7..7....8...  coloin 18C
.........................*.......................................................


JPF