Advanced ALS Chains -A Tutorial ASI#3b

Advanced methods and approaches for solving Sudoku puzzles

Advanced ALS Chains -A Tutorial ASI#3b

Postby DonM » Sun Sep 05, 2010 3:10 pm

ADVANCED ALS CHAINS –A TUTORIAL (ASI #3b)

INTRODUCTION
A previous tutorial described the use of Basic ALS Chains. If you are relatively unfamiliar with ALS Chains then you should start with the Basic ALS Chains tutorial here:

viewtopic.php?t=6443&start=0

The distinction between basic and advanced ALS Chains is somewhat arbitrary and there will be some overlap between the two. However, broadly, the differences are very real. The possibility of manually-derived advanced ALS Chains was suggested to me by the relatively complex computer-derived ALS Chains used to solve an advanced puzzle recently on this forum (see Credits). Those results indicated that ALS Chains are more prevalent and can be used to solve more difficult puzzles than previously thought. However, particularly exciting to me is that fact that the examples presented here confirm that advanced ALS chains can also be found manually and provide yet another method of solving advanced-difficulty puzzles.


WHY ADVANCED ALS CHAINS?
As mentioned in the previous tutorial, finding ALS Chains, especially when using a Sudoku solver (purely as a frontend) such as Simple Sudoku that allows the manual coloring of cells, is pure pattern solving (or pattern A solving as I call it to distinguish it from finding chain-based patterns or pattern B solving). The benefit of utilizing these patterns is two-fold: First, one doesn’t have to know a lot about the underlying logic to use them and so they can serve as a very powerful ‘next step’ after basic solving methods that likewise use pattern A solving (x-wings, 2-string kites and the like), but without having to know anything about nice loops or AIC chains. Basic ALS Chains can provide end-stage solving solutions of the most difficult newspaper puzzles and perhaps of puzzles a little beyond that level, but Advanced ALS Chains are far more powerful and can solve a number of Extreme level puzzles that previously required chains such as nice loops and AICs to solve. Second, if one is experienced in solving with nice loops and AICS and, in addition, develops proficiency in finding the advanced ALS patterns described below, they will provide new sources of strong links for use in chains even if one has no interest in solving puzzles with pure ALS Chain patterns.

But there’s actually a third reason to solve with advanced ALS chains: it’s fun! Think of trying to solve Extreme level puzzles with nothing but ALS chains as a new form of challenge: a puzzle within a puzzle! This may be just what you need if you’re getting tired of the same old same old! :)

Here's a good example of the sort of fun I get out of the pure pattern solving of ALS Chains (basic or advanced) and a reason why I think they add a new realm of sudoku solving enjoyment. Below is a graphic of the latest version of the Iphone/Itouch app, Enjoy Sudoku, showing the same pattern as the first graphic in the examples that follow (note that the pink cells are where the eliminations take place). The author very kindly added the ability to color cells after a strong :) request from myself & sirdave. This means that you can solve fairly advanced puzzles using basic methods and ALS Chains on the road in places where it isn't that practical to find & document nice loops or AICs. (Btw: I have absolutely no relationship with the author or company other than wanting to have features such as coloring.)

Image


DIFFERENCES BETWEEN BASIC AND ADVANCED ALS CHAINS
The differences between basic and advanced ALS chains range from subtle to obvious. Basic ALS chains tend to consist more of 2 or 3 cell sets. Bivalue cells are common. The cells of the sets are more often than not inline ie. tend to follow each other in a row or column. The general patterns of basic ALS chains are relatively easy to see and easy to find. Finding advanced ALS chain patterns is not as intuitive a process, particularly when one is looking for them for the first time. But with practice it turns out that they are really only hiding in plain sight. They are also surprisingly common even in Extreme level puzzles and even where there are fewer bivalue cells.

Some of the constructs of advanced ALS chain patterns that distinguish them from basic ALS chains are:
a) Sets can contain as many as 5-6 (or even more) cells.
b) Cells of a set may be arranged in particularly irregular patterns.
c) The cells of a set may be some distance from each other.
d) A cell or cells of one set may be surrounded by the cells of another set.
e) 2 sets may share a common cell.
f) More than one conjugate-based link may be used.

