ALS chains with overlap/cannibalism

Advanced methods and approaches for solving Sudoku puzzles

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

aran wrote:One little chain deals with all that :
69r7c37=7r3c7-(7=1)r1c3-(1=9)r1c7-(9=6)r7c7 : =><6>r7c68
End of story. No words required.

I don't understand this chain, but then it should be stated up front that I'm not versed in Eureka notation. r3c7 is a given <7>. How can it be linked in any fashion to 69r7c37? Did you mean =9r1c7? I think words are required.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby Allan Barker » Wed Mar 25, 2009 9:06 pm

Aran wrote: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.

Yes, that is a good way of seeing it.

In fact, it is a bit similar to how the general triplet rules are derived, by looking at the logic with and without (in this case) 8r8c4 occupied, then deducing that either case leads to rank 1, at least for some region.
.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby Allan Barker » Wed Mar 25, 2009 9:10 pm

RonK wrote:So it could be said that, because of the linkset triple, raw rank 2 becomes effective rank 1, right?

Yes, correct, in the region of the elimination, which starts at the triplet. This region is determined by finding a lower rank cover set when (in this case) 8r8c4 is assumed to be un-occupied. When 8r8c4 is occupied, one candidate occupies two links thus the effective rank is 1 anyway.

RonK wrote: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

Nice deduction and good point. Of course, this is much easier to work with.

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

.Hmm, well, ah, I suppose that depends on the definition of a Death Blossom.:)
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby Luke » Wed Mar 25, 2009 9:25 pm

PIsaacson wrote:
aran wrote:One little chain deals with all that :
69r7c37=7r3c7-(7=1)r1c3-(1=9)r1c7-(9=6)r7c7 : =><6>r7c68
End of story. No words required.

I don't understand this chain, but then it should be stated up front that I'm not versed in Eureka notation. r3c7 is a given <7>. How can it be linked in any fashion to 69r7c37? Did you mean =9r1c7? I think words are required.

Paul, try: 69r7c37=7r7c3-(7=1)r1c3-(1=9)r1c7-(9=6)r7c7 : =><6>r7c68
Code: Select all
+------------------+--------------------+------------------+
|   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 |
+------------------+--------------------+------------------+ 

User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby PIsaacson » Wed Mar 25, 2009 10:56 pm

Luke451 wrote:Paul, try: 69r7c37=7r7c3-(7=1)r1c3-(1=9)r1c7-(9=6)r7c7 : =><6>r7c68

:idea:Eureka! Always wanted to use that.:D
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby PIsaacson » Wed Mar 25, 2009 11:32 pm

ImageImage

Two exemplar dual-linked Type 1 DBs from royle17 #123. Red and orange are eliminations resulting in green assignments -- some are absent due to ??? (help me out here, Allan). The assignments are not directly found by my ALS engine, but should be "caught" by NS/HS processing immediately after.

Left hand side - stem cell r4c1 ALSs: A 4-r4c8 B 9-r6c1589
Right hand size - stem cell r3c9 ALSs: A 6-r6c1589 7-r4c1689

The end results after NS/HS processing/assignments are equivalent, but my current implementation did not correctly locate all the possible eliminations. I'm working on it... And in order to head this off in advance, yes I know that a simple XY-wing would suffice to solve the puzzle. The point is to demonstrate that dual-linked DBs exist and appear to be plenty powerful. I have hundreds more if anyone wants to review them. I'm slowly going through them and making notes regarding elimination rules. Already found one -- the stem cells can also have candidate eliminations for non-participating candidates in multi-location Type 2 DBs. Wheh!!!
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby aran » Thu Mar 26, 2009 12:05 am

PIsaacson wrote:
Luke451 wrote:Paul, try: 69r7c37=7r7c3-(7=1)r1c3-(1=9)r1c7-(9=6)r7c7 : =><6>r7c68

:idea:Eureka! Always wanted to use that.:D


Luke
In your debt for amending my typo:)
Paul
If that did clear things up, do you agree with me at all about the mountain and the molehill ?
aran
 
Posts: 334
Joined: 02 March 2007

Postby Luke » Thu Mar 26, 2009 1:52 am

My browser's not picking up either of your graphics.:( You may have to upload the jpg's to a sharing site then link to them in your post.

Edit: fine now, problem was on my end.
Last edited by Luke on Sat Mar 28, 2009 12:23 pm, edited 1 time in total.
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby PIsaacson » Thu Mar 26, 2009 2:27 am

