ALS Chains -A Tutorial ASI#3

Advanced methods and approaches for solving Sudoku puzzles

Postby ronk » Thu Nov 27, 2008 5:14 am

PIsaacson wrote:top50000 results:

1) Old ALS RCD rules: 35747 solved with 475282 ALS chains resulting in 569390 eliminations [...]

2) New ALS RCD rules: 41005 solved with 618588 ALS chains resulting in 749733 eliminations [...]

There were no invalid eliminations caused by the new adjacency rule and these results look subjectively more "promising" than the top1465 results.

Many of those eliminations might have resulted from other "advanced" techniques, but the numbers are still impressive IMO. However, I suspect your new restricted common candidate (RCC) rules are still overly restrictive.

Conjecture: Adjacent ALSs can have the same non-adjacent RCC value as long as the ALSs do not share a cell.

Application of the ALS doubly-linked xz-rule -- where two ALSs share two RCCs -- is an obvious example.
Code: Select all
top1465 #451
..2...9..9....6..18..4...3.....6..5..3...82........3.7.2.9..1..6.1.5.....7...4...
 
 13457  6      2     | 13578 378   1357  | 9     478   458
 9      45     345-7 | 23578 2378  6     | 4578  2478  1
 8     A15    A57    | 4     79-2  179-25| 6     3    A25
---------------------+-------------------+------------------
 127-4 B1489  B4789  | 1237  6     1237-9|B48    5    B489
 1457   3      4569-7| 157   479   8     | 2     1469  469
 1245   4589-1 45689 | 125   249   1259  | 3     14689 7
---------------------+-------------------+------------------
 345    2      3458  | 9     378   37    | 1     4678  34568
 6      489    1     | 2378  5     237   | 478   4789  3489
 35     7      3589  | 6     1     4     | 58    289   23589

Sets: A={r3c239} = {1257}; B={r4c2379} = {14789}; x,z or z,x = 1,7

Elims: r6c2<>1, r25c3<>7, r3c5<>2, r3c6<>25, r4c2<>4, r4c6<>9

Terse NL:
als:r3c239 -7- als:r4c2379 -1- continuous loop

Verbose NL:
als:([r3c2,r3c9] =1|25|7= r3c3) -7- als:([r4c3,r4c79] =7|489|1= r4c2) -1- continuous loop

In the verbose NL notation, note the truly locked candidates are shown between '|' symbols. No matter which ALS ultimately holds a given RCC, digits 2 and 5 are locked (aran might say overlocked:) ) in ALS A, and digits 4, 8 and 9 are locked in ALS B.

The conjecture should hold for both continuous and discontinuous loops.

[edit: Replaced the term "distant" with "non-adjacent".]
Last edited by ronk on Fri Nov 28, 2008 9:19 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby aran » Thu Nov 27, 2008 7:06 am

Ronk wrote
Conjecture: Adjacent ALSs can have the same "distant" RCC value as long as the ALSs do not share a cell.

Application of the ALS doubly-linked xz-rule -- where two ALSs share two RCCs -- is an obvious example.
Code:

top1465 #451
..2...9..9....6..18..4...3.....6..5..3...82........3.7.2.9..1..6.1.5.....7...4...

13457 6 2 | 13578 378 1357 | 9 478 458
9 45 345-7 | 23578 2378 6 | 4578 2478 1
8 A15 A57 | 4 79-2 179-25| 6 3 A25
---------------------+-------------------+------------------
127-4 B1489 B4789 | 1237 6 1237-9|B48 5 B489
1457 3 4569-7| 157 479 8 | 2 1469 469
1245 4589-1 45689 | 125 249 1259 | 3 14689 7
---------------------+-------------------+------------------
345 2 3458 | 9 378 37 | 1 4678 34568
6 489 1 | 2378 5 237 | 478 4789 3489
35 7 3589 | 6 1 4 | 58 289 23589

Sets: A={r3c239} = {1257}; B={r4c2379} = {14789}; x,z or z,x = 1,7

