UR+2B/2SL

Advanced methods and approaches for solving Sudoku puzzles

UR+2B/2SL

Postby surbier » Thu Feb 24, 2011 7:35 am

Hi,

I have coded all URs from this post (Mike Barker, Sat Apr 22, 2006 10:27 pm) and I have been
looking for examples. Surprisingly, the UR+1, UR+2x and the UR+2B/1SL
(aka as hidden UR type 2) are by far the most frequent URs.

In the following situation, there is a UR in (23)[r5c6 | r6c8]

Code: Select all
000000006090000800000007203029504700600090000004080001060000000008050000170830002


Code: Select all
+------------------------+----------------------------+------------------------+
|  _5_    34      37     | 13       _2_       _8_     | 149     179      >6<   |
| 24       >9<    237    | 13       _6_       _5_     |  >8<    17      47     |
|  _8_     _1_     _6_   |  _9_     _4_       >7<     |  >2<     _5_     >3<   |
+------------------------+----------------------------+------------------------+
|  _3_     >2<     >9<   |  >5<     _1_       >4<     |  >7<     _6_     _8_   |
|  >6<     _8_     _1_   |  _7_     >9<     *23       | 45     *23      45     |
|  _7_     _5_     >4<   | 26       >8<     *236      | 39     *239      >1<   |
+------------------------+----------------------------+------------------------+
| 249      >6<    23     | 24       _7_      12       | 135      _8_    59     |
| 249     34       >8<   | 246      >5<      126      | 13      137     79     |
|  >1<     >7<     _5_   |  >8<     >3<       _9_     |  _6_     _4_     >2<   |
+------------------------+----------------------------+------------------------+

( >7< is a clue and _8_ is a solved cell)

With the strong link 3[r5c6]=3[r6c6], this is a UR+2B/1SL and results
in r6c8<>2. Since there is a second strong link of the same kind:
2[r5c8]=2[r6c8] one could argue r6c6<>3. Since both eliminations are
cannibalistic, I can formally eliminate only on of both, as the deadly
pattern is destroyed after the first elimination.

This isn't quite satisfactory, since I miss one elimination. Note the
programming point of view, where eliminations are executed strictly
step-by-step. Furthermore none of the more complex URs like the UR+3,
UR+4 cover this situation. To catch both eliminations in one UR,
I would need a UR+2B/2SL like this:

Code: Select all
-abX   --a--   ab

a-bY   --b--   ab


Which I haven't found yet in the NSPF (please let me know if I overlooked
it) but found this constellation named as a doubly HUR2 elimination in
the method description of a sudoku programm. So I think it's known and
used by sudoku players. Given the fact that UR+2B/1SL is one of the
most frequent URs, I propose the UR+2B/2SL, not as something new but as
something to complete/extend the compilation mentioned above.

surbier
surbier
2012 Supporter
 
Posts: 54
Joined: 06 June 2008

Re: UR+2B/2SL

Postby eleven » Thu Feb 24, 2011 2:42 pm

As has been mentioned several times here, a UR is not "destroyed", when one of the UR numbers has been eliminated. You always can (mentally) reinsert the eliminated candidate, when it allows an elimination then.

Personally i dont look for UR type patterns (there are different classifications also). Its enough for me to look
o what do the extra candidates imply (covers types 1,2,3,4) ?
o are there UR candidates, which (more or less directly) lead to a deadly pattern (covers UR+strong links and others) ?
o where else can the UR candidates be in the 2 rows/colums/boxes ?
e.g. in the sample in rows 56 you only have 2 in r6c4 or 3 in r6c7 (at least one of them must be true to avoid the deadly pattern).
r6c4=2 -> r5c6=3 => r5c8,r6c6<>3
r6c7=3 -> r5c8=2 => r5c6,r6c8<>2
eleven
 
Posts: 1586
Joined: 10 February 2008

Re: UR+2B/2SL

Postby daj95376 » Thu Feb 24, 2011 6:59 pm