Manually-derived examples of of these patterns follow directly below and are from the UK forum Extreme #133 which was largely solved using advanced ALS chains. Following those are the complete solutions of 2 Extreme-level puzzles using nothing but advanced ALS chains (and basic methods as necessary). An attempt has been made to keep the graphics as simple as possible for maximum clarity. The restricted commons are connected with black lines and red lines are used to join the digits in flanking sets with the digit(s) for elimination which are circled in red. Digits that are part of conjugate pair links are circled in black. Conjugate strong links are described using the #-conjugate terminology where # is the digit value being used eg. 1-conjugate for a pair of 1s in a row or column.

UK forum Extreme #133

Image

Green set-> rc=1 ->Blue set-> rc=9 ->Yellow set => r23c2<>8

A 3-set chain with a bivalue cell as a middle set (this pattern sometimes referred to as a Death Blossom).


Image

Green set-> rc=7 ->Blue set-> rc=9 ->Yellow set => r3c5<>1

A fairly complex pattern (generally, a Death Blossom pattern similiar to the previous chain) with a 5-cell Yellow set.


Image

Green set-> rc=9 thru 9-conjugate ->Blue set-> rc=7 ->Yellow set => r2c2<>1

Another 3 set chain with a middle bivalue cell (aka Death Blossom) and there is one conjugate-based link.


Image

Green set-> rc=1 ->Blue set => r5c1<>6

Not too complex a pattern, but not all that obvious either.


Image

Green set-> rc=9 ->Blue set-> rc=3 ->Yellow set =>r8c2<>6

A particularly complex 4 set chain and one of the more difficult to find manually. A common ‘overlay’ cell, r7c2, used in both the Green set and the Brown set, is required to make it work. Thus the Green set is r57c2 and the Brown set is r7c123.


Image

Green set-> rc=9 thru dual 9-conjugate ->Blue set => r5c2<>1

The 2 sets are simple, but the restricted common connection between them, a dual conjugate-based link is not. At first glance, it would not seem obvious that the 2 sets, though close to each other, could be connected.


Image

Green set-> rc=1 ->Blue set => r3c7<>6

Another pattern that would be hard to find if one wasn’t thinking outside the box :) .


Image

Green set-> rc=6 thru 6-conjugate ->Blue set rc=9 thru 9-conjugate => r2c8<>2

An extremely complex pattern utilizing 2 conjugate-based links and a common overlay cell. Both the Green and Yellow sets require r2c7 to be valid and make the pattern work. Thus, the Green set is r234c7 and the Yellow set is r2c467.

The solutions to 2 Extreme level puzzles follow below both to reinforce how powerful advanced ALS chains are and to give several examples of many of the various general patterns that are possible. The basic methods such as locked candidates, x-wings and the like that were used as they became available during the solving process are not shown. Also no attempt was made to optimize the solutions. Not necessarily all the ALS chains shown are mandatory for the final solution.

A note about the Extreme level puzzles and the ER difficulty rating: The ER rating for these puzzles is often deceivingly low and may sometimes not appear to be that much higher than the newspaper Diabolicals ie. 7.1 to 7.3. But the fact is that while most newspaper Diabolicals can be mostly or totally solved with basic methods, the Extremes almost always require advanced methods such as nice loops or AIC chains to solve.

(Credits: Paul Isaacson’s excellent recent work on computer-derived ALS Chains inspired some of the above search for manually-derived advanced ALS chains.)
DonM
2013 Supporter
 
Posts: 400
Joined: 13 January 2008

Re: Advanced ALS Chains -A Tutorial ASI#3b

Postby DonM » Sun Sep 05, 2010 3:13 pm

An Extreme level puzzle ER=7.3 (Draco 05/21/09) starting at the SSTS position (ie. generally speaking, after basic methods).

Image

Green set-> rc=3 ->Blue set => r8c7<>9


Image

Green set-> rc=3 ->Blue set-> rc=6 ->Yellow set => r8c89<>9


