ALS chains with overlap/cannibalism

Advanced methods and approaches for solving Sudoku puzzles

Postby DonM » Wed Mar 25, 2009 6:56 am

PIsaacson wrote:The following is a 5 petal Death Blossom from the royle17 collection: Puzzle #9 royle17 36628 collection...


If only I could find something like that manually. I could be somebody, I could be a contender and not just a bum. (Quoting freely from a great movie.:) ).
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby StrmCkr » Wed Mar 25, 2009 7:15 am

"rocky"...."rocky"

don
edit: i was ...close but no cigar...

and if you managage to find them by hand

"adrain we did it" fits nicely too.
Last edited by StrmCkr on Wed Mar 25, 2009 4:48 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 673
Joined: 05 September 2006

Postby ronk » Wed Mar 25, 2009 7:17 am

DonM wrote:
ronk wrote:Mike Barker is the originator of the Death Blossom term. Would someone please provide a link to where Mike said the "stem" of a Death Blossom could be smaller than a tri-valued cell:?:

One could also ask for a link where Mike said it couldn't be smaller than a tri-value cell. Pending clarification from Mike himself, the bi-value cell example seems to have been accepted by no less than Ruud (if memory serves, he put up the Sudopedia example) and Andrew Stuart, who uses the 2nd bi-value example I posted above in his book...

Show me one example of where Mike Barker used a bivalue for the stem of a Death Blossom.

[edit: I found some examples. Mike seems to have used the Death Blossom term for a bivalued stem and Kraken Death Blossom for "stems" larger than a bivalue. My bad.]
Last edited by ronk on Wed Mar 25, 2009 3:52 am, edited 2 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby DonM » Wed Mar 25, 2009 7:29 am

StrmCkr wrote:"rocky"...."rocky"

don
its miss quoted ..(yes i know you said freely).close but no cigar...

and if you managage to find them by hand

"adrain we did it" fits nicely too.


Actually StrmCkr, it's Terry (Marlon Brando) from On The Waterfront: "I could have been a contender, I could have been somebody, instead of a bum which is what I am."
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby Luke » Wed Mar 25, 2009 7:30 am

DonM wrote:
Luke451 wrote:Here's another Death Blossom, but I prefer to see it as two hidden sets with a bivalue in between:
Code: Select all
 *-----------------------------------------------------------*
 | 2     3     1-4   | 6     9     457   | 15   *147   8     |
 | 457   156   9     | 48    578   3     | 156   2     567   |
 | 4578  568   456   | 2     1     45    | 9     34    367   |
 |-------------------+-------------------+-------------------|
 | 9     4     3     | 7     6     2     | 8     5     1     |
 | 6     25    25    | 1     3     8     | 7     9     4     |
 | 1     7     8     | 5     4     9     | 23    6     23    |
 |-------------------+-------------------+-------------------|
 | 358   568   7     | 48    2     145   | 156  *13    9     |
 | 58    9     26    | 3     58    17    | 4    *17    26    |
 | 345  *12   *124   | 9     57    6     |*23    8     257   |
 *-----------------------------------------------------------*



I see it, once again, as just a 3-set ALS Chain (aka ALS xy-wing rule) with a bivalue middle set at r9c7 whereby the restricted common 3 joins it with one set at r178c8 and restricted common 2 with the other set at r9c23. Thus those two flanking sets both 'see' the 4 at r1c3. Not sure why one would want to re-invent the wheel?:)

Edit: I find that looking on those structures as hidden sets just complicates things because IMO, they are operating as ALSs as part of an ALS chain. In my mind (and maybe only in my mind), I prefer to see hidden sets as the structure whereby an elimination can be made right away and an almost hidden set as that where an elimination could be made if not for one digit in the same house. That way, I can more easily keep what I view as ALSs separate from AHPs.

As Contender-Come-Lately I know I've no right to reinvent anything:) . This may be one of them "POPP" (Point Of Personal Preference) issues, because I know you're right in saying that this is an ALS chain.

It just seems easier to me to examine what contradictions I can force in the first and last legs of a chain without ever trying to be sure I've identified my restricted/other commons, or really ever even knowing that I've stumbled on a "Death Blossom."
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby PIsaacson » Wed Mar 25, 2009 7:56 am

