Homework exercise

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

Homework exercise

Postby JPF » Mon Jan 24, 2022 10:19 am

1) a pattern is not minimal if there is no minimal puzzle containing this pattern.
Prove that the pattern below is not minimal:
Code: Select all
+-------+-------+-------+
| . . . | . x . | . . . |
| . . . | . x . | . . . |
| . . . | . x . | . . . |
+-------+-------+-------+
| . . . | x . x | . . . |
| x x x | . . . | x x x |
| . . . | x . x | . . . |
+-------+-------+-------+
| . . . | . x . | . . . |
| . . . | . x . | . . . |
| . . . | . x . | . . . |
+-------+-------+-------+

You can have a look at Mauricio's post/JPF's thread to get a hint on how it can be proven.

2) The pattern above is fully symmetric.
Based on question 1 and on serg's thread here, for how many valid fully symmetric patterns can we be sure that there are not minimal?
List them all.

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

Re: Homework exercise

Postby Serg » Mon Jan 24, 2022 2:49 pm

Hi, JPF!
I am sorry, but the term "minimal pattern" is busy - see the thread Minimal patterns.

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

Re: Homework exercise

Postby JPF » Mon Jan 24, 2022 4:01 pm

busy?
I don't want to have lengthy discussions about terminology or paternity, but...

in this thread "Minimal Puzzles"dated : Sat Sep 29, 2007, I wrote in the introduction post:
A pattern is called non minimal if there is no minimal valid puzzle containing this pattern

Mauricio, ravel, coloin, gsf, m_b_metcalf among others posted in that thread.

The concept I had was that some patterns can't have any minimal puzles.

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

Re: Homework exercise

Postby Serg » Tue Jan 25, 2022 8:22 am

Hi, JPF!
Formally you are right - your definition was published before mine. It looks like I saw discussions on similar themes before 2007, but without definitions.

These entities ("non minimal patterns") are interesting and can be useful during generation of high-clue minimal puzzles (40+ clues). But "non minimal patterns" containing many clue cells look like less useful, than "non minimal patterns" containg fewer cells. For example, there is evident "non minimal pattern", containing 81 clues:
Code: Select all
+-----+-----+-----+
|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|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+

The fewer cells in the "non minimal pattern", the more interesting it is. More strickly speaking, the most interesting should be non minimal patterns not having other non minimal patterns as subsets. I think, such patterns should be called as "basic" or "minimal". Should one say "minimal non minimal pattern"? I propose to change the term "non minimal pattern" to "avoidable pattern". In this case we could talk about "minimal avoidable patterns".

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

Re: Homework exercise

Postby Serg » Tue Jan 25, 2022 12:17 pm

Hi, JPF!
JPF wrote:1) a pattern is not minimal if there is no minimal puzzle containing this pattern.
Prove that the pattern below is not minimal:
Code: Select all
+-------+-------+-------+
| . . . | . x . | . . . |
| . . . | . x . | . . . |
| . . . | . x . | . . . |
+-------+-------+-------+
| . . . | x . x | . . . |
| x x x | . . . | x x x |
| . . . | x . x | . . . |
+-------+-------+-------+
| . . . | . x . | . . . |
| . . . | . x . | . . . |
| . . . | . x . | . . . |
+-------+-------+-------+

You can have a look at Mauricio's post/JPF's thread to get a hint on how it can be proven.

This pattern is non minimal, because it contains another non minimal pattern as subset
Code: Select all
+-------+-------+-------+
| . . . | x x x | x x x |
| x . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+

This pattern was proven to be non minimal by Mauricio in the thread you cited.

I wonder if there are non minimal patterns having less than 7 clues?

Serg

[Edited. I corrected typos.]
Last edited by Serg on Tue Jan 25, 2022 1:27 pm, edited 1 time in total.
Serg
2018 Supporter
 
Posts: 785
Joined: 01 June 2010
Location: Russia

Re: Homework exercise

Postby champagne » Tue Jan 25, 2022 12:32 pm

deleted, not in line with the concept
Last edited by champagne on Tue Jan 25, 2022 2:01 pm, edited 1 time in total.
champagne
2017 Supporter
 
Posts: 7257
Joined: 02 August 2007
Location: France Brittany

Re: Homework exercise

Postby JPF » Tue Jan 25, 2022 1:08 pm

Hi Serg!

Correct!
It's funny, but I had a longer proof...
I didn't see that I could use that Mauricio's non minimal pattern!!
you wrote:I wonder if there are non minimal patterns having less than 7 clues?

Good question! Let's put it as the third question of the homework!

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

Re: Homework exercise

Postby JPF » Sat Jan 29, 2022 11:00 am