Aran,

Did that clear things up for me? Yes! It hit me like a ton of bricks. Over the head with a two-by-four, which is exactly what I needed in order to finally "get it".

Do I agree with you about the mountain and the mole-hill? Long pause... Much head scratching... No light bulbs...

I don't know whether or not it can be proven that all DBs can be re-stated as nice-loops. Let's assume for the sake of discussion that it's possible. So how does one now measure the relative "easiness" of finding said nice-loop equivalent in order to assert that DBs are a mole-hill? I think this a slippery slope to climb and one that I certainly can't scale.

Regardless of their height or pitch, dual-linked Death Blossoms at least provide some very pretty 3d images in Xsudo!

Luke451,

Try http://pisaacson.fileave.com/XSudo/123_000.jpg and http://pisaacson.fileave.com/XSudo/123_001.jpg
I use Firefox and it seems to be working fine with the Img tags. Just tried IE and that's working okay for me as well. Fileave is one of those free hosting sites, so perhaps I hit my daily download limit??? I'll check... Nope, nowhere near the limit, so I don't know what could be preventing you from seeing the images. PM me if you can't open the links directly and I'll try something else.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby aran » Thu Mar 26, 2009 3:54 am

PIsaacson wrote:Aran,

Did that clear things up for me? Yes! It hit me like a ton of bricks. Over the head with a two-by-four, which is exactly what I needed in order to finally "get it".

Do I agree with you about the mountain and the mole-hill? Long pause... Much head scratching... No light bulbs...

I don't know whether or not it can be proven that all DBs can be re-stated as nice-loops. Let's assume for the sake of discussion that it's possible. So how does one now measure the relative "easiness" of finding said nice-loop equivalent in order to assert that DBs are a mole-hill? I think this a slippery slope to climb and one that I certainly can't scale.
Regardless of their height or pitch, dual-linked Death Blossoms at least provide some very pretty 3d images in Xsudo!


Paul
First of all I may not agree with myself anymore...
My point had been that DB as a rank 1 structure didn't hold much interest (well to me) since a hidden set approach would get there quicker. I still think that.
But what is new is your second example above.
If I understand, what you are saying is that there are stem cells which create a second link between the ALSs thus doubly-linking them (the function of r3c9) so creating a rank 0 structure...which is a completely different kettle of fish.
Is that in fact what you have in mind ?
As to the eliminations : I see a small number (<9>r5c1, <4>r6c6, <8>r6c6) arising from basic dual-link ALS logic, +<6>r4c9 which if true would remove both partners in the stem-cell generated second link ie 7r4c9 and 6r6c9 (ie it works like <9>r5c1). Thereafter other reasoning will deal with the others, but for the moment I don't see them as arising from the structure.
Can you let me know how you see it ?
aran
 
Posts: 334
Joined: 02 March 2007

Postby PIsaacson » Thu Mar 26, 2009 4:28 am

Aran,

I have to admit that I really don't know what to make of what I've called Type 1 DBs. They look/feel/smell like dual-linked ALSs and certainly perform like them in terms of eliminations. I'm slowly looking at over 1200 of these things just from the royle17 collection and I have thousands more from other collections. I guess these are what you call rank-0 structures?

I haven't even nailed down the elimination rules, although I'm working on the assumption that they are similar to standard dual-linked ALSs, and so far that's working. But, my engine is not finding all the potential eliminations as identified by Allan Barker's Xsudo during analysis of the involved sets/link-sets, so there's lots of room for exploration here.

So, is that what I see or have in mind? I guess the answer is that I'm not exactly sure where this is going, but it's been fun so far...

Cheers,
Paul

And as usual, code/executables have been refreshed with the latest dual-link DB code if anyone wants to play in my sandbox.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby PIsaacson » Thu Mar 26, 2009 6:24 am

A thought occurred while taking a shower:

What if we check any (AIC/NL/ALS/etc.) chain that begins/ends with an ALS to see if they share an additional RCD?

I was trying to come up with other simple methods of linking two ALSs and winding up with something akin to the bi-value/local DB linkage. It finally dawned on me that the bi-value was just a standard ALS chain length 3 with the start/end ALSs also RCD linked. Well, if that works, then any length ALS chain might also involve a start/end ALS pair that links. Dooh!!! That's the sound of dim light bulbs glowing.