When you provide the original puzzle, it's not necessary to mark the PM grid for all given and all solved cells. At most, you need to mark the solved cells in a DP.

Code: Select all
 +-----------------------+
 | . . . | . . . | . . 6 |
 | . 9 . | . . . | 8 . . |
 | . . . | . . 7 | 2 . 3 |
 |-------+-------+-------|
 | . 2 9 | 5 . 4 | 7 . . |
 | 6 . . | . 9 . | . . . |
 | . . 4 | . 8 . | . . 1 |
 |-------+-------+-------|
 | . 6 . | . . . | . . . |
 | . . 8 | . 5 . | . . . |
 | 1 7 . | 8 3 . | . . 2 |
 +-----------------------+

 +-----------------------------------------------------+
 |  5    34   37   |  13   2    8    |  149  179  6    |
 |  24   9    237  |  13   6    5    |  8    17   47   |
 |  8    1    6    |  9    4    7    |  2    5    3    |
 |-----------------+-----------------+-----------------|
 |  3    2    9    |  5    1    4    |  7    6    8    |
 |  6    8    1    |  7    9   *23   |  45  *23   45   |
 |  7    5    4    |  26   8   *23+6 |  39  *23+9 1    |
 |-----------------+-----------------+-----------------|
 |  249  6    23   |  24   7    12   |  135  8    59   |
 |  249  34   8    |  246  5    126  |  13   137  79   |
 |  1    7    5    |  8    3    9    |  6    4    2    |
 +-----------------------------------------------------+
 # 42 eliminations remain

Although it's sometimes necessary to perform concurrent UR eliminations or "remember" candidates when sequentially performing UR eliminations, there are also times when it's not necessary to do either. Because of the strong link on <3> in [c6] and the strong link on <2> in [c8], performing either of your URs individually will lead, through basics, to the eliminations in the other UR.

Code: Select all
 [band 2] after r6c8<>2 and subsequent Singles
 |-----------------+-----------------+-----------------|
 |  3    2    9    |  5    1    4    |  7    6    8    |
 |  6    8    1    |  7    9   *3    |  45  *2    45   |
 |  7    5    4    |  26   8   *2+6  |  39  *3+9  1    |
 |-----------------+-----------------+-----------------|

Code: Select all
 [band 2] after r6c6<>3 and subsequent Singles
 |-----------------+-----------------+-----------------|
 |  3    2    9    |  5    1    4    |  7    6    8    |
 |  6    8    1    |  7    9   *3    |  45  *2    45   |
 |  7    5    4    |  26   8   *2+6  |  39  *3+9  1    |
 |-----------------+-----------------+-----------------|

My solver sees it as 4x eliminations:

Code: Select all
 r56c68  <23> UR via s-link              <> 2    r5c6,r6c8
 r56c68  <23> UR via s-link              <> 3    r5c8,r6c6

However, you still have a possible DP (*) remaining and it forces the strong link (6)r6c6 = (9)r6c8 -- which was present from the beginning. FWIW: I don't worry about "remembering" candidates to realize that a UR exists. The presence of <3> in r5c6,r6c8 and the presence of <2> in r5c8,r6c6 form an "X" in a rectangle of cells in [band 2], and is sufficient for my UR routine to decide that a UR exists.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: UR+2B/2SL

Postby surbier » Fri Feb 25, 2011 7:59 pm

Hi eleven, Hi daj95376,

You are right, I overlooked that one HUR2 eliminatiom destroyes the other strong link,
and that the UR+3B/2SL can be easily perfomed by one HUR1 followed by hidden singles.

On the other hand, there exists another precedences:
The UR6 (UR+2D/1SL) eliminations, which can be perfomed by two intersecting hidden unique rectanges of type 1 (UR+3C/2SL).
But the fact that UR6 got a name is maybe due to historical reasons.

However, you still have a possible DP (*) remaining and it forces the strong link (6)r6c6 = (9)r6c8 -- which was present from the beginning. FWIW: I don't worry about "remembering" candidates to realize that a UR exists. The presence of <3> in r5c6,r6c8 and the presence of <2> in r5c8,r6c6 form an "X" in a rectangle of cells in [band 2], and is sufficient for my UR routine to decide that a UR exists.