Elims: r6c2<>1, r25c3<>7, r3c5<>2, r3c6<>25, r4c2<>4, r4c6<>9

Terse NL:
als:r3c239 -7- als:r4c2379 -1- continuous loop

Verbose NL:
als:([r3c2,r3c9] =1|25|7= r3c3) -7- als:([r4c3,r4c79] =7|489|1= r4c2) -1- continuous loop


Or using eureka :
(125)r3c239=7r3c4-7r4c4=(1489)r4c2379-1r3c2=(257)r3c239 : an interesting creature being a loop over three cells.
Using the handy rule of thumb that weak links are conjugate in continuous loops, all the eliminations result.

The loop in any case generates all its consequences because it is a loop and not because ALS are involved.

Ronk : (subject to what you mean by "distant RCC"), I don’t think the conjecture can be true…as demonstrated by the {z, e, R1} piece of a while back...
Just because it’s obfuscatory doesn’t mean it isn’t right:)
There can only be question of adjacent cells in a chain of at least three sets; with two sets there's no room for adjacents : there's only first set, last set, and one RCC (at a time).
aran
 
Posts: 334
Joined: 02 March 2007

Postby ttt » Thu Nov 27, 2008 11:41 pm

aran wrote:Or using eureka :
(125)r3c239=7r3c4-7r4c4=(1489)r4c2379-1r3c2=(257)r3c239

I can't follow..., as Eureka! I present:
Code: Select all
(hp79)r3c56=(7)r3c3-(7=ht489)r4c379-(489=1)r4c2-(1)r3c2=(1)r3c6 => loop


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

Postby tarek » Fri Nov 28, 2008 6:03 am

ronk has PMed me a simplified diagram of the 3 ALS loop diagram I previously posted
ronk wrote:
Code: Select all
                     .....*z....
                    .           .
                   .             .
                  .               .
                 z.................z
                /                   \
               /                     \
*a.......a----A           B           C----c.......c*
               \         /|\         /
                x.......x | y.......y
                .       . | .       .
                 .     .  b  .     .
                  .   .   .   .   .
                   *x     .    *y
                         *b

x,y,z: Restricted commons
*: Possible eliminations
tarek
User avatar
tarek
 
Posts: 2612
Joined: 05 January 2006

Postby aran » Fri Nov 28, 2008 6:32 am

ttt wrote:
aran wrote:Or using eureka :
(125)r3c239=7r3c4-7r4c4=(1489)r4c2379-1r3c2=(257)r3c239

I can't follow..., as Eureka! I present:
Code: Select all
(hp79)r3c56=(7)r3c3-(7=ht489)r4c379-(489=1)r4c2-(1)r3c2=(1)r3c6 => loop


ttt

Your loop is fine, and mine would have been if the typo c4:( had been written c3 in the second and third nodes.
That should clear up the problem
aran
 
Posts: 334
Joined: 02 March 2007

Postby Allan Barker » Sat Nov 29, 2008 1:59 am

DonM wrote:It is important to note that when searching out the components of ALS Chains of greater than 2 sets, the restricted commons in the chain must have different values for the chain to result in a valid elimination. For instance, it is easy to make the mistake of having a restricted common, say 5, between two sets in the first part of a chain and then find another apparent restricted common 5 between two sets later in the chain. However, such a chain will result in an invalid elimination.

PIsaacson wrote:On the testing front, I modified my ALS-chain method to either use the former "no RCD re-use" rule or the new and improved "no RCD adjacent" rule which allows a qualified re-use. The long and short seems to be that this works and provides (some) additional ALS chains that would have otherwise been invalid.

Since my understanding of ALS methods is not so good, I tried to study the underlying base/cover sets to see what I could learn. I made a brief posting yesterday which I pulled after Ronk's quick eye spotted an error, which actually helped with the answer. Lets see if I can get it right this time.

The answer is close to what PIssacson has postulated, that an ALS chain can always reuse restricted common digits as long as they are not adjacent. An ALS chain with two adjacent RCDs will not cause an elimination except under special conditions. 1) The set group between the adjacent RCDs is a locked set, LS, and not an ALS, or 2) there is one more additional RCD, i.e., one of the ALS links has 2 RCDs. In either of these cases the chain still works.