ronk wrote:Mike Barker is the originator of the Death Blossom term. Would someone please provide a link to where Mike said the "stem" of a Death Blossom could be smaller than a tri-valued cell:?:

Ron,

I just assumed based on the Sudopedia and other entries in the APE extended thread that bi-value/local stems were legit. Certainly for the bi-value case, there should always exist an ALS chain of length 3 that exactly matches, and these types of DBs are "uninteresting". Bi-locals are slightly different because the rules for building ALS chains (currently) do not include using anything other than directly linking ALSs via peer'ed RCDs, so DB allows for some additional dual-linked ALS chains to be located.

The tri- and larger stem cells seem to be in a separate category and are distinct from standard ALS chains. I'm looking at them as ALS networks. Which makes me wonder if multiple stems can be linked to form a Death Bouquet? Although it might be pretty, I can't envision that combining several DBs would "extend" their capability. Just thinking out loud...

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

Postby StrmCkr » Wed Mar 25, 2009 8:47 am

oh i was going with mikies lecture to rockyin the first movie...

"you always where a contender, you could have been some body instead of the bum you are".... not sure on the whole quote or its self in whole...

cheers
chris.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 673
Joined: 05 September 2006

Postby PIsaacson » Wed Mar 25, 2009 10:36 am

For the record:

The great Marlon Brando in "On the Waterfront" 1954: http://www.youtube.com/watch?v=nrq96cW2BuY
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby Allan Barker » Wed Mar 25, 2009 1:17 pm

PIsaacson wrote:The following is a 5 petal Death Blossom from the royle17 collection:
[............]
The ALS chain r8c4.<n58> -8- r8c8.<n28> -2- r8c6.<n12> -1- r14569c5.<n145678> => r7c5 is the closest match to the DB, but my engine doesn't find any equivalent for r5c4 or something that covers both in one fell swoop.

Some of the Death Blossoms posted here are true beauties that might be described in a variety of ways however, PIsaacson's Royal 5 is really something different. (For the sake of argument, I have included one of the two eliminations but the second one follows the same argument)

Code: Select all
Puzzle #9 royle17 36628 collection [from PIsaacson]
+------------------+------------------------+----------------------+
| 38   5689  35679 | 345678  45678    34567 | 3689   1      2      |
| 4    2568  1356  | 3568    9        12    | 368    3678   3678   |
| 12   689   3679  | 3678    12       367   | 3689   5      4      |
+------------------+------------------------+----------------------+
| 138  7     3459  | 2       (456)    34569 | 13568  3689   35689  |
| 6    2589  1359  | 379-5   (57)     3579  | 4      23789  135789 |
| 23   459   3459  | 1       (4567)   8     | 2356   3679   35679  |
+------------------+------------------------+----------------------+
| 7    1     8     | 4569    2456     4569  | 2356   3469   3569   |
| 9    46    46    | (58)    3        (12)  | 7      (28)   158    |
| 5    3     2     | 46789   (14678)  4679  | 168    4689   689    |
+------------------+------------------------+----------------------+

DEB2 20 Nodes, Rank = 2 (linksets - sets)
     7 Sets = {8N4 4569N5 8N6 8N8}
     9 Links = {28r8 5c4 467c5 5b5 18b8}
     1 Elimination --> r5c4<>5

Just a quick summary to help explain.

Rank 0 One class of logic always has N strong sets (truths) that can be contained inside of N links (rank 0). This includes continuous loops, most fish, and hidden/naked multiples. "Links" only means contained in the same house/cell or, "can see".

Rank 1 A second class of logic always has N strong sets that can be contained inside of N+1 links (rank 1), which includes most all chains and most all other Sudoku methods.

But not this baby.

Image
In this case, all seven cells can only be covered using 9 links, which makes this logic rank 2 (rare). Then according to rank rules, any candidate contained in 3 links, or seeing 3 cells, can be eliminated.