I see: you mean an avoidable rectangle of type 3, which does not result into any elimination.
surbier
2012 Supporter
 
Posts: 54
Joined: 06 June 2008

Re: UR+2B/2SL

Postby ronk » Sat Feb 26, 2011 12:15 am

daj95376 wrote:My solver sees it as 4x eliminations:

Code: Select all
 r56c68  <23> UR via s-link              <> 2    r5c6,r6c8
 r56c68  <23> UR via s-link              <> 3    r5c8,r6c6

Two strong links are requred to do either one of those two lines. Does that mean you are supporting surbier's proposal for a "UR+2B/2SL" type?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: UR+2B/2SL

Postby daj95376 » Sat Feb 26, 2011 1:28 am

ronk wrote:
daj95376 wrote:My solver sees it as 4x eliminations:

Code: Select all
 r56c68  <23> UR via s-link              <> 2    r5c6,r6c8
 r56c68  <23> UR via s-link              <> 3    r5c8,r6c6

Two strong links are requred to do either one of those two lines. Does that mean you are supporting surbier's proposal for a "UR+2B/2SL" type?

No. I had a terrible time trying to follow Mike Barker's classifications for URs. I still don't understand/remember/use them.

My comment was strictly an FYI on eliminations produced by strong links in the UR pattern. This approach lets me find eliminations in a large number of Mike's patterns. I'm planning to (eventually) get back to the few that I can't duplicate.

Regards, Danny
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: UR+2B/2SL

Postby David P Bird » Sat Feb 26, 2011 9:36 am

Using AICs there's no particular problem with this puzzle as two UR chains and one Avoidable Rectangle chain fall out quite nicely:

(6)r6c6 =[(23)UR:r56c69]= (9)r6c8 - (9=3)r6c7 => r6c6 <> 3
(4)r8c4 =[(26)UR:r68c46]= (1)r8c6 - (1=2)r7c6 - (2=6)r6c6 - (6=2)r6c4 => r8c4 <> 2
(6)r6c6 =[(23)AR:r23c68]= (9-3)r6c8 = (3)r8c8 - (3=4)r8c2 - (4=6)r8c4 => r8c6 <> 6

After tidying up, one final chain might be:
(9)r8c1 = (9-7)r8c9 = (7-4)r2c9 = (4)r2c1 => r8c1 <> 4

Not being a devotee of patterns, I don't know how these translate into UR type numbers though.

Surbier, URs and ARs both boil down to the same rule: Unless one of them holds a given, a rectangle of four cells in two boxes must contain at least three different digits.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Re: UR+2B/2SL

Postby surbier » Sat Feb 26, 2011 8:21 pm

@ David P Bird
I don't know how these translate into UR type numbers though.

The Mike Barker post considers URs with locked sets and
with strong links only between the UR cells, but not between candidates of other cells.
So far your mentioned AURs are not matched.

general:

There is one point that confuses me a little bit in the comments given above:

the strong link (6)r6c6 = (9)r6c8


I thought a strong link describes an exclusive OR, but
in the UR example given above the 6 in r6c6 does not exclude the 9 in r6c8 and vice-versa.
For me this is not a strong link, since both (the 6 and the 9) could be true to avoid the DP.
Only a further bi-value cell in row 6 with (69) would exclude the case '(6)r6c6 and (9)r6c8'
and would make the relation (6)r6c6 = (9)r6c8 really strong link.

I must say I know and practice AICs also with group nodes and with ALS, where
I did not encounter links like that.
I haven't looked deeper into AICs with URs (= AURs). Thinking twice I would say, that at most
one of a link provided by an UR, of which I think is not really strong, would be allowed within an AIC.
surbier
2012 Supporter
 
Posts: 54
Joined: 06 June 2008

Re: UR+2B/2SL

Postby JasonLion » Sat Feb 26, 2011 8:56 pm

