The New Sudoku Players' Forum

[Serg]

Hi, all!
Suppose we consider Sudoku puzzles, having 9 clues in B3, B6, B7, B8 and B9 boxes. How many clues must all remaining 4 boxes (B1, B2, B4, B5) contain to form valid Sudoku puzzle?

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" denotes clue cell.)

It turns out (I've done exhaustive search), boxes B1, B2, B4 and B5 must contain at least 2 clues to form valid puzzles. There are 3 only "irreducible" minimal patterns (up to isomorphs), producing valid patterns, which have minimal number of clues in B1, B2, B4, B5 boxes.

Code: Select all

         Q1                        Q2                        Q3
+-----+-----+-----+       +-----+-----+-----+       +-----+-----+-----+
|. . .|. . .|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 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|
+-----+-----+-----+       +-----+-----+-----+       +-----+-----+-----+

Here are examples of valid puzzles for Q1-Q3 patterns:

......689......137......254......792.....9368..2...415235197846817546923964238571
......689......371......245......596......427..5.27138541873962832619754967245813
......689......217.....6354......493......165..5...728317529846548631972692784531

Patterns Q1-Q3 are minimal - if we remove at least one clue in the B1, B2, B4, B5 boxes area, resulting patterns will have no valid puzzles.
Every pattern, containing 9 clues in B3, B6, B7, B8, B9 boxes and having valid puzzles must be subset of some isomorph of pattern Q1 or Q2 or Q3. Moreover, let's consider any pattern, producing valid puzzles. Each Sudoku grid has 9 4-box subsets forming "square" (occupying 2 bands and 2 stacks). Patterns of clues in each such 4-box subsets must be superset for some Q1-Q3 4-box (B1, B2, B4, B5) patterns.

Serg

[JPF]

Nice work!
and you can extend the results for Q1 for example to a pattern like:

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


JPF

[Serg]

Hi, JPF!

Nice work!

Thank you!

... and you can extend the results for Q1 for example to a pattern like:

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


Yes, some extra clue cells can be removed from B36789 crossing, because those cells cannot participate UA set. Here are some other examples of clues elimination.

Code: Select all

     Example 1                 Example 2                 Example 3
+-----+-----+-----+       +-----+-----+-----+       +-----+-----+-----+
|. . .|. . .|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 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|
+-----+-----+-----+       +-----+-----+-----+       +-----+-----+-----+

Serg

[JPF]

Actually, I was referring to B9, based on the lemma given here and confirmed by Red Ed

JPF

[Serg]

Hi, JPF!

Actually, I was referring to B9, based on the lemma given here and confirmed by Red Ed

Thank for the link! Red Ed's proof is simple and elegant as always.
Now I am trying to present more general statement.

Virtual Clue Principle
Each empty cell of Sudoku puzzle can have or have not property "potential participant of unavoidable set".
Empty cell is potential participant of unavoidable set if and only if following statements are true.

1. Empty cell's row contain at least one another "adjacent" empty cell having property "potential participant of unavoidable set".
2. Empty cell's column contain at least one another "adjacent" empty cell having property "potential participant of unavoidable set".
3. Empty cell's box contain at least one another "adjacent" empty cell having property "potential participant of unavoidable set".
4. Adjacent empty cells in the row and in the column aren't located in the same box as given empty cell. Both adjacent cells (for row and column) must be located in the different boxes or one of them may be located in the same box as given empty cell, but the second must be located in the different box.

If given empty cell has not property "potential participant of unavoidable set", its value is determined by puzzle's clue cells, and this cell can be treated as clue cell during analisys - has considered pattern valid puzzles or not.

This Virtual Clue Principle provides conversion of all empty cells to clue cells in B36789 in your example and in my examples.

Serg

[JPF]

Let me put it this way:
a pattern is valid if it exists a valid puzzle with this pattern.
a pattern is (valid) minimal if it doesn't contain a valid pattern other than itself.

What you said : Q1 is a valid pattern.
There are many valid patterns Q included in Q1 : Q⊆Q1 ; you proved that they need to have one clue in each box B4 and B5 in a different row.

What I added : among the valid patterns Q included in Q1, there are those in which B9 is empty and having only 8 clues in B3,B6,B7,B8.
Taking your example and using lemma 1, we can delete the clues in B9 and one clue in each box B3,B6,B7,B8:

Code: Select all

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


The resulting pattern is not minimal.
It would be interesting to know how many minimal patterns are included in Q1 and such that B9=[0] or/and those having the lowest number of clues.

JPF

[Serg]

Hi, JPF!

Let me put it this way:
a pattern is valid if it exists a valid puzzle with this pattern.
a pattern is (valid) minimal if it doesn't contain a valid pattern other than itself.

Did you see the thread Minimal patterns? In any way your definition is quite acceptable.

What you said : Q1 is a valid pattern.
There are many valid patterns Q included in Q1 : Q⊆Q1 ; you proved that they need to have one clue in each box B4 and B5 in a different row.

What I added : among the valid patterns Q included in Q1, there are those in which B9 is empty and having only 8 clues in B3,B6,B7,B8.
Taking your example and using lemma 1, we can delete the clues in B9 and one clue in each box B3,B6,B7,B8:

Code: Select all

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


The resulting pattern is not minimal.

You are right, pattern Q1 is not minimal in the strict sense. But it is rather "partially" minimal - it is minimal in the area B1245, but isn't minimal in the area B36789. I propose to call such "partially" minimal patterns as "restricted minimal patterns" - their minimality is restricted to some boxes only.

It would be interesting to know how many minimal patterns are included in Q1 and such that B9=[0] or/and those having the lowest number of clues.

Let me say about more grandiose goal - to find all possible minimal patterns. I think there are 100-150 thousands of minimal patterns (including 30000+ 17-clue patterns). I hope patterns Q1-Q3 published above can lead us to full catalog of minimal patterns in future.

As for your question "how many minimal patterns are included in Q1 and such that B9=[0] or/and those having the lowest number of clues", I think there are several thousands of such minimal patterns. And the task to find all those patterns is very complicated.

Serg

[qiuyanzhe]

Virtual Clue Principle: Show

Virtual Clue Principle
Each empty cell of Sudoku puzzle can have or have not property "potential participant of unavoidable set".
Empty cell is potential participant of unavoidable set if and only if following statements are true.

1. Empty cell's row contain at least one another "adjacent" empty cell having property "potential participant of unavoidable set".
2. Empty cell's column contain at least one another "adjacent" empty cell having property "potential participant of unavoidable set".
3. Empty cell's box contain at least one another "adjacent" empty cell having property "potential participant of unavoidable set".
4. Adjacent empty cells in the row and in the column aren't located in the same box as given empty cell. Both adjacent cells (for row and column) must be located in the different boxes or one of them may be located in the same box as given empty cell, but the second must be located in the different box.

If given empty cell has not property "potential participant of unavoidable set", its value is determined by puzzle's clue cells, and this cell can be treated as clue cell during analisys - has considered pattern valid puzzles or not.

It's not sufficient for a cell to be a "potential participant".
For instance, in the grids

Two counterexamples:: Show

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



, R1C1 in both grids can be determined. Counterexamples that I've found currently are all based on intersections or fishes.

P.S. Are cells in potential BUGs "potential participants"? We define it by actual results or by usual view?
e.g. A BUG template with no solution when it's really a BUG(so it has no solution normally, or unique solution, or it's a 0-solution BUG)

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


