Almost Locked Sets xz-rule (doubly-linked)

Advanced methods and approaches for solving Sudoku puzzles

Postby aran » Sun Apr 19, 2009 1:04 pm

ronk wrote:
aran wrote:I was however astonished by your statement which strikes me as a failure.
...
blinkered thinking ... staggering ... extraordinary

aran, nice rant, but take the rants elsewhere.

As old as the hills to deal with the form and not the substance...
aran
 
Posts: 334
Joined: 02 March 2007

Postby ttt » Sun Apr 19, 2009 1:20 pm

:::Off Topic:::
aran wrote:
ronk wrote:
aran wrote:I was however astonished by your statement which strikes me as a failure.
...
blinkered thinking ... staggering ... extraordinary

aran, nice rant, but take the rants elsewhere.

As old as the hills to deal with the form and not the substance...

I don’t know how I and other can learn from this “Advanced Solving Technique”:D

ttt
ttt
 
Posts: 185
Joined: 20 October 2006
Location: vietnam

Postby aran » Mon Apr 20, 2009 10:48 am

For the benefit of any who may be following this thread, but possibly not fully comprehending, I think it might well be appreciated if clarity on a small number of points was established, all with respect to dual-linked ALS
1. I have pointed out (but had it been another, I would be making the same point) that with very simple logic, the eliminations can immediately be noted.
I did refer to this approach as child's play, not at all intended as exaggeration.
That is : without recourse to ALS chains, or ALS nice loops, or base sets and different rank 0 coverings, one gets there faster and simpler.

For those who are continuing with a more complicated approach, and discussing complexifying definitions such as
Doubly-linked ALS xz-rule: When ALS1 in unit U1 (row, column, box, sector, house) and ALS2 in U2 are doubly-linked by RCC1 in U3 and RCC2 in U4, except for the candidates of ALS1 and ALS2, the following eliminations are valid:

* in U1, all non-RCC-like candidates of ALS1,
* in U2, all non-RCC-like candidates of ALS2.
* in U3, all RCC1-like candidates, and
* in U4, all RCC2-like candidates.

Should ALS1 (or ALS2) be confined to a box-line intersection, U1 (or U2) is a box. "Non-RCC-like" means both RCC1 and RCC2

can you expian the need for that ? or at least agree that yes, from a manual solver's point of view, it is all unnecessary but of interest from a programming perspective.
Otherwise I believe there is or will be confusion where there should be enlightenment.
2 Why is there is continuing reference to ALS-xz when that technique would apply merely to the (generally speaking) minor eliminations (ie anything which for a given RCD sees all its occurences it in both sets) ? I find this a misnomer and must assume that it is confusing.
aran
 
Posts: 334
Joined: 02 March 2007

Postby ronk » Mon Apr 20, 2009 2:51 pm

PIsaacson wrote:
Code: Select all
+-------------------------+---------------+-------------------------+
| 369   35679    3679     | 2   1567  137 | 8        679   4        |
| 48-2  4567     2678     | 9   5678  47  | 3        267   1        |
| 1     34679    236789   | 48  678   347 | 2579     2679  2579     |
+-------------------------+---------------+-------------------------+
| 5     479      789-2    | 3   279   6   | 2479     1     2789     |
| (28)  13679    13679-28 | 15  4     279 | 25679    (38)  25679-38 |
| (24)  13679-4  13679-2  | 15  279   8   | 25679-4  (34)  25679-3  |
+-------------------------+---------------+-------------------------+
| 79    8        4        | 6   3     5   | 1        279   279      |
| 369   1369     1369     | 7   289   249 | 469      5     3689     |
| 3679  2        5        | 48  189   149 | 4679     48-3  36789    |
+-------------------------+---------------+-------------------------+

From one perspective: ALS A r56c1 {248} -48- ALS B r56c8 {348}

The NRL {2} in ALS A eliminates r456c3<>2 in cover b4 as well as r2c2<>2 in c1
The NRL {3} in ALS B eliminates r56c9<>3 in cover b6 as well as r9c8<>3 in c8