A strong link exists when at least one of the two must be true. Another way to say that is when they can't both be false. In the logic of chains, strong links where both ends are true is allowed. In practice, most of the commonly found strong links are indeed XOR, but none of the logic behind the links/chains reasoning requires that. Another way to look at it is that a link which is both strong and weak is XOR, but neither strong or weak links require XOR. Weak links can both be false, and strong links can both be true.
User avatar
JasonLion
2017 Supporter
 
Posts: 625
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: UR+2B/2SL

Postby daj95376 » Sat Feb 26, 2011 11:26 pm

surbier wrote:I thought a strong link describes an exclusive OR, ...

paraphrasing Sudopedia wrote:an SL can be used for SI or WI, but a WL can only be used for WI

exception wrote:an SL in a UR/ALS structure can not always be used as WI
Last edited by daj95376 on Sat Feb 26, 2011 11:33 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: UR+2B/2SL

Postby David P Bird » Sat Feb 26, 2011 11:28 pm

Surbier, It appears that you have been using AICs with some misconceptions about strong inferences. This won't have mattered very much for simple puzzles where most strong inferences come from bilocals and bivalues because these candidates are also weakly linked, but for puzzles involving URs etc you then run into problems.

With this chain

(6)r6c6 =[(23)UR:r56c69]= (9)r6c8 - (9=3)r6c7 => r6c6 <> 3

to stop the (23)UR one or BOTH of (6)r6c6 and (9)r6c8 must be true. There is therefore the inference that they can't both be false, which as Jason says is the proper interpretation of a strong inference. There is a single strong inference between these candidates but notating it as =[(23)UR:r56c69]= shows the source of the inference in the square brackets.

Read the chain from left to right assuming (6)r6c6 is false and you'll find (3)r6c7 must be true.
Read the chain from right to left assuming (3)r6c7 is false and you'll find (6)r6c6 must be true
This proves the general theorem that nodes reached on strong links at either end of an AIC can't both be false.

Danny The Sudopedia entry isn't very well written because at that time no-one had identified any strong-only links as we have with deadly patterns. This was covered later here.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Re: UR+2B/2SL

Postby daj95376 » Sun Feb 27, 2011 5:52 am

David P Bird wrote:The Sudopedia entry isn't very well written because at that time no-one had identified any strong-only links as we have with deadly patterns. This was covered later here.

Thanks David for the later link. I missed the finer points when I first read that topic.

Regards, Danny
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: UR+2B/2SL

Postby surbier » Mon Feb 28, 2011 9:50 am

I got it.

I had same vague memory about that issue, in connection with
two perpenticularly oriented grop nodes within a 3x3 box
of a x-chain (empty rectangle).

I was certainly not the first and won't be the last who falls into this trap.

Thanks for the clear words.
surbier
2012 Supporter
 
Posts: 54
Joined: 06 June 2008

Re: UR+2B/2SL

Postby David P Bird » Tue Mar 01, 2011 11:25 am

Post Script

Thinking about the way to notate URs in AICs, perhaps it's better to use the complementary weak inference that opposite sides of the UR can't hold the same digit pair.

Strong (6)r6c6 =[(23)UR:r56c68]= (9)r6c8 - (9=3)r6c7 => r6c6 <> 3

Weak (6=23)r56c6 -[UR]- (23=9)r56c8 - (9=3)r6c7 => r6c6 <> 3

Using the weak inference, the candidates and cells involved are given in the adjacent nodes so don't need identifying in the in the square brackets. Apart from the couple of characters it saves, I think this representation is simpler to scan and absorb.

Now it's funny that the strong links used in each cell pair go back to being conjugate!
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Re: UR+2B/2SL

Postby daj95376 » Tue Mar 01, 2011 7:22 pm

David P Bird wrote:Thinking about the way to notate URs in AICs, ...

I give the reader credit for finding the UR once I identify the strongly linked candidates and cells.

Code: Select all
<23>UR(6=9)r6c68 - (9=3)r6c7 => r6c6 <> 3
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Next

Return to Advanced solving techniques