POM: vulnerable triplet cells

Advanced methods and approaches for solving Sudoku puzzles

POM: vulnerable triplet cells

Postby surbier » Fri Jan 09, 2009 8:22 am

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.
[edit: this statement is wrong, see e.g. link in the thread on collection of advanced methods]
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.....

068000005090108047010004600201900800000400000080207090030001080000029000029800000
with 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 = abcdefghijk
4 = abcd
5 = abcdefgh
6 = abcdefg
7 = 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 |         8
7(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 |         9
7(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 = abcdefgh
4 = bcd
5 = acdefgh
6 = abcdfg
7 = 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
reductions can be made:

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

Postby Myth Jellies » Mon Jan 12, 2009 8:08 pm

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    3cdgi
R4         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    |                     |               4ab
R6              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

Postby surbier » Fri Jan 16, 2009 8:04 am

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

Postby Myth Jellies » Sat Jan 17, 2009 7:22 pm

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

Postby surbier » Thu Jan 22, 2009 3:23 am

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 = r2r3
b = r1r3
c = 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


Return to Advanced solving techniques

cron