Strong inferences induced by the UR

Advanced methods and approaches for solving Sudoku puzzles

Strong inferences induced by the UR

Postby storm_norm » Sat Apr 04, 2009 11:07 am

Strong inferences induced by the Unique Rectangle.

Unique rectangles, or the UR, present yet another but interesting way in forming a strong inference. As a demonstration and
hopefully a useful tool to rely on, this thread will provide examples of some inferences that are not commonly sought after
as steps along the path to a solution.
All of these examples rely on the core intuitive idea behind the UR. If the candidates that form the UR are locked into the
UR cells then the deadly pattern is forced to exist. the puzzle will have multiple solutions.
There are common moves (type 1...type 2...etc) that prevent the UR candidates from being the only candidates to occupy the UR cells.

this concept needs to be understood or this thread may not make sense.
-----------
the remaining text will provide examples of the following...

I. The type 3 UR provides the most common strong inference created by a UR.
II. Inferences associated with the Type 2 UR
III. Inferences associated with the Type 4 UR
IV An uncommon UR inference
V. A short cut method to some classic Type 3 URs
-----------


I.The type 3 UR is the most common example of a strong inference that can be formed in a UR
for example
this portion of a grid

Code: Select all
| .  12 A123 |
--------------
| .  12 B124 |

the strong inference can be made between the 3 at A and the 4 at B
UR12[(3)B = (4)B]... this is because neither the 4 nor the 3 can both be false or the UR is left, which is a NO NO !!

the most common use of the Type 3 UR (and its original definition) is seeing the 3 and 4 as a single cell and forming a locked set with another {3,4} cell in the same box, row or column. AND!! seeing any candidates in the A and B cells and forming a locked "tuple" with other candidates in the same box, row or column.

the other use of the strong inference created is to use the 3 and the 4 in a chain.
this is a partial example
x cells cannot be 4
Code: Select all
+----------+--------+--------+
| . 12 123 | . 37 . | . 47 . |
| . 12 124 | . .  . | x x  x |
| . .  .   | . .  . | . .  . |
+----------+--------+--------+
| . .  .   | . .  . | . .  . |
| . .  .   | . .  . | . .  . |
| . .  .   | . .  . | . .  . |
+----------+--------+--------+
| . .  .   | . .  . | . .  . |
| . .  .   | . .  . | . .  . |
| . .  .   | . .  . | . .  . |
+----------+--------+--------+
if the 4 in r2c3 is true, then r2c789 cannot be 4
if the 4 in r2c3 is not true, then r1c3 has to be a 3 (rules of a UR type 1)
leads to... r1c5 is 6... r1c8 is 4... r2c789 cannot be 4.
either way, the 4's in r2c789 can not be 4
or it can be viewed as this chain
UR12[(4)r2c3 = (3)r1c3] - (3=7)r1c5 - (7=4)r1c8; r2c789 <> 4

the type 3 UR provides a nice alternative strong inference that may be needed to keep the puzzle moving.

if the type 3 UR is a common sudoku tool then its no surprise that the next few examples in this thread should be recognized.
------------


II. Inferences associated with the type 2 UR

Part A. examples of strong inferences induced by the classic type 2 UR.
as unorthodox as it may be, explaining Type 2 UR inferences after the type 3 is necessary because of a simple fact. The Type 2 UR needs more candidates included in the cells of the UR. Naturally, the inferences are going to happen accross more cells. Its the nature of the beast.

what is a type 2 UR?
here it is
Code: Select all
+--------+---------+-------+
| . 12 . | 123 . . | . . . |
| . 12 . | 123 . . | . . . |
| . .  . | .   . . | . . . |
+--------+---------+-------+

the example says that any other 3's in box 2 and any other 3's in column 4 can be eliminated.

adding some candidates to the grid...
Code: Select all
+---------+---------+-------+
| . 124 . | 123 . . | . . . |
| . 124 . | 123 . . | . . . |
| . .   . | .   . . | . . . |
+---------+---------+-------+

the grid now says that there exists a strong inference on the 4's in r12c2 and the 3's in r12c4. Again, if both the 3's and the 4's are removed then the UR is forced to exist in the UR cells. neither can both be false.
this strong inference is made... UR12[(4)r12c2 = (3)r12c4]...
imagine removing the 4's, then by the rule of a type 2, the 3's must exist in r12c4. the opposite is also true.

the following are examples of chains that can come in handy using this type of strong inference.