The reason can be seen in terms of base/cover sets. Ordinary chains have n bi-value base sets and n+1 cover sets, thus they are rank (n+1) - (n) = 1. They eliminate candidates by the overlap of any two cover sets.

An ALS has n cells and n+1 values that can always be covered by n+1 cover sets, and is thus rank 1. M independent ALSs will have a rank of m. When building an ALS chain, each adjacent ALS pair must share a digit covered by a single cover-set to maintain a rank of 1 for the chain.

This works as long as adjacent RCDs have different values. When two adjacent RCDs have the same value, their cover-sets cover only one of the common ALS's values, not two. This increases the rank to 2 preventing eliminations. However, the chain's rank will be 1 if the common "ALS" has one less digit, i.e., it is a locked set, or if one more RCD is present. The most general rule would be the ALS chain will work as long as it has a rank of 1. The role of an RCD is to lower the rank by 1.

Without puzzles, I tried some test cases in my simulator and they all seem to work. In all the examples als3_A = r246c2, als3_B = r5c146, als3_C = r368c5 and als3_D = r7c368. The examples are:


Ex 1(non adjcent): 1r2c8 - als3_A(1245) - 5 - als3_B(3567) - 3 - als3_C(3456) - 5 - als3_D(1589) - 1r2c8 => r2c8<>1
Ex 2(adjacent): 1r2c8 - als3_A(1245) - 5 - ls3_B(567) - 5 - als3_C(3456) - 3 - als3_D(1389) - 1r2c8 => r2c8<>1
Ex 3(adjacent +RCD): 1r2c8 - als3_A(1245) - 45 - als3_B(4567) - 5 - als3_C(3456) - 3 - als3_D(1389) - 1r2c8 => r2c8<>1

Other combinations of RCDs and LS/ALS/AALS should also work as long as the overall rank is 1. It should also be possible to make various ALS loops as long as they are rank 0. I imagine much of this is understood with different terminology, I thought I would present the base/cover set logic view.

Thumbs left to right ex1, ex2, ex3.
ImageImageImage

Code: Select all
  +-----------------------------------------------------------+
  | .     .     .     | .     .     .     | .     .     .     |
  | .     (124) .     | .     .     .     | .    -1     .     |
  | .     .     .     | .     (46)  .     | .     .     .     |
  +-----------------------------------------------------------+
  | .     (245) .     | .     .     .     | .     .     .     |
  | (567) .     .     | (367) .     (67)  | .     .     .     | <- B
  | .     (24)  .     | .     (346) .     | .     .     .     |
  +-----------------------------------------------------------+
  | .     .     (89)  | .     .     (589) | .     (189) .     | <- D   
  | .     .     .     | .     (456) .     | .     .     .     |
  | .     .     .     | .     .     .     | .     .     .     |
  +-----------------------------------------------------------+
            ^A                 ^C

  +-----------------------------------------------------------+
  | .     .     .     | .     .     .     | .     .     .     |
  | .     (124) .     | .     .     .     | .    -1     .     |
  | .     .     .     | .     (46)  .     | .     .     .     |
  +-----------------------------------------------------------+
  | .     (245) .     | .     .     .     | .     .     .     |
  | (567) .     .     | (567) -6    (67)  | .     .     .     | <- B
  | .     (24)  .     | .     (456) .     | .     .     .     |
  +-----------------------------------------------------------+
  | .     .     (89)  | .     .     (389) | .     (189) .     | <- D
  | .     .     .     | .     (346) .     | .     .     .     |
  | .     .     .     | .     .     .     | .     .     .     |
  +-----------------------------------------------------------+
            ^A                 ^C

  +-----------------------------------------------------------+
  | .     .      .    | .     .     .     | .     .     .     |
  | .     (12)   .    | .     .     .     | .    -1     .     |
  | .     .      .    | .     (46)  .     | .     .     .     |
  +-----------------------------------------------------------+
  | .     (245)  .    | .     .     .     | .     .     .     |
  |(4567) .      .    | (567) -6    (67)  | .     .     .     | <- B
  | .     (24)   .    | .     (456) .     | .     .     .     |
  +-----------------------------------------------------------+
  | .     .      (89) | .     .     (389) | .     (189) .     | <- D
  | .     .      .    | .     (346) .     | .     .     .     |
  | .     .      .    | .     .     .     | .     .     .     |
  +-----------------------------------------------------------+

