7-cell Unavoidable Sets

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

7-cell Unavoidable Sets

Postby dobrichev » Sun Jan 05, 2025 2:31 am

19 years after the original study, I think it's worth publishing two 7-cell patterns missing from popular UA lists.
At least McGuire's code in Checker doesn't find them, and they aren't included in Ed Russell's list.

Both look like a compound of two U4 with a swapped value in the common corner.
Code: Select all
Canonical form:

.  .  13 |  .  .  .  |  31 .  .
.  .  21 |  32 .  .  |  13 .  .
.  .  32 |  23 .  .  |  .  .  .

Example:
+----------+----------+----------+
| 1  2  3  | 4  5  6  | 7  8  9  |
| 4  5  6  | 7  8  9  | 1  3  2  |
| 7  8  9  | 2  3  1  | 5  4  6  |
+----------+----------+----------+
| 2  39 1  | 8  6  5  | 93 7  4  |
| 6  73 5  | 1  97 4  | 39 2  8  |
| 8  97 4  | 3  79 2  | 6  5  1  |
+----------+----------+----------+
| 3  4  7  | 6  1  8  | 2  9  5  |
| 5  1  8  | 9  2  7  | 4  6  3  |
| 9  6  2  | 5  4  3  | 8  1  7  |
+----------+----------+----------+



Canonical form:

.  .  .  |  .  .  .  |  .  .  .
.  12 .  |  21 .  .  |  .  .  .
31 23 .  |  12 .  .  |  .  .  .
--------- ----------- ---------
13 31 .  |  .  .  .  |  .  .  .
.  .  .  |  .  .  .  |  .  .  .
.  .  .  |  .  .  .  |  .  .  .

Example:
+----------+----------+----------+
| 1  2  3  | 4  5  6  | 7  8  9  |
| 4  5  6  | 7  8  9  | 1  3  2  |
| 7  8  9  | 2  3  1  | 5  4  6  |
+----------+----------+----------+
| 2  3  14 | 8  6  5  | 9  71 47 |
| 6  7  5  | 1  9  4  | 3  2  8  |
| 8  9  41 | 3  7  2  | 6  5  14 |
+----------+----------+----------+
| 3  4  7  | 6  1  8  | 2  9  5  |
| 5  1  8  | 9  2  7  | 4  6  3  |
| 9  6  2  | 5  4  3  | 8  17 71 |
+----------+----------+----------+
dobrichev
2016 Supporter
 
Posts: 1871
Joined: 24 May 2010

Re: 7-cell Unavoidable Sets

Postby champagne » Sun Jan 05, 2025 8:59 am

dobrichev wrote:19 years after the original study, I think it's worth publishing two 7-cell patterns missing from popular UA lists.
At least McGuire's code in Checker doesn't find them, and they aren't included in Ed Russell's list.

Hi Mladen,

This pushes me years back as well.
But I must say that when I learned from you a better way to produce an use unavoidable sets, I forgot the list of templates for UAs of size <=12.
And an unavoidable set with 3 digits is very easy to get using the brute force.
champagne
2017 Supporter
 
Posts: 7490
Joined: 02 August 2007
Location: France Brittany

Re: 7-cell Unavoidable Sets

Postby Serg » Sun Jan 05, 2025 10:44 am

Hi, Mladen!
dobrichev wrote:19 years after the original study, I think it's worth publishing two 7-cell patterns missing from popular UA lists.

I think both your examples are unavoidable sets, but not minimal ones. Both UAs contain U4 as subsets. Let me redefine the first UA set in more suitable for me form (letter denotes some digit):
Code: Select all
..A|...|C..
..B|C..|A..
..C|B..|...

One can see that
Code: Select all
...|...|...
..B|C..|...
..C|B..|...
is U4 subset.

You pointed not all candidates in your definitions. I think your first definition must look like this:
Code: Select all
.  .  13 |  . .  .  | 31 .  .
.  .  123| 32 .  .  | 13 .  .
.  .  32 | 23 .  .  |  . .  .

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

Re: 7-cell Unavoidable Sets

Postby Serg » Sun Jan 05, 2025 12:30 pm