example 1...
the x cells cannot be 5.
Code: Select all
+---------+---------+-------+
| . 124 . | 123 . . | . . . |
| . 124 . | 123 . . | . . . |
| . .   . | .   . . | . . . |
+---------+---------+-------+
| . .   . | .   . . | . . . |
| . 45  . | x   x x | . . . |
| x x   x | 35  . . | . . . |
+---------+---------+-------+
(5=4)r5c2 - UR12[(4)r12c2 = (3r12c4] - (3=5)r6c4


example 2...
the x cells cannot be 5
Code: Select all
+---------+----------+-------+
| . x   . | .   . 35 | . . . |
| . 124 . | 123 . .  | . . . |
| . 124 . | 123 . .  | . . . |
+---------+----------+-------+
| . .   . | .   . .  | . . . |
| . 45  . | .   . x  | . . . |
| . .   . | .   . .  | . . . |
+---------+----------+-------+

(5=4)r5c2 - UR12[(4)r23c2 = (3)r23c4] - (3=5)r1c6; r1c2 and r5c6 cannot be 5



Part B examples of strong inferences induced by the type 2B UR
the type 2B states that the roof cells happen in two separate boxes.
Code: Select all
+---------+---------+-------+
| .   . . | .   . . | . . . |
| 12  . . | 12  . . | . . . |
| 123 . . | 123 . . | . . . |
+---------+---------+-------+
| .   . . | .   . . | . . . |
| .   . . | .   . . | . . . |
| .   . . | .   . . | . . . |
+---------+---------+-------+

the grid says that no other 3 in r3 can exist (this is not to be confused with the type 4 which will come later)
obviously the same rules apply as a type 2 except that since the roof cells are ONLY in the same row, then that row is where the eliminations happen. in this case row 3.

now adding a candidate into the mix and some interesting inferences can be made.


example 3...
the simplest example of a type 2B strong inference.
x cells cannot be 4
Code: Select all
+---------+---------+--------+
| .   . . | .   . . | . . .  |
| 12  . . | 124 . . | x x x  |
| 123 . . | 123 x x | . . 34 |
+---------+---------+--------+

imagine removing the 3's in r3c14, then the 4 must exist in r2c4 (rules of a type 1 UR). if the 4 is removed from r2c4, then the 3's must exist in r3c14 (rules of a type 2B UR). if either is the case, then the 4's in r2c789 cannot exist.
the strong inference is between the 4 in r2c4 and the 3's in r3c14 because if both are false, the UR is left.
UR12[(4)r2c4 = (3)r2c14] - (3=4)


example 4... the sillyness starts to make its presence felt.
x cell cannot be 3
Code: Select all
+---------+-----------+----------+
| .   . . | .   36 .  | 45 . .   |
| 12  . . | .   .  .  | .  . 124 |
| 123 . . | 379 39 37 | .  . 123 |
+---------+-----------+----------+
| .   . . | .   .  .  | .  . .   |
| .   . . | .   .  .  | .  . .   |
| .   . . | .   x  .  | 35 . .   |
+---------+-----------+----------+

again the strong inference is on the 4 in r2c9 and the 3's in r3c19...UR12[(4)r2c9 = (3)r3c19]...
remember that if the 4 is removed from r2c9 then a type 2B exists in r23c19 on {1,2} and the 3's in r3c19 must remain in order to break up the UR pattern.
(3=5)r6c7 - (5=4)r1c7 - UR12[(4)r2c9 = (3)r3c19] - (3)r3c456 = (3); r6c5 <> 3

although the inferences induced by a type 2 UR might be harder to find then a type 3, the usefulness is still nice to find.

-------------


III. Inferences associated with the type 4 UR

the type 4 UR provides the most interesting and sometimes outlandish step in reaching strong inferences through URs. Type 3 and Type 2 URs are very specific in nature because the move limits the number of candidates that can be present in the roof cells. The type 4 UR, on the other hand, allows multiple candidates to exist in the roof cells.

Part A... examples of strong inferences induced by the type 4 UR

what is a type 4 UR?
the type 4 says that the UR can be avoided if it is shown that one of the UR candidates is locked (or conjugate to the box, row or column that they are in) into the roof cells, the other candidate can be removed from the roof cells.
Code: Select all
+---------------+----------+-----------+
| 12    . 12    | . .  .   | .  .   .  |
| .     . .     | . .  .   | .  .   .  |
| .     . .     | . .  .   | .  .   .  |
+---------------+----------+-----------+
| 12345 . 12345 | . 18 158 | .  .   .  |
| .     . .     | . .  .   | .  .   .  |
| .     . .     | . .  .   | .  .   .  |
+---------------+----------+-----------+

notice that r1c13 are the floor cells and only contain the UR candidates.
in the grid, the 2's are shown to be locked into (the only place in row 4 they can exist) r4c13. by applying the rule on type 4, we can safely remove the 1's from r4c13 and avoid the deadly pattern.
What might not be apparant is how this rule can add any information in finding a strong inference.

as before a candidate is added. the 9 in r1c3

Code: Select all
+---------------+----------+-----------+
| 12    . 129   | . .  .   | .  .   .  |
| .     . .     | . .  .   | .  .   .  |
| .     . .     | . .  .   | .  .   .  |
+---------------+----------+-----------+
| 12345 . 12345 | . 18 158 | .  .   .  |
| .     . .     | . .  .   | .  .   .  |
| .     . .     | . .  .   | .  .   .  |
+---------------+----------+-----------+

the inference in this case, isn't between the added 9 and the 1's in r4c13. instead the inference is between the 9 and the 1's in r4c56. if both the 9 and the 1's in r4c56 are false, then the UR candidates {1,2} are forced to exist in the UR cells. this is key. if this was the case, the puzzle would not have a unique solution. the 1's and the 2's could be switched and create another solution.
again, if it is shown that the UR candidates are locked into the UR cells, then a deadly pattern exists.

example...
this next grid contains an iconic and devastating move that fully exposes why a type 4 UR induced strong inference, or any move likes this is a gem to find.
Code: Select all
.------------------.------------------.------------------.
| 5     9     16   | 14    24    7    | 26    8     3    |
| 4     7     68   | 3     5     28   | 1     26    9    |
| 38    2     138  | 189   6     89   | 4     5     7    |
:------------------+------------------+------------------:
| 1     8     2    | 45    7    *456  | 3     9    *56   |
| 6     5     7    | 2     9     3    | 8     1     4    |
| 39    4     39   | 58    1    *568  | 257   27  *A256  |
:------------------+------------------+------------------:
| 789   1     5    | 6    C24   D249  | 279   3   E-28   |
| 2     6     89   | 7     3     1    | 59    4     58   |
| 79    3     4    | 59    8    B259  | 2679  267   1    |
'------------------'------------------'------------------'

notice that the UR {56} cells are marked "*" in r46c69. the added candidate in this case is the 2 at A. removing that 2 will then expose a UR type 4 on {5,6} and the 5's in r46c6 can be removed, which forces 5 to exist in r9c6.
The strong inference is between the 2 in r6c9 and the 5 in r9c6 because if both are false, then the deadly pattern is forced to exist in the UR cells... this partial chain...
UR56[(2)A = (5)B]...
the elegance of this inference is the chain that ensues.
UR56[(2)A = (5)B] - (2)B = (2)CD; E cannot be 2. nothing but singles are left.

Part B... examples of strong inferences induced by the type 4B UR.

as expected, the type 4B UR deviates from a type 4 in that the roof cells are not contained in the same box. this means that the eliminations are ONLY made across the column or row that they occupy. many times it is mentioned how a type 4B and a type 2B can be the same, and in many cases they are the same. But, it is not safe to say that all type 2B URs are type 4Bs, or vice versa.

type 4B says the same as the type 4 except that one of the UR candidates has to be locked (or conjugate to the row or column) into the roof cells. this allows the safe removal of the opposite candidate from the roof cells.
Code: Select all
+-----------+----------+-----------+
| .     . . | .  .   . | .     . . |
| 12    . . | .  .   . | 12    . . |
| 12345 . . | 18 158 . | 12345 . . |
+-----------+----------+-----------+

r2c17 are the floor cells and the 2 is locked into the roof cells, the 1's can be eliminated from the roof cells r3c17.

this inference has so far eluded my attempts to find an example.

The type 4 and type 4B URs have a lot more going on and need careful inspection into which candidates are truly included in the inferences. Again, these are not common and probably not readily seen along a solution path.
-------------

IV. An uncommon UR inference.

This next type of inference isn't derived from a particular type of UR at all. Its derived straight from the concept behind avoiding the UR in the first place. The concept is that there are instances where none of the commonly known types are not going to make any eliminations but there is still a way to take advantage of the rules of URs and create a strong inference without the help of a common type. There are still strong inferences to be made if the right conditions are met.

Credit goes to Danny for expanding this type of UR in a earlier "other puzzle" thread into a contradiction which then helped me see the light once I got my head around it.

The trick is to notice what looks like a UR, but really can't take advantage of the common rules of URs to make any eliminations. AND its very important that the UR candidates are the ONLY candidates left in the floor cells. as in this grid
Code: Select all
+--------+-----------+-------+
| 12 . . | 12345 . . | . . . |
| .  . . | .     . . | . . . |
| 12 . . | 12345 . . | . . . |
+--------+-----------+-------+
| .  . . | .     . . | . . . |
| .  . . | 13    . . | . . . |
| .  . . | 25    . . | . . . |
+--------+-----------+-------+
| .  . . | .     . . | . . . |
| .  . . | .     . . | . . . |
| .  . . | .     . . | . . . |
+--------+-----------+-------+

it just so happens that there is another 1 and another 2 in column 4. both cannot be false at the same time (that will force the UR to exist, NO NO !!) This provides yet another strong inference to exploit
UR12[(1)r5c4 = (2)r6c4]...


the same can be said in this example
Code: Select all
+--------+-------------+-------+
| 12 . . | 12345 .  .  | . . . |
| .  . . | .     25 14 | . . . |
| 12 . . | 12345 .  .  | . . . |
+--------+-------------+-------+

the inference made is on the extra 1 and 2 in row 2


this is also true even if the roof cells don't occupy the same box (like in a type 2B or 4B) as in this example.
Code: Select all
+-----------+--------+------------+
| 12    . . | .  . . | 12    . .  |
| .     . . | .  . . | .     . .  |
| 12345 . . | 25 . . | 12345 . 14 |
+-----------+--------+------------+

the inference is still on the 1 in r3c9 and the 2 in r3c4.


example 1...
this following grid contains the kind of example which shows off the concept nicely.
this rule can be implemented using the UR {1,8} in r78c17, marked *
Code: Select all
.---------------------.---------------------.---------------------.
| 5     D68     4     | 7      1238   123   | 139    18    C13689 |
| 7      2      38    | 6      138    9     | 5      4      138   |
| 389    1      69    | 5      348    34    | 2      7      368   |
:---------------------+---------------------+---------------------:
| 38     9      1378  | 138    6      137   | 4      2      5     |
| 2      5      138   | 1348   9      134   | 6      18     7     |
| 6      4      178   | 128    5      127   | 13     9      138   |
:---------------------+---------------------+---------------------:
|*189   A78     5     | 24     24     6     |*1789   3     B19    |
|*18     3      2     | 9      7      5     |*18     6      4     |
| 4      67     69    | 13     13     8     | 79     5      2     |
'---------------------'---------------------'---------------------'

UR {1,8} r78c17 says that neither the 8 at A nor the 1 at B can both be false
or the deadly pattern on {1,8} is forced to exist in those UR cells.
creates this strong inference...UR18[{8}A = (1)B]...

can be extended into this chain...
UR18[(8}A = (1)B] - (9)B = (9-6)C = (6)D; r1c2 <> 8


example 2...
Code: Select all
.---------------------.---------------------.---------------------.
| 2     *34589  158   | 18     57     6     |*35789  145   *489   |
|*145    6      158   | 3      57     9     | 578    1245   248   |
|U1359  U3589   7     | 4      2      18    |*3589   6     *89    |
:---------------------+---------------------+---------------------:
| 8      1      3     | 9      4      5     | 2      7      6     |
|U59    U59     2     | 6      1      7     | 4      8      3     |
| 6      7      4     | 2      8      3     | 1      9      5     |
:---------------------+---------------------+---------------------:
| 1345   3458   158   | 7      6      48    | 589    245    2489  |
| 7      458    9     | 58     3      2     | 6      45     1     |
|*45     2      6     | 158    9      148   |-58     3      7     |
'---------------------'---------------------'---------------------'

notice the UR cells marked on {5,9}. the UR says that in order to avoid the deadly pattern, both the 5 in r3c7 and the 9's in r3c79 cannot both be false.
in other words, UR59[(5)r3c7 = (9)r3c79]... which can be extended to eliminate the 5 in r9c7...
UR59[(5)r3c7 = (9)r3c79] - (9)r1c79 = (9-4)r1c2 = (4)r2c1 - (4=5)r9c1; r9c7 <> 5

When two bi-value cells in the same column or row stick out like a soar thumb, take notice to it and wonder if a UR can be formed. This type of move can be rewarding to the curious onlooker.

---------

V. A short cut method to SOME classic Type 3 URs

just a warning that this does not work with all type 3's. only in certain conditions.

This alternative view shows that when the extra UR candidates of the UR share a common cell, then by virtue of the rules of URs, those are the only two candidates that can exist in that cell.

this concept comes last because the type 3 is already employed by the solvers that see the locked "tuples" created by some type 3's. these can make some nice eliminations.
this section is here to provide an alternative view of seeing eliminations without knowing which "tuples" are locked and without realizing that its a type 3 at all.

In section IV, it was shown that a strong inference can be made if there are extra UR candidates in the same row, column or box, and none of the common UR rules apply. this will show what happens when those candidates share a common cell.

here is a type 3 again
Code: Select all
+--------+---------+-------+
| 12 . . | 123 . . | . . . |
| .  . . | .   . . | . . . |
| 12 . . | 124 . . | . . . |
+--------+---------+-------+
| .  . . | 345 . . | . . . |
| .  . . | 346 . . | . . . |
| .  . . | 34  . . | . . . |
+--------+---------+-------+

the 3 in r1c4 and the 4 in r3c4 act like a single cell and thereby act like a locked set with the {3,4} cell in r6c4, eliminating any other 3's and 4's in column 4.

consider this grid and notice the UR {1,2} in r46c14
Code: Select all
+--------+-------------+-------+
| .  . . | 3456789 . . | . . . |
| .  . . | 3456789 . . | . . . |
| .  . . | 12(3456). . | . . . |
+--------+-------------+-------+
| 12 . . | 12345   . . | . . . |
| .  . . | .       . . | . . . |
| 12 . . | 12345   . . | . . . |
+--------+-------------+-------+
| .  . . | 3456789 . . | . . . |
| .  . . | 3456789 . . | . . . |
| .  . . | 3456789 . . | . . . |
+--------+-------------+-------+

as stated before, the extra UR candidates 1 and 2 in r3c4 exist in the same cell. From the rules of URs we can now eliminate the {3,4,5,6} from r3c4 because neither the 1 nor the 2 can be false at the same time.
in other words, if r3c4 is anything other than 1 or 2, the deadly pattern is forced to exist in the UR cells.
having that knowledge can make it easier to remove {3,4,5,6} from r3c4 instead of looking for the locked sets.
this works when the "floor" cells contain only the UR candidates.
---------

I hope this provides some insight into some different yet available strong inferences derived from the rules of URs.
I welcome all feedback and corrections or suggestions that was not covered.
Last edited by storm_norm on Thu Apr 09, 2009 3:31 am, edited 5 times in total.
storm_norm
 
Posts: 85
Joined: 27 February 2008

Postby champagne » Tue Apr 07, 2009 11:32 pm

Hi,

This is a nice work.

However, it is lacking examples of puzzles where the shown patterns apply.

This would give incentive to go deeper in the concept.

I introduced recently in my solver several (among the easiest) of the here above "rules" but with no noticed spectacular change in the paths to the solutions.

Reversely, "ttt" makes wonderfull things out of URs.

champagne
champagne
2017 Supporter
 
Posts: 5640
Joined: 02 August 2007
Location: France Brittany

Postby DonM » Tue Apr 07, 2009 11:59 pm

Storm_norm: Very useful subject -a relatively untapped one at that- and nicely presented. Hopefully, some actual puzzle examples can be added as this thread continues.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby ronk » Wed Apr 08, 2009 12:32 am

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

Postby Luke » Wed Apr 08, 2009 1:07 am

Here's an example from the link ronk provided. It fits your category "Inferences associated with the type 2 UR." Carcul referred to these as "Type 1 AUR."
Code: Select all
 167  2    13478| 468   3489 468  | 5     79   168
 156  138  9    | 7     358  2568 | 246   246  1268
 567 *478 *478  | 24568 4589 1    | 79    3    268   
----------------+-----------------+-----------------
 4    15   126  | 13    7    58   | 1236  2568 9
 3    59   16   | 458   2    4589 | 16    58   7
 8    1579 127  | 13    6    59   | 123   25   4
----------------+-----------------+-----------------
 127  6    38   | 9     1458 24578| 247   247  235
 1279*147 *147  | 256   15   3    | 8     2679 256
 279  38   5    | 2468  48   24678| 24679 1    236

[r2c2]=3=[r1c3]-3-[r7c3]=3=[r7c9]=5=[r8c9]-5-[r8c5]-1-[r8c2|r8c3]=1|8=[r3c2|r3c3]-8-[r2c2] => r2c2<>8.

[r3c5]=9=[r1c5]=3=[r1c3]-3-[r7c3]=3=[r7c9]=5=[r8c9]-5-[r8c5]-1-[r8c2|r8c3]=1|8=[r3c2|r3c3]-8-[r3c5] => r3c5<>8.

I'm wondering if this is the same notation that is in use nowadays (i.e., with the "pipe".)
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Re: Strong inferences induced by the UR

Postby aran » Wed Apr 08, 2009 1:11 am

Storm Norm
Always good to see work on deadly rectangles.
The section on innovative strong link generation is of great interest.

Just a couple of observations.
The strong links generated can of course be developed in both directions with potential results both ways
eg with respect to this :
Storm Norm wrote:
Code: Select all
.---------------------.---------------------.---------------------.
| 1478 F1-78    3     | 15     15789 A79    | 6      2      4578  |
| 9      1278   25    |*1567   4     *67    | 138    357    3578  |
| 6      178    45    | 3      1578   2     | 18     457    9     |
:---------------------+---------------------+---------------------:
| 124    1269   7     | 8      129    3     | 5      14     46    |
| 134    5      49    |*167    179  *B679   | 2      8      347   |
| 123    1236   8     | 4      127    5     | 9      137    367   |
:---------------------+---------------------+---------------------:
| 5     E37     1     | 9     D37     8     | 4      6      2     |
| 2378   23789  29    |C257    6      4     | 38     35     1     |
| 238    4      6     | 25     35     1     | 7      9      358   |
'---------------------'---------------------'---------------------'

again, the UR {6,7} cells are marked "*". notice that removing the 9 at B exposes the type 4B UR on {6,7}. this allows the removal of the 7's in r25c4 which forces 7 into C. so the inference is on the 9 at B and the 7 at C because if both are false then the UR candidates are locked into the deadly pattern.

From the fine strong link 9r5c6/7r8c4 which you established :
one can develop 7r8c4=9r5c6 and 9r5c6=7r8c4.
Even if obvious there might be a tendency to settle for one direction only:)
Here
7r8c4=9r5c6-(9=127)r456c5-7r7c5=7r7c2 :=><7>r8c12=>r7c2=7 (which pretty much cracks the puzzle...but suppose it didn't...)
9r5c6=7r8c4-7r7c5=7r7c2-(7=128)r123c2-(2=5)r2c3-(5=4)r3c3-(4=9)r5c3 : =><9>r5c5

The deductions in the section Uncommon UR Inference are excellent and illustrate the power of lateral DR thinking.
Storm Norm wrote:
Code: Select all
.---------------------.---------------------.---------------------.
| 5     D68     4     | 7      1238   123   | 139    18    C13689 |
| 7      2      38    | 6      138    9     | 5      4      138   |
| 389    1      69    | 5      348    34    | 2      7      368   |
:---------------------+---------------------+---------------------:
| 38     9      1378  | 138    6      137   | 4      2      5     |
| 2      5      138   | 1348   9      134   | 6      18     7     |
| 6      4      178   | 128    5      127   | 13     9      138   |
:---------------------+---------------------+---------------------:
|*189   A78     5     | 24     24     6     |*1789   3     B19    |
|*18     3      2     | 9      7      5     |*18     6      4     |
| 4      67     69    | 13     13     8     | 79     5      2     |
'---------------------'---------------------'---------------------'

UR {1,8} r78c17 says that neither the 8 at A nor the 1 at B can both be false
or the deadly pattern on {1,8} is forced to exist in those UR cells.
creates this strong inference...UR18[{8}A = (1)B]...
can be extended into this chain...
UR18[(8}A = (1)B] - (9)B = (9-6)C = (6)D; r1c2 <> 8

Here you could also have taken the route :
8r7c2=1r7c9-(1=8)r8c7 :=><8>r8c1=1, <8>r7c7

Storm Norm wrote:
Code: Select all
.---------------------.---------------------.---------------------.
| 2     *34589  158   | 18     57     6     |*35789  145   *489   |
|*145    6      158   | 3      57     9     | 578    1245   248   |
|U1359  U3589   7     | 4      2      18    |*3589   6     *89    |
:---------------------+---------------------+---------------------:
| 8      1      3     | 9      4      5     | 2      7      6     |
|U59    U59     2     | 6      1      7     | 4      8      3     |
| 6      7      4     | 2      8      3     | 1      9      5     |
:---------------------+---------------------+---------------------:
| 1345   3458   158   | 7      6      48    | 589    245    2489  |
| 7      458    9     | 58     3      2     | 6      45     1     |
|*45     2      6     | 158    9      148   |-58     3      7     |
'---------------------'---------------------'---------------------'

notice the UR cells marked on {5,9}. the UR says that in order to avoid the deadly pattern, both the 5 in r3c7 and the 9's in r3c79 cannot both be false.
in other words, UR59[(5)r3c7 = (9)r3c79]... which can be extended to eliminate the 5 in r9c7...
UR59[(5)r3c7 = (9)r3c79] - (9)r1c79 = (9-4)r1c2 = (4)r2c1 - (4=5)r9c1; r9c7 <> 5

A real classic (as I have said before about this beauty):)
aran
 
