Simple example of a POM vulnerable pairs operation

Advanced methods and approaches for solving Sudoku puzzles

Postby Carcul » Wed Jan 25, 2006 5:13 pm

Hi Gsf.

Gsf wrote:...but no one has come up with a method to identify the backdoors besides exhaustive search...


If that method would exist, then I think part of the challenge of solving a Sudoku puzzle would be lost, but this is just a personal opinion.

Gsf wrote:so do any of the cycle/loop/pattern methods identify any of the backdoor pairs for this puzzle?


Regarding the puzzle of Wolfgang, I don´t think so, unless the proof is extremely complicated for a human to find, or unless that proof can be found in an advanced stage of the solving process. Regarding your puzzle above, right now I don't have time but maybe tonight I will analize your puzzle (the grid look very hard, so don't expect great things from me).

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby Myth Jellies » Thu Jan 26, 2006 3:58 am

From a POM perspective, you would think that a cell which had very few patterns in it out of a lot of possibilities would make a good candidate for a magic cell, but, at first glance, I see nothing special in the POM-patterns for the magic cells of wolfgang's puzzle.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Re: Simple example of a POM vulnerable pairs operation

Postby aeb » Mon Jan 30, 2006 5:00 am

Myth Jellies wrote:M. Mepham's "unsolvable" #10 is a nice one for showing off the simplest of POM functions.


The most simple function is to serve as an oracle for what digits can occur what places.
Cf. http://homepages.cwi.nl/~aeb/games/sudoku/solving22.html
Last edited by aeb on Thu Feb 02, 2006 9:15 am, edited 1 time in total.
aeb
 
Posts: 83
Joined: 29 January 2006

Postby Carcul » Tue Jan 31, 2006 7:35 pm

Hi Gsf.

I have now solved the puzzle that you have posted. I have noted that during the solving process, even in an advanced stage of the solving, I was not able to deduce any of the backdoors, with perhaps the exception of r9c5=9 which I could demonstrate only when this cell was a bivalue in "8,9", and even then the demonstration was very complex. However, I did not use this demonstration in my solution. It appears to me that, in these very difficult puzzles, finding backdoors by hand is almost impossible.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby ronk » Mon Feb 06, 2006 5:00 am

Myth Jellies wrote:If A <> n implies that B = n; then A & B are a vulnerable pair. You can eliminate all potential patterns for n which are not in either A or B. Note that you can use this rule with almost unique rectangles of the form

Code: Select all
ab  | abn
    |
abn | ab

to kill all potential patterns of n that are not part of this structure.

Would you please give an example of potential patterns that may be killed?

TIA, Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Tue Feb 07, 2006 6:35 am

ronk wrote:Would you please give an example of potential patterns that may be killed?


ronk,

This one should be familiar to you, you presented it at the end of an AUR thread. If you run your grid...
Code: Select all
 2    47   5    | 8    19   6    | 3    14   79
 134  9    134  |^234  7   ^24   | 8    5    6
 8    347  6    | 34   5    19   | 2    14   79
----------------+----------------+---------------
 147  145  2    | 57   39   349  | 6    8    13
 9    8    14   |^24   6   ^234  | 5    7    13
 367  356  37   | 1    8    57   | 9    2    4
----------------+----------------+---------------
 137  2    137  | 6    13   8    | 4    9    5
 5    13   8    | 9    4    13   | 7    6    2
 46   46   9    | 57   2    57   | 1    3    8

...through Vidar's program you get...
Code: Select all
2   | 4a   | 5    | 8      | 1ab  | 6    | 3| 1cd  | 7def   
    | 7abc |      |        | 9a   |      |  | 4bcde| 9b 
----+------+------+--------+------+------+--+------+--------
1ac | 9    | 1bd  | 2a     | 7    | 2b   | 8| 5    | 6
3abc|      | 3def |*3gh    |      | 4--  |  |      |         
4b  |      | 4cd  | 4ae    |      |      |  |      |         
----+------+------+--------+------+------+--+------+--------
8   | 3gh  | 6    | 3abcdef| 5    | 1cd  | 2| 1ab  | 7abc
    | 4e   |      | 4bcd   |      | 9b   |  | 4a   | 9a 
    | 7def |      |        |      |      |  |      |     
----+------+------+--------+------+------+--+------+--------
1d  | 1ab  | 2    | 5b     | 3adgh| 3be  | 6| 8    | 1c
4c  | 4d   |      | 7bcef  | 9b   | 4abe |  |      | 3cf 
7ad | 5a   |      |        |      | 9a   |  |      |         
----+------+------+--------+------+------+--+------+--------
9   | 8    | 1c   | 2b     | 6    | 2a   | 5| 7    | 1abd
    |      | 4abe | 4--    |      |*3cf  |  |      | 3abdegh 
    |      |      |        |      | 4cd  |  |      |       
----+------+------+--------+------+------+--+------+--------
3efg| 3ad  | 3bch | 1      | 8    | 5a   | 9| 2    | 4
6a  | 5b   | 7cf  |        |      | 7ad  |  |      |         
7be | 6b   |      |        |      |      |  |      |         
----+------+------+--------+------+------+--+------+--------
1b  | 2    | 1a   | 6      | 1cd  | 8    | 4| 9    | 5       
3dh |      | 3ag  |        | 3bcef|      |  |      |         
7cf |      | 7abde|        |      |      |  |      |         
----+------+------+--------+------+------+--+------+--------
5   | 1cd  | 8    | 9      | 4    | 1ab  | 7| 6    | 2               
    | 3bcef|      |        |      | 3adgh|  |      |         
----+------+------+--------+------+------+--+------+--------
4ade| 4bc  | 9    | 5a     | 2    | 5b   | 1| 3    | 8       
6b  | 6a   |      | 7ad    |      | 7bcef|  |      |         

It is a little less than stellar example, because the program eliminates the 4's in your grid. However, we know that you can't really destroy a unique rectangle--the reductions remain for all time, so they still apply. Therefore, we know that the only valid patterns for 3 are those that show up in r2c4 or r5c6. Thus we can eliminate 3abde. The correct pattern turns out to be 3c.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Tue Feb 07, 2006 3:40 pm