Hi, Mladen!
dobrichev wrote:Example:
Code: Select all
+----------+----------+----------+
| 1  2  3  | 4  5  6  | 7  8  9  |
| 4  5  6  | 7  8  9  | 1  3  2  |
| 7  8  9  | 2  3  1  | 5  4  6  |
+----------+----------+----------+
| 2  39 1  | 8  6  5  | 93 7  4  |
| 6  73 5  | 1  97 4  | 39 2  8  |
| 8  97 4  | 3  79 2  | 6  5  1  |
+----------+----------+----------+
| 3  4  7  | 6  1  8  | 2  9  5  |
| 5  1  8  | 9  2  7  | 4  6  3  |
| 9  6  2  | 5  4  3  | 8  1  7  |
+----------+----------+----------+

Let's consider puzzle for your example
Code: Select all
+-----+-----+-----+
|1 2 3|4 5 6|7 8 9|
|4 5 6|7 8 9|1 3 2|
|7 8 9|2 3 1|5 4 6|
+-----+-----+-----+
|2 . 1|8 6 5|. 7 4|
|6 . 5|1 . 4|. 2 8|
|8 . 4|3 . 2|6 5 1|
+-----+-----+-----+
|3 4 7|6 1 8|2 9 5|
|5 1 8|9 2 7|4 6 3|
|9 6 2|5 4 3|8 1 7|
+-----+-----+-----+

1234567894567891327892315462.1865.746.51.4.288.43.2651347618295518927463962543817

This puzzle has 3 solutions:
Code: Select all
123456789456789132789231546231865974675194328894372651347618295518927463962543817
123456789456789132789231546231865974695174328874392651347618295518927463962543817
123456789456789132789231546291865374635174928874392651347618295518927463962543817

Serg

[Edited. I wrongly stated that the puzzle has 2 solutions. My mistake, thanks to coloin for correction.]
Last edited by Serg on Sun Jan 05, 2025 11:58 pm, edited 1 time in total.
Serg
2018 Supporter
 
Posts: 909
Joined: 01 June 2010
Location: Russia

Re: 7-cell Unavoidable Sets

Postby dobrichev » Sun Jan 05, 2025 1:39 pm

Serg wrote:I think both your examples are unavoidable sets, but not minimal ones.


Hi Serg,
I agree with you. Partially.
The tricky point is whether you look at the pattern from perspective of given/non-given value (vanilla sudoku), or allowed/forbidden candidate (pencilmark sudoku).
We can open an infinite discussion on definitions of minimality, hitting, the differences between deadly pattern and unavoidable set, etc.

Below is a more brutal example of pattern of 77 cells, which IMHO is minimal (i.e. hitting/eliminating any of the candidates leads to unique solution), but without taking into account the rest of the restrictions on involved cells (only 2 candidates allowed) you get multiple solutions.
Code: Select all
All but 4 cells are bivalue, 2 solutions. Eliminating any single candidate leads to unique solution.
+----------+----------+----------+
| 15 8  69 | 47 3  27 | 56 19 24 |
| 36 25 17 | 68 59 24 | 34 17 89 |
| 27 49 34 | 19 18 56 | 78 26 35 |
+----------+----------+----------+
| 78 36 15 | 18 25 39 | 79 24 46 |
| 49 12 37 | 57 6  48 | 28 59 13 |
| 25 49 68 | 39 24 17 | 16 35 78 |
+----------+----------+----------+
| 49 36 28 | 45 7  16 | 15 38 29 |
| 38 17 25 | 26 49 59 | 34 78 16 |
| 16 57 49 | 23 18 38 | 29 46 57 |
+----------+----------+----------+

On the other hand, on first UA7, removing 9 as candidate in r4c2 but dropping the restrictions to other cells leads to multiple solutions.
Code: Select all
+-------------------------------+-------------------------------+-------------------------------+
| 1         2         3         | 4         5         6         | 7         8         9         |
| 4         5         6         | 7         8         9         | 1         3         2         |
| 7         8         9         | 2         3         1         | 5         4         6         |
+-------------------------------+-------------------------------+-------------------------------+
| 2         3         1         | 8         6         5         | 123456789 7         4         |
| 6         123456789 5         | 1         123456789 4         | 123456789 2         8         |
| 8         123456789 4         | 3         123456789 2         | 6         5         1         |
+-------------------------------+-------------------------------+-------------------------------+
| 3         4         7         | 6         1         8         | 2         9         5         |
| 5         1         8         | 9         2         7         | 4         6         3         |
| 9         6         2         | 5         4         3         | 8         1         7         |
+-------------------------------+-------------------------------+-------------------------------+


Do these patterns have any application in generating and solving puzzles? I think so.

Should they be distinguished from regular UA sets? Rather, yes.

