Almost Locked Sets xz-rule (doubly-linked)

Advanced methods and approaches for solving Sudoku puzzles

Postby ronk » Thu Apr 23, 2009 11:05 pm

PIsaacson wrote:
ronk wrote:Note that A is doubly-linked to both B and C.

I don't see how candidate 4 in A qualifies as an RCC peer of all the 4s in either B or C? But a really interesting set of ALSs regardless of how they are linked.

As of now, I don't really understand it either, but somehow covers 4r1 and 4r8 probably work together. (Maybe Allan can explain it.) Too unconventional perhaps, but my other examples look way too much like continuous loops of bivalues.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby aran » Fri Apr 24, 2009 1:38 am

Allan thanks indeed for the triple dual-linked ALS.
Paul that was an interesting structure.
A feature in your example (or so it seemed to me) was that re-covering the original base could produce all of the elims except the 2s in c1 : while to reach those the base had to be reduced.
It does look to me more and more as if sets and cover is the simplest way to deal with all these eliminations.

As for Ronk's example that was positively intriguing for a variety of reasons :
1. the ease with which it can be seen in base/cover terms (including the r1/b3 switch for 4r1c78)
2. the increased difficulty is seeing how those same eliminations resulted from the nice loop (and even in seeing the loop)
3. the yet greater difficulty in seeing it as a dual-linked set of 3 ALS.

Here is how I reckon it :
loop
4r8c2=6r8c2-6r8c78=>2 locked sets=>4r1c78 and 4r8c78 (being the only 4s in the locked sets) must be in Xwing formation=>4 over r8c78=>-4r8c2

dual linked ALS
6r8c2 (set A) : RCC with 6r8c7 (set B) and RCC with r8c8 (set C)
4r8c2 (set A) =>not 4 (r8c78)=>6 is true over r8c78 (if not : =>sets B and C locked, and since not 4r8c78=>4r1c7 and 4r1c8 : impossible).
Hence 4r8c2 (set A) is weakly linked to the other 6 (the false one) in r8c78 (we don't know which) ie : 4 setA is weakly linked on 6 to one of set B or set C.
Suppose set B=>set B locked (since 6 absent)=>4r1c7 is assigned=>false4r1c8 and since 6r8c8=>no place for 4 is set C=>4 set A is weakly linked on 4 to set C.
Thus the dual-linking is established.
As I said, base/cover looks simple compared to the rest:)
aran
 
Posts: 334
Joined: 02 March 2007

Postby Allan Barker » Fri Apr 24, 2009 5:44 am

ronk wrote:
PIsaacson wrote:
ronk wrote:Note that A is doubly-linked to both B and C.

I don't see how candidate 4 in A qualifies as an RCC peer of all the 4s in either B or C? But a really interesting set of ALSs regardless of how they are linked.

As of now, I don't really understand it either, but somehow covers 4r1 and 4r8 probably work together. (Maybe Allan can explain it.) Too unconventional perhaps, but my other examples look way too much like continuous loops of bivalues.


Ronk's description:
View 1) as three ALSs, the ALSs are r8c2 (A), r1348c7 (B) and r1348c8 (C). Note that A is doubly-linked to both B and C.
View 2) as one AALS and two ALSs, the AALS is r8c278 ... and the two ALSs are r134c7 and r134c8.


In my last post, I explained that in view 2, the two redundant digit 1 RCCs restrict digit 1 to at most 2 of the 3 A*LS. When the two redundant RCCs are combined, they fulfill the role of one RCC.

In view 1, the digit 4 does exactly the same. The three possible digit 4s in three ALS are restricted to at most two by the redundant digit 4 RCCs.

From these examples, it seems the RCC concept extends nicely to multiple ALS, and, oh, no!, has the same meaning as "reduced cover constraints",:!:
.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby aran » Fri Apr 24, 2009 10:53 am

Allan Barker wrote:
Ronk wrote:View 1) as three ALSs, the ALSs are r8c2 (A), r1348c7 (B) and r1348c8 (C). Note that A is doubly-linked to both B and C.
View 2) as one AALS and two ALSs, the AALS is r8c278 ... and the two ALSs are r134c7 and r134c8