I understand Serg's concern about the existence of non-minimal patterns contained in a non-minimal pattern.
Let's leave this point aside for the moment.
Consider the following six non-minimal patterns. None of them contain another.
For patterns F1,F2,F3 see here
For pattern F6 see here
Code: Select all
 F1              F2              F3              F4              F5              F6
+---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+
|.xx|xxx|xxx|   |...|xxx|xxx|   |...|...|...|   |xxx|...|...|   |xxx|xxx|xxx|   |xxx|x.x|...|
|...|...|...|   |x..|...|...|   |...|.x.|...|   |xxx|...|...|   |...|...|...|   |...|...|...|
|...|...|...|   |...|...|...|   |...|...|...|   |xxx|...|...|   |...|...|...|   |xxx|x.x|...|
+---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+
|x..|...|...|   |...|...|...|   |...|x.x|...|   |...|...|...|   |...|...|...|   |...|xxx|...|
|...|...|...|   |...|...|...|   |...|x.x|...|   |...|...|...|   |...|...|...|   |...|x.x|...|
|...|...|...|   |...|...|...|   |...|x.x|...|   |...|...|...|   |...|...|...|   |...|xxx|...|
+---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+
|...|...|...|   |...|...|...|   |...|...|...|   |...|...|...|   |...|...|...|   |...|...|...|
|...|...|...|   |...|...|...|   |...|...|...|   |...|...|...|   |...|...|...|   |...|...|...|
|...|...|...|   |...|...|...|   |...|...|...|   |...|...|...|   |...|...|...|   |...|...|...|
+---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+

Let's apply the filter of these patterns to the set of fully symmetrical patterns (FS)
As mentionned here there are 6016 ed-patterns.

In this thread Serg showed that there are only 5145 valid patterns (i.e. pattern having at least one valid puzzle).
The question is: how many of these patterns are non-minimal?
Without fully answering the question, we can use the previous filters to eliminate some which are not.

The result is the following: 3297 can be eliminated as non minimal.
Here are the details by number of clues:

Code: Select all
                                                                                             
   clues     valids     elimin.                                                                 
                                                                                               
       20        16         0                                                                 
       21        22         0                                                                 
       24        87         9                                                                 
       25        89        13                                                                 
       28       178        31                                                                 
       29       180        39                                                                 
       32       271        72                                                                 
       33       272        86                                                                 
       36       345       139                                                                 
       37       346       154                                                                 
       40       381       217                                                                 
       41       382       231                                                                 
       44       370       275                                                                 
       45       370       282                                                                 
       48       319       282                                                                 
       49       319       285                                                                 
       52       245       237                                                                 
       53       245       237                                                                 
       56       165       165                                                                 
       57       165       165                                                                 
       60        98        98                                                                 
       61        98        98                                                                 
       64        52        52                                                                 
       65        52        52                                                                 
       68        24        24                                                                 
       69        24        24                                                                 
       72        10        10                                                                 
       73        10        10                                                                 
       76         4         4                                                                 
       77         4         4                                                                 
       80         1         1                                                                 
       81         1         1                                                                 
               ----      ----                                                                 
    TOTAL      5145      3297                                                                 


Then, it proves that there are no minimal FS puzzles with more than 53 clues. Not a surprise actually.

Filter efficiency
For this particular set of patterns (FS), here is the number of eliminated elements by each filter:
Code: Select all
     Filter eliminated patterns                                                           
                                                                                         
        F1                1495                                                           
        F2                2387                                                           
        F3                2490                                                           
        F4                 923                                                           
        F5                 832                                                           
        F6                 638                                                           
 

Some patterns are eliminated by only one filter:
Code: Select all
F3
+---+---+---+
|.x.|.x.|.x.|
|xx.|...|.xx|
|...|...|...|
+---+---+---+
|...|xxx|...|
|x..|x.x|..x|
|...|xxx|...|
+---+---+---+
|...|...|...|
|xx.|...|.xx|
|.x.|.x.|.x.|
+---+---+---+


Code: Select all
F2
+---+---+---+
|.x.|.x.|.x.|
|xxx|...|xxx|
|.x.|...|.x.|
+---+---+---+
|...|x.x|...|
|x..|...|..x|
|...|x.x|...|
+---+---+---+
|.x.|...|.x.|
|xxx|...|xxx|
|.x.|.x.|.x.|
+---+---+---+


Code: Select all
F1
+---+---+---+
|xxx|x.x|xxx|
|x..|...|..x|
|x..|...|..x|
+---+---+---+
|x..|.x.|..x|
|...|xxx|...|
|x..|.x.|..x|
+---+---+---+
|x..|...|..x|
|x..|...|..x|
|xxx|x.x|xxx|
+---+---+---+