I don't know if this is a good example because it can be viewed in several alternate ways as an ALS/XY loop, or as r5c18-23-r6c18 or r56c1-48-r56c8 DL ALS-XZs.

I think the most appropriate term for this pattern is xy-ring, as Jeff AFAIK coined on his Forcing chains: Terminology and Definition thread (near the end of the post). As you've noted, the xy-ring is subsumed by the doubly-linked ALS xz rule.

PIsaacson wrote:From the r5c18-23-r6c18 POV, there are no multi-cover NRL eliminations.

"Multi-cover" applies to the RCC candidates as well. IOW the two cover sets {8r5 4r6 2c1 3c8} and {8r5 4r6 2b4 3b6} apply no matter how the four bivalues are paired to make ALSs.

PIsaacson wrote:I thought it was an interesting little example since it's a really simple 4 cell structure with 11 eliminations.

Here is another, also with 11 eliminations, where "multi-cover" does not apply.
Code: Select all
top1465 #1357
7..9.2..53.....9.7.4.7...8....2.........1..3...46..21..1.......2.7...6...3...1..8

After SSTS
 7     *68       18-6  | 9    348-6  2     | 134  *46      5
 3      256-8    2568  | 1    4568   4568  | 9     26-4    7
 569    4        12569 | 7    356    356   | 13    8       23
-----------------------+-------------------+------------------
 1      5679-8   3     | 2    45789  45789 | 578   57      46
 568    25679-8  2568  | 458  1      45789 | 578   3       46
 58     57-8     4     | 6    3578   3578  | 2     1       9
-----------------------+-------------------+------------------
 45689  1        5689  | 458  267    67    | 3457  2579-4  23
 2     *58       7     | 3    489-5  489-5 | 6    *45      1
 4569   3        569   | 45   267    1     | 457   2579-4  8

As an xy-ring in NL notation: - r1c2 -6- r1c8 -4- r8c8 -5- r8c2 -8- r1c2 - continuous loop

 ==> r1c35<>6, r279c8<>4, r8c56<>5, r2456c2<>8
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Luke » Tue Apr 21, 2009 12:06 am

Once again, thanks to everyone for reiterating the basics on this topic. I was curious because I've noticed references elsewhere to its power and usefulness, once identified. Don said, "Would love to believe that some of these as described above could be found manually." At the very least, it's another very interesting arrow to have in one's quiver.

When I asked if "doubly" and "dually" linked meant the same thing, I asked the wrong question. What I really was wondering:
Is a "Doubly-linked ALS-xz" the same thing as a "Dual-linked ALS?"
It seems obvious there is a difference, but the distinction escapes me so far. Here are some of the references from earlier in this thread noting the distinction :
PIsaacson wrote:I keep forgetting that a doubly-linked ALS xz is a specific form of a dual-linked ALS set.

PIsaacson wrote:I'm of the opinion that dual-linked ALSs are a unique category. An ALS-xz that has 2 RCDs is simply one method of forming a dual-linked ALS.

I hate to make guesses because I'm good at guessing wrong, but there must some use for the "other common" or there'd be no need to mention "Z." However, several have pointed out this:
hobiwan wrote:....the main difference between a Standard ALS-XZ and a Doubly Linked ALS-XZ, is that the latter doesn't need a Z (and that is a rather large difference IMO).
If no Z is needed, why is it a "Doubly-linked ALS-xz?"

I suspect the answers lie in the fact that this discussion was renewed in recent months to explore the implementation of the technique into solving programs. I for one found the alternative approach presented by aran to be simple and immediately understandable from the RJ perspective (Regular Joe.) Because of this I think it deserves a place in the discussion. I don't know if that approach can be coded into a computer program, though!
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby PIsaacson » Tue Apr 21, 2009 12:45 am

Luke451 wrote:What I really was wondering: Is a "Doubly-linked ALS-xz" the same thing as a "Dual-linked ALS?"