In my last post, I explained that in view 2, the two redundant digit 1 RCCs restrict digit 1 to at most 2 of the 3 A*LS. When the two redundant RCCs are combined, they fulfill the role of one RCC.

In view 1, the digit 4 does exactly the same. The three possible digit 4s in three ALS are restricted to at most two by the redundant digit 4 RCCs

Allan
Just to be clear about your use of the term "redundant digit 4 RCCs".
I take it you mean :
- it can be shown that the 4s cannot occur three times in the three sets => one of them is "redundant"
and to occur twice and not thrice =>"restricted".
Then finally since :
6 candidate in all 3 ALS can only occur once at most
4 candidate in all 3 ALS can only occur twice at most.
=>d-links all round.
aran
 
Posts: 334
Joined: 02 March 2007

Postby Allan Barker » Fri Apr 24, 2009 4:44 pm

Aran wrote:Just to be clear about your use of the term "redundant digit 4 RCCs".
I take it you mean :
- it can be shown that the 4s cannot occur three times in the three sets => one of them is "redundant"
and to occur twice and not thrice =>"restricted".
Then finally since :
6 candidate in all 3 ALS can only occur once at most
4 candidate in all 3 ALS can only occur twice at most.
=>d-links all round.

Your thinking is correct. Redundant came from the idea that the digit 4 is redundant between rows 1 and 8, which means digit 4 does not make conventional RCCs. But digit 4 is restricted because it can occur only twice in three ALS. In effect, I have expanded the definition of an RCC as A digit which cannot be present in 2 ALS at the same time. to:

A distributed RCC A digit which cannot be present in N ALS N times

Note: The definition for RCC above is from the Sudopedia definition of a "Restricted Common" .
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby aran » Sat Apr 25, 2009 11:41 pm

Allan Barker wrote:In effect, I have expanded the definition of an RCC as A digit which cannot be present in 2 ALS at the same time. to:
A distributed RCC A digit which cannot be present in N ALS N times

Allan
It might be an idea to include in the definition that the total RCC presence or count=N (as in the "46" example : 1*6+2*4=3, arithmetic on a par with your recent 6+6=7:) ).
Another feature of d-l ALS whatever their number is that the RCCs operate as a nice loop all on their own.

To return to a point I made earlier :
the base/cover approach seems
- simpler than the d-l ALS approach
- stronger.
Which is a bit...disappointing...
If we take recent examples :
Ronk's "46" example (46 13746 12546).
- the base/cover approach was much easier to read, and all the eliminations fell out without any fuss
- with d-l ALS approach, first of all, establishing that "46" could occupy at most 3 cells involved some work, then making some of the eliminations involved more work eg the 4s in r1 : to eliminate them under d-l logic one had to show that if true they eliminated 2 4s, hence false.
Fair enough, but there's gymnastics in all of that, and none in the base/cover approach.
Paul's most recent example where the RCCs are in xy yz zx formation : began with a d-l approach from which only 7 eliminations resulted, then 8 more from a base/cover approach on the same base, and a further 2 with a reduced base.
In fact the 15 (7+8) would result from a base/cover approach applied straight away.
(I can get to the 15 within d-l logic using that trick I once mentioned about getting a contradiction=>false for anything which if true would bring about a 3rd RCC. But that was more gymnastics).
At this moment, it might look as if 2 ALS d-linked may be the optimum structure for a d-l approach ("easy" to see...once seen, and probably produces (almost) equivalent eliminations to a base/cover approach) but that once into 3 or more ALS base/cover is better.
aran
 
Posts: 334
Joined: 02 March 2007

Postby PIsaacson » Sun Apr 26, 2009 10:49 pm

Code: Select all
From the top1465 #2:
708000300000201000500000000040000026300080000000100093090600004000070500000000000

+------------------------+----------------------+-----------------------+
| 7      (126)   8       | 459    4569   4569   | 3       1456    1259  |
| (469)  (36)    (3469)  | 2      34569  1      | (4679)  45678   5789  |
| 5      (1236)  12469-3 | 78     3469   78     | 12469   146     129   |
+------------------------+----------------------+-----------------------+
| 189    4       1579    | 3579   59     3579   | 18(7)   2       6     |
| 3      (1267)  12679   | 479    8      2469   | 14(7)   145(7)  15(7) |
| 268    25678   2567    | 1      2456   24567  | 48(7)   9       3     |
+------------------------+----------------------+-----------------------+
| 128    9       12357   | 6      125    2358   | 127     1378    4     |
| 12468  12368   12346   | 3489   7      23489  | 5       1368    1289  |
| 12468  135678  1234567 | 34589  12459  234589 | 12679   13678   12789 |
+------------------------+----------------------+-----------------------+