open questions

  • smallest number of clues of not-minimal patterns
  • is F3 the only one with 7 clues ?
  • is there any with only 6 clues ?
  • Find new ones

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

Re: Homework exercise

Postby marek stefanik » Sat Jan 29, 2022 9:44 pm

I am attempting a classification of the proofs that have been used, based on the contradictions with minimality that they use.
I hope it can give us a better idea of how to prove non-minimality of other patterns.


The simplest one, proof by a hidden single (demonstrated on one of the original non-minimal patterns found by Mauricio):
Code: Select all
 . . . | . . . | . . .
 . . . | . x . | . . .
 . . . | . . . | . . .
-------+-------+-------
 . . . | x . x | . . .
 . . . | x . x | . . .
 . . . | x . x | . . .
-------+-------+-------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .
Let a be the digit given in r2c5. In b5, a is forced into the given cells. Deleting the given of a in b5 will make it a hidden single, therefore it is redundant and the pattern is non-minimal.


Similarly, we can use naked singles (but AFAIK this cannot prove a pattern non-minimal by itself):
Code: Select all
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|. . .|x x x|. . .|
|. . .|x . x|. . .|
|. . .|x x x|. . .|
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+
Let a be the digit not given in b5. If a were given anywhere in b2468, any given in b5 seen by the a given would be redundant, as its cell would be a naked single.
With eight givens in a line, the missing digit cannot be given anywhere in the grid (as it makes one of the givens redundant or eliminates the last candidate from the non-given cell).


We can use fish patterns:
With a set of given cells, if the absence of a digit from these cells would result in a m\m-1 fish on that digit, that digit must appear at least twice within that set of givens.
Proof: One appearance is required for a solution, therefore would be redundant as a given when other cells of the set are filled with other digits.
Demonstration on a pattern I came up with:
Code: Select all
+-----+-----+-----+
|x x x|x . x|. . .|
|. . .|. . .|. . .|
|x x x|x . x|. . .|
+-----+-----+-----+
|. . .|x x x|. . .|
|. . .|x . x|. . .|
|. . .|x x x|. . .|
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+
Let a be the digit not given in b5. There is a fish ab125\r2c5 + given cells in b12. Therefore a must be given at least twice in these boxes.
It can only be given once in b1, hence it must be given in b2, which is a contradiction with the naked single argument above. This pattern is non-minimal.


We can use the generalisation of fish, multifish, as well.
In this case the individual fish creating the multifish are way more significant then they are when solving a sudoku (demonstrated on a pattern by Mauricio):
Code: Select all
+-------+-------+-------+
| . . . | x . x | . . . |
| . . . | x . x | . . . |
| . . . | x . x | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | x . x | . . . |
| . . . | x . x | . . . |
| . . . | x . x | . . . |
+-------+-------+-------+
Every digit a has the fish ab28\c5 + givens in b28, hence each of them must appear in them at least twice. That makes 18 givens which must be placed inside 12 cells, ie. a contradiction (as there can only be one given in each cell). The pattern is non-minimal.


I have a few patterns that came from a discussion with JCO where we were trying to extend the argument I had for my previous pattern.
I will post them once I check if they contain smaller non-minimal patterns that can be proven with the multifish argument.

Marek
marek stefanik
 
Posts: 250
Joined: 05 May 2021

Re: Homework exercise

Postby marek stefanik » Sat Jan 29, 2022 11:10 pm

I didn't find a way to apply it to them, so here they are:
Code: Select all
+-----+-----+-----+
|x . x|. . .|x . x|
|. . .|. . .|. . .|
|x . x|. . .|x . x|
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|x . x|. . .|x x x|
|. . .|. . .|x . x|
|x . x|. . .|x x x|
+-----+-----+-----+
Let's call a the digit not given in b9.
NS argument => a cannot be given in b37.
HS ab9
fish argument: ab137\r2c2 + givens in b137 => a must be given at least twice in b137
The two arguments combined mean that a must be given at least twice in b1, ie. contradiction.
The pattern is non-minimal.

Code: Select all
+-----+-----+-----+
|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|
+-----+-----+-----+
Let's call a the digit not given in b6.
NS argument => a cannot be given in b349
HS ab6
fish argument: a b1379\r28c2 + givens in b1379 => a must be given at least twice in b1379
combined a must be given at least twice in b17 while not given in b4 => no a candidate left in c2, ie. contradiction
The pattern is non-minimal.