Posts: 334
Joined: 02 March 2007

Postby Luke » Wed Apr 08, 2009 1:27 am

Gee, Storm, no action for days, then BAM:) . I've been studying it, though. Here's something from my notes:

storm_norm wrote:I.The type 3 UR is the most common example of a strong inference that can be formed in a UR
for example
Code: Select all
+----------+--------+--------+
| . 12 123 | . 37 . | . 47 . |
| . 12 124 | . .  . | x x  x |
| . .  .   | . .  . | . .  . |
+----------+--------+--------+
| . .  .   | . .  . | . .  . |
| . .  .   | . .  . | . .  . |
| . .  .   | . .  . | . .  . |
+----------+--------+--------+
| . .  .   | . .  . | . .  . |
| . .  .   | . .  . | . .  . |
| . .  .   | . .  . | . .  . |
+----------+--------+--------+

Until a real world example emerges, would this work better?
Code: Select all
+----------+--------+--------+
| . 12 .   |123 . 37|   47 . |
| . 12 .   |124   . | x x  x |
| . .  .   | . .  . | . .  . |
+----------+--------+--------+
| . .  .   | . .  . | . .  . |
| . .  .   | . .  . | . .  . |
| . .  .   | . .  . | . .  . |
+----------+--------+--------+
| . .  .   | . .  . | . .  . |
| . .  .   | . .  . | . .  . |
| . .  .   | . .  . | . .  . |
+----------+--------+--------+
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby daj95376 » Wed Apr 08, 2009 1:49 am

