## POM: vulnerable triplet cells

Advanced methods and approaches for solving Sudoku puzzles

### POM: vulnerable triplet cells

Hi

Being inspired by a recent exercise, I wonder if the concept of vulnerable
pairs as part of POM can be extended to vulnerable triplets or even
quads. I didn't found any reference on POM vulnerable triples. Nor in
this neither in the EUREKA forum.
I explored this variance a little bit.
After some search I finally found an example:

Code: Select all
`.68.....5.9.1.8.47.1...46..2.19..8.....4......8.2.7.9..3...1.8.....29....298.....068000005090108047010004600201900800000400000080207090030001080000029000029800000with solution:468732915592168347317594628271953864953486172684217593735641289846329751129875436`

After some hidden singles and pointing pairs:

Code: Select all
`+---------------------+---------------------+----------------------+|  4      6      8    |  37     37     2    |   9      1      5    ||  5      9      2    |   1     6      8    |   3      4      7    || 37      1     37    |   5     9      4    |   6      2      8    |+---------------------+---------------------+----------------------+|  2    457       1   |   9    35    356    |   8   3567    346    ||  9     57    3567   |   4     8    356    |   1   3567      2    || 36      8    3456   |   2     1      7    |  45      9    346    |+---------------------+---------------------+----------------------+| 67      3     45    |  67    45      1    |   2      8      9    ||  8    457   4567    | 367     2      9    | 457     35      1    ||  1      2      9    |  8   3457     35    | 457    356    346    |+---------------------+---------------------+----------------------+`

The next most easy step would be an xyz-wing, but instead I follow POM.
Looking for patterns of single digits, the only reduction possibility
is for digit 5:

