What is the smallest minimal puzzle?

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

What is the smallest minimal puzzle?

Postby JPF » Sat Apr 03, 2021 8:58 pm

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
JPF
2017 Supporter
 
Posts: 4726
Joined: 06 December 2005
Location: Paris, France

Re: What is the smallest minimal puzzle?

Postby coloin » Sat Apr 03, 2021 11:46 pm

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

coloin
 
Posts: 2004
Joined: 05 May 2005

Re: What is the smallest minimal puzzle?

Postby JPF » Sun Apr 04, 2021 6:16 am

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
JPF
2017 Supporter
 
Posts: 4726
Joined: 06 December 2005
Location: Paris, France

Re: What is the smallest minimal puzzle?

Postby Mathimagics » Sun Apr 04, 2021 6:37 am

JPF wrote: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?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1677
Joined: 27 May 2015
Location: Canberra

Re: What is the smallest minimal puzzle?

Postby JPF » Sun Apr 04, 2021 6:40 am

Mathimagics wrote: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
JPF
2017 Supporter
 
Posts: 4726
Joined: 06 December 2005
Location: Paris, France

Re: What is the smallest minimal puzzle?

Postby Mathimagics » Sun Apr 04, 2021 8:29 am

Ok, how's this?

Code: Select all
.................1.....1.2...1.....3..2..4.....4..56...5..7..4..6.3..5...8.9.....
User avatar
Mathimagics
2017 Supporter
 
Posts: 1677
Joined: 27 May 2015
Location: Canberra

Re: What is the smallest minimal puzzle?

Postby JPF » Sun Apr 04, 2021 8:44 am

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
2017 Supporter
 
Posts: 4726
Joined: 06 December 2005
Location: Paris, France

Re: What is the smallest minimal puzzle?

Postby JPF » Sun Apr 04, 2021 11:16 am

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
2017 Supporter
 
Posts: 4726
Joined: 06 December 2005
Location: Paris, France

Re: What is the smallest minimal puzzle?

Postby JPF » Sun Apr 04, 2021 5:00 pm

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
JPF
2017 Supporter
 
Posts: 4726
Joined: 06 December 2005
Location: Paris, France

Re: What is the smallest minimal puzzle?

Postby coloin » Mon Apr 05, 2021 8:22 pm

Its funny - that we havent done this exercise before ....and it depends on the way you fill in the first 2 bands ...
JPF wrote: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.|
+---+---+---+   
coloin
 
Posts: 2004
Joined: 05 May 2005

Re: What is the smallest minimal puzzle?

Postby JPF » Mon Apr 05, 2021 10:18 pm

Congratulations for your finding!
you wrote: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
JPF
2017 Supporter
 
Posts: 4726
Joined: 06 December 2005
Location: Paris, France

Re: What is the smallest minimal puzzle?

Postby Serg » Mon Apr 05, 2021 10:39 pm

Hi, JPF!
JPF wrote: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
Serg
2018 Supporter
 
Posts: 742
Joined: 01 June 2010
Location: Russia

Re: What is the smallest minimal puzzle?

Postby coloin » Mon Apr 05, 2021 11:50 pm

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
 
Posts: 2004
Joined: 05 May 2005


Return to General