Norm has applied his approach to several puzzles in the DailySudoku forum. I'm sure he is gathering them up now to add to this thread.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ronk » Wed Apr 08, 2009 2:58 am

Luke451 wrote:Here's an example from the link ronk provided. It fits your category "Inferences associated with the type 2 UR." Carcul referred to these as "Type 1 AUR."

The usefulness of type numbers for AURs is questionable IMO but, if there has to be one, storm_norm's Type 2 makes more sense than Carcul's Type 1. The reason should be obvious.

Luke451 wrote:
Carcul wrote:[r2c2]=3=[r1c3]-3-[r7c3]=3=[r7c9]=5=[r8c9]-5-[r8c5]-1-[r8c2|r8c3]=1|8=[r3c2|r3c3]-8-[r2c2] => r2c2<>8.

[r3c5]=9=[r1c5]=3=[r1c3]-3-[r7c3]=3=[r7c9]=5=[r8c9]-5-[r8c5]-1-[r8c2|r8c3]=1|8=[r3c2|r3c3]-8-[r3c5] => r3c5<>8.

I'm wondering if this is the same notation that is in use nowadays (i.e., with the "pipe".)

There aren't many of us actively posting nice loop (NL) notation these days, but I've been using the pipe ('|') symbol ever since. The refinements I've been using are
  • Replacement of square brackets ('[' and ']') with white space,
  • Labels such as "aur:( ... )" to indicate the type and scope of the derived strong inference, and
  • More compact cell groupings such as r8c23.