Image

Green set-> rc=4 ->Blue set => r5c6<>8


Image

Green set-> rc=3 ->Blue set-> rc=7 ->Yellow set => r7c8<>9


Image

Green set-> rc=6 ->Blue set-> rc=7 ->Yellow set-> rc=3 ->Brown set => r9c8<>9


Image

Green set-> rc=7 thru 7-conjugate -> r1c3<>9 thru dual 9-conjugate.


Image

Green set-> rc=3 thru 3-conjugate ->Blue set => r1c9<>1


Image

Green set-> rc=7 ->Blue set => r2c9<>5


Image

Green set-> rc=3 ->Blue set-> rc=7 ->Yellow set => r2c3<>1


Image

Green set-> rc=3 ->Blue set-> rc=5 ->Yellow set => r3c5<>1 thru 1-conjugate
DonM
2013 Supporter
 
Posts: 400
Joined: 13 January 2008

Re: Advanced ALS Chains -A Tutorial ASI#3b

Postby DonM » Sun Sep 05, 2010 3:13 pm

An Extreme level puzzle ER=7.1 starting at the SSTS position.

Image

Green set-> rc=9 ->Blue set => r7c5<>2


Image

Green set-> rc=7 ->Blue set-> rc=6 ->Yellow set => r6c4<>9


Image

Green set-> rc=6 thru 6-conjugate ->Blue set-> rc=1 ->Yellow set => r8c3<>5


Image

Green set-> rc=2 ->Blue set => r3c8<>9 thru 9-conjugate


Image

Green set-> rc=5 ->Blue set => r7c6<>2
DonM
2013 Supporter
 
Posts: 400
Joined: 13 January 2008

Re: Advanced ALS Chains -A Tutorial ASI#3b

Postby DonM » Sun Sep 05, 2010 3:13 pm

Regarding bug reports: Errors are likely to creep in when posting these types of graphics and the number of them at one time. The solving was not done with Simple Sudoku used as a frontend, but since it still provides particularly clear graphics, all the patterns had to be transferred over, so errors are even more likely. If people want to report any major errors, I'd appreciate it that it is done as much as possible thru PMs to keep the thread from being bogged down by bug reports that become irrelevant after the bugs are fixed. Thanks.
DonM
2013 Supporter
 
Posts: 400
Joined: 13 January 2008

Re: Advanced ALS Chains -A Tutorial ASI#3b

Postby ronk » Sun Sep 05, 2010 3:14 pm

DonM, that all cells of one almost-locked-set (ALS) don't need to see each other is ALS heresy AFAIC.
ronk
2012 Supporter
 
Posts: 4691
Joined: 02 November 2005
Location: Southeastern USA

Re: Advanced ALS Chains -A Tutorial ASI#3b

Postby DonM » Sun Sep 05, 2010 3:14 pm

ronk wrote:DonM, that all cells of one almost-locked-set (ALS) don't need to see each other is ALS heresy AFAIC.


Hmmm. It seems that in few of the sets I [may have gotten] a little carried away in 'optimizing', but it raises an interesting question: If all the digits of a given value see each other in the set, does it really matter when it comes to the functioning of the chain? In all of those sets, since all the digits of the same value do see each other which is mandatory for a valid chain, then all that is necessary to be technically correct is to simply add another set. But in the end, what does it change? Still, don't want to fool with the correct structure of ALS sets. Will have to ponder this when my head clears a little after all this posting.

Edit: Having pondered it, I think that 'heresy' may be as unfounded as previous heresys in history. If the structure has N+1 digits in N cells and each digit value sees all like digit values then it appears to me that everything works- remove one digit value & the other digits are locked. Usually, if not always (not having check any other situation), if there is an 'outlying' cell, it is a bivalue cell. I still may be missing something, but for the moment that's my take on the subject.
DonM
2013 Supporter
 
Posts: 400
Joined: 13 January 2008

Re: Advanced ALS Chains -A Tutorial ASI#3b

Postby ronk » Sun Sep 05, 2010 3:14 pm

