The New Sudoku Players' Forum

[JPF]

To each valid pattern (i.e. containing a valid puzzle), we associate the binary number representing the pattern in its MinLex representation

Example:

Code: Select all

Puzzle           Pattern        MinLex pattern
+---+---+---+   +---+---+---+   +---+---+---+
|.12|..3|4..|   |.xx|..x|x..|   |...|...|..x|
|..4|5..|1..|   |..x|x..|x..|   |...|..x|.x.|
|3.5|...|...|   |x.x|...|...|   |..x|.x.|xxx|
+---+---+---+   +---+---+---+   +---+---+---+
|...|6..|.2.|   |...|x..|.x.|   |...|..x|...|
|...|..5|3.6|   |...|..x|x.x|   |.x.|..x|x..|
|..7|..1|.4.|   |..x|..x|.x.|   |x.x|.x.|..x|
+---+---+---+   +---+---+---+   +---+---+---+
|...|...|8..|   |...|...|x..|   |.xx|.x.|...|
|7..|29.|...|   |x..|xx.|...|   |x..|.x.|...|
|..3|..8|.12|   |..x|..x|.xx|   |x..|x..|x.x|
+---+---+---+   +---+---+---+   +---+---+---+


Code: Select all

Puzzle              .12..34....45..1..3.5.........6...2......53.6..7..1.4.......8..7..29......3..8.12
Pattern (Lex)       .11..11....11..1..1.1.........1...1......11.1..1..1.1.......1..1..11......1..1.11
Pattern (MinLex)    ........1.....1.1...1.1.111.....1....1...11..1.1.1...1.11.1....1...1....1..1..1.1


Now, the question is : what is the smallest (valid) pattern?

Here is a first proposal:

Code: Select all

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

.................1.....1.....1........1..1..1..1..1.1..1..1...1.1..1..1..1..1..11


Filtering: assuming we know the smallest pattern Pmin, we have a kind of filter for the patterns:
if a pattern P is such that MinLex(P) <Pmin, then we can conclude that the pattern P is not valid.

The filter is not really efficient but it exists.
For a random set of (1,000,000) 17 clue patterns 25% didn't pass the test (i.e. were invalid), assuming my Pmin is the right one...

JPF

[coloin]

It looks like it is the smallest pattern - initial search drew only similar pattern puzzles - and its clear from your puzzle why the minlex pattern puzzle can be larger than the resultant minlex puzzle [eg swop row 4 and row 5 and more]

Code: Select all

.................1.....2.....3........1..4..5..6..7.4..4..1...3.8..3..9..5..2..78
.................X.....X.....X........X..X..X..X..X.X..X..X...X.X..X..X..X..X..XX


In your pattern the only room for improvements looks like the r6c8 -> r6c9 or r8c8 -> r8c9 - and maybe these are impossible patterns

With 2 clues in the first band - there are 111 18C puzzles- and none of these have a smaller pattern
There are no 17C puzzles with 2 clues in a band anyway.

This is one of the 4 18C puzzles with the minimal template of the 111 - [which is larger than yours]

Code: Select all

+---+---+---+
|...|...|...|
|...|...|..1|
|...|..2|...|
+---+---+---+
|..3|...|...|
|..1|..4|..5|
|..6|..7|.2.|
+---+---+---+
|.4.|.1.|..8|
|.2.|.3.|.7.|
|.7.|8..|.9.|
+---+---+---+
 18C minlexpattern puzzle

[coloin]

And having established the minimum pattern which necessarily must have 2 clues in the first band
If we are to define a pattern filter
One could find the minimum pattern which has a first band of the min lex pattern with these 3 clues, for example

Code: Select all

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

Code: Select all

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

an improvement - but approaching sergs patterns work i suppose

Code: Select all

+---+---+---+
|...|...|..1|
|...|...|..2|
|...|..3|...|
+---+---+---+
|..4|...|52.|
|..6|..7|...|
|..7|..4|38.|
+---+---+---+
|.5.|.3.|.6.|
|.8.|9..|.7.|
|7.9|24.|..5|
+---+---+---+



[JPF]

or this one:

Code: Select all

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


and an improvement:

Code: Select all