With these refinements, the above looks like ...
r2c2 =3= r1c3 -3- r7c3 =3= r7c9 =5= r8c9 -5- r8c5 -1- aur:(r8c23 =1|8= r3c23) -8- r2c2 => r2c2<>8

r3c5 =9= r1c5 =3= r1c3 -3- r7c3 =3= r7c9 =5= r8c9 -5- r8c5 -1- aur:(r8c23 =1|8= r3c23) -8- r3c5 => r3c5<>8
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Luke » Wed Apr 08, 2009 4:15 am

ronk wrote:The usefulness of type numbers for AURs is questionable IMO but, if there has to be one, storm_norm's Type 2 makes more sense than Carcul's Type 1. The reason should be obvious.

That occurred to me as well. Could cause confusion if someone tries to find a non-existent Type 1 UR. BTW, thanks for the notation update. I'll put that in my pipe and smoke it...

Norm, I think your contribution to Don's SAM #1 is an excellent example of an "Inferences associated with the type 4 UR:"
Code: Select all
.---------------------.---------------------.---------------------.
| 7     U128    4     | 18     5      189   | 6      3     U129   |
| 58    U125    9     | 36     4      36    | 18     7     U12    |
| 3     *18     6     |*-189   2      7     | 5      48    *49    |
:---------------------+---------------------+---------------------:
| 59     6      2     | 7      8      49    | 3      145    145   |

