The New Sudoku Players' Forum

[Mauricio]

I redid the calculations without the potential hole and found that this pattern is not minimal.

Code: Select all

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

The hole is that I added a few clues (2-4) at a time and then I removed duplicates, but a sudoku morphism that identify 2 isomorphic subpuzzles of that pattern may not be a pattern morphism of the full pattern, and so we would not count some valid puzzles afterwards. In other words, if 2 subpuzzles are isomorphic but the morphism is not a pattern morphism of the full pattern, and we remove the second of them, then we will not be counting some puzzles (offsping of the second one) that could be valid (on the premise that they are isomorphic to a offsping puzzle of the first one, and that could be false).

[JPF]

While Mauricio is looking for some new non minimal patterns, I'd like to raise an open question :

Knowing that a puzzle is minimal, is there any specific techniques to solve it ?

btw, a while ago, I posted this non minimal puzzle :

Here is one non minimal puzzle.
x are clues.

Any solvers ?

Code: Select all

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



JPF

[RW]

Here is one non minimal puzzle.
x are clues.

Any solvers ?

Code: Select all

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



I just spent 10 valuable minutes of my life solving that puzzle, only to find out that Ocean had found the same solution 18 months ago...

Knowing that a puzzle is minimal, is there any specific techniques to solve it ?

This problem is a lot harder than the non minimal puzzle above. I thought about this problem a long time ago when Bill Smythe first proposed it here. If I recall correctly, back then I came to the conclusion that such a technique is impossible...

RW

[JPF]

I just spent 10 valuable minutes of my life solving that puzzle, only to find out that Ocean had found the same solution 18 months ago...

Sorry, I should have produced an other puzzle.
I gave it (again) just as an extreme example in this thread of a way to "solve" a puzzle when information on minimality is known.
What would be the conclusions if this information is not given ?

Knowing that a puzzle is minimal, is there any specific techniques to solve it ?

This problem is a lot harder than the non minimal puzzle above. I thought about this problem a long time ago when Bill Smythe first proposed it here. If I recall correctly, back then I came to the conclusion that such a technique is impossible...

Could you elaborate please ?

JPF

[Mauricio]

If I recall correctly, back then I came to the conclusion that such a technique is impossible...

Could you elaborate please ?

JPF

What could such a technique say? Eliminate a candidate? If that is the case, I can't see how adding a candidate and some reasoning would lead us to the conclusion that the puzzle without the added candidate is not minimal, don't you think?

[JPF]

What could such a technique say? Eliminate a candidate? If that is the case, I can't see how adding a candidate and some reasoning would lead us to the conclusion that the puzzle without the added candidate is not minimal, don't you think?

I share your scepticism on such a possible technique.

In addition, if P is the initial (minimal) puzzle, such technique would have to be applied just at the beginning :
as soon as the first cell c is known, P + c is not minimal anymore.

JPF

[Serg]

Hi, people!
I've done exhaustive search for one-band nonminimal patterns (defined and published in this thread - see Non minimal patterns definition). I've found 22 patterns. Here they are:

Code: Select all

         N1                      N2                      N3

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

         N4                      N5                      N6

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

         N7                      N8                      N9

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

        N10                     N11                     N12

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

        N13                     N14                     N15

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

        N16                     N17                     N18

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

        N19                     N20                     N21

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

        N22

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

Some of them are well known, but there are several new ones.

• N1 - trivial.
• N2 - published by ravel.
• N3 - published by Mauricio.
• N4 - published by Mauricio.
• N5 - trivial.

Remaining patterns are new. (Mauricio published pattern similar to N7, but with 1 extra clue.)

Serg