Are they truly deadly patterns? Apparently so.
dobrichev
2016 Supporter
 
Posts: 1871
Joined: 24 May 2010

Re: 7-cell Unavoidable Sets

Postby Serg » Sun Jan 05, 2025 2:14 pm

Mladen,
I think I understand you. UA7 unavoidable sets don't exist in vanilla 9 x 9 Sudoku world, but may exist in Sukaku (pencilmark Sudoku) world. Apparently both your examples can be treated as deadly patterns, but in Sukaku world only.

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

Re: 7-cell Unavoidable Sets

Postby coloin » Sun Jan 05, 2025 10:40 pm

Serg wrote:This puzzle has 2 solutions, which differ in 4 cells only...

actually it has 3 solutions !
Code: Select all
1234567894567891327892315462.1865.746.51.4.288.43.2651347618295518927463962543817
                                                                                 
123456789456789132789231546231865974675194328894372651347618295518927463962543817
123456789456789132789231546231865974695174328874392651347618295518927463962543817
123456789456789132789231546291865374635174928874392651347618295518927463962543817

however each solution has a U4 and 3 extraneous clues [ which have their own set of UAs]...

we are going to have to re-write the fruitless books !!!
coloin
 
Posts: 2514
Joined: 05 May 2005
Location: Devon

Re: 7-cell Unavoidable Sets

Postby Serg » Mon Jan 06, 2025 12:34 am

Hi, coloin!
You are right, the puzzle for Mladen's first example has 3 solutions. (I corrected my post.) My solver was ajusted to find 2 first solutions only by default, but I fogot about it. I am sorry!

So, the question isn't so simple as it looks like. Let's consider Red Ed's unavoidable sets nature explanation (see the last post on this page). Here are 3 puzzle's solution, where cells containing the same digits for all solutions are omitted:
Code: Select all
............................3....9...7..9.3...9..7...............................
............................3....9...9..7.3...7..9...............................
............................9....3...3..7.9...7..9...............................

We would consider this set of 7 cells as "atomic" (minimal) UA set with 3 permutations if at least one of these permutations would be "unique", i.e. would contain all 7 digits differing from other permutations' digits. Otherwise, this set of 7 cells should be consider as UA sets mix. One can see that there is no unique permutations in our case, so this set of 7 cells cannot be treated as minimal UA set.

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

Re: 7-cell Unavoidable Sets

Postby nazaz » Mon Jan 06, 2025 6:30 pm

In the spirit of the original U4-inspired definition, dobrichev's two 7-cell examples are new, valid examples of what I think people mean by a "deadly pattern" (but not "unavoidable set"), in that each solution to those pencilmarks contains a minimal unavoidable set. The Sudopedia page on DPs seems too strict (i.e. wrong) on that point: "whose solutions are minimal unavoidable sets".
User avatar
nazaz
 
Posts: 11
Joined: 06 November 2018

Re: 7-cell Unavoidable Sets

Postby Serg » Mon Jan 06, 2025 10:51 pm

Hi, nazaz!
Deadly Pattern is a technique to solve Sudoku, isn't it? Why should we search for 7-cell DP, if such DP always contain more simple 4-cell DP? The first Mladen's example can potentially be found in Sukaku (pencilmark Sudoku) only. I am sure, that in "vanilla" Sudokus (having clue digits) can be found modified Mladen's example only:
Code: Select all
.  .  13 |  . .  .  | 31 .  .
.  .  123| 32 .  .  | 13 .  .
.  .  32 | 23 .  .  |  . .  .

This configuration contains two 4-cell "almost deadly" patterns (which is a deadly pattern but for the presence of additional candidates) - see Sudopedia DP article:
Code: Select all
Almost deadly pattern number 1
.  .  13 |  . .  .  | 31 .  .
.  .  123| .  .  .  | 13 .  .
.  .  .  | .  .  .  |  . .  .

Almost deadly pattern number 2
.  .  .  |  . .  .  | .  .  .
.  .  123| 32 .  .  | .  .  .
.  .  32 | 23 .  .  |  . .  .

So, it's no need to define new 7-cell DP.

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

Re: 7-cell Unavoidable Sets

Postby blue » Tue Jan 07, 2025 6:36 am

FWIW ...

Code: Select all
...9.5.2......8..7....1.9...2.8.14.51...6..9.8....26.......78..6.........374....1