1 (1 29 Candidates, Raw Rank = 6 (linksets - sets)
     8 Sets = {2N1 1235N2 2N3 2N7 7B6}
     14 Links = {469r2 7r5 126c2 7c7 456n7 5n8 5n9 3b1}
     1 Elimination --> =>
     r3c3<>3

When considered as a doubly-linked ALS 1 r2c1237 -3|7b6- r1235c2, the following eliminations resulted:
     r89c2<>1, r68c2<>2, r3c3<>3, r2c58<>4, r2c58<>6, r689c2<>6, r2c59<>9


This was discovered as a Death Blossom with stem cell(s) 7b6 ALS[1] -7- r2c1237.<n34679> ALS[2] -7- r1235c2.<n12367> => r3c3<>3

I was dismayed that it was not considered a doubly-linked ALS set since each ALS has a "peered" candidate 3, but my ALS engine did not consider 3 a valid RCC since cell r2c2 is common to both ALSs. However, when I forged ahead and modified my code to allow RCCs in overlapping cells, while this particular set produced valid doubly-linked eliminations, most newly found overlapping doubly-linked ALSs did not. Upon reflection, it seems that there must have been a good reason why I deliberately avoided RCC overlap, but otherwise did not restrict it for non-RCC containing cells.

Xsudo and base/cover logic both agree that r3c3<>3 is the only legal elimination from the DB with a single RCC 7, even though the others are permissible. So, I'm having a tough time believing the 13 additional eliminations were all the result of "good luck", but I can't come up with an explanation as to why they should be considered legal either. Is there some unusual configuration here of AALSs, ALSs and the like that account for these eliminations? Or is it really just fortuitous and coincidental circumstance?
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby aran » Mon Apr 27, 2009 12:37 am

PIsaacson wrote:
Code: Select all
From the top1465 #2:
708000300000201000500000000040000026300080000000100093090600004000070500000000000

+------------------------+----------------------+-----------------------+
| 7      (126)   8       | 459    4569   4569   | 3       1456    1259  |
| (469)  (36)    (3469)  | 2      34569  1      | (4679)  45678   5789  |
| 5      (1236)  12469-3 | 78     3469   78     | 12469   146     129   |
+------------------------+----------------------+-----------------------+
| 189    4       1579    | 3579   59     3579   | 18(7)   2       6     |
| 3      (1267)  12679   | 479    8      2469   | 14(7)   145(7)  15(7) |
| 268    25678   2567    | 1      2456   24567  | 48(7)   9       3     |
+------------------------+----------------------+-----------------------+
| 128    9       12357   | 6      125    2358   | 127     1378    4     |
| 12468  12368   12346   | 3489   7      23489  | 5       1368    1289  |
| 12468  135678  1234567 | 34589  12459  234589 | 12679   13678   12789 |
+------------------------+----------------------+-----------------------+

Xsudo and base/cover logic both agree that r3c3<>3 is the only legal elimination from the DB with a single RCC 7, even though the others are permissible. So, I'm having a tough time believing the 13 additional eliminations were all the result of "good luck", but I can't come up with an explanation as to why they should be considered legal either. Is there some unusual configuration here of AALSs, ALSs and the like that account for these eliminations? Or is it really just fortuitous and coincidental circumstance?

By permissible I'm taking you to mean that they turn out to be correct.
For the moment I don't see any of those eliminations forced by the structure under examination, other than <3>r3c3.
One can note that all of those "permissibles" if true force the weak-link : those in c2 force the 7 in c2, those in r2 force the 7 in r2 : since the 7s are weakly linked, it follows that at least half of those permissibles must indeed be false.
So I reckon it's 50% structure, 30% fortuity and 20% serendipity:)
aran
 
Posts: 334
Joined: 02 March 2007

Postby PIsaacson » Mon Apr 27, 2009 1:03 am

Aran,

Thanks for confirming that sometimes, the coin lands on its edge. For a moment, I thought I had found tons of new doubly-linked ALSs. Then reality came crashing in...

Cheers,
Paul
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Re: Almost Locked Sets xz-rule (doubly-linked)

Postby Luke » Thu Apr 26, 2012 3:55 am

"Restricted Uncommons"

Here's another "restoring the record after the crash" post.

This thread seems to be a good place for this restoration in that the
technique employed is not just a doubly-linked ALS. It is also
an example of a twist on the technique that I have not seen expressed
before or after this.

Of course, I do not have the original thread to reproduce, only my
notes. I do have an accurate copy of the PM at the point of discussion,
but not the givens. I did not record the original poster's handle, but
he was stuck at the position below.

The original thread was posted in November 2009 in the Sudoku Players'
Forum under the header "Tricky?" in the "Help With Particular Puzzles"
sub-forum. One of those "What now?" type posts.

On Nov 11, 2009 aran responded with doubly-linked ALS in which
one of the restricted common candidates was a weakly linked AIC. He called
it at one point a "generated" RCC and at another a "developed" RCC. This
was nothing new and is actually discussed earlier in this (ronk's) thread.

Now to the point!

During the discussion aran pointed out that "developed" RCCs do not have
to be the same value
, only weakly linked (as all RCCs are anyway.)
He somehow came up with an example using the "Tricky" puzzle and half-
jokingly called it a "restricted uncommon."

Code: Select all
 *--------------------------------------------------------------------*
 | 68-9   7      29     | 168    5      14     | 24     3      2469   |
 | 3      89     4      | 2678   28     67     | 5      269    1      |
 | 16     5      12     | 3      246    9      | 247    8      2467   |
 |----------------------+----------------------+----------------------|
 | *2458  348    7      | 68     1      35     | 9      2456   23468  |
 | *59    1     #359    | 4      678    2      | 378    56     3678   |
 | *2458  348    6      | 78     9      35     | 1      245    23478  |
 |----------------------+----------------------+----------------------|
 | *149   6     #139    | 5      234    8      | 234    7      2349   |
 | 7      349    8      | 12     234    14     | 6      249    5      |
 | *45    2     #35     | 9      67     67     | 348    1      348    |
 *--------------------------------------------------------------------*

* Set A (124589)r45679c1
# Set B (1359)r579c3

1st RCC (1)r7c1 -(1)r7c3
2nd RCC (8)r46c1-(9)r57c3

Elim: r1c1<>9

The full AIC for the 2nd RCC :
(8)r46c1-r1c1=r2c2-(8=2)r2c5-(2=34)r78c5-(4)r8c6=r1c6-(4=2)r1c7-(2=9)r1c3-(9)r57c3

The elim is not significant, as it was just a demonstration of the possibilities.
If there are other examples of this usage I'd be keen to see them.
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Re: Almost Locked Sets xz-rule (doubly-linked)

Postby ronk » Thu Apr 26, 2012 3:26 pm

Sorry Luke451, I don't have an interest in pursuing this, but perhaps someone else does. Once derived inferences, particularly weak inferences, are permitted within simple patterns, the pattern definition becomes seriously diluted. IMO the suggested term "restricted uncommons" is strong evidence of this.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Almost Locked Sets xz-rule (doubly-linked)

Postby daj95376 » Thu Apr 26, 2012 3:36 pm

[Withdrawn: I missed something!!! You can always force-feed a goose to make its liver larger. But, it's still a goose.]
Last edited by daj95376 on Thu Apr 26, 2012 5:19 pm, edited 2 times in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Almost Locked Sets xz-rule (doubly-linked)

Postby aran » Thu Apr 26, 2012 4:36 pm

[Withdrawn : response to daj's withdrawn post]

Just for the record, the object of the exercise, referred to above by Luke, was to consider a variation on a theme, the theme being restricted commons in a DL-ALS setting, and the variation being to push the logic from x-x to x-y, this latter necessarily involving an AIC.

Of course with a different prism, variation on a theme can be seen as dilution of a pattern.
De gustibus non disputandum est.
aran
 
Posts: 334
Joined: 02 March 2007

Previous

Return to Advanced solving techniques