Myth Jellies wrote:Therefore, we know that the only valid patterns for 3 are those that show up in r2c4 or r5c6. Thus we can eliminate 3abde. The correct pattern turns out to be 3c.

Great answer, and the scary part is I understand.:) Next I need to learn how POM patterns are generated.

Thanks, Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Thu Feb 09, 2006 7:15 am

There is an even better POM reduction you can do with a more general type 5 uniqueness case

If you have the following scenario...
Code: Select all
 ab  | abX
 abY | ab

...where X and Y can be multiple digits. You can eliminate any 'a' and 'b' patterns which are common to the abX-cell and the abY-cell. Thus you could eliminate 2a in the grid above, which would be more sigificant if we hadn't already basically solved for 2b...oh well.:)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Re: Simple example of a POM vulnerable pairs operation

Postby ronk » Tue Feb 28, 2006 8:06 pm

Myth Jellies wrote:Since the 5's and the 7's appear exactly twice in each box, we know there can't be more than 2 potential solution patterns for each of them. They are the same patterns that you would get from simple coloring. So labeling them 'A' and 'B' for each, we get the following.

Code: Select all
 6    18     4    | 3    5    2   | 9     7    18   
 5B9  189    2    | 4    7    18  | 5A8   3    6   
 3    7      5A8  | 6    9    18  | 4     15B  2   
------------------+---------------+-----------------
 4    2      9    | 5    3    6   | 1     8    7   
 7    5      1    | 2    8    4   | 3     6    9   
 8    6      3    | 7    1    9   | 2     45A  45B 
------------------+---------------+-----------------
 2    4      7A8  | 1    6    5A7B| 5B8   9    3   
 1    389    5B7B8| 89   4    37A | 6     2    5A8   
 5A9  389    6    | 89   2    35B | 7     14   14   


A pair of cells which contain all of the potential patterns for a number, I call a vulnerable pair. You can note by inspection that in r8c3 and r7c6, the 7B pattern occupies cells containing both of 5's patterns. This means that if 7B were true, then 5's could not possibly have a valid pattern. Thus we can eliminate 7B, which basicly solves the puzzle.

This deduction can be expressed: Given that 7B (true) excludes 5A (true) and 5B excludes 7B then, since either 5A or 5B must be true, 7B must be false.

(Since I have a tough time following conjugate parity when the letters are 'A' and 'B' instead of 'A' and 'a' -- at least for multiple conjugate chains -- I'll use upper and lower case.)

Then the equivalent statement for the above is: Given that 7a (true) excludes 5A (true) and 5a excludes 7a then, since either 5A or 5a must be true, 7a must be false.

This can obviously be extended to three (and more) conjugate chains. For example, for 3 chains we might have:

Given that 1A excludes 2a, 2A excludes 3a, and 3A excludes 1A ... then 1A must be false. Would you consider this scenario "vulnerable pairs" also?

TIA, Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Simple example of a POM vulnerable pairs operation

Postby Myth Jellies » Tue Feb 28, 2006 10:17 pm

ronk wrote:Then the equivalent statement for the above is: Given that 7a (true) excludes 5A (true) and 5a excludes 7a then, since either 5A or 5a must be true, 7a must be false.

This can obviously be extended to three (and more) conjugate chains. For example, for 3 chains we might have:

Given that 1A excludes 2a, 2A excludes 3a, and 3A excludes 1A ... then 1A must be false. Would you consider this scenario "vulnerable pairs" also?


Your technique and deduction are certainly valid. I think a more descriptive term for your construction might be a vulnerable pair chain rather than just a vulnerable pair, though I would keep an open mind to changing my opinion once I see a concrete example of your execution.

You appear to be poised to make a great connection between POM vulnerable pairs and more complex examples of either multi-digit coloring or forcing chains.:)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Re: Simple example of a POM vulnerable pairs operation

Postby ronk » Wed Mar 01, 2006 6:51 pm

Myth Jellies wrote:I think a more descriptive term for your construction might be a vulnerable pair chain rather than just a vulnerable pair, though I would keep an open mind to changing my opinion once I see a concrete example of your execution.

Here is a concrete example using #651 of the top1465. With basic techniques (and a more complex version of this "vulnerable pair chain" technique addressed below), the puzzle can be advanced to:
Code: Select all
 4    689  5    | 7    2    3    | 1    69   689
 1    2369 79   | 46   8    45   | 5679 234  2469
 27   2368 68   | 1    456  9    | 5678 234  24678
----------------+----------------+-----------------
 3    5    2    | 469  1469 14   | 68   7    468
 9    7    146  | 8    46   2    | 3    14   5
 8    46   146  | 35   37   57   | 69   124  2469
----------------+----------------+-----------------
 257  29   79   | 35   37   6    | 4    8    1
 567  1    3    | 49   459  8    | 2    69   679
 67   48   48   | 2    19   17   | 679  5    3

Illustrating only the coloring of 2s, 5s, and 7s affecting the deduction, we have:
Code: Select all
 .    .    .   | .   .   .   | .    .    . 
 .    .    7A  | .   .   5A  | 5a7a .    .   
 2b7a .    .   | .   .   .   | .    .    .   
---------------+-------------+---------------
 .    .    .   | .   .   .   | .    .    . 
 .    .    .   | .   .   .   | .    .    .
 .    .    .   | 5A  .   5a  | .    .    .   
---------------+-------------+---------------
 2B5A .    .   | 5a  .   .   | .    .    .
 .    .    .   | .   .   .   | .    .    . 
 .    .    .   | .   .   .   | .    .    . 

In r2c7, (color) 7a (true) excludes 5a (true); in r7c1, 5A excludes 2B; and in r3c1, 2b excludes 7a. Using "!" to indicate "exclude", we have the chain: 7a!5a, 5A!2B, and 2b!7a. Therefore, all 7a's (candidate 7s colored 'a') must be false.