Code: Select all
+-----+-----+-----+
|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|
+-----+-----+-----+
Let's call a the digit not given in b9.
NS argument => a cannot be given in b3678
HS ab9
fish argument: a b12468\r25c25 + givens in b12468 except for r2c2 => a must be given at least twice in b12468, not counting r2c2
combined a must be given at least twice in b124 not counting r2c2 while not given in b37
a given in b12 => no a candidate in r2
a given in b14 => no a candidate in c2
a given in b24 => fish ar2c2\b1 + given in r2c2 => not enough cells for two appearances of a
The pattern is non-minimal.

Using the multifish argument I managed to find a non-minimal subpattern in my first find:
Code: Select all
+-----+-----+-----+
|x x x|x . x|. . .|
|. . .|. . .|. . .|
|x x x|x . x|. . .|
+-----+-----+-----+
|. . .|x . x|. . .|
|. . .|x . x|. . .|
|. . .|x . x|. . .|
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+
fish b125\r2c5 + givens in b125 on every digit => 18 givens in 16 cells
The pattern is non-minimal.


JPF wrote:For this particular set of patterns (FS), here is the number of eliminated elements by each filter:
Interesting results. I believe that this Mauricio's pattern could make a great filter as well:
Code: Select all
+-------+-------+-------+
| . . . | x . x | . . . |
| . . . | x . x | . . . |
| . . . | x . x | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | x . x | . . . |
| . . . | x . x | . . . |
| . . . | x . x | . . . |
+-------+-------+-------+


JPF wrote:open questions
  • smallest number of clues of not-minimal patterns
  • is F3 the only one with 7 clues ?
  • is there any with only 6 clues ?
  • Find new ones
With eight or less clues any subpuzzle that doesn't repeat a digit and has solutions is minimal (there is always an isomorphic puzzle with one of the missing digits instead of the one used).
This way you only have to check one puzzle per pattern. Mostly. There could be patterns without such subpuzzles that aren't non-minimal.
Personally I highly doubt that there are any, though.

Marek
marek stefanik
 
Posts: 250
Joined: 05 May 2021

Re: Homework exercise

Postby Serg » Sun Jan 30, 2022 7:52 pm

Hi, JPF!
It's nice idea - to check methods of fast patterns minimality detection in the fully symmetrical patterns area. These patterns are rather well studied, so they can be used as "guinea pigs". I think methods of fast patterns minimality detection can be useful both for high-clue minimal puzzles search (40+ clues) and for exhaustive search for 17-clue puzzles. All valid fully symmetrical patterns are supersets of 49 "basic" minimal valid patterns. Those patterns produce minimal puzzles only. Supersets of those minimal patterns can be of 2 types - patterns producing minimal and non-minimal valid puzzles and patterns producing non-minimal valid puzzles only. Part of those patterns producing non-minimal valid puzzles only you filtered out.

Well done!

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

Re: Homework exercise

Postby Serg » Sun Jan 30, 2022 7:59 pm

Hi, Marek!
Your results are very interesting!
marek stefanik wrote:Similarly, we can use naked singles (but AFAIK this cannot prove a pattern non-minimal by itself):
Code: Select all
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|. . .|x x x|. . .|
|. . .|x . x|. . .|
|. . .|x x x|. . .|
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+

Of course, this pattern isn't non-minimal (avoidable). Otherwise many minimal puzzles published in the thread "More Homework!" would be non-minimal. The same is true for 8-clue "row" pattern.

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

Re: Homework exercise

Postby JPF » Mon Jan 31, 2022 8:45 am

marek stefanik wrote:I believe that this Mauricio's pattern could make a great filter as well:
Code: Select all
+-------+-------+-------+
| . . . | x . x | . . . |
| . . . | x . x | . . . |
| . . . | x . x | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | x . x | . . . |
| . . . | x . x | . . . |
| . . . | x . x | . . . |
+-------+-------+-------+

Yeah..I missed that one!
That filter (F7) increases the number of eliminations from 3297 to 3306.
F7 alone eliminates 1138 FS patterns.
There are patterns only eliminated by F7 ; here is an example:
Code: Select all
+---+---+---+
|x..|x.x|..x|
|.x.|x.x|.x.|
|..x|x.x|x..|
+---+---+---+
|xxx|...|xxx|
|...|...|...|
|xxx|...|xxx|
+---+---+---+
|..x|x.x|x..|
|.x.|x.x|.x.|
|x..|x.x|..x|
+---+---+---+

Here are the revised data:
Code: Select all
      Filter      eliminated patterns                                                           
                                                                                         
        F1                1495                                                           
        F2                2387                                                           
        F3                2490                                                           
        F4                 923                                                           
        F5                 832                                                           
        F6                 638
        F7                1138 


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


Return to General