pattern for digit 5
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     |ab    |X     |X     |c       |defg  |X     |h     |X     |+------+------+------+------+--------+------+------+------+------+|X     |cde   |f     |X     |X       |abh   |X     |g     |X     |+------+------+------+------+--------+------+------+------+------+|X     |X     |gh    |X     |X       |X     |abcdef|X     |X     |+------+------+------+------+--------+------+------+------+------+|X     |X     |acd   |X     |befgh   |X     |X     |X     |X     |+------+------+------+------+--------+------+------+------+------+|X     |fgh   |be    |X     |X       |X     |      |acd   |X     |+------+------+------+------+--------+------+------+------+------+|X     |X     |X     |X     |ad      |c     |gh    |bef   |X     |+------+------+------+------+--------+------+------+------+------+`

There are 8 patterns for candidate 5 (abcdefg). cell [87] is not part
of any of these 8 patterns, so <5>r8c7

As here are no further single digit pattern recution possibilities,
I generated the POM merge grid:

Code: Select all
`|          4 |           6 |            8 |      3(abcd) | 3(efghijk) |             2 |          9 |            1 |           5|          . |           . |            . |        7(ab) |   7(cdefg) |             . |          . |            . |           .| ---------- |  ---------- |   ---------- |   ---------- | ---------- |    ---------- | ---------- |   ---------- |  ----------|          5 |           9 |            2 |            1 |          6 |             8 |          3 |            4 |           7| ---------- |  ---------- |   ---------- |   ---------- | ---------- |    ---------- | ---------- |   ---------- |  ----------| 3(abcefgh) |           1 |      3(dijk) |            5 |          9 |             4 |          6 |            2 |           8|     7(cde) |     7(abfg) |            . |            . |          . |             . |          . |            . || ---------- |  ---------- |   ---------- |   ---------- | ---------- |    ---------- | ---------- |   ---------- |  ----------|          2 |      4(abc) |            1 |            9 |       3(a) |       3(befi) |          8 |    3(gj)5(h) |     3(cdhk)|          . | 5(ab)7(acf) |            . |            . |       5(c) | 5(defg)6(abc) |          . | 6(de)7(bdeg) |   4(d)6(fg)| ---------- |  ---------- |   ---------- |   ---------- | ---------- |    ---------- | ---------- |   ---------- |  ----------|          9 |      5(cde) |       3(abe) |            4 |          8 |     3(cdghjk) |          1 |    3(fi)5(g) |           2|          . |      7(bdg) | 5(f)6(a)7(e) |            . |          . | 5(abh)6(defg) |          . |  6(bc)7(acf) |           .| ---------- |  ---------- |   ---------- |   ---------- | ---------- |    ---------- | ---------- |   ---------- |  ----------|    3(dijk) |           8 |  3(cfgh)4(d) |            2 |          1 |             7 |       4(a) |            9 |      3(abe)|     6(bdf) |           . |  5(gh)6(ceg) |            . |          . |             . |  5(abcdef) |            . |   4(bc)6(a)| ---------- |  ---------- |   ---------- |   ---------- | ---------- |    ---------- | ---------- |   ---------- |  ----------|    6(aceg) |           3 |         4(b) |       6(bdf) |     4(acd) |             1 |          2 |            8 |           9|    7(abfg) |           . |       5(acd) |       7(cde) |   5(befgh) |             . |          . |            . |           .| ---------- |  ---------- |   ---------- |   ---------- | ---------- |    ---------- | ---------- |   ---------- |  ----------|          8 |        4(d) |   4(ac)5(be) |   3(efghijk) |          2 |             9 |       4(b) |      3(abcd) |           1|          . |  5(fgh)7(e) |  6(bdf)7(cd) | 6(aceg)7(fg) |          . |             . |      7(ab) |       5(acd) |           .| ---------- |  ---------- |   ---------- |   ---------- | ---------- |    ---------- | ---------- |   ---------- |  ----------|          1 |           2 |            9 |            8 | 3(bcd)4(b) |          3(a) | 4(cd)5(gh) |       3(ehk) |     3(fgij)|          . |           . |            . |            . | 5(ad)7(ab) |          5(c) |   7(cdefg) | 5(bef)6(afg) | 4(a)6(bcde)`

and the pattern IDs are:

Code: Select all
`3 = abcdefghijk4 = abcd5 = abcdefgh6 = abcdefg7 = abcdefg`

There are lots of vulnerable pairs, but only a few lead to some pattern
reduction and to two candidate eliminations:

vulnerable pair for digit 4 in [42] [75]
pattern 5b can be eliminated in [42], [56], [75] and [83]

vulnerable pair for digit 4 in [42] [97]
patterns 7c and 7f can be eliminated in [42], [97], [15], [31]c only,
[33]f only, [58], [71]f only, [74]c only, [83]c only, and [84]f only.

vulnerable pair for digit 5 in [67] and [7][5]
pattern 4a can be eliminated in [42], [67], [75], [83], and [99]

There is no longer any 4 in [67] and in [99]; hence candidate 4 can be
canceled in the candidate grid.

vulnerable pair for digit 6 in [61] [84]
patterns 3ijk can be eliminated in [15], [33], [46]i, [48]j, [49]k,
[56]jk, [58]i, [61], [84], and [99]ij

vulnerable pair for digit 7 in [48] [71]
pattern 6e can be eliminated in [48], [56], [63], [71], [84], and [99]

After these reduction steps the merge grid looks like this:

Code: Select all
`---------  +  --------- +   --------- ++  --------- +  --------- +     --------- ++   --------- +   --------- + ---------4          |          6 |           8 ||    3(abcd) |    3(efgh) |             2 ||           9 |           1 |         5           |            |             ||      7(ab) |     7(deg) |               ||             |             |---------  +  --------- +   --------- ++  --------- +  --------- +     --------- ++   --------- +   --------- + ---------5          |          9 |           2 ||          1 |          6 |             8 ||           3 |           4 |         7---------  +  --------- +   --------- ++  --------- +  --------- +     --------- ++   --------- +   --------- + ---------3(abcefgh) |          1 |        3(d) ||          5 |          9 |             4 ||           6 |           2 |         87(de)      |            |      7(abg) ||            |            |               ||             |             |---------  +  --------- +   --------- ++  --------- +  --------- +     --------- ++   --------- +   --------- + ------------------  +  --------- +   --------- ++  --------- +  --------- +     --------- ++   --------- +   --------- + ---------2          |      4(bc) |           1 ||          9 |       3(a) |        3(bef) ||           8 |    3(g)5(h) |    3(cdh)           |   5(a)7(a) |             ||            |       5(c) | 5(defg)6(abc) ||             | 6(d)7(bdeg) | 4(d)6(fg)---------  +  --------- +   --------- ++  --------- +  --------- +     --------- ++   --------- +   --------- + ---------9          |     5(cde) |  3(abe)5(f) ||          4 |          8 |       3(cdgh) ||           1 |    3(f)5(g) |         2           |     7(bdg) |    6(a)7(e) ||            |            |  5(ah)T6(dfg) ||             |   6(bc)7(a) |---------  +  --------- +   --------- ++  --------- +  --------- +     --------- ++   --------- +   --------- + ---------3(d)       |          8 | 3(cfgh)4(d) ||          2 |          1 |             7 ||         4() |           9 |    3(abe)6(bdf)     |            |  5(gh)6(cg) ||            |            |               ||    5(acdef) |             | 4(bc)6(a)---------  +  --------- +   --------- ++  --------- +  --------- +     --------- ++   --------- +   --------- + ------------------  +  --------- +   --------- ++  --------- +  --------- +     --------- ++   --------- +   --------- + ---------6(acg)     |          3 |        4(b) ||     6(bdf) |      4(cd) |             1 ||           2 |           8 |         97(abg)     |            |      5(acd) ||      7(de) |    5(efgh) |               ||             |             |---------  +  --------- +   --------- ++  --------- +  --------- +     --------- ++   --------- +   --------- + ---------8          |       4(d) |    4(c)5(e) ||    3(efgh) |          2 |             9 ||        4(b) |     3(abcd) |         1           | 5(fgh)7(e) |  6(bdf)7(d) ||T6(acg)7(g) |            |               ||       7(ab) |      5(acd) |---------  +  --------- +   --------- ++  --------- +  --------- +     --------- ++   --------- +   --------- + ---------1          |          2 |           9 ||          8 | 3(bcd)4(b) |          3(a) ||       4(cd) |  3(eh)5(ef) |  3(fg)4()           |            |             ||            | 5(ad)7(ab) |          5(c) || 5(gh)7(deg) |      6(afg) |   T6(bcd)---------  +  --------- +   --------- ++  --------- +  --------- +     --------- ++   --------- +   --------- + ---------`

With remaining patterns:

Code: Select all
`3 = abcdefgh4 = bcd5 = acdefgh6 = abcdfg7 = abdeg`

Now, the cells [56], [84] and [99] build a vulnerable triplet for
candidate 6. These three cells show together all remaining patterns for digit
6, so this digit must be in at least one of the three cells. Any pattern of
another digit that claims all these cells can be eliminated. Pattern 3g
claims all three cells, and can be excluded in [15], [31], [48], [56],
[63], [84], [99]. Candidate 3 can be eliminated in [48]

At this point I did not find any further reductions based on vulnerable
cell pairs, triplets or quads. But in the candidate view further

Code: Select all
`+--------------------------+--------------------------+--------------------------+|   4        6        8    | 37       37         2    |   9        1        5    ||   5        9        2    |   1        6        8    |   3        4        7    || 37         1      37     |   5        9        4    |   6        2        8    |+--------------------------+--------------------------+--------------------------+|   2      457        1    |   9      35       356    |   8      567      346    ||   9      57       3567   |   4        8      356    |   1      3567       2    || 36         8      3456   |   2        1        7    | 5          9      346    |+--------------------------+--------------------------+--------------------------+| 67         3      45     | 67       45         1    |   2        8        9    ||   8      457      4567   | 367        2        9    | 47       35         1    ||   1        2        9    |   8      3457     35     | 457      356      36     |+--------------------------+--------------------------+--------------------------+`
surbier
2012 Supporter

Posts: 54
Joined: 06 June 2008

I'll toss in a link to Vidar's POM Solver

I'll continue from Vidar's output which hasn't applied some of your earlier deductions yet, just to bring up a few new simple techniques.

Code: Select all
`   C1      C2   C3    | C4     C5     C6    | C7      C8    C9 -------------------------------------------------------------R1 4       6    8     | 3abcd  3efghi 2     | 9       1     5 R1                    | 7ab    7cdefg       |                      |                     |R2 5       9    2     | 1      6      8     | 3       4     7                       |                     |R3 3abcefg 1    3dhi  | 5      9      4     | 6       2     8 R3 7cde         7abfg |                     |-------------------------------------------------------------R4 2       4ab  1     | 9      3a     3befh | 8       5h    3cdgiR4         5ab        |        5c     5defg |         6de   4c R4         7acf       |               6abc  |         7bdeg 6fg                        |                     |R5 9       5cde 3abe  | 4      8      3cdgi | 1       3fh   2 R5         7bdg 5f    |               5abh  |         5g      R5              6a    |               6defg |         6bc     R5              7e    |                     |         7acf                          |                     |R6 3dhi    8    3cfg  | 2      1      7     | 5       9     3abe    R6 6bdf         4c    |                     |               4abR6              5gh   |                     |               6a  R6              6ceg  |                     |  ------------------------------ ------------------------------R7 6aceg   3    4a    | 6bdf   4bc    1     | 2       8     9 R7 7abfg        5acd  | 7cde   5befgh       |                       |                     |R8 8       4c   4b    | 3efghi 2      9     | 4a      3abcd 1 R8 8       5fgh 5be   | 6aceg               | 7ab     5acd   R8 8       7e   6bdf  | 7fg                 |R8 8            7cd   |                     |                      |                     |R9 1       2    9     | 8      3bcd   3a    | 4bc     3egi  3fh R9                    |        4a     5c    | 5gh     5bef  6bcde  R9                    |        5ad          | 7cdefg  6afg  R9                    |        7ab          |`

The 5 being set in r6c7 means that 5gh must be false.

From here there are a few POM moves that are as simple as vulnerable pairs to use. Note that the rookeries contained within a cell can be used like the endpoints of an AIC or nice loop.

Thus r8c7 means that one of 4a7ab must be true. If you look at r9c5 you can thus eliminate 3bcd and 5ad (which does the same thing as the hidden pair). Also if you look at r45c2 you can see that either r4c2 is 4a7a, or r5c2 is 7b which eliminates 7cf.

After that, a vulnerable pair in 7's for r1c5 & r2c3 will do some solves, as would the pairs and triplets you found, etc. etc. Many of the bivalued cells have simple endpoint type reductions available to them if you look at other cells.

Have fun with it.
Myth Jellies

Posts: 593
Joined: 19 September 2005

I see, it is worthwhile to continue in POM space after having found all possible vulnerable sets.

Myth Jellies wrote:Thus r8c7 means that one of 4a7ab must be true. If you look at r9c5 you can thus eliminate 3bcd and 5ad (which does the same thing as the hidden pair).

This seems to be the simplest application of POM equation analysis, I find it a very nice rule for an easy spotable constellation of pattern overlays. It is convenient when compared to the sometimes longer Boolean substitution algebra.

I could immediately apply this rule to 3a5c in r9c6 or r4c5 to make some reductions in r8c8.

Another example is 1c3cf in r4c9 in the example you gave here.
surbier
2012 Supporter

Posts: 54
Joined: 06 June 2008

Yes, that's another quick hitter. r7c5 or r8c2 force 1d 3be false, while r2c1 forces 3ab false
Myth Jellies

Posts: 593
Joined: 19 September 2005

Hi Myth,

I included the first of your tricks in my solver and for that reason I had to rewrite them more formal:

If all patterns of a cell appear as subset of pattern in another cell,
then the non-common patterns can be deleted.

or

If subsets of pattern of two cells A and B coadd to all patterns of
a third (reference) cell R:

R [ r1 r2 ]
A [ a r1 ]
B [ b r2 ]

(a,b,r1 and r2 are a subset of patterns in a cell) one can get:

r1 = b
r2 = a

because from A: r1 or a; from R: a or b; from B: b or r2

When I coded the first trick, it came up to my mind, that the NOT operator was not used for the deductions, hence your tricks do not make use of the number of patterns en course for a given digit. This has no direct implication but it is easier to handle. As your two tricks differ in the number of cells over which the patterns (of the reference cell) are distributed, I was thinking about three cells:

Suppose the patterns in the reference cell can be divided in three
subsets r1, r2, r3 and there are three cells with patterns
A[a r1], B[b r2], C[c r3].

From R: NOT r1 = r2r3; NOT r2 = r1r3; and NOT r3 = r1r2

From A: NOT r1 = a
From B: NOT r2 = b
From C: NOT r3 = c

hence

Code: Select all
`a = r2r3b = r1r3c = r1r2`

I have used the NOT operator, but it cancels out again, so the number of patterns per digit isn't used here as well. I tried the example above with

R = r8c7 with subsets: r1 = 4a, r2 = 7a, r3 = 7b
and using
r7c3 : 4a or 5acd
r1c7 : 7a or 7b3abcd
r5c2 : 7b or 7dg5cde

I get in a quick manner three equations, which show the principle, but unfortunately they don't lead to any elimination in this particular case:

7ab = 5acd
4a7b = 7b3abcd
4a7a = 7dg5cde

It looks like the right hand side of any of the three equations (r1r2) is always composed by more than one pattern. For the elimination you proposed here, one need (target) cells, in which the non-common pattern subsets (a, b, c) are really one single pattern.
surbier
2012 Supporter

Posts: 54
Joined: 06 June 2008