+---+---+---+
|...|...|..1|
|...|...|..2|
|...|..3|...|
+---+---+---+
|..1|...|...|
|..2|...|..4|
|..5|..6|.7.|
+---+---+---+
|.7.|.6.|...|
|.3.|.17|.89|
|.6.|248|1..|
+---+---+---+


JPF

[coloin]

Code: Select all

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


but easy to have an empty column ... which gives a smaller overall pattern with an empty row 1

[JPF]

Code: Select all

+---+---+---+
|...|...|..1|
|...|...|..2|
|...|..3|...|
+---+---+---+
|..1|...|...|
|..4|...|..3|
|..5|..6|.7.|
+---+---+---+
|.2.|..5|..8|
|.6.|.8.|1.5|
|5.7|6.9|2..|
+---+---+---+


JPF

[JPF]

and this one:

Code: Select all

+---+---+---+   +---+---+---+
|...|...|..1|   |...|...|..x|
|...|...|..2|   |...|...|..x|
|...|..3|...|   |...|..x|...|
+---+---+---+   +---+---+---+
|..1|...|...|   |..x|...|...|
|..2|...|..4|   |..x|...|..x|
|..5|..6|.7.|   |..x|..x|.x.|
+---+---+---+   +---+---+---+
|.6.|..7|...|   |.x.|..x|...|
|.3.|.4.|18.|   |.x.|.x.|xx.|
|1.4|82.|6.5|   |x.x|xx.|x.x|
+---+---+---+   +---+---+---+


can probably be improved...

JPF

[coloin]

Code: Select all

+---+---+---+
|...|...|..5|
|...|...|..1|
|...|..3|...|
+---+---+---+
|..8|...|...|
|..1|...|...|
|.3.|.98|64.|
+---+---+---+
|.2.|.56|.8.|
|.95|.82|.14|
|8.7|3..|.5.|
+---+---+---+



[JPF]

Code: Select all

+---+---+---+
|...|...|..1|
|...|...|..2|
|...|..3|...|
+---+---+---+
|..3|...|...|
|..4|...|...|
|..5|26.|78.|
+---+---+---+
|.3.|..6|.9.|
|.6.|.1.|..5|
|1.7|.49|.38|
+---+---+---+


JPF

[coloin]

Code: Select all

+---+---+---+
|...|...|..1|
|...|...|..2|
|...|..3|...|
+---+---+---+
|..3|...|...|
|..4|...|...|
|..5|26.|.78|
+---+---+---+
|.3.|..6|8.4|
|.6.|.19|..5|
|1.7|5..|.6.|
+---+---+---+


Getting near to the smallest now

[JPF]

Code: Select all

+---+---+---+
|...|...|..1|
|...|...|..2|
|...|..3|...|
+---+---+---+
|..4|...|...|
|..3|...|...|
|..5|61.|.78|
+---+---+---+
|.6.|..8|9.3|
|.1.|.39|..4|
|2..|.7.|.1.|
+---+---+---+

and better:

Code: Select all

+---+---+---+
|...|...|..1|
|...|...|..2|
|...|..3|...|
+---+---+---+
|..3|...|...|
|..4|...|...|
|..5|16.|.78|
+---+---+---+
|.3.|..6|9.4|
|.1.|.29|...|
|2.9|.4.|8.5|
+---+---+---+


JPF

[coloin]

Edited - Wouldn’t have thought we would get this far !!
Yet there IS further to go !!

[JPF]

Your puzzle is invalid...
Here is one with the same pattern:

Code: Select all

+---+---+---+
|...|...|..1|
|...|...|..2|
|...|..3|...|
+---+---+---+
|..4|...|...|
|..5|...|...|
|..3|16.|.78|
+---+---+---+
|.6.|..4|3..|
|.1.|.28|..5|
|2..|9..|.1.|
+---+---+---+


JPF

[coloin]

Code: Select all

+---+---+---+
|...|...|..1|
|...|...|..2|
|...|..4|...|
+---+---+---+
|..4|...|...|
|..5|...|...|
|..3|16.|.78|
+---+---+---+
|.6.|..8|3..|
|.1.|.2.|.95|
|2..|7..|.8.|
+---+---+---+


[JPF]

improvement:

Code: Select all

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


JPF