^A ^C
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby aran » Sat Nov 29, 2008 4:03 am

Allan
The answer is close to what PIssacson has postulated, that an ALS chain can always reuse restricted common digits as long as they are not adjacent. An ALS chain with two adjacent RCDs will not cause an elimination except under special conditions. 1) The set group between the adjacent RCDs is a locked set, LS, and not an ALS, or 2) there is one more additional RCD, i.e., one of the ALS links has 2 RCDs. In either of these cases the chain still works.

Glad to see that you agree with my conclusions earlier posted:)
Without recourse to any theory : the very fact that any RCD must see all instances of itself in the succeeding ALS is sufficient to show that there can never be re-use in adjacents.
As to the special cases you mention
1) How can there be an LS in an ALS chain ?
Within the chain, a preceding ALS must lock the succeeding set : that's the mechanism. A locked set can't be further locked. Or do you mean something else ?
2) Of course that is true. But it isn't a "special" case : since there is no "re-use" : the second RCD is being used for the first time.
aran
 
Posts: 334
Joined: 02 March 2007

Postby ronk » Sat Nov 29, 2008 4:38 am

Allan Barker wrote:Ex 3(adjacent +RCD): 1r2c8 - als3_A(1245) - 45 - als3_B(4567) - 5 - als3_C(3456) - 3 - als3_D(1389) - 1r2c8 => r2c8<>1

Example #3 is very interesting! "Bare bones NL-like notation' might look like ...

r2c8 -1- r246c2 -45- r5c246 -5- r368c5 -3- r7c368 -1- r2c8 ==> r2c8<>1

... which shows only the ALSs and the cover sets external to them. Adding internal cover sets to the notation could be done as ...

r2c8 -1- (2)r246c2 -45- (67)r5c246 -5- (46)r368c5 -3- (89)r7c368 -1- r2c8 ==> r2c8<>1

... where the digit 6 occurrence in two adjacent ALSs hints of an additional potential elimination, namely r5c5<>6.

I view your first two examples as degenerate cases ... due to the locked set, of course. Prior recognition of the locked set would have caused r5c5<>6 and left a digit 5 conjugate link in r5.

aran wrote:Glad to see that you agree with my conclusions earlier posted:)
Without recourse to any theory : the very fact that any RCD must see all instances of itself in the succeeding ALS is sufficient to show that there can never be re-use in adjacents.

Apparently you didn't look close enough. In example 3, RCC value 5 is used both between ALS sets A & B and between sets B & C.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby aran » Sat Nov 29, 2008 5:43 am

ronk wrote:
Allan Barker wrote:Ex 3(adjacent +RCD): 1r2c8 - als3_A(1245) - 45 - als3_B(4567) - 5 - als3_C(3456) - 3 - als3_D(1389) - 1r2c8 => r2c8<>1

Example #3 is very interesting! "Bare bones NL-like notation' might look like ...

r2c8 -1- r246c2 -45- r5c246 -5- r368c5 -3- r7c368 -1- r2c8 ==> r2c8<>1

... which shows only the ALSs and the cover sets external to them. Adding internal cover sets to the notation could be done as ...

r2c8 -1- (2)r246c2 -45- (67)r5c246 -5- (46)r368c5 -3- (89)r7c368 -1- r2c8 ==> r2c8<>1

... where the digit 6 occurrence in two adjacent ALSs hints of an additional potential elimination, namely r5c5<>6.

I view your first two examples as degenerate cases ... due to the locked set, of course. Prior recognition of the locked set would have caused r5c5<>6 and left a digit 5 conjugate link in r5.