DonM wrote:
ronk wrote:DonM, that all cells of one almost-locked-set (ALS) don't need to see each other is ALS heresy AFAIC.

Will have to ponder this when my head clears a little after all this posting.

Having pondered it, I think that 'heresy' may be as unfounded as previous heresys in history. If the structure has N+1 digits in N cells and each digit value sees all like digit values then it appears to me that everything works- remove one digit value & the other digits are locked.
[...]
I still may be missing something, but for the moment that's my take on the subject.

For one, you're missing Ruud's sudopedia.org definition ... An Almost Locked Set is a group of N cells in a single house with candidates for N+1 digits.

For another, you would be unnecessarily complicating the relationship between an ALS and its complementary almost-hidden-set (AHS).
ronk
2012 Supporter
 
Posts: 4691
Joined: 02 November 2005
Location: Southeastern USA

Re: Advanced ALS Chains -A Tutorial ASI#3b

Postby DonM » Sun Sep 05, 2010 3:15 pm

ronk wrote:
DonM wrote:
ronk wrote:DonM, that all cells of one almost-locked-set (ALS) don't need to see each other is ALS heresy AFAIC.

Will have to ponder this when my head clears a little after all this posting.

Having pondered it, I think that 'heresy' may be as unfounded as previous heresys in history. If the structure has N+1 digits in N cells and each digit value sees all like digit values then it appears to me that everything works- remove one digit value & the other digits are locked.
[...]
I still may be missing something, but for the moment that's my take on the subject.

For one, you're missing Ruud's sudopedia.org definition ... An Almost Locked Set is a group of N cells in a single house with candidates for N+1 digits.

For another, you would be unnecessarily complicating the relationship between an ALS and its complementary almost-hidden-set (AHS).


As to the latter, that is a matter of opinion. IMO, the question and the only question is whether the pattern that includes the addition of an 'outlying' bivalue cell as my original graphics showed operates as any other ALS N+1 values in N cells such that the removal of any digit value results in the remaining values being locked to the remaining cells. As the reigning sudoku theorist, if anyone can disprove that premise, I'm sure it is you.

As to the former, when it came to the Death Blossom definition including a bivalue cell, the Ruud sudopedia example I gave apparently didn't impress you, but in this case a similar situation in reverse seems to fit your purpose. You had to backtrack in that case as I will have to backtrack in this case -and ask absolution for my heresy- if you can show me where those patterns didn't operate as ALSs. :)
DonM
2013 Supporter
 
Posts: 400
Joined: 13 January 2008

Re: Advanced ALS Chains -A Tutorial ASI#3b

Postby ronk » Sun Sep 05, 2010 3:15 pm

DonM, since you've already corrected [ed: the four] examples, continuing this debate seems pointless.
ronk
2012 Supporter
 
Posts: 4691
Joined: 02 November 2005
Location: Southeastern USA

Re: Advanced ALS Chains -A Tutorial ASI#3b

Postby DonM » Sun Sep 05, 2010 3:16 pm

ronk wrote:DonM, since you've already corrected your examples, continuing this debate seems pointless.


I 'changed' the examples rather than 'corrected' them (until proven otherwise) because the information (specifically the graphics) is treading IMO on enough new ground without adding to it so don't assume this proves the premise of your vague opening remark. There's no debate here. Either those structures as I describe in my previous post act as any other ALS or they don't. Having raised the issue in that way as opposed to a form that engenders interesting discussion and then apparently skedaddling when the point has been responded to seems...interesting. So, again did or did not those structures operate as ALSs and if not, why not? I'm ready and willing to be corrected by substance rather than innuendo. Or you could just delete your posts and I'll delete mine.
DonM
2013 Supporter
 
Posts: 400
Joined: 13 January 2008

Re: Advanced ALS Chains -A Tutorial ASI#3b

Postby ronk » Sun Sep 05, 2010 3:16 pm

DonM wrote:So, again did or did not those structures operate as ALSs and if not, why not? I'm ready and willing to be corrected by substance rather than innuendo.

I never said your "bent ALSs" didn't operate as true ALSs. Remote pairs operate as naked pairs too, but I don't call them naked pairs, do you?