[Edited. I added link to nonminimal patterns definition in the JPF's post.]

[champagne]

Hi, people!
I've done exhaustive search for one-band nonminimal patterns (defined and published in this thread).
Serg

Hi serg
I tried to understand what you did, but I confess that I am lazy.
instead of (defined and published in this thread) a link to the corresponding post could help

[coloin]

Hi, people!
I've done exhaustive search for one-band nonminimal patterns

N1 is an invalid pattern - cant have any puzzles, but i guess the point is that you cant have 9 clues in a row...

If the other patterns all have valid puzzles but these cannot be minimal ... its a nice list !

At a stroke... with N6 we could compile a big list of complete puzzle 18C patterns which cant have minimal puzzles !!!

Maybe patterns from band1plusrow4 [4 rows] with no non-minimal puzzles would be interesting too

Code: Select all

+---+---+---+
|...|...|...|
|...|...|..4|
|..3|456|789|
+---+---+---+
|1..|...|...|

Example [ but not verified]

[Serg]

Hi, coloin!

N1 is an invalid pattern - cant have any puzzles, but i guess the point is that you cant have 9 clues in a row...

You are right. Pattern N1 (9 clues in a row) means that any minimal puzzle cannot contain 9 clues in a row. If you are searching for 9x9 Sudoku patterns, potentially producing minimal puzzles or even patterns, producing minimal puzzles only (those patterns are called minimal valid), you can exclude from search space patterns, containing non-minimal patterns as subset. This rule applies regardless of whether pattern has valid puzzles or no. So, this is a filter assisting in searching for minimal puzzles/patterns. JPF showed it in the thread Homework exercise.

I have a proof of pattern N6 non-minimality.
Let's consider diagonally placed minirows of any Sudoku solution grid. The are 2 cases only of digits placement:

Code: Select all

       Case 1                  Case 2

+-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|a b c|     |. . .|. . .|a b e|
|. . .|a b c|. . .|     |. . .|a b d|. . .|
|a b c|. . .|. . .|     |a b c|. . .|. . .|
+-----+-----+-----+     +-----+-----+-----+

(Letters denote some digits, those digits can be really permuted within each minirow.) Any pair of those diagonally placed minirows contains at least 2 digits in common. Let's analyze some puzzle, having 9 clues in diagonally placed minirows, for minimality. One should first determine 2 common digits ("a" and "b") of minirows r3c123 and r2c456. Now we know that minirow r1c789 must contain digits "a" and "b". So, we can safely remove digit "a" or digit "b" from r1c789 minirow. Analyzed puzzle isn't minimal. (This is not full proof, only 2 cases from 4 are considered, as Blue pointed in the next post.)

I've just done exhausteve search for "corner" non-minimal patterns (having clues in B124 area only). Surprisingly, the only one such pattern does exist. It was found by marek stefanic (see his post in the thread Homework exercise). Here it is:

Code: Select all

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

Serg

[Edited. The proof posted isn't full, see the next post of Blue.]

[blue]

Hi Serg,

I have a proof of pattern N6 non-minimality.
Let's consider diagonally placed minirows of any Sudoku solution grid. The are 2 cases only of digits placement:

Code: Select all

       Case 1                  Case 2

+-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|a b c|     |. . .|. . .|a b e|
|. . .|a b c|. . .|     |. . .|a b d|. . .|
|a b c|. . .|. . .|     |a b c|. . .|. . .|
+-----+-----+-----+     +-----+-----+-----+

(Letters denote some digits, those digits can be really permuted within each minirow.) Any pair of those diagonally placed minirows contains at least 2 digits in common. Let's analyze some puzzle, having 9 clues in diagonally placed minirows, for minimality. One should first determine 2 common digits ("a" and "b") of minirows r3c123 and r2c456. Now we know that minirow r1c789 must contain digits "a" and "b". So, we can safely remove digit "a" or digit "b" from r1c789 minirow. Analyzed puzzle isn't minimal.

Two cases are missing: what you would see in the clue cells, if you completed the bands and swapped rows 1 & 2.

Code: Select all

       Case 1                  Case 2

+-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|a b c|     |. . .|. . .|a b e|
|. . .|a b c|. . .|     |. . .|a b d|. . .|
|a b c|. . .|. . .|     |a b c|. . .|. . .|
+-----+-----+-----+     +-----+-----+-----+

-> (complete bands)

+-----+-----+-----+     +-----+-----+-----+
|g h i|d e f|a b c|     |h i d|f g c|a b e|
|d e f|a b c|g h i|     |f g e|a b d|h i c|
|a b c|g h i|d e f|     |a b c|h i e|f g d|
+-----+-----+-----+     +-----+-----+-----+

-> (swap rows)

+-----+-----+-----+     +-----+-----+-----+
|d e f|a b c|g h i|     |f g e|a b d|h i c|
|g h i|d e f|a b c|     |h i d|f g c|a b e|
|a b c|g h i|d e f|     |a b c|h i e|f g d|
+-----+-----+-----+     +-----+-----+-----+

-> (mask clues)

       Case 3                  Case 4

+-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|g h i|     |. . .|. . .|h i c|
|. . .|d e f|. . .|     |. . .|f g c|. . .|
|a b c|. . .|. . .|     |a b c|. . .|. . .|
+-----+-----+-----+     +-----+-----+-----+

In case 3, each clue is redundant.
In case 4, each 'c' is redundant.

[Serg]

Hi, Blue!
You are rignt - my proof of N6 pattern's non-minimality was not full. It should be extended by "case 3" and "case 4" to be complete.

Serg