This is likely old news to everyone else here, so forgive me for coming late to the party. I need to modify my ALS engine to always check the start/end ALSs. If this works, then we might have another chapter to include in our ALS primers as I don't recall reading anything about always checking for dual-links regardless of chain length. But then, as I've said before, never underestimate my lack of understanding.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby ronk » Thu Mar 26, 2009 6:24 am

Paul, your "Type 1" examples are continuous loops comprised of 3 ALSs with at least one ALS being a bivalue. One bivalue is serving as the "stem" of your Death Blossom. That said, I don't understand all the eliminations shown on the xsudo graphics you posted. For example, for "123 r4c1.<49> 4-r4c8 9-r6c1589", I see only four eliminations.
Code: Select all
 7    6    4    | 1    9    5    | 8    2    3
 3    2    59   | 8    6    7    | 4    1    59
 8    1    59   | 4    3    2    | 79   56   67
----------------+----------------+---------------
A49   3    2    | 5    1    68   | 79  B46   78-6
 45-9 8    6    | 7    2    49   | 1    3    59
C459  7    1    | 3   C48   69-48| 2   C45  C68
----------------+----------------+---------------
 6    5    8    | 2    7    1    | 3    9    4
 1    9    3    | 6    48   48   | 5    7    2
 2    4    7    | 9    5    3    | 6    8    1

 - r4c1 -4- r4c8 -6- als:(r6c9,r6c58 =6|48|9= r6c1) -9- r4c1 - continuous loop

 ==> r5c1<>9, r6c6<>48, r4c9<>6

From a sets perspective, there are three ALSs and three restricted commons. RCC digit 4 connects sets A & B, RCC 6 connects sets B & C, and RCC 9 connects sets C & A. Each ALS is "doubly-linked", once to the ALS on its left and once to the ALS on its right.

If a search for continuous loops comprised of two ALSs had been made first, sets A & B would have been combined for a doubly-linked ALS-xz.

PIsaacson wrote:What if we check any (AIC/NL/ALS/etc.) chain that begins/ends with an ALS to see if they share an additional RCD?

Are you already checking for a continuous loop if there is neither a beginning nor an ending ALS?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby PIsaacson » Thu Mar 26, 2009 1:54 pm

Ron,
ronk wrote:I don't understand all the eliminations shown on the xsudo graphics you posted. For example, for "123 r4c1.<49> 4-r4c8 9-r6c1589", I see only four eliminations...

If you squint really really hard, you may be able to see 4 incredibly tiny dots in the corner of those candidates in both xsudo graphics. These dots, and the xsudo positions, are generated by my test engine using the options to generate a *.sud file. I could only locate those same 4 eliminations, which is why I want to learn Allan's set/link-set theory. It can squeeze a lot of extra mileage out of dual-linked ALS sets.

ronk wrote:Are you already checking for a continuous loop if there is neither a beginning nor an ending ALS?

Everything I'm reporting here is based on the test engine which is strictly ALS chains and now DB, so everything always starts/ends with an ALS. Regardless, the ALS engine does check for loops and whips, so I guess the answer is "Yes", if you amend it to say "both a beginning and ending ALS?" But prior to today, I was never checking for dual-linked conditions with chains longer than 2. I never thought an XY-wing type of ALS structure could form into a dual-linked structure.

In my group nice-loop/nrczt engines, if a chain started and ended with an ALS, I likewise didn't check whether or not it converted into a dual-linked condition. I am now correcting that in all my various ALS dependent engines. So for those engines, I would answer "Yes" to your question without any qualifications. But I've deliberately tried to avoid using any NL presentations of ALS chains, and now DB in this thread. And I have deliberately hacked all my other engines out of the test-bed that I've uploaded to focus on just ALS/DB.

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

Postby Allan Barker » Thu Mar 26, 2009 2:48 pm

PIsaacson wrote:Red and orange are eliminations resulting in green assignments -- some are absent due to ??? (help me out here, Allan).

Answer Part I

Paul, your logic is being loaded in the Auto Drawing mode, which automatically adds (to your logic) any linking sets that can cause additional eliminations or assignments. The logic is correct, i.e., these eliminations are caused by this group of cells. In this case, the logic is sufficient to solve the cells thus the large number of green assigned candidates. Red and orange eliminatees are the same except red ones are in the cells (stong sets).

Allan
Edit: to label this as part 1 of a 2 part answer
Last edited by Allan Barker on Thu Mar 26, 2009 12:33 pm, edited 1 time in total.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

PreviousNext

Return to Advanced solving techniques

cron