The nice loop expression for this deduction is:
r3c1-7-r2c3=7=r2c7=5=r2c6-5-r6c6=5=r6c4-5-r7c4=5=r7c1=2=r3c1 implying r3c1<>7


Now let's begin again with the starting grid.
Code: Select all
 4..|723|1..
 1..|.8.|...
 ...|..9|...
 ---+---+---
 .52|...|.7.
 .7.|...|3.5
 8..|...|...
 ---+---+---
 ...|..6|48.
 .13|...|2..
 ...|2..|.53

After "basic techniques" and a Unique Rectangle (35) in r67c5, the first sticking point is ...
Code: Select all
 4    689   5    | 7     2     3   | 1     69   689
 1    2369  679  | 46    8     45  | 5679  234  24679
 27   2368  678  | 146   1456  9   | 5678  234  24678
-----------------+-----------------+-----------------
 3    5     2    | 1469  1469  14  | 68    7    468
 9    7     146  | 8     46    2   | 3     14   5
 8    46    146  | 35    37    57  | 69    124  2469
-----------------+-----------------+-----------------
 257  29    79   | 35    37    6   | 4     8    1
 567  1     3    | 49    459   8   | 2     69   679
 67   48    48   | 2     19    17  | 679   5    3

 Illustrating only the 1s, 4s, 5s and 9s affecting the deduction   
   .    .   . |     .      .    . |    .   .     .
   .    .   . |     .      .   5A |    .   .     .
   .    .   . |     1A   1a5a   . |    .   .     .
 -------------+-------------------+----------------
   .    .   . |   1a9A     .    . |    .   .     .
   .    .   . |     .      .    . |    .   .     .
   .    .   . |     5A     .   5a |    .   .     .
 -------------+-------------------+----------------
   .    .   . |     5a     .    . |    .   .     .
   .    .   . |   4b9a   4B5A   . |    .   .     .
   .    .   . |     .      .    . |    .   .     . 

Using the same notation as above, we have the exclusion chain: 1a!5a, 5A!4B, 4b!9a and 9A!1a, therefore 1a is false.

The nice loop expression for this deduction is:
r4c4-1-r3c4=1=r3c5=5=r2c6-5-r6c6=5=r6c4-5-r7c4=5=r8c5=4=r8c4=9=r4c4 implying r4c4<>1


Myth Jellies wrote:You appear to be poised to make a great connection between POM vulnerable pairs and more complex examples of either multi-digit coloring or forcing chains.:)

I disagree with the "great", but flowers are always appreciated:) . I really do like coloring as a technique and am using this as a stepping stone to "advanced coloring" or "supercoloring" or whatever the proper name is.

I don't think I totally understand the basic principles behind POM. The link here doesn't appear to lead to any of the earliest posts (likely yours), so I would appreciate your pointing to some of them.

[edit: simplified coloring grids and shortened loops]

TIA, Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ronk » Wed Jul 05, 2006 7:56 pm

Vidar's POM Solver

Vidar, have you withdrawn your on-line solver ... or is there a new link?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby vidarino » Thu Jul 06, 2006 5:33 pm

ronk wrote:Vidar's POM Solver

Vidar, have you withdrawn your on-line solver ... or is there a new link?


Oops. I redesigned my site some time ago, and forgot to copy the sudoku directory to the new location. Fixed.:)
vidarino
 
Posts: 295
Joined: 02 January 2006

Re: Simple example of a POM vulnerable pairs operation

Postby StrmCkr » Thu Jan 04, 2018 3:47 am

https://web.archive.org/web/20060215091649/http://www.sudoku.org.uk/discus/messages/2/323.html?1131920808


a bit of necroposting, as i cannot find much information on "template" or pattern overlay method.
Code: Select all
for the missing links the wayback machine is still applicable for the post


Let me preface this presentation by stating that using POM on a
super-extreme puzzle such as this is an exercise of mental
masochism. And an unfortunate problem with the Pattern Overlay
Method in its current stage of development is that there really
is no decent shorthand or graphical or computer assisted means
of presenting the solution like you have with forcing chains or
colors. You just have to grit down and present each logical
step, hopefully, as clearly as possible.

I have enumerated most of the steps for easy reference, and
color-coded some of the equations so that the more difficult
pattern eliminations can be made more apparent. I have also put
extra descriptions in the steps so that this thread can be used
as an advanced POM tutorial of sorts.

I believe this puzzle was one of Tso's Killer Sudoku in another
forum. I can't find that thread, but here is the puzzle.

. . . 1 . . 7 . .
. 2 . 6 9 . . . .
9 . . . . 3 . 8 2
. . . . . . 4 6 .
6 4 . . . . . 5 7
. 5 8 . . . . . .
2 1 . 8 . . . . 9
. . . . 1 6 . 7 .
. . 4 . . 2 . . .


Simple Sudoku reduces this to

3458 368 356 1 2 58 7 9 3456
134578 2 1357 6 9 578 135 134 1345
9 67 1567 457 457 3 156 8 2
137 379 12379 2357 3578 1579 4 6 138
6 4 1239 23 38 19 1389 5 7
137 5 8 347 6 1479 139 2 13
2 1 3567 8 3457 457 356 34 9
358 389 359 3459 1 6 2 7 3458
3578 36789 4 3579 357 2 13568 13 13568


The pattern overlay method (POM) merge grid is an overlay of all
of the possible solution patterns for each number. For example,
let's take the easiest number for our puzzle, the twos. There
are only two possible solution patterns for the twos, 2a and 2b,
represented by the a and b on the grid below.

X X X X 2 X X X X
X 2 X X X X X X X
X X X X X X X X 2
X X a b X X X X X
X X b a X X X X X
X X X X X X X 2 X
2 X X X X X X X X
X X X X X X 2 X X
X X X X X 2 X X X


A slightly more complex example are the four patterns
(a, b, c, and d) which are possible solution patterns for the
digit, four, shown below