It's just one type of dual-linked ALS. But that's just my perspective on this:

Take any two ALSs - say ALS A and ALS B. Ignore for now the exact details, but suppose they share 2 RCDs - call them RCD 1 and RCD 2. Then that constitutes a dual-linked ALS.

The doubly linked ALS XZ is just one method of "linking" the two RCDs. In this case, it's because all the RCD 1s in both ALS A and ALS B can "see" each other (are peers of) AND all the RCD 2s in both ALS A and ALS B can likewise "see" each other. But that's not the only way to connect the RCDs.

In a Death Blossom, for example, one RCD can be linked by a bi-local cell while the second is a peer relationship. In a long ALS chain, the start/end ALSs can be ALS A and ALS B with the intermediate ALS chain providing a mechanism for linking one RCD, while the second is, once again, a peer relationship. There are many potential methods of connecting the RCDs and I'm currently debugging several -- almost fish/ERs/AURs are in the works.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby ronk » Tue Apr 21, 2009 12:56 am

Luke451 wrote:When I asked if "doubly" and "dually" linked meant the same thing, I asked the wrong question. What I really was wondering:
Is a "Doubly-linked ALS-xz" the same thing as a "Dual-linked ALS?"
It seems obvious there is a difference, but the distinction escapes me so far.

Escapes me too. Has anyone even defined "dual-linked ALS"? If so, a link would be appreciated.