aran wrote:Glad to see that you agree with my conclusions earlier posted:)
Without recourse to any theory : the very fact that any RCD must see all instances of itself in the succeeding ALS is sufficient to show that there can never be re-use in adjacents.

Apparently you didn't look close enough. In example 3, RCC value 5 is used both between ALS sets A & B and between sets B & C.


This is not how I read that.
Let me use my {z,e,R} notation just once...
to recall this dialect :
{..} candidates in the ALS sets
z =elim candidate
R =restricted commons
e for extra = all other candidates if any
Sets are ordered exactly {zeR} first cell, {Rez} last cell, and {ReR} in between. In this example, RCs are in bold.

Then example 3 is
{1245} {45 67} {67 5} {5463} {3891}
(the extra set is obviously r5c46)
So in other words there are 5 sets, with 45 a double RC between sets 1+2, and 67 a double RC between sets 2+3.
I don't see any special case adjaceny.
What this does however point to interestingly is the existence of double RCs operating between sets.

So from the above the start and final z (ie 1) eliminate any z seen in common ie 1r2c2.
The 6 elim in r5c5 resulting from the 2 set {6,7,5} {5,4,6} in box 5
aran
 
Posts: 334
Joined: 02 March 2007

Postby ronk » Sat Nov 29, 2008 8:20 am

aran wrote:Then example 3 is
{1245} {45 67} {67 5} {5463} {3891}
(the extra set is obviously r5c46)
So in other words there are 5 sets, with 45 a double RC between sets 1+2, and 67 a double RC between sets 2+3.
I don't see any special case adjaceny.

That's actually a good way to look at it, but is inconsistent with ...
aran wrote:Glad to see that you [edit: Allan] agree with my conclusions earlier posted

... since Allan Barker clearly interpreted the chain as 4 sets rather than 5 sets. Moreover, you split set r5c146 into two sets, r5c1 and r5c46, yet stated the extra set is obviously r5c46. Are these more examples of your obfuscatory talents?:(

Besides, I question the applicability of this POV to PIsaacson's programmed solver. Are you suggesting a search for chains containing various quantities and combinations of ALSs, AALSs and AAALSs?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby aran » Sat Nov 29, 2008 12:37 pm

Ronk wrote
Aran wrote
Then example 3 is
{1245} {45 67} {67 5} {5463} {3891}
(the extra set is obviously r5c46)
So in other words there are 5 sets, with 45 a double RC between sets 1+2, and 67 a double RC between sets 2+3.
I don't see any special case adjaceny.

That's actually a good way to look at it, but is inconsistent with ...
aran wrote:Glad to see that you [edit: Allan] agree with my conclusions earlier posted
...since Allan Barker clearly interpreted the chain as 4 sets rather than 5 sets

"Glad to see" wasn't an imprimatur to the entire post...but intended in reference to the principal conclusion :
The answer is close to what PIssacson has postulated, that an ALS chain can always reuse restricted common digits as long as they are not adjacent
Allan then added a rider to that conclusion about special cases with which I disagreed.
As to
Moreover, you split set r5c146 into two sets, r5c1 and r5c46, yet stated the extra set is obviously r5c46. Are these more examples of your obfuscatory talents?:(

That's not it : r5c16 served for {45 67}, and then r5c4 served for {67 5}.
Besides, I question the applicability of this POV to PIsaacson's programmed solver. Are you suggesting a search for chains containing various quantities and combinations of ALSs, AALSs and AAALSs?

I am not suggesting anything...au contraire, just like to keep the logic right...and if it's all too much for the computers, tant mieux:)
Last edited by aran on Sat Nov 29, 2008 11:00 pm, edited 1 time in total.
aran
 
Posts: 334
Joined: 02 March 2007

Postby ronk » Sat Nov 29, 2008 1:34 pm

aran, we seem to be on totally different wavelengths, so I'll simply let others decipher your posts.

Corollary: Since I don't intend to decipher your posts, please don't post to me.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Allan Barker » Sat Nov 29, 2008 4:23 pm

Hi, aran,

I too, am glad that I agree with your earlier conclusions, from the perspective of a student who gets the same answer as the professor. What I was trying to do was show how base/cover sets are applicable.

aran wrote:1) How can there be an LS in an ALS chain ?
Within the chain, a preceding ALS must lock the succeeding set : that's the mechanism. A locked set can't be further locked. Or do you mean something else ?

A really naive answer is, well, it's there and it works. From a base/cover set perspective, I can use adjacent equal value RCDs but only if the common group is an LS and not an ALS. This is required to make the rank come out as 1. Here again, I'm very much the student wrt proper ALS rules and terminology, I can only report what I see and let the experts provide the correct ALS perspective.

From the diagram for example 2, you can see that all the LS/ALS are linked via RCDs. In the case of the LS in question, it is linked on both sides with the digit 5. The way I mentally envision this is first stare at the LS

Code: Select all
ALS---5       5---ALS
      |       |
      6---6---6
      |   |   |
      7---7---7

then change one of the RCDs to a different digit
Code: Select all
              3---ALS
ALS---5       |
      |       |
      6---6---6
      |   |   |
      7---7---7

This makes no logical difference to the overall set structure of the chain however, in one case, the center group is a LS and in the other, it's an ALS.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby aran » Sun Nov 30, 2008 2:07 am

Hi Allan
Allan Barker wrote:Hi, aran,

...
aran wrote:1) How can there be an LS in an ALS chain ?
Within the chain, a preceding ALS must lock the succeeding set : that's the mechanism. A locked set can't be further locked. Or do you mean something else ?