| 1      45     7     | 26     3      26    | 49     459    8     |
| 89     48     3     | 49     1      5     | 2      6      7     |
:---------------------+---------------------+---------------------:
| 6      7      8     | 1245   9      124   | 14     125    3     |
| 24     9      1     | 23458  6      2348  | 7      258    45    |
| 24     3      5     | 1248   7      1248  | 1489   1289   6     |
'---------------------'---------------------'---------------------'
Notice the marked cells contain the deadly pattern on {1,2}.If the 9 is removed from r9c1 then we know that the resulting UR can be avoided by removing the 1's in r12c2, this would force 1 into r3c2. In other words, neither the 9 in r1c9 nor the 1 in r3c2 can both be false or the deadly pattern is forced to exist.
creates this inference...

UR12[(9)r9c1 = (1)r3c2]...can be used in this chain
(9)r3c4 = (9)r3c9 - UR12[(9)r9c1 = (1)r3c2]; r3c4 <> 1


Here's the one from the tutorial:
Code: Select all
.------------------.------------------.------------------.
| 5     9     16   | 14    24    7    | 26    8     3    |
| 4     7     68   | 3     5     28   | 1     26    9    |
| 38    2     138  | 189   6     89   | 4     5     7    |
:------------------+------------------+------------------:
| 1     8     2    | 45    7    *456  | 3     9    *56   |
| 6     5     7    | 2     9     3    | 8     1     4    |
| 39    4     39   | 58    1    *568  | 257   27  *A256  |
:------------------+------------------+------------------:
| 789   1     5    | 6    C24   D249  | 279   3   E-28   |
| 2     6     89   | 7     3     1    | 59    4     58   |
| 79    3     4    | 59    8    B259  | 2679  267   1    |
'------------------'------------------'------------------'

