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

Previous

Return to Advanced solving techniques