[edit: I now see PIsaacson's recent post immediately above.]

Luke451 wrote:
hobiwan wrote:....the main difference between a Standard ALS-XZ and a Doubly Linked ALS-XZ, is that the latter doesn't need a Z (and that is a rather large difference IMO).
If no Z is needed, why is it a "Doubly-linked ALS-xz?"

'x' and 'z' are merely placeholders. Whether or not doubly-linked, 'x' is a restricted-common-candidate (RCC). In continuous loops, the doubly-linked case, 'z' is also a RCC; in discontinuous loops it is not.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ronk » Tue Apr 21, 2009 1:40 pm

hobiwan wrote:Nice definition, although I still think the restriction to boxes is neither necessary nor intuitive (I do understand where it comes from).

I agree ... and have revised my earlier post.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby aran » Tue Apr 21, 2009 2:31 pm

ronk wrote:
Luke451 wrote:
hobiwan wrote:....the main difference between a Standard ALS-XZ and a Doubly Linked ALS-XZ, is that the latter doesn't need a Z (and that is a rather large difference IMO).
If no Z is needed, why is it a "Doubly-linked ALS-xz?"

'x' and 'z' are merely placeholders. Whether or not doubly-linked, 'x' is a restricted-common-candidate (RCC). In continuous loops, the doubly-linked case, 'z' is also a RCC; in discontinuous loops it is not.


Wide of the mark.
And again failing to deal with a point.
z is not a mere place-holder in ALS-xz.
It is the external elimination candidate which if true generates a contradiction by eliminating z from both ALS
That is : it locks both sets but the RCD then causes an insurmountable problem. So the external z is false.
That's the mechanism.
Express that any way you wish : as a chain : z(set A)=(set A locked inc RCD)-RCD(set B)=(set B locked inc z) :=> <z external>.
Hence the key features of z in ALS-xz are :
- occurs in both sets
- any external z which sees both is false.
The end result is generally the elimination of a single candidate.
All of that can also be called a Rank 1 structure using Allan Barker's terminology.

Dual-linked ALS are uterly different.
1. they are Rank 0 structures ie fundamentally different
2. there are often multiple eliminations
3. the vast majority of those (generally speaking) need only see or be connected to a candidate in one ALS alone


Are you being disingenuous ?
aran
 
Posts: 334
Joined: 02 March 2007

Postby aran » Tue Apr 21, 2009 2:42 pm

Luke451 wrote:What I really was wondering: Is a "Doubly-linked ALS-xz" the same thing as a "Dual-linked ALS?"

Paul, what you are saying in reply to Luke quoted above is that the key thing is to (seek to) establish two RCDs between the ALS.
Once we have that, we have all the power of this often magnificent rank 0 structure.
If the links are immediate, call that dual-linked .
If the one or both links is established by a chain call that double-lnked.
Or else the other way round.
An alternative would be to stick to one term (or use them interchangeably as I do at present)
One could then call anything which requires a chain to establish either or both RCDs as a Kraken Dual-linked ALS (in line with use of that term in other contexts).
aran
 
Posts: 334
Joined: 02 March 2007

Postby hobiwan » Tue Apr 21, 2009 3:41 pm

aran wrote:
ronk wrote:
Luke451 wrote:
hobiwan wrote:....the main difference between a Standard ALS-XZ and a Doubly Linked ALS-XZ, is that the latter doesn't need a Z (and that is a rather large difference IMO).
If no Z is needed, why is it a "Doubly-linked ALS-xz?"

'x' and 'z' are merely placeholders. Whether or not doubly-linked, 'x' is a restricted-common-candidate (RCC). In continuous loops, the doubly-linked case, 'z' is also a RCC; in discontinuous loops it is not.


Wide of the mark.
And again failing to deal with a point.
z is not a mere place-holder in ALS-xz.

It is perfectly possible too see one of the RCDs as X and the other one as Z (and then swap them). In fact this method is still part of the definition of ALS-XZ on Sudopedia.

Of course doing that would cause you to miss lots of eliminations (as anybody here knows).

That saying: Since a Doubly Linked ALS-XZ does anything a normal ALS-XZ does plus more, I do see it as an extended form of ALS-XZ (the weak links on the RCDs are the normal ALS-XZ part, the Locked Sets are the addition).

hobiwan wrote:the latter doesn't need a Z

Since we have come to pretty much splitting hairs in this part of the discussion, I should more precisely have written:
the latter doesn't need a Z in addition to the two RCDs who can each play the role of Z
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby aran » Tue Apr 21, 2009 7:25 pm

Hobiwan
Firstly thanks for your reply.
It is perfectly possible too see one of the RCDs as X and the other one as Z (and then swap them). In fact this method is still part of the definition of ALS-XZ on Sudopedia

Here is the Sudopedia reference
Note that it doesn't matter whether or not Z is also restricted common to A and B, except that if Z is also restricted common, we can remove X as a candidate of any cells outside A and B that can see all the X candidates in both A and B. That is, each candidate, in turn, gets to play the role of restricted common, giving us the chance to eliminate the other candidate from outside cells

This author has seen that if Z is a second RCD, then he can play the same trick with X the first RCD.
In other words he has had a glimpse of what dual-linked ALS can do.
But he hasn't seen the major part, which concerns eliminations that require sight of one set only.
Put another way, he hasn't got out of rank 1 mode.
As you say
Of course doing that would cause you to miss lots of eliminations (as anybody here knows)

When however you say
I do see it as an extended form of ALS-XZ
and
Since we have come to pretty much splitting hairs in this part of the discussion

well if I did agree, I wouldn't be expressing myself as strongly as I have of late...
I have too much respect for dual-linked ALS to describe them as extensions of ALS-xz.
I don't think of the computer as an extended form of abacus:)
One amazing thing about dual-linked ALS is that they are both powerful (or can be) and extremely simple, which one would never gather from this thread...
I'm not hair-spitting, I'm trying to draw the curtains and let in some light.
aran
 
Posts: 334
Joined: 02 March 2007

Postby Luke » Tue Apr 21, 2009 9:12 pm

PIsaacson wrote:There are many potential methods of connecting the RCDs and I'm currently debugging several -- almost fish/ERs/AURs are in the works.

I think I now see at least part of what your project encompasses.

The links don't have to be "immediate" between the restricted commons. In other words, they don't have to see one another directly. The RCDs will perform the same function if they are linked by a chain or a structure. I'm getting murky now, but the chain or structure would have to infer that both RCDs can't be true, right? In other words, weakly linked .

The possible scenarios start to get mind-boggling. I imagine one RCD could be immediately linked, while the other is connected by a chain or structure. Maybe both RCDs could have such extended connections. One could be linked by a chain, the other by an ER, and on and on with endless possibilities. Not to mention, sets up to six candidates per set.....why does my head hurt ?:)