The strong inference is between the 2 in r6c9 and the 5 in r9c6 because if both are false, then the deadly pattern is forced to exist in the UR cells.

This is a beauty, too. I'd like to point out something here. Until your SAM#1 post, if I looked at the above UR I'd take my eraser out: r6c6<>5. While the elimination is legit, it makes it hard to notice any subsequent UR based moves. So now what I do is rather than erase a UR elim straight away, I "ghost" it out so I know it's there for later. If it serves me, Ill reinvent the eliminated digit for a UR chain/AUR/etc.
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby ronk » Wed Apr 08, 2009 4:44 am

Luke451 wrote:Until a real world example emerges, would this work better?
Code: Select all
+----------+--------+--------+
| . 12 .   |123 . 37|   47 . |
| . 12 .   |124   . | x x  x |
| . .  .   | . .  . | . .  . |
+----------+--------+--------+
| . .  .   | . .  . | . .  . |
| . .  .   | . .  . | . .  . |
| . .  .   | . .  . | . .  . |
+----------+--------+--------+
| . .  .   | . .  . | . .  . |
| . .  .   | . .  . | . .  . |
| . .  .   | . .  . | . .  . |
+----------+--------+--------+

Yes, two boxes, not one. Good catch:!:
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby storm_norm » Wed Apr 08, 2009 6:38 am

I should express my respect for those who have posted beforehand on the usefulness of URs. my enthusiasm IS because of the prior work on this subject. I cannot bring this thread to life without the work done on the many types of URs.
AND
I was absolutely comfortable with this thread being lost for a few days or weeks.:D:D:D

ehem. all kidding aside.

champagne, Donm,
in response to your first posts.

I am confident by starting this thread that not only I but others will see examples and post them. but maybe more importantly, this thread will provide a place to post an example of a strong inference that is in question.
as for real life examples missing in the posting? in hindsight, and from your and Luke's request, the omission of these examples is gross negligence on my part. It was the result of trying to keep the posting as simple to read as possible. I tried to avoid a posting with example after example... etc because I felt the concept of the example was more important.
ronk,
thanx for the threads on the prior stuff. Carcul was very fond of these inferences. I have noticed Carcul's work on them and its one of my inspirations for using the UR more often in the first place. I am not convinced, however, that Carcul's work has been explored to the max especially on the Eureka side of things. I think the biggest criticism Carcul was so adept at receiving is that his chains were so elaborate and brilliant that the usefulness was forgotten.

ronk said:
The usefulness of type numbers for AURs is questionable IMO but, if there has to be one, storm_norm's Type 2 makes more sense than Carcul's Type 1. The reason should be obvious

lets say by some strange chance the solver could erase that part of the memory that had URs tucked away in it. Would it be beyond reason to order the types differently if we knew what we know about inferences now? With how important it is to see inferences, I would venture to guess that some Types would be more sought after than others.
on the flip side, assuming we know nothing about inferences, Its very obvious why the types are numbered. The real leap in faith, for my money, is going from the type 2 to the type 3.
the type 3 is where the strong inference discusson starts when talking about a UR.:!: so in a real twist of fate, the UR type 3 is the first type of UR inference.

aran,
as always, its nice to have a fresh set of eyes and this time they had the feel of being brand new. your insights are quite frankly, humbling for lack of a better word.

Luke451 said:
This is a beauty, too. I'd like to point out something here. Until your SAM#1 post, if I looked at the above UR I'd take my eraser out: r6c6<>5. While the elimination is legit, it makes it hard to notice any subsequent UR based moves. So now what I do is rather than erase a UR elim straight away, I "ghost" it out so I know it's there for later. If it serves me, Ill reinvent the eliminated digit for a UR chain/AUR/etc.


the dirty little secret about the inferences generated by the UR is that the effort may not seem worth it. Try explaining that to aran when he found those alternative chains:D . the hidden UR which you mention is just another example of how a bi-value cell (easy to find) can influence one's route. This reminds me of a discussion on another board when the argument was made that a BUG can always be ingored by finding a xy-wing or chain or that URs will always be destroyed by a clever chain.
ok, benefit of the doubt kind of argument.
but nothing screams elegance louder than a UR inference which wipes the puzzle clean.

