The New Sudoku Players' Forum

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

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

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

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

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

The New Sudoku Players' Forum

POM: vulnerable triplet cells

POM: vulnerable triplet cells