Does anyone have an example from an actual puzzle of, say, a chain linking one of the RCDs?

Has this idea been applied to plain-ole ALS-xz?
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby PIsaacson » Tue Apr 21, 2009 9:47 pm

Luke451,

I've been looking at Kraken structures based on Aran's suggestion for calling ALSs with RCD(s) linked by anything other than direct peer relationships, Kraken dual-linked ALSs.

I found this example by Mike Barker: http://forum.enjoysudoku.com/viewtopic.php?p=34939#p34939

The example can be viewed as a newly titled Kraken dual-linked ALS r8c7 -2(r13c7|r13c9) 9- ALS r69c9 with the RCD 9 a direct peer relationship and the RCD 2 a "Kraken" link via the box/line constraints of 2b3. The additional eliminations from the dual-linked formation were not presented in the original explanation. Prior to Aran's comments, I would have called this a Death Blossom by declaring the 2b3 strong link the stem cells.
Code: Select all
900000050320000800010000030009000000002814395103070600200490160004105070001630500

+---------------+------------------+------------------------+
| 9   47   678  | 237  2468  12368 | 47(2)   5     167-4(2) |
| 3   2    567  | 579  456   169   | 8       14    1679-4   |
| 45  1    5678 | 279  2568  2689  | 479(2)  3     679(2)   |
+---------------+------------------+------------------------+
| 45  458  9    | 235  256   236   | 47-2    1248  17-24    |
| 67  67   2    | 8    1     4     | 3       9     5        |
| 1   458  3    | 259  7     29    | 6       28    (24)     |
+---------------+------------------+------------------------+
| 2   357  57   | 4    9     78    | 1       6     38       |
| 68  369  4    | 1    28    5     | (29)    7     38       |
| 78  79   1    | 6    3     278   | 5       24    (249)    |
+---------------+------------------+------------------------+

Almo 0 Candidates, Raw Rank = 8 (linksets - sets)
     4 Sets = {8N7 69N9 2B3}
     12 Links = {2479c7 24c9 134n7 13n9 9b9}
     5 Eliminations --> c9) =>
     r1c9<>4, (4c9) => r2c9<>4, (2c7*4n7) => r4c7<>2, (2c9) => r4c9<>2, (4c9) => r4c9<>4

Luke451 wrote:I'm getting murky now, but the chain or structure would have to infer that both RCDs can't be true, right? In other words, weakly linked.

I believe it requires a strong link. But I could be wrong, so don't take me as an authority on this...

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

Postby ronk » Tue Apr 21, 2009 10:51 pm

PIsaacson wrote:I've been looking at Kraken structures based on Aran's suggestion for calling ALSs with RCD(s) linked by anything other than direct peer relationships, Kraken dual-linked ALSs.

I found this example by Mike Barker: http://forum.enjoysudoku.com/viewtopic.php?p=34939#p34939

The example can be viewed as a newly titled Kraken dual-linked ALS r8c7 -2(r13c7|r13c9) 9- ALS r69c9 with the RCD 9 a direct peer relationship and the RCD 2 a "Kraken" link via the box/line constraints of 2b3.

Sorry, there's no kraken. It's a simple continuous loop with one ALS ... well two, I suppose, if one insists on considering the r8c7 bivalue as an ALS.

- r8c7 -2- r13c7 =2= r13c9 -2- als:(r69c9 =2|4|9= r9c9) -9- r8c7 - continuous

The hallmark of a kraken deduction is at least one multi-inference. I see none. Strictly speaking, an ALS is itself a multi-inference pattern but it is not (usually) counted as such.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to Advanced solving techniques

cron