But, 5r5c4 sees only 2 cells through box 5b5 and through column 5c4. The answer is that the triplet 5r8c4 decreases the rank along the path containing column link 5c4, then the 2 overlapping links eliminate 5r5c4. (Likewise, another group of cover sets will eliminate candidate 5r7c5 in PIsaacson's example.).

Although interesting, it's not clear to me to see how exactly this relates to the various ALS rules.
.
Last edited by Allan Barker on Wed Mar 25, 2009 11:44 am, edited 1 time in total.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby PIsaacson » Wed Mar 25, 2009 2:33 pm

Well, I just got my DB dual-link code working and guess what? There are two types of new dual-linked ALSs.

Type 1 is via a bi-value stem with 2 ALSs that also share a common RCD in addition to the stem.
Type 2 is via a bi-local stem with 2 ALSs that also share a common RCD in addition to the stem.

Type 2 could be considered a "standard" dual-linked ALS with the bi-local bridging one of the RCDs, but what the heck is up with a Type 1?

In all cases, the stem must be considered as one of the participating RCD cells for whichever candidate is being used as an RCD with the respective ALS. In the case of Type 2, both ALSs "see" the same RCD value. In the case of Type 1, each ALS "sees" a different RCD value, so it almost looks like they are sharing a trio of candidate values. Weird, but it works like a charm.

I'll be posting details tomorrow and refreshing the code for those who might want to look at these things in Xsudo. In the royle17 collection and filtering just on DB dual-links, there were 1756 located with 7378 eliminations. In contrast, using the same collection and filtering on ALS dual-links, there were only 867 located with 4624 eliminations.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby ronk » Wed Mar 25, 2009 4:59 pm

PIsaacson wrote:Well, I just got my DB dual-link code working and guess what? There are two types of new dual-linked ALSs.

Type 1 is via a bi-value stem with 2 ALSs that also share a common RCD in addition to the stem.
Type 2 is via a bi-local stem with 2 ALSs that also share a common RCD in addition to the stem.

Type 2 could be considered a "standard" dual-linked ALS with the bi-local bridging one of the RCDs, but what the heck is up with a Type 1?

Would you please post an example of your "Type 1"?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby aran » Wed Mar 25, 2009 6:53 pm

Allan Barker wrote:
PIsaacson wrote:The following is a 5 petal Death Blossom from the royle17 collection:
[............]
The ALS chain r8c4.<n58> -8- r8c8.<n28> -2- r8c6.<n12> -1- r14569c5.<n145678> => r7c5 is the closest match to the DB, but my engine doesn't find any equivalent for r5c4 or something that covers both in one fell swoop.

Some of the Death Blossoms posted here are true beauties that might be described in a variety of ways however, PIsaacson's Royal 5 is really something different. (For the sake of argument, I have included one of the two eliminations but the second one follows the same argument)

Code: Select all
Puzzle #9 royle17 36628 collection [from PIsaacson]
+------------------+------------------------+----------------------+
| 38   5689  35679 | 345678  45678    34567 | 3689   1      2      |
| 4    2568  1356  | 3568    9        12    | 368    3678   3678   |
| 12   689   3679  | 3678    12       367   | 3689   5      4      |
+------------------+------------------------+----------------------+
| 138  7     3459  | 2       (456)    34569 | 13568  3689   35689  |
| 6    2589  1359  | 379-5   (57)     3579  | 4      23789  135789 |
| 23   459   3459  | 1       (4567)   8     | 2356   3679   35679  |
+------------------+------------------------+----------------------+
| 7    1     8     | 4569    2456     4569  | 2356   3469   3569   |
| 9    46    46    | (58)    3        (12)  | 7      (28)   158    |
| 5    3     2     | 46789   (14678)  4679  | 168    4689   689    |
+------------------+------------------------+----------------------+

DEB2 20 Nodes, Rank = 2 (linksets - sets)
     7 Sets = {8N4 4569N5 8N6 8N8}
     9 Links = {28r8 5c4 467c5 5b5 18b8}
     1 Elimination --> r5c4<>5

Just a quick summary to help explain.

Rank 0 One class of logic always has N strong sets (truths) that can be contained inside of N links (rank 0). This includes continuous loops, most fish, and hidden/naked multiples. "Links" only means contained in the same house/cell or, "can see".

Rank 1 A second class of logic always has N strong sets that can be contained inside of N+1 links (rank 1), which includes most all chains and most all other Sudoku methods.

But not this baby.

Image
In this case, all seven cells can only be covered using 9 links, which makes this logic rank 2 (rare). Then according to rank rules, any candidate contained in 3 links, or seeing 3 cells, can be eliminated.

But, 5r5c4 sees only 2 cells through box 5b5 and through column 5c4. The answer is that the triplet 5r8c4 decreases the rank along the path containing column link 5c4, then the 2 overlapping links eliminate 5r5c4. (Likewise, another group of cover sets will eliminate candidate 5r7c5 in PIsaacson's example.).

Although interesting, it's not clear to me to see how exactly this relates to the various ALS rules.
.

Concerning the rank 2 structure above,
5r5c4 takes out two linksets immediately (5b5, 5c4) and then immediately by "placing" 8r8c4 takes out the linkset 8b8 (remembering that this covers only r9c5 since 8r8c4 is covered by linkset 8r8).
Thus three linksets are removed, hence contradiction, hence <5>r5c4.
At any rate, I think that is a simpler way of seeing it.

As to the chain transcription :
5r8c4=8r8c4-(8=2)r8c8-(2=1)r8c6-(18)r9c5=4567r4569c5 : <5> r5c4
aran
 
Posts: 334
Joined: 02 March 2007

Postby aran » Wed Mar 25, 2009 7:56 pm

PIsaacson wrote:Aran,

The reason I'm interested in DB is exactly because they allow setting up dual-linked ALSs in cases where the "normal" ALS chaining rules don't apply.

Specifically: http://forum.enjoysudoku.com/viewtopic.php?p=67972#p67972

Allan Barker characterized the example as an ALS loop, but another way of looking at it is a DB with a bi-location stem cell. That was what I was alluding to in my first paragraph. I should have included the url reference. Mea culpa...

I haven't finished coding DB, but in loading examples in Xsudo, I have seen examples of rank 0 structures involving the use of such bi-local stems. I even have some really interesting tri-value and tri-local DBs that contain a dual-linked ALS on 2 of the 3 petals.

Preliminary findings on the royle17 collection show that DBs are prevalent, and as compared to ALS chains size 3 (including all possible dual-links), dual and tri value/location stem celled DBs are more powerful.

Aran wrote:... there is a simple structure (hidden set) which achieves the same purpose quicker

Could you please explain or give references? In your example, it looks like you are using an AIC to link/extend the RCD(s) of 2 ALSs. If so, then how is this different from ALS grouped nice-loops? I don't understand the hidden set reference. Yet another gaping hole in my understanding of sudoku theory/techniques...

Cheers,
Paul

Paul
My point really is that so far anything I have seen on DB just seems like making a mountain out of a molehill.
Example : (to which I think reference has been made somewhere in this thread) :
In the next example r1c3 sees the "1" in r1c7 so a valid link exists to the ALS: r17c7 (169). The "6" in r7c7 is seen by r7c6 again creating a valid link since r7c7 is the only cell of the ALS containing a "6". On the other hand the "9" in r7c8 sees only the "9" in r7c7, but not the one in r1c7. Thus the link cannont be made since r7c8 doesn't see all the cells of the ALS: r17c7 which contain "9".

In the second link, the "7" in r7c3 of the ALS r7c37 (679) is seen by r1c3 and the "6" of r7c37 is seen by r7c6 again creating valid links. In this case, the "9" can also create a valid link, but all links must be valid for the elimination to occur.

Note that the fact that the two ALS overlap is immaterial. Each short link/chain is established independently which is one of the reasons I think the technique works so well. Its also IMO the strength of the approach since several short chains are constructed instead of one or several long ones. Note also that multiple exclusions can be made (in this case r7c8<>6 as well).
Code: Select all
3-valued Death Blossom (SUM Exclusion) (r1c3-1-r17c7-6-, r1c3-7-r7c37-6-): r1c3 => r7c68<>6
+------------------+--------------------+------------------+
|   6    137   *17 |   39     48     48 |   #19      2   5 |
|  49     18   148 |    5      2      7 |     3     19   6 |
|  39      5     2 |    1      6     39 |     7      8   4 |
+------------------+--------------------+------------------+
|   1    689     3 |   67    458  45689 |     2    467  78 |
|   2     68     5 |   37  13478   3468 |  1468   1467   9 |
|   7      4   689 |  269     18   2689 |     5     16   3 |
+------------------+--------------------+------------------+
|   8     27  @679 |    4    357  -2356 |  #@69  -3679   1 |
|  34  12367   146 |  267      9    236 |   468      5  78 |
|   5   3679  4679 |    8     37      1 |   469  34679   2 |
+------------------+--------------------+------------------+



One little chain deals with all that :
69r7c37=7r7c7-(7=1)r1c3-(1=9)r1c7-(9=6)r7c7 : =><6>r7c68
End of story. No words required.
Until it can be demonstrated why the quoted version (to which I give all my due respects) is preferable, then I must remain skeptical.
I find this to be true in every example I have seen.
I'll be very interested in examining the rank 0 DBs that you mention, since for the time being I regard them as having rank 1.

Edited to correct the typo 7r3c7 to 7r7c7 (thanks Luke)
Last edited by aran on Fri Mar 27, 2009 1:46 pm, edited 1 time in total.
aran
 
Posts: 334
Joined: 02 March 2007

Postby ronk » Wed Mar 25, 2009 8:05 pm

Allan Barker wrote:Rank 1 A second class of logic always has N strong sets that can be contained inside of N+1 links (rank 1), which includes most all chains and most all other Sudoku methods.

But not this baby.
[...]
Code: Select all
DEB2 20 Nodes, Rank = 2 (linksets - sets)
     7 Sets = {8N4 4569N5 8N6 8N8}
     9 Links = {28r8 5c4 467c5 5b5 18b8}
     1 Elimination --> r5c4<>5
[...]
In this case, all seven cells can only be covered using 9 links, which makes this logic rank 2 (rare). Then according to rank rules, any candidate contained in 3 links, or seeing 3 cells, can be eliminated.

But, 5r5c4 sees only 2 cells through box 5b5 and through column 5c4. The answer is that the triplet 5r8c4 decreases the rank along the path containing column link 5c4, then the 2 overlapping links eliminate 5r5c4.

So it could be said that, because of the linkset triple, raw rank 2 becomes effective rank 1, right? Interestingly, if ALS r8c468 is replaced with the complementary and equivalent AHS 15r8, then raw rank = 1 as well.
Code: Select all
DEB2 19 Nodes, Rank = 1 (linksets - sets)
     7 Sets = {8N4 4569N5 15R8}
     8 Links = {8n9 5c4 467c5 5b5 18b8}
     1 Eliminations --> r5c4<>5

But then it's not a Death Blossom, I suppose, or is it?

Allan Barker wrote:Although interesting, it's not clear to me to see how exactly this relates to the various ALS rules.

Many view multiple paths with a common outcome separately. For example ...
Code: Select all
r9c5 -467- als:r456c5 -5- r5c4
 or
r9c5 -8- als:r8c4 -5- r5c4
 or
r9c5 -1- als:r8c468 -5- r5c4

... where the overlap at r8c4 matters not.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby PIsaacson » Wed Mar 25, 2009 8:26 pm

ronk wrote:Would you please post an example of your "Type 1"?

Here's the Xsudo *.sud file: http://pisaacson.fileave.com/XSudo/db_sud.bin

Download, rename it to db.sud and place it in the Xsudo puzzle subdir. It's the first 399 DB dual-links from the royle17 collection with a mixture of Type 1 and 2. The first number in the description is the puzzle id. The second entry is the stem cell The next two are the ALSs preceded by the RCD linking them to the stem cell. I forgot to place the final RCD linking the 2 ALSs. It's on my bug list. Try looking at the 5th entry from puzzle #123. It's a winner in terms of eliminations, even though the puzzle could be solved at that point with a simple XY-wing.

P.S. If you see tiny dots on the eliminations, that means my ALS engine also found them. No dot, no direct elimination from the current dual-link rules.
Last edited by PIsaacson on Wed Mar 25, 2009 4:44 pm, edited 1 time in total.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

PreviousNext

Return to Advanced solving techniques