after basics:
+---------------+------------+----------+
| 47   18  138  | 9    47  5 | 13  2  6 |
| 349  6   1239 | 23   34  8 | 13  5  7 |
| 37   5   23   | 237  1   6 | 9   8  4 |
+---------------+------------+----------+
| 39   2   6    | 8    39  1 | 4   7  5 |
| 1    7   35   | 35   6   4 | 2   9  8 |
| 8    49  459  | 57   79  2 | 6   1  3 |
+---------------+------------+----------+
| 5    14  14   | 6    2   7 | 8   3  9 |
| 6    89  89   | 1    5   3 | 7   4  2 |
| 2    3   7    | 4    8   9 | 5   6  1 |
+---------------+------------+----------+

2-String-Kite:
   3r5c3 = r5c4 - r4c5 = 3r2c5 => -3r2c3

+---------------+------------+----------+
| 47   18 *13+8 | 9    47  5 |*13  2  6 |
| 349  6  *12+9 |*23   34  8 |*13  5  7 |
| 37   5  *23   |*23+7 1   6 | 9   8  4 |
+---------------+------------+----------+
| 39   2   6    | 8    39  1 | 4   7  5 |
| 1    7   35   | 35   6   4 | 2   9  8 |
| 8    49  459  | 57   79  2 | 6   1  3 |
+---------------+------------+----------+
| 5    14  14   | 6    2   7 | 8   3  9 |
| 6    89  89   | 1    5   3 | 7   4  2 |
| 2    3   7    | 4    8   9 | 5   6  1 |
+---------------+------------+----------+