Moreover, I posted substance in my prior 2-point post. Since that was unconvincing, there's no point continuing.
ronk
2012 Supporter
 
Posts: 4691
Joined: 02 November 2005
Location: Southeastern USA

Re: Advanced ALS Chains -A Tutorial ASI#3b

Postby DonM » Sun Sep 05, 2010 3:16 pm

ronk wrote:
DonM wrote:So, again did or did not those structures operate as ALSs and if not, why not? I'm ready and willing to be corrected by substance rather than innuendo.

I never said your "bent ALSs" didn't operate as true ALSs.

No matter what you didn't say, anyone who understands the definition and implication of heresy (one definition being 'an opinion, doctrine, or practice contrary to the truth'), would have assumed that that was what was implied. In fact, since in the past, you have made a point of being persnickety about terminology ('dual' vs. 'doubly'), I can only assume that not only did you mean just that, but in doing so, you didn't appreciate that they functioned as any legitimate ALS.


Remote pairs operate as naked pairs too, but I don't call them naked pairs, do you?


I have a feeling that I am not the only one dismayed by that analogy. Your term 'bent ALS' is a rather nice one and I'm pleased to see that you call it an ALS. In fact, I'm prepared to say that all cells of an ALS do not have to necessarily occupy the same house, but I am only certain of that when the outlying cell is bivalue since all of the structures in question involved bivalues and all of those structures operated exactly the same as those in the now 'modified' form. What is an absolute rule is that all digits of the same value have to see each other (ie. be in the same house).


Moreover, I posted substance in my prior 2-point post. Since that was unconvincing, there's no point continuing.


Yes, I agree with you. It was unconvincing. And since, I think the point is now clear, I agree that there is no need to continue.
DonM
2013 Supporter
 
Posts: 400
Joined: 13 January 2008

Re: Advanced ALS Chains -A Tutorial ASI#3b

Postby Luke » Sun Sep 05, 2010 3:17 pm

Don,

Kudos on another great addition to your ALS series :) . Your selfless and ongoing efforts represent the definitive work on the topic and will be appreciated by players of all levels for years to come. I'm sure I'm speaking for many in thanking you for all of this :!:

I'd like to discuss a few points, but first, would you please look at this PM? I went straight from your latest tutorial to the puzzle I was working on, and immediately found this:
Code: Select all
.6.529.4...931...8.........6.....3..97..8..52..3.....1.........7...582...5.962.7.
 *-----------------------------------------------------------------------------*
 | 138     6       78      | 5       2       9       | 17      4       37      |
 | 245     24      9       | 3       1       467     | 567     26      8       |
 | 1245    123     1247    | 8       47      467     | 15679   12369   5679    |
 |-------------------------+-------------------------+-------------------------|
 | 6       1248    5       | 124     479     14      | 3       89      479     |
 | 9       7       14      | 146     8       3       | 46      5       2       |
 | 248     248     3       | 2467    479     5       | 46789   689     1       |
 |-------------------------+-------------------------+-------------------------|
 | 1248    12489   2468    | 147     3       147     | 145689  1689    4569    |
 | 7       139     146     | 14      5       8       | 2       1369    469     |
 | 1348    5       148     | 9       6       2       | 148     7       34      |
 *-----------------------------------------------------------------------------*

Code: Select all
Set A: (34679)r1489c9, restricted common 6;
Set B: (1468)r589c3, rc 8:
Set C: (1378)r1c379, rc 3;
Set D: (34)r9c9
=>r7c9<>4.

I present this as sets because that is how I found the move, DonM style. It may make sense to some like this:
Code: Select all
(3479)r1489c9=6r8c9-r8c3=(148)r589c3-8r1c3=(137)r1c379-(3=4)r9c9 =>r7c9<>4.

Just for interest, can I combine the last two sets and "Bend it like Beckham?"
User avatar
Luke
2014 Supporter
 
Posts: 431
Joined: 06 August 2006
Location: Southern Northern California

Re: Advanced ALS Chains -A Tutorial ASI#3b

Postby aran » Sun Sep 05, 2010 3:17 pm