bcd X X X X X X X a
a X X X X X X cd b
X X X c abd X X X X
X X X X X X 4 X X
X 4 X X X X X X X
X X X d X abc X X X
X X X X c d X ab X
X X X ab X X X X cd
X X 4 X X X X X X


Now if you find the possible solution patterns for every digit,
and then merge the patterns together into a single grid, you get
the complete POM merge grid. Here is my version of the complete
merge grid for this puzzle.

4bcd 8cdi
3[DabcEabcFdefijkIabcJdefijkKaLadeMabPabcQdefijkRa SadeTabVabcWaXaZdefijk@ade#ade%abc&ab?ab]
5[EaFbcHaIbcLaMacNaQbcR*Sbc] 6c 8abg
3[AabcdeBabcCcdeijkGabcHcdeijkKbcLbcfghMcdeNabcOcd eijkRbcSbcfghTcdeUabcWbcXbcYcdeijk@bcfgh#bcfgh$abc de&cde?cde] 6---
3[AfgBdCfghDdefEdeFghlmnGdHfghIdeJghlmnNdOfghQghlm nPdeUdVdeYfghZghlmn$fg%def]
5[AcdB*CcDcGcJcKacOcdP*] 1 2 8efh
5[AabCaDaFaGaIaJaOabQaSa] 7 9 4a 6ab
3[CabFabcopqHabJabcopqLijOabQabcopqSijYabZabcopq@i j#ij]
5[CbdDbdEbGbdHbJbdKbdLbMbdNb]
1abc 4a 7efkl 8efh
3[FopqJopqLijQopqSijZopq@ij#ij]
5[EbFaHbIaLbMbdNbQaSa] 2 1de 7cdghoqr
3[CabFabcHabJabcOabQabcYabZabc]
5[AbCdDdGdJdKbdOb] 6 9 7abijmnp 8abcdgi
5[AcCbDbFbGbIbJbOcQbSb] 1fg
3[CcdefFdefghHcdefJdefghLabcOcdefQdefghSabcYcdefZd efgh@abc#abc]
5[AadB*FcIcOadP*QcR*Sc] 1hijkl 4cd
3[A*B*D*E*G*I*K*M*N*P*R*T*U*V*W*X*$*%*&*?*] 1mno 4b
3[CghijkFijklmnHghijkJijklmnLdefghOghijkQijklmnSde fghYghijkZijklmn@defgh#defgh]
5[CacDacEaGacHaJacKacLaMacNa]
9 6b 7ajnp 1fghijklmno 6a 7bim
5[AaCabDabGabJabOa] 4c 7cegkqr
5[AdBbGcdH*IcJcdKcdL*McdOdPbQcRb] 4abd 7dfhlo
5[BaCcdDcdE*FcKabMabN*PaRaSc] 3 1abcde 6c
5[AbcFabIabObcQabSab] 8 2
1egiklno 7abcd
3[DdeEdFabglmIdJabglmKbLbfgMcdPdQabglmRbSbfgTcdVdW bXbZabglm@bfg#bfg%de&cd?cd] 7efghi 9ch
3[AfgBdCabfghGdHabfghKaLadeijMabNdOabfghRaSadeijTa bUdWaXaYabfgh@adeij#adeij$fg&ab?ab] 1a 2a 7jkl 9defg
3[AabBaCcijDabEaFdijopGaHcijIaJdijopNaOcijPaQdijop UaVaYcijZdijop$ab%ab] 2b 7mno
3[AcdDcfNbOdkPbQceknqShTeUbVbYdkZceknq@h$cd%cf&e]
5[AabcBaGabIabJabKabMabOabcPaQabRa] 7pq 8bdfghi
3[BbCdkEbFceknqGbHdkIbJceknqLhMe#h?e]
5[BbCabDabFabKcdMcdPbRbSab] 1cjm 7r 9ab
5[AdCcdDcdE*FcGcdH*IcJcdL*N*OdQcSc] 4 6 1bdfh 8ace
3[BcCeEceFfhGcHeIceJfhKcLcNcOePceQfhRcScUcVceWcXcY eZfh@c#c]
6 4 1bc 2b 9ab
3[AcdeBbcCdekDcEbcFefkqGbcHdekIbcJefkqNbcOdekqPbcQ efkqUbcVbcYdekZefkq$cde%c] 2a
3[AafDadNadOacfgiPadeQadghiloRabcSabcdfiTacUadVade WabcYacfgiZadghilo@abcdfi$af%ad&ac] 8ace
3[BadCacfgiEadeFadghiloGadHacfgiIadeJadghiloKabcLa bcdfiMacXabc#abcdfi?ac] 1adefghilo 9cde 1jkmn 8bdfghi 9fgh
3[AbcegCbhjDbefFbcjmnpHbhjJbcjmnpLeghjMbdeObhjQbcj mnpSeghjTbdeYbhjZbcjmnp@eghj#eghj$bceg%bef&bde?bde ] 5 7
1dfhjm 7mnopqr
3[DfEeFchnIeJchnKcLchMePeQchnRcSchTeVeWcXcZchn@ch# ch%f&e?e] 5 8 4d 7abdhijl
3[AbegDbeNcObehjPcQbfjmpSegjTbdUcVcYbehjZbfjmp@egj $beg%be&bd] 6abc
3[BcCbehjEcFbfjmpGcHbehjIcJbfjmpLegjMbd#egj?bd] 1bkn 4abc 7cefgk 9fgh 1lo 9abcde
3[AadfCagikDacdFaikloqHagikJaikloqLdfiMacOagikQaik loqSdfiTacYagikZaikloq@dfi#dfi$adf%acd&ac?ac] 2 1acegi
3[BabdCcdfEabdFdegGabdHcdfIabdJdegKabLabNabdOcdfPa bdQdegRabSabUabdVabdWabXabYcdfZdeg@ab#ab]
2 1 6bc 7aefnp
3[M*T*X*#*?*]
5[F*I*N*S*] 8 4c 7bcgijkmr
3[A*D*U*V*W*Y*Z*@*$*%*&*]
5[A*J*L*O*Q*] 4d 7dhloq
5[B*K*M*P*R*] 6a
3[B*E*G*I*K*N*P*R*]
5[C*D*E*G*H*] 4ab
3[C*F*H*J*L*O*Q*S*] 9
8ab
3[G*H*N*O*U*Y*$*]
5[D*G*J*K*O*P*] 8cdef 9aeg
3[I*J*P*Q*V*Z*%*] 9ch
3[K*L*R*S*W*@*&*]
5[E*H*L*M*Q*R*] 4ab 9bdf
3[B*C*E*F*X*#*?*]
5[C*N*S*] 1 6 2 7 4cd 8ghi
3[A*D*M*T*]
5[A*B*F*I*]
7ghij 8g
3[A*B*C*]
5[A*B*C*] 6a 7bcdklmoqr 8hi 9bdf
3[D*E*F*] 4 7fp 9acegh
3[G*H*I*J*K*L*M*]
5[D*E*F*] 7aen
3[N*O*P*Q*R*S*T*]
5[G*H*I*] 2 1hi 6b 8ace
3[U*V*W*X*]
5[J*K*L*M*N*] 1abcdefgmno
3[Y*Z*@*#*] 1jkl 6c 8bdf
3[$*%*&*?*]
5[O*P*Q*R*S*]


Now, there are several things to note about this merge grid.
First and foremost, the solution patterns for the threes and the
fives are a complete nightmare. There were so many of them that
I had to adopt a two-character (uppercase-lowercase) representation
for each solution pattern of the threes and fives. I generated
my solution patterns for threes and fives by associating the
capital letter/symbol to unique solutions for the bottom third
of the puzzle, and then using the lowercase letter to further
differentiate solutions using the remainder of the puzzle.
Unfortunately, in the case of the threes, I ran out of capital
letters and had to make use of some other symbols ('@', '#', '$',
'%', '&', and '?'). I used the following shorthand. '4abc'
represents three of the solution patterns for the fours, 4a, 4b,
and 4c. '3[CabGbJi]' or '3CabGbJi' represents four of the solution
patterns for threes, '3Ca', '3Cb', '3Gb', and '3Ji'. For threes
and fives, the final character may be a wildcard asterisk. '5A*'
represents all of the remaining solution patterns for fives that
start with '5A'. Thus, at the beginning of the puzzle, '5A*B*'
equals '5Aa', '5Ab', '5Ac', '5Ad', '5Ba', and '5Bb'.

The second thing to note about the merge grid is that I messed up
when I was determining the solution patterns for the threes by
including cell r6c5 as a possible candidate cell for threes when
it was already solved for a six. To show that it solves for a
six I put all of six's solution patterns in that cell as well.
This is not really too much of a mistake since I can just kill
all of three's patterns in that cell when I solve it for six. I
decided to include this mistake in my merge grid so that people
would not have to deal with letter gaps in any list of solution
patterns for threes, and I did not want to have to get rid of the
letter gaps by regenerating all of my 200+ solution patterns for
threes from scratch.

The final thing to note about the merge grid is that no solution
pattern for the sixes could make use of candidate cell r1c3. If
we isolate on the six's solution patterns, it should be pretty
apparent that any selection in block 9 either results in a
selection of r7c3, and/or it results in the selection of
r1c9, either of which precludes selection of r1c3.

X c -- X X X X X ab
X X X 6 X X X X X
X b a X X X c X X
X X X X X X X 6 X
6 X X X X X X X X
X X X X 6 X X X X
X X bc X X X a X X
X X X X X 6 X X X
X a X X X X b X c


Now, on to the steps to the solution. Along the way, I will try
to illuminate and explain some of the POM terminology so that
this thread may be used as sort of an advanced POM tutorial.

1. Eliminate candidate 6 from r1c3 because cell contains no
valid pattern for sixes.

2. r6c5 already solved for 6; kills 3BcCbehjEcFbfjmpGcHbehjIcJbfjmpLegjMbd#egj?bd

3. Now we come to the concept of vulnerable cell pairs.
Consider the solution patterns for sixes above. The general
pattern exclusion rule states that if a pattern prevents
another number from having a valid solution pattern then that
pattern is invalid. Look at cells r1c9 and r7c3. Taken together,
they contain all of the possible solution patterns for the digit
six. Thus, any non-six pattern which occupies both of these
cells would, if it were true, kill all of the valid six patterns.
Since that cannot be, those non-six patterns occupying both r1c9
and r7c3 must be invalid. These cells which contain all of six's
patterns are called vulnerable pairs for the number 6 and are
abbreviated v.p.6 - r1c9 & r7c3. The following vulnerable pairs
killed patterns.

vp4 - r1c1 & r3c5 Þ kills 5(EaFcMaNaRaSc)
vp4 - r1c1 & r7c8 Þ kills 3(FdeikJdeikLadQdefijkSade)
vp4 - r1c1 & r8c4 Þ kills 3(EabXa#ad?a) 5Sb
vp4 - r2c8 & r6c6 Þ kills 1k
vp4 - r2c8 & r8c4 Þ kills 3(B*E*X*?*)
vp4 - r3c5 & r6c6 Þ kills 7f
vp4 - r3c5 & r8c9 Þ kills 5Ba
vp6 - r1c9 & r7c3 Þ kills 3(#i) 5(Nb)
vp8 - r4c5 & r9c7 Þ kills 5(KcdMcd)

4. The pattern exclusion rule also applies to implied patterns.
The way we get implied patterns is through pattern equations.
Any cell may be used as the basis of one pattern equation for
every candidate digit in the cell. The way you get equations is

NOT the patterns for one digit in the cell EQUALS all the remaining patterns in the cell.

Thus, for cell r3c2 we would get the following two equations,
6(NOT b) = 6(ac) = 7(ajnp) and
7(NOT ajnp) = 7(bcdefghiklmoqr) = 6b

You can then use these equations to substitute one set of
patterns for another anywhere else in the grid. When you make
one of these substitutions, one of the most common ways that the
exclusion rule manifests itself is through the duplication of
patterns after the substitution. Thus

r5c5 Þ 8ace = (all the 3 patterns not in r5c5); substitute into
r9c7 duplicates and kills 3(U*V*W*) and kills candidate 3 in r9c7.

5. r5c5 Þ 8ace = (all the 3 patterns not in r5c5); substitute into
r9c7 duplicates and kills 3(NcOePceQhRcScYeZfh@c).

6. r5c4 Þ 2a = (3-patterns not in r5c4) Þ r4c3 kills
3(AbCciDbFoGaHciIaJoOjQpYjZjp$b%b)

7. r7c8 Þ 4(ab) = 3(A*B*D*E*I*K*M*N*P*R*T*X*Y*Z*@*#*$*%*&*) Þ
r8c4 kills 3(#*)

8. r3c2 Þ 6b = 7(bcdeghiklmoqr); Þ r7c3 kills 7e

9. r3c2 Þ 7(ajnp) = 6(ac); Þ r2c6 Þ
equation 1: 6b = 7(bim) 8(abcdgi) 5(AcCbDbFbGbIbJbOcQb);

10. Equation 1 Þ r7c3 kills 5(FbIb)

11. Equation 1 Þ r9c7 kills 5(Jb) 8(ac)

12. Equation 1 Þ r1c9 kills 5(CbDbGb)

13. Note that the elimination of 8(ac) has openned up several
more vulnerable pair cells for the 8:
vp8 - r4c5 & r2c1 Þ kills 3(FqJq) 5(FaSa)
vp8 - r4c5 & r1c6 Þ kills 5(CaDa)
vp8 - r4c5 & r8c2 Þ kills 3(IbJcn)
vp8 - r5c7 & r2c1 Þ kills 3(Sj@j)
vp8 - r5c7 & r8c2 Þ kills 3(QbcmnZbcmn%ef) 9g

14. r5c5 Þ 8e = (3-patterns not in r5c5) Þ r2c1 kills 3(QoqSiZoq@i)

15. r5c5 Þ 8e = (3-patterns not in r5c5) Þ r8c2 kills 3(P*Q*Z*%*)

Equation 2: 8e = 3(A*CdkD*FcnGbHdkLhMeN*O*R*S*T*Y*@*$*&*);
Equation 3: 8(bdfghi) = 3(CafgFaghlGdHafgI*J*K*LbcfiMac);

16. Pattern elimination via multiple conversion equations.
Sometimes having multiple substitution equations between two
numbers may reslt in the elimination of patterns on either side
of the equals sign. I'll use color coding to help illustrate
this. For example:
r9c8 Þ 1(hijl) = 3(Y*@*); 1(abcdefgmno) = 3(not Y*@*);
r6c9 Þ 1(bdfhjlmno) = 3(CdfFgGbdHdfIdJgKabLbNabdOcdfRabSbYcdf@ab)
hence,
1(hjl) = 3(Ycdf@ab)
1(i) = 3(Yabghik@defgh)
1(bdfmno) = 3(CdfFgGbdHdfIdJgKabLbNabdOcdfRabSb)
additionally,
Equation 2 Þ r4c9 Þ 1(bdfh) = 3(CafgFaglGdHafgIdJaglKabLbfiMac)
kills 1h because no red terms on opposite side of equation.
kills 3(CagFalHagJalLfiMac) because no blue terms opposite.
kills candidate 3 in r2c1.
Leaves,
Equation 4: 1(bdf) = 3(CfFgGdHfIdJgKabLb);
Equation 5: 1(mno) = 3(CdGbHdN*OcdfR*Sb);
Equation 6: 1(aceg) = 3(A*CkD*FchnHkIeJhKcLchM*OabghikSfghT*$*&*);
Equation 7: 1(jl) = 3(Ycdf@ab);
Equation 8: 1i = 3(Yabghik@defgh);

17. r9c7 & Equation 3 & Equation 8 Þ
8(bdfghi) = 3(CfFghGdHfIdeJghKabcLbc) = 3(Yabghik@defgh) 6b 5(J*K*L*M*N*);
Left side of equation is missing any potential orange patterns
which kills 3(Yabghik@defgh), 1i, and candidate 1 from r9c7.

18. Sometimes you can come up with an equation which can only
be partially converted on both sides of the equals sign. This
often leads to an inequality where you can only say that a given
set of patterns either contains another set, or is a subset of
another set of patterns. If X is a subset of Y, I usually write
that out as either X £ Y or Y ³ X. The following shows how
these subset relationships can come about:
r4c1 & Equation 4 Þ 1(acjm)1(bdf) =
1(acjm) 3(CfFgGdHfIdJgKabLb) = 7(abcd) 3(DdeFgIdJgKbLbRbSbfgTcd@b&cd)
Now 7(abcd) might contain some blue, red, and green terms as
well as some cyan patterns. We just can't tell from this equation.
However, we still can get some useful information. We know that,
7(abcd) ³ 3(CfGdHfKa)
1j ³ 3(@b)
1m ³ 3(RbSb)
1(ac) ³ 3(DdeSfgTcd&cd)
Applying the last, blue inequality along with Equation 2 to r2c1
kills 3(DdeSfgTcd&cd).

19. r7c8 Þ
Equation 9: 4(cd) = 3(C*F*H*J*L*O*S*);
Equation 10: 4(ab) = 3(A*D*G*I*K*M*N*R*T*Y*@*$*&*);

20. r5c7 Þ 1(abcdefglo) = 9(fh) 8(bdfghi) 3(AcegDfFcnLhM*ObhShTbe$ceg&be);
applying equations 3, 4, and 6 changes this to,
1(lo) 3(A*CfkD*F*GdHfkI*J*K*L*M*OabghikS*T*$*&*) =
9(fh) 3(AcegCfDfF*GdHfI*J*K*L*M*ObhShTbe$ceg&be);
getting rid of common patterns on both sides of the equation leaves,
9(fh) = 1(lo) 3(AadfCkDacHkOagikSbTa$adf&a); applying this
equation plus equation 10 to r6c6 kills 3(AadfDacTa$adf&a).

21. r8c4 and Equation 10 Þ
9(acegh) = 3(C*F*) 3(A*D*G*I*K*M*N*R*T*Y*@*$*&*); Þ r9c4;
kills 3(G*I*K*M*)

22. r1c6 Þ
Equation 11: 8(bdgi) = 5(AabGaIaJaOabQa);
Equation 12: 8(efh) = 5(AcdB*C*D*E*GcdH*IcJcdK*L*M*OcdP*QbcR*);
r2c1 and Equation 12 kills 5(EbHbLbMb)

23. r2c6 and equation 11 Þ
Equation 13: 7(cdghkloqr) = 5(AabcGaIaJaOabcQab);
Equation 14: 7(abijmnp) = 5(AdB*C*D*GcdH*IcJcdK*L*OdP*QcR*);
note that 8(efh) = 7(abijmnp) 5(AcOcQb);

24. r3c5 and then equation 14 Þ
4(abd) 5(C*D*K*Pa) = 7(cgkqr) 7(abijmnp) same as
4(abd) 5(C*D*K*Pa) = 7(cgkqr) 5(AdB*C*D*GcdH*IcJcdK*L*OdPabQcR*);
thus
Equation 15: 4(abd) = 7(cgkqr) 5(AdB*GcdH*IcJcdL*OdPbQcR*);

25. r7c6 and then equation 14 Þ
4d 5(B*K*P*R*) = 7(cgkr) 7(abijmnp) same as
4d 5(B*K*P*R*) = 7(cgkr) 5(AdB*C*D*GcdH*IcJcdK*L*OdP*QcR*);
Equation 16: 4d = 7(cgkr) 5(AdC*D*GcdH*IcJcdL*OdQc);
Comparing above equation to equation 15 kills 5(C*D*); kills
candidate 5's in r9c4 and r8c4;

26. Equation 16 Þ r1c1 kills 5(HaLa)

27. Equation 12 and r2c1 =>
4(bcd) = 1(abc) 7(kl) 5(AcdB*GcdI*JcdK*OcdP*Q*R*) => r1c1
kills 5(IcQbcR*); kills candidate 5 in r1c1;

28. r3c3 Þ 1(abcde) = 6a 7(bim) 5(AaGaJaOa); Þ r3c7
contains 6(ac) 7(bim) 5(AabcGaI*JaOabcQ*);

temporary new vp6 - r3c7 & r9c7 Þ kills 5(Ja);
temporary new vp6 - r3c7 & r7c3 Þ kills 5(I*); kills
candidate 5 in r7c3;

29. r3c5 Þ 4c = 7(dhlo) 5(K*Pa);
Equation 15 is now 4d = 7(cgkr) 5(AdGcdJcdOd);
Equation 17: 4(cd) = 7(cdghklor) 5(AdGcdJcdK*OdPa);

30. Equation 17 => r8c9 kills 5(Ad) Þ
7(abijmnp) 7q = 8(ghi) 3(A*D*T*) 5(A*B*GcdJ*K*OdPa);
apply updated Equation 14 and get
7q 5(B*GcdJ*K*OdPab) = 8(ghi) 3(A*D*T*) 5(A*B*GcdJ*K*OdPa);
Thus 7q 5(Pb) = 8(ghi) 3(A*D*T*) 5(A*)
Hence 7q ³ 5(A*) Þ r2c3 kills 5(Ab);

31. r7c3 Þ 6a = 7(anp) 3(T*) Þ r9c2 Þ
9(aceh) = 7(abcdklmnopqr) 3(D*F*T*) 8(hi) Þ r9c4 which
kills 7p and candidate 7 from r9c4.

32. r9c4 Þ 9(bdf) = 3(H*J*L*); Þ r8c4 Þ
4(ab) = 3(A*D*N*O*R*S*T*Y*@*$*&*) Þ r7c8 kills 3(O*S*)

Updating some previous equations:
Equation 2: 8e = 3(A*CdkD*FcnHdkLhN*R*T*Y*@*$*&*);
Equation 3: 8(bdfghi) = 3(CfFghHfJ*Lbc);
Equation 9: 4(cd) = 3(C*F*H*J*L*);
Equation 10: 4(ab) = 3(A*D*N*R*T*Y*@*$*&*);
Equation 18: 9(bdf) = 3(H*J*L*);
Equation 19: 9(aceh) = 3(A*C*D*F*N*R*T*Y*@*$*&*);
Equation 4: 1(bdf) = 3(CfFgHdfJgLb);
Equation 5: 1(mno) = 3(CdHdN*R*);
Equation 6: 1(aceg) = 3(A*CkD*FchHkJhLchT*$*&*);
Equation 7: 1(jl) = 3(Y*@*);

33. Equation 9 Þ r8c9 leaves 8(ghi) 3(C*F*H*J*L*) 3(A*D*T*) 5(A*B*);
from equation 3 we can see that 8(ghi) £ 3(C*F*H*J*L*),
thus whatever 8(ghi) is, it will be duplicated in the cell.
Hence 8(ghi) is invalidated, killing candidate 8's in r8c9, r9c1,
and r9c2.

34. r8c9 and then equation 10 Þ
Equation 20: 5(A*B*) = 3(N*R*Y*@*$*&*);

35. Sometimes you can use the fact that two pattern sets are
subsets of two larger non-intersecting pattern sets to eliminate
patterns. For example, assume X and Y are large sets of patterns,
and that there is no pattern common to both X and Y. Also assume
x is a subset of X patterns, and y is a subset of Y patterns. Now,
if you get an equation like x = y + z, you can kill pattern subset
y because there are no unknowns on x's side of the equation to
allow any B patterns to be valid. In our puzzle:
Equations 3 & 20 show 5(A*B*) and 8(bdf) to be non-intersecting.
r1c6 Þ 8(bd) = 5(Aa) 5(GaOabQa); kills 5(Aa);

36. Noting that currently 5(A*) = 5(Ac);
Equation 20 Þ r1c3 kills 3(NdYf$g);

37. Equations 3 & 10 show 8(bdf) & 4(ab) to be non-intersecting.
r1c1 Þ 4a = 8d 3(RaTb@a&b); kills 8d;

38. r1c1 Þ 4a = 3(RaTb@a&b); with Equation 2 Þ r2c1
kills 3(RaTb@a&b) and 4a; solves for 4 in r1c1 and kills
candidate 4's in r2c1 and r1c9;

39. r1c6 Þ Equation 21: 8b = 5(GaOabQa);
Equation 21 Þ r8c1 kills 5(GaOab);
Equation 21 Þ r9c9 kills 5(OabQa);
kills candidate 5's in r1c6, r2c1, r3c3, r8c3; kills 8b, killing
candidate 8's in r1c2, r2c6, and r8c1; solves for 8's in r1c6,
r2c1, and r8c2; kills 1(abc) 7(kl) 3(J*) and 9(ae); kills
candidate 1's in r4c3 and r5c3;

40. Another way a substitution into a cell can kill patterns is
if patterns are missing when a cell has been completely converted
to patterns belonging to a single digit. In this step, the 3(H*)
patterns are invalidated because they are missing from the
wholly converted cell.
r9c4 Þ Equation 22: 9(ch) = 3(A*C*D*F*N*R*T*Y*@*$*&*);
Equation 22 Þ r8c3 kills 3(H*R*@*&*);
Equation 22 Þ r4c2 kills 3(AgCf); kills candidate 3 in r4c2.

41. Another way substitutions into a cell can kill patterns is
when the cell contains all of the patterns for a digit and it
contains some extra patterns on top of that. In that case, the
extra patterns can be invalidated. This step is an example of
this type of invalidation:

r5c4 Þ 3(NaYc) = 2b Þ r4c3 kills 7j 9(df); kills
candidate 7 in r4c3; kills candidate 9 in r4c3; exposes a 2-3-9
triple in comumn 3; kills candidate 3's in r1c3, r2c3, and r7c3;
kills 3(D*F*T*); kills candidate 3's in r1c9 and r9c2; solves for
5 in r1c3 killing candidate 5's in r1c9 and r2c3; kills 5(GdJdKb);
solves for 6 in r1c9, killing 6c and candidate 6's in r1c2, r3c7,
and r9c9; solves for 3 in r1c2;

Equation Updates
Equation 20: 5(A*B*) = 3(N*Y*$*);
Equation 9: 4(cd) = 3(C*L*);
Equation 10: 4(b) = 3(A*N*Y*$*);
Equation 2: 8e = 3(A*C*LhN*Y*$*);
Equation 3: 8f = 3(Lbc);
Equation 4: 1(df) = 3(Lb);
Equation 5: 1(mno) = 3(CdN*);
Equation 6: 1(eg) = 3(A*CkLch$*);
Equation 7: 1(jl) = 3(Y*);

42. Equation 23: 5(G*J*K*O*P*) = 3(A*C*L*); from Equation 20.
r9c9 Þ 1(defgmno) = 8f 3($*) 5(O*P*) Þ equations 3,4,5,6 Þ
3(A*C*L*N*$*) = 3(Lbc$*) 5(O*P*) Þ
5(O*P*) = 3(A*C*LhN*) kills 3(N*) since
there are no balancing orange or unknown terms on other side of the
equation; kills candidate 3 from r7c7 and r9c5.

Equation 20: 5(A*B*) = 3(Y*$*);
Equation 24: 5(O*P*) = 3(A*C*Lh);
Equation 25: 5(G*J*K*) = 3(Lbc) = 8f;

43. Updated equation 22: 9(ch) = 3(A*C*Y*$*) Þ r4c2 Þ
Equation 26: 7(an) 7(bcdmoqr) = 3(A*C*Y*$*); Þ 7(an) £ 3(A*C*Y*$*);

44. r9c5 Þ 7(an) = 5(A*B*O*P) 5(J*K*), which, coupled
with equations 20 & 24 Þ 7(an) = 3(A*C*Y*$*) 3(Lh) 5(J*K*);
comparing with equation 26 kills 7(bcdmoqr), 3(Lh), and 5(J*K*);
kills candidate 5 in r9c7; kills candidate 7's in r4c5, r4c6,
and r9c2;

45. r9c5 Þ 7(an) = 5(A*B*O*P*); Þ r2c6 kills 5(AcOc);
kills candidate 5's in r2c6, r3c7; solves for 7 in r2c6; solves
for 1 in r3c7; kills 1(fghlmno) 2b 3(CdY*) 7(gh); kills candidate
1's from r3c3, r2c7, r2c8, r2c9, r4c6, r5c7, r6c6, r6c7, & r9c9;
solves for 1 in r5c6 & r9c8, killing 9c; solves for 2 in r4c3 &
r5c4, killing remaining candidate 2's; kills candidate 7's in
r2c3, r3c4, r3c5, r6c6, & r7c6;

46. r6c7 Þ 9b = 3(A*L*$*) Þ r5c3 kills 3(A*$*);
updating equations 10 and 20 indicates this kills 4b and 5(A*B*)
as well; solves for 4 in r2c8 & r8c9; solves for 3 in r7c8;
solves for 5 in r8c1; kills candidate 3's in r5c7, r4c4, r8c1,
r7c5, r8c9, r9c9, and r6c4; kills candidate 5 in r4c5.

47. From various equation updates, and cells on the grid we
have 5(Gc) = 3(Lbc) = 9b = 6b = 7i = 8f;
r6c4 Þ 4c = 7(ai) Þ r7c5 kills 7i; which also kills
5(Gc), 3(Lbc), 9b, 6b, and 8f; among other things, this solves
for 7 in r9c5 which unlocks the rest of the puzzle fairly trivially.

So there it is, for those with the gumption to wade through it.

Myth Jellies
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1417
Joined: 05 September 2006

Previous

Return to Advanced solving techniques