After the "basics", there are two UR patterns present: 23r23c34 and 13r12c37.
The Kite (3's in r5 and c5) destroys them both, but the DP for dobrichev's unavoidable set, remains.
blue
 
Posts: 1059
Joined: 11 March 2013

Re: 7-cell Unavoidable Sets

Postby Serg » Tue Jan 07, 2025 10:21 am

Hi, Blue!
blue wrote:The Kite (3's in r5 and c5) destroys them both, but the DP for dobrichev's unavoidable set, remains.

I am poor Sudoku solver, so I don't understand your point. What is remaining after Kite application?

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

Re: 7-cell Unavoidable Sets

Postby dobrichev » Tue Jan 07, 2025 12:55 pm

Blue, thank you for the example.

Serg, as a poor solver too, I will try to explain Blue's example in most elementary words.

We have a vanilla puzzle and assume it has unique solution.
In the pattern in band 1 which contains the 2 unavoidable rectangles and the exotic UA7 as a subset of their union, there are no givens.
So, the solution shouldnt contain these patterns and it actually doesn't.

Code: Select all
Solution:

481975326
369248157
752316984
926831475
173564298
845792613
514627839
698153742
237489561

Solution cells of interest in band 1:

..1 ... 3..
..9 2.. 1..
..2 3.. ...


At the point before Kite elimination, we can investigate the still existing two UR patterns, where, in order to avoid a secondary solution, one of the additional candidates in the pattern cells must be true.
For pattern values 2,3 in rows 2,3 and columns 3,4 the remaining candidates are 1,9 in r2c3 and 7 in r3c4. One of them must be true, but this doesn't contribute to the further solving process.
Similarly, for pattern values 1,3 in rows 1,2 columns 3,7 the remaining candidates are 8 in r1c3 and 2,9 in r2c3. One of them must be true, but this doesn't contribute to the further solving process too.

After the Kite elimination both UR are destroyed, but the exotic UA7 13r1c37 12r2c3 23r2c4 13r2c7 23r3c34 still remains.
The point is that, even in vanilla sudoku solving process, such case can appear.
Again, in order to avoid a secondary solution, one of the additional candidates in the pattern cells (after the "+" in the picture), must be true.
One of 8r1c3, 9r2c3, 7r3c4 must be true. And this ... also does not contribute to the further solving process. :)

I continue to have serious doubts about the practical value of these exotic patterns in vanilla Sudoku.
However, in any variant like X-sudoku, pencilmark sudoku, when solving overlapping grids, where candidates can be restricted externally, they can be useful in both generating and solving puzzles.
dobrichev
2016 Supporter
 
Posts: 1871
Joined: 24 May 2010

Re: 7-cell Unavoidable Sets

Postby Serg » Tue Jan 07, 2025 4:37 pm

Hi, Mladen!
Blue's example convinced me that your first "U7 example" can be treated as Deadly Pattern. But I am still sure it cannot be treated as minimal unavoidable set. (One should publish example solution grid with this "U7" to prove opposite.)

It turns out that deadly patterns and unavoidable sets are not the same entities :?

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

Re: 7-cell Unavoidable Sets

Postby denis_berthier » Wed Jan 08, 2025 12:09 pm

dobrichev wrote:At the point before Kite elimination, we can investigate the still existing two UR patterns, where, in order to avoid a secondary solution, one of the additional candidates in the pattern cells must be true.
For pattern values 2,3 in rows 2,3 and columns 3,4 the remaining candidates are 1,9 in r2c3 and 7 in r3c4. One of them must be true, but this doesn't contribute to the further solving process.
Similarly, for pattern values 1,3 in rows 1,2 columns 3,7 the remaining candidates are 8 in r1c3 and 2,9 in r2c3. One of them must be true, but this doesn't contribute to the further solving process too.

In short, the two URs "after basics" allow to conclude that there are two ORk-relations: respectively OR3(n1r2c3, n9r2c3, n7r3c4) and OR3(n8r1c3, n2r2c3, n9r2c3).
Can they contribute to a solution? It all depends on how you deal with ORk-relations.
If you consider that ORk-relations are persistent (once proven, they remain true forever) and/or ultra-persistent (splitting rules can be applied to them in order to reduce the number of candidates) and if you use ORk-chains, they may indeed allow later eliminations (see * below).

I originally introduced ORk-chains to deal with ORk-relations deduced from exotic patterns, in particular impossible patterns, but they can be used more extensively. As I'm not very interested in uniqueness, I've not done it in this context, but it'd be totally valid.

In the present case, what does the UR7 allow to conclude? Only that OR5(n1r2c3, n9r2c3, n7r3c4, n8r1c3, n2r2c3), which is much weaker than the previous two conclusions. My conclusion: only minimal UAs are useful if the ORk relations they allow to assert are considered as persistent.

(*) Starting from the resolution state "after basics"
Code: Select all
(init-sukaku-grid
    +---------------+------------+----------+
    ! 47   18  138  ! 9    47  5 ! 13  2  6 !
    ! 349  6   1239 ! 23   34  8 ! 13  5  7 !
    ! 37   5   23   ! 237  1   6 ! 9   8  4 !
    +---------------+------------+----------+
    ! 39   2   6    ! 8    39  1 ! 4   7  5 !
    ! 1    7   35   ! 35   6   4 ! 2   9  8 !
    ! 8    49  459  ! 57   79  2 ! 6   1  3 !
    +---------------+------------+----------+
    ! 5    14  14   ! 6    2   7 ! 8   3  9 !
    ! 6    89  89   ! 1    5   3 ! 7   4  2 !
    ! 2    3   7    ! 4    8   9 ! 5   6  1 !
    +---------------+------------+----------+
)

I forced the 2 ORk-relations into SudoRules, as follows:
Code: Select all
(assert
    (ORk-relation
        (OR-name UR2)
        (OR-complexity 4)
        (OR-size 3)
        (OR-candidates 123 923 734)
    )
)
(assert
    (ORk-relation
        (OR-name UR2)
        (OR-complexity 4)
        (OR-size 3)
        (OR-candidates 813 223 923)
    )
)

and I did get a solution based on an OR2-whip:

finned-x-wing-in-rows: n3{r5 r3}{c4 c3} ==> r2c3≠3, r1c3≠3
singles ==> r1c7=3, r2c7=1
At least one candidate of a previous UR2-OR3-relation between candidates n1r2c3 n9r2c3 n7r3c4 has just been eliminated.
There remains an UR2-OR2-relation between candidates: n9r2c3 n7r3c4
UR2-OR2-whip[2]: OR2{{n7r3c4 | n9r2c3}} - r2n2{c3 .} ==> r3c4≠2
stte

(This is useless in this example, as the OR2-whip could be replaced by a bivalue-chain[3]:
biv-chain[3]: r2c4{n2 n3} - r5n3{c4 c3} - r3c3{n3 n2} ==> r3c4≠2, r2c3≠2
but it shows the principle.)

[Edit]: if you have a list of UAs in some uniform readable format, I can easily write the program that will transform it into rules for asserting the corresponding ORk-relations, exactly as I did with eleven's 630 impossible 3-digit patterns.
.
denis_berthier
2010 Supporter
 
Posts: 4275
Joined: 19 June 2007
Location: Paris

Next

Return to General