Danny,
glad you posted.
The uncommon inference section was definitely inspired by the example you posted on the daily site and our interactions following. I believe that example needs to be included in this discussion. however, I am unable to find the thread.:(
storm_norm
 
Posts: 85
Joined: 27 February 2008

Postby DonM » Wed Apr 08, 2009 7:23 am

storm_norm wrote:lets say by some strange chance the solver could erase that part of the memory that had URs tucked away in it. Would it be beyond reason to order the types differently if we knew what we know about inferences now? With how important it is to see inferences, I would venture to guess that some Types would be more sought after than others.
on the flip side, assuming we know nothing about inferences, Its very obvious why the types are numbered.


I strongly believe that the assignment of UR Types is particularly useful to those in the initial stages of the learning solving process, especially those who don't yet fully understand the underlying logic from the inside out and may never get there if they don't move on to advanced solving. Not to mention that it makes tutorials on the subject somewhat easier. Learning to recognize the basic Types 1-4, will provide some automatic eliminations in a number of the newspaper diabolicals that some newer solvers consider a major challenge (as one example) and that will be without the need for a firm grasp of what's really going on.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby storm_norm » Wed Apr 08, 2009 8:21 am

champagne wrote:Hi,

This is a nice work.

However, it is lacking examples of puzzles where the shown patterns apply.

This would give incentive to go deeper in the concept.

I introduced recently in my solver several (among the easiest) of the here above "rules" but with no noticed spectacular change in the paths to the solutions.

Reversely, "ttt" makes wonderfull things out of URs.

champagne

absolutely.
more examples need to be presented and I will be posting more.

I agree that ttt does make very nice use of the AUR, but it should be noted that ttt's main use of the UR is in forming strong sets.

you say that you don't notice a difference in a puzzle's path if your solver employs the easier UR inferences?
I can't deny or affirm that these inferences are ever needed in solving sudoku puzzles. I am leaning towards never.
storm_norm
 
Posts: 85
Joined: 27 February 2008

Postby storm_norm » Wed Apr 08, 2009 9:06 am

it should be noted that Carcul did post about the type 3 strong inference and the type 2 strong inferences in the threads that ronk listed.

UR Type 3 strong inference

Code: Select all
.------------------.------------------.------------------.
| 1     37    8    | 479   479   5    | 367   3679  2    |
| 2     367   36   | 379   1     8    | 4     5     39   |
| 9     5     4    | 37    6     2    | 37    8     1    |
:------------------+------------------+------------------:
| 346   36    1    | 5     234   9    | 8     23    7    |
| 34    9     2    | 467   8     367  | 5     1     36   |
| 5     8     7    | 1     23    36   | 9     236   4    |
:------------------+------------------+------------------:
| 3678  4     36   | 2     5     1    | 367   3679  3689 |
| 378   2     5    | 679   379   367  | 1     4     38   |
| 367   1     9    | 8     37    4    | 2     367   5    |
'------------------'------------------'------------------'

UR {2,3}r46c58 says that neither the 4 in r4c5 or the 6 in r6c8 can both be false.
UR23[(4)r4c5 = (6)r6c8] - (6=3)r5c9 - (3=4)r5c1; r5c4 <> 4

Type 2 UR generated inference

real example.
this puzzle is easily solved SSTS. but it does contain an example of a type 2 based inference.
Code: Select all
.---------------.---------------.---------------.
| 25   9    47  |U578 U578  1   | 3    24   6   |
| 6    3    47  | 2    9   *57  |*45   1    8   |
| 258  1    28  | 6    4    3   | 9    7    25  |
:---------------+---------------+---------------:
| 3    5    9   | 17   17   8   | 24   6    24  |
| 7    8    6   | 59   2    4   | 1    59   3   |
| 12   4    12  | 3    6    59  | 8    59   7   |
:---------------+---------------+---------------:
| 148  2    5   | 79   3    79  | 6    48   14  |
| 148  7    3   |U158 U158  6   |*245  248  9   |
| 9    6    18  | 4   -158  2   | 7    3   *15  |
'---------------'---------------'---------------'

the UR on {5,8} in r18c45 says that neither the 1's in r8c45 or the 5's in r1c45 can both be false.
creates this strong inference...
UR58[(1)r8c45 = (7)r1c45]...

can be extended into this chain...
UR58[(1)r8c45 = (7)r1c45] - (7=5)r2c6 - (5)r2c7 = (5)r8c7 - (5=1)r9c9; r9c5 <> 1

UR Type 2B generated strong inference
Code: Select all
.---------------------.---------------------.---------------------.
| 9      6      25    | 245    14     125   | 3      7      8     |
| 4      1      27    | 8      37     237   | 5      6      9     |
| 37     35     8     | 6      9      57    | 1      4      2     |
:---------------------+---------------------+---------------------:
| 37     8      4     | 9      37     6     | 2      1      5     |
| 1      2      9     | 37     5      4     |U67     8     U367   |
| 6      35     57    | 1      2      8     |*47-9   39    *347   |
:---------------------+---------------------+---------------------:
| 2      7      36    | 345    146    1359  | 8      359   *34    |
| 5      4      1     | 237    8      2379  |U679    239   U367   |
| 8      9      36    | 23457  46     2357  | 47     235    1     |
'---------------------'---------------------'---------------------'

note the cells marked U contain the UR on {6,7}. also see that if the 9 is removed from r8c7 then the type 2B UR remains on {6,7} which says that the 3's in r58c9 cannot be removed.
this provides a strong inference on the 9 and the 3's because neither can both be false.
UR67[(9)r8c7 = (3)r58c9]... and this can be extended into this chain.

UR67[(9)r8c7 = (3)r58c9] - (3=4)r7c9 - (4)r6c9 = (4)r6c7; r6c7 <> 9
----------
edited for some grammatical errors
Last edited by storm_norm on Wed Apr 08, 2009 6:01 pm, edited 1 time in total.
storm_norm
 
Posts: 85
Joined: 27 February 2008

Next

Return to Advanced solving techniques