[Serg]

Hi, qiuyanzhe!

Virtual Clue Principle
Each empty cell of Sudoku puzzle can have or have not property "potential participant of unavoidable set".
Empty cell is potential participant of unavoidable set if and only if following statements are true.

1. Empty cell's row contain at least one another "adjacent" empty cell having property "potential participant of unavoidable set".
2. Empty cell's column contain at least one another "adjacent" empty cell having property "potential participant of unavoidable set".
3. Empty cell's box contain at least one another "adjacent" empty cell having property "potential participant of unavoidable set".
4. Adjacent empty cells in the row and in the column aren't located in the same box as given empty cell. Both adjacent cells (for row and column) must be located in the different boxes or one of them may be located in the same box as given empty cell, but the second must be located in the different box.

If given empty cell has not property "potential participant of unavoidable set", its value is determined by puzzle's clue cells, and this cell can be treated as clue cell during analisys - has considered pattern valid puzzles or not.

It's not sufficient for a cell to be a "potential participant".
For instance, in the grids

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



, R1C1 in both grids can be determined. Counterexamples that I've found currently are all based on intersections or fishes.

Your observation is very interesting! First of your counterexamples was analyzed by blue in the thread Investigation of one-crossing-free patterns in 2013. He proved that some class of patterns, having empty cells in two rows and two columns only always produce multisolution puzzles and can be reduced by adding one or more clues to patterns producing valid puzzles. Have you some kind of proof for your second counterexample?