Code: Select all
.6.529.4...931...8.........6.....3..97..8..52..3.....1.........7...582...5.962.7.
 *-----------------------------------------------------------------------------*
 | 138     6       78      | 5       2       9       | 17      4       37      |
 | 245     24      9       | 3       1       467     | 567     26      8       |
 | 1245    123     1247    | 8       47      467     | 15679   12369   5679    |
 |-------------------------+-------------------------+-------------------------|
 | 6       1248    5       | 124     479     14      | 3       89      479     |
 | 9       7       14      | 146     8       3       | 46      5       2       |
 | 248     248     3       | 2467    479     5       | 46789   689     1       |
 |-------------------------+-------------------------+-------------------------|
 | 1248    12489   2468    | 147     3       147     | 145689  1689    4569    |
 | 7       139     146     | 14      5       8       | 2       1369    469     |
 | 1348    5       148     | 9       6       2       | 148     7       34      |
 *-----------------------------------------------------------------------------*

Luke
off-topic but just out of interest in relation to your grid :
689r467c8=1r7c8
A : -1r8c8
B : -(1=48)r9c7
C : -1r7c46=1r8c4-1r5c4=1r5c3-(1=48)r9c3
C+B : -(4=3)r9c9
C+B+A : -(13=69)r8c8
hence : 689r467c8=689r468c8 : =><69>r23c8 =>r2c8=2, r2c2=4, r2c1=5 => r3c128=123 =><12>=7r3c3
ste
aran
 
Posts: 331
Joined: 02 March 2007

Re: Advanced ALS Chains -A Tutorial ASI#3b

Postby DonM » Sun Sep 05, 2010 3:17 pm

Luke451 wrote:Don,

Kudos on another great addition to your ALS series :) . Your selfless and ongoing efforts represent the definitive work on the topic and will be appreciated by players of all levels for years to come. I'm sure I'm speaking for many in thanking you for all of this :!:

I'd like to discuss a few points, but first, would you please look at this PM? I went straight from your latest tutorial to the puzzle I was working on, and immediately found this:
Code: Select all
.6.529.4...931...8.........6.....3..97..8..52..3.....1.........7...582...5.962.7.
 *-----------------------------------------------------------------------------*
 | 138     6       78      | 5       2       9       | 17      4       37      |
 | 245     24      9       | 3       1       467     | 567     26      8       |
 | 1245    123     1247    | 8       47      467     | 15679   12369   5679    |
 |-------------------------+-------------------------+-------------------------|
 | 6       1248    5       | 124     479     14      | 3       89      479     |
 | 9       7       14      | 146     8       3       | 46      5       2       |
 | 248     248     3       | 2467    479     5       | 46789   689     1       |
 |-------------------------+-------------------------+-------------------------|
 | 1248    12489   2468    | 147     3       147     | 145689  1689    4569    |
 | 7       139     146     | 14      5       8       | 2       1369    469     |
 | 1348    5       148     | 9       6       2       | 148     7       34      |
 *-----------------------------------------------------------------------------*

Code: Select all
Set A: (34679)r1489c9, restricted common 6;
Set B: (1468)r589c3, rc 8:
Set C: (1378)r1c379, rc 3;
Set D: (34)r9c9
=>r7c9<>4.

I present this as sets because that is how I found the move, DonM style. It may make sense to some like this:
Code: Select all
(3479)r1489c9=6r8c9-r8c3=(148)r589c3-8r1c3=(137)r1c379-(3=4)r9c9 =>r7c9<>4.

Just for interest, can I combine the last two sets and "Bend it like Beckham?"


Thanks for the kind words Luke. Your taking in the information and putting it into practice so effectively makes the work worthwhile. This is an excellent 4-set chain with 2 shared overlapping cells at r1c9 and r9c9, very much an advanced ALS chain. The last 2 sets can be combined. The fact that one cell doesn't see the other cells doesn't matter as far as both the logic and the results are involved.
DonM
2013 Supporter
 
Posts: 400
Joined: 13 January 2008

Next

Return to Advanced solving techniques