A really naive answer is, well, it's there and it works. From a base/cover set perspective, I can use adjacent equal value RCDs but only if the common group is an LS and not an ALS. This is required to make the rank come out as 1. Here again, I'm very much the student wrt proper ALS rules and terminology, I can only report what I see and let the experts provide the correct ALS perspective.
From the diagram for example 2, you can see that all the LS/ALS are linked via RCDs. In the case of the LS in question, it is linked on both sides with the digit 5.

wrt your example 2 :
the 5 link between A {1245} (r246c2) and B {567} (r5c146) is not an RCD. To qualify as such, 5r4c2 must see 5r5c1 and 5r5c6, which obviously it doesn’t. So it’s merely a CD. What it does change is the composition of the locked set B.
Put another way, it’s a CD going into the exisiting locked set B, and an RCD coming out of it, thus enabling the ALS mechanism to resume, since now the 5 link Bmodified to C is indeed an RCD.
There is no dispute at all as to the logic of your eliminations, all I am saying is that they don’t arise as presented from a pure ALS chain since at the first hurdle the « weak link » is not an RCD. My point therefore was : this is not a special adjaceny case : there is no adjacency of RCDs to begin with.
These eliminations can be found within the realms of pure ALS chains by splitting your set B r5c146 into 2 sets B° r5c16 and B* r5c4 : ie giving
z(1) locks A =>RCD 5 locks B°=> RCD 67 locks B*=> RCD 5 locks C=> RCD 3 locks D : => z<1> r2c8.
aran
 
Posts: 334
Joined: 02 March 2007

Postby aran » Sun Nov 30, 2008 2:59 am

ronk wrote:aran, we seem to be on totally different wavelengths, so I'll simply let others decipher your posts.

Corollary: Since I don't intend to decipher your posts, please don't post to me.


I don't post to you : I just respond to texts identified for ease of reference by author.

BTW : in my last post in response to author Ronk, wrt to this excerpt :

Ronk : Moreover, you split set r5c146 into two sets, r5c1 and r5c46, yet stated the extra set is obviously r5c46. Are these more examples of your obfuscatory talents?

Aran : That's not it : r5c146 served for {45 67}, and then r5c46 served for {67 5} ie overlapping sets
.

My reply should have read :

That's not it : r5c16 served for {45 67}, and then r5c4 served for {67 5}.
I'll grant you that needed deciphering, and will edit.
aran
 
Posts: 334
Joined: 02 March 2007

PreviousNext

Return to Advanced solving techniques

cron