You of course are right. My 4 requirements are not sufficient for a cell to be a "potential participant". I'll ponder how to change that definition. Really we are interesting not in "potential participant" cells, but on the contrary - in the cells not having this property.

P.S. Are cells in potential BUGs "potential participants"? We define it by actual results or by usual view?
e.g. A BUG template with no solution when it's really a BUG(so it has no solution normally, or unique solution, or it's a 0-solution BUG)

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


Yes, such patterns can extend "virtual clue" concept. But that concept should be formulated in more suitable way.

Serg

[Serg]

Hi, all!
Virtual Clue Principle (version 2)

Empty cell can be treated as "virtual clue cell" if at least one of the following statements is true.

1. Empty cell's row or column or box contains 8 clue cells.
2. Empty cell's row and column contain no empty cells outside the box of considered empty cell.
3. Empty cell's 2 bands and 2 stacks configuration (one band and one stack contain given empty cell) is equivalent to the following pattern ('.' denotes empty cell, "x" denotes clue cell) with r1c1 cell considered as given empty cell.

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 |

...

Virtual clue cell can be considered as true clue cell while applying rules given above or during determining the property of a pattern - can this pattern produce valid puzzles?

Serg

[Edited. I fixed errors in "virtual clue" definition.]

[JPF]

Hi Serg,

I don't understand the concept.
Can you give an example ?

JPF

[Serg]

Hi, people!
One can think that "virtual clues" are far from practice, but on the contrary - "virtual clue" concept was invented to solve my pactical tasks.
For example, I encountered serious problems when checked "Sample Pattern" - has it valid puzzles or no?

Code: Select all

  Sample Pattern

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

Exhaustive search for all possible puzzles for this patterns was too long, so I was forced to invent some "tricks" to speed up the search. Virtual clue principle allowed to reduce this pattern to Cross Pattern.

Code: Select all

   Cross Pattern

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

Exhaustive search for Cross Pattern is much more simple, so I managed to reduced initial task to simpler (feasible) task using Virtual Clue principle.

Serg

[Hajime]

And row 5 and column 5 can be made completely empty...

[coloin]

....Let me say about more grandiose goal - to find all possible minimal patterns. I think there are 100-150 thousands of minimal patterns (including 30000+ 17-clue patterns). I hope patterns Q1-Q3 published above can lead us to full catalog of minimal patterns in future.

As for your question "how many minimal patterns are included in Q1 and such that B9=[0] or/and those having the lowest number of clues", I think there are several thousands of such minimal patterns. And the task to find all those patterns is very complicated.

Serg

so the 30,000 minimal 17C [valid] patterns each expand [81-17 = 64 ] to upwards of x 64 18C [non-minimal valid] patterns

interesting .... which might explain the finding that 18 clue patterns which have a valid puzzle each have on average 20 ED [Edit ... it might even be 50 !!]* puzzles ...... which means the vast majority of 18C patterns dont have puzzles [ and probably can be expanded to maximal non-valid patterns - as in your example above]
so for the 18C
There may be 2e9 puzzles and there may well be 1.3e11 potential patterns [ 81! / [ 63! x 18! x 6^8 x 2 ] ?]

Edit !
* Estimation of number of ED puzzles per valid patttern with n clues This is unvalidated I should add !

[coloin]

and overnight a little thought ....
Your initial post was showing patterns with clues in B1245 which have puzzles. any less clues in B1245 will be a maximal pattern which doest have a puzzle.

We have investigated this topic, and you have shown that the maximal magic pattern doesnt have puzzles, and indeed its easier to show that a maximal pattern has no puzzles if it has full boxes,rows and or columns.
These are as you have termed "maximal" patterns ... and they dont have puzzles. Maximal in that adding any additional clue wll result in a pattern which will have valid puzzles. .... and, as you say, any subset of these maximal patterns inherently cant have valid puzzles either.

There could well be more patterns to be proved in my thread here
just how to prove that a virtual pattern or empty region in a grid always has x number of disjoint UAs, and therefore always needs at least x clues is problematic ... but you have proved it in the 4 box pattern, although since 1 clue is needed in B124 we therefore need need 2 clues in B1245 ..

Minimal patterns that have puzzles is now a new concept to me.... and indeed there is work that could be done.

With a large collection of 18C puzzles, we will have many patterns which are without the 30,000 17C patterns plus 1 clue

we also have all the 18C puzzles with 2 clues in a band, and any new [ non+1] pattern 19C puzzle would be a minimal pattern
we also have all the puzzles which have 7 clues in 2 bands

Of course ,with the proviso that there may be a few more 17C still to be found / not found !!