The New Sudoku Players' Forum

[ronk]

... an interesting ALS loop that acts like a dual-linked, excuse me, a doubly-linked set ...

re 'doubly':

Bob Hanson (not me) first used the 'doubly' term on his almost-locked sets -- doubly weakly linked thread way back in Dec 2005.

BTW since you're a programmer you must be familiar with some of the works of Donald E. Knuth. Tell me, does he use the term 'doubly-linked list' or 'dual-linked list'?

re 'restricted common candidate' (RCC):

bennys introduced the concepts (and terms) of Almost locked sets xz rule and Almost locked sets xy wing rule back in Nov and Dec of 2005, respectively.

He wrote 'restricted common' and 'common candidate'. He didn't write 'restricted common digit' or even 'common digit'. Since then 'restricted common candidate' (RCC) has stuck for many of us here. But 3 years later you decided here that 'restricted common digit' (RCD) is better, even though AFAICT it means exactly the same thing.

[ronk]

Here is a three ALS deduction that has a little more meat on its bones. [edit: However, this example is not a continuous loop version -- a doubly-linked version -- of an ALS xy-wing.]

Code: Select all

6.9.....8...7.1...4.1.......98.6...4.2.....3..3....5...1.5...7.8...9..........2..

+---------------+-----------------------+------------------------+
| 6    57    9  | 23-4    235-4  235-4  |B(1347) C(1245)   8     |
| 23   58    23 | 7       458    1      | 469     469-5    569   |
| 4    578   1  | 69      2358   69     |B(37)   C(25)     2357  |
+---------------+-----------------------+------------------------+
| 157  9     8  | 123     6      2357   |B(17)   C(12)     4     |
| 157  2     46 | 1489    1457   45789  | 689-17  3        1679  |
| 17   3     46 | 12489   1247   2479   | 5       689-12   12679 |
+---------------+-----------------------+------------------------+
| 239  1     23 | 5       34     3468   | 4689    7        369   |
| 8   A(46)  57 | 123-46  9      237-46 |B(1346) C(1456)   135-6 |
| 39   46    57 | 13468   1347   34678  | 2       4689-15  13569 |
+---------------+-----------------------+------------------------+

TP13 26 Candidates, Raw Rank = 0 (linksets - sets)
     9 Sets = {8N2 1348N7 1348N8}
     9 Links = {4r18 6r8 137c7 125c8}
     15 Eliminations -->
     r1c456<>4, r8c469<>6, r8c46<>4, r69c8<>1, r29c8<>5, r5c7<>17, r6c8<>2

There is another rank 0 cover set {4r8 6r8 137c7 125c8 4b3} for added eliminations r2c78<>4.

When viewed as three ALSs, the ALSs are r8c2 (A), r1348c7 (B) and r1348c8 (C). Note that A is doubly-linked to both B and C. [edit: However, as noted above, this example is not a doubly-linked ALS xy-wing.]

When viewed as one AALS and two ALSs, the AALS is r8c278 ... and the two ALSs are r134c7 and r134c8. This would (I think) normally yield three RCCs for the AALS, but for some reason there are four here, with candidate <1> being repeated.

[Allan Barker]

When viewed as one AALS and two ALSs, the AALS is r8c278 ... and the two ALSs are r134c7 and r134c8. This would (I think) normally yield three RCCs for the AALS, but for some reason there are four here, with candidate <1> being repeated.

Nice catch and observation. The reason for the apparent extra RCC is:

Neither RCC (1)c7 or (1)c8 is an RCC by itself, at least when RCCs are defined as digits that cannot appear (be true) in 2 A*LS at the same time. However, RCC 1c7 and 1c8 combined do the job of a single RCC. This can be described a couple of ways.

1. The 2 combined RCCs prevent the digit 1 from appearing in all 3 A*LS at the same time, or.
2. The 2 combined RCCs are able to cover the digit 1 in all three A*LS.

The N-Way rule above is still correct but would require an additional rule for redundant RCCs to cover this case.

[DonM]

Further thoughts on terminology (since it is raised above): My view is that the best terminology is that which both causes the least confusion and is the most descriptive. Sometimes there is a collision between both goals. Thus, the doubly-linked thread has been around long enough such that introducing another term would cause, and already has caused, confusion, but in addition to that, 'doubly' does appropriately describe the structure (even though, as I've said, I like the sound of 'dual' better).

The term Kraken is another matter. Much as I like the originator of the term, my guess is that it has caused a lot of confusion because it has been applied to all sorts of structures that have no relationship to each other. How would someone trying to learn advanced solving possibly figure this out on their own. The term Kraken was first used to apply to the multi-inference Kraken/cell,row,column (what I prefer to call AAICs because its more descriptive), but very soon after, circa Aug-Sept 2006, was applied to various other entities, some of which are far 'simpler' than multi-inferences, but which, now given the Kraken moniker, imply complexity.

Take the Kraken fish: It's nothing more than a structure whereby an x-wing fin 'sees' the typical x-wing cec(s) thru a conjugate link. Either the x-wing being true or the fin being true will kill the target candidates. There must be a better name for this: Conjugate Finned X-wing? . But it's too late for that methinks. In any event, IMO, the preferred terminology for any future 'new' structures should be, as much as possible, descriptive of the structure for the benefit of the poor new solver trying to figure all these terms out.

[PIsaacson]

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.

[ronk]

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.

[aran]

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

[Allan Barker]

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",
.

[aran]

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.

[Allan Barker]

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" .

[aran]

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.

[PIsaacson]

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?

[aran]

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

[PIsaacson]

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

[Luke]

"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.