The New Sudoku Players' Forum

[Allan Barker]

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, I would agree with this whole picture, especially since I was looking for the official ALS perspecitive.

Of course, in my text I was referring to Recurrent Common Digits.
.

[aran]

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, I would agree with this whole picture, especially since I was looking for the official ALS perspecitive.

Of course, in my text I was referring to Recurrent Common Digits.
.

Thanks Allan. So it was an R°CD entering B and an R*CD on exit

[ronk]

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.

That's just further evidence that we are on totally different wavelengths, so let me re-phrase ...

Since I have no desire to decipher your posts, please don't respond to text that I author.

[aran]

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.

That's just further evidence that we are on totally different wavelengths, so let me re-phrase ...

Since I have no desire to decipher your posts, please don't respond to text that I author.

You can no more determine who reads your posts than who responds to them.

[DonM]

Okay, after all this study (by others), are we able to state an absolute, reliable rule for repeating restricted commons in ALS Chains? I think I know what it is- but I'm not sure it's been stated to a certainty so that it can be added to the tutorial.

[PIsaacson]

Don,

I took December off to spend time with family/friends for the holidays, but now it's time to get back to my sudoku obsession!

I need to verify Allan Barker's example 3 that demonstrates the reuse of one of the RCDs following a dual-linked ALS segment in the chain.

Also, there is a new thread http://forum.enjoysudoku.com/viewtopic.php?t=3979 regarding dual-linked ALS chains that has extended the scope of CECs by treating dual-linked ALS set eliminations from a base/cover or subset counting POV.

Worse, I'm starting to modify my ALS chaining method to include hidden ALSs. Allan Barker presented one in the above thread and I think this warrants further investigation. Every ALS has a "paired" hidden ALS in the same sector, so this would effectively double the search space. A really bad idea for run times, but hopefully a good idea for additional reductions. I'm really speculating on the rules/limitations/conditions of including a mixture of ALSs and HALSs, so any advice or guidance would be greatly appreciated.

[PIsaacson]

Preliminary results for Allan Barker's pre/post dual-linked adjacency reuse of RCDs from his 3rd example:

Given ALS A -N- ALS B -12- ALS C -1 or 2- ALS D, then N cannot be 1 or 2. Anything else is okay.
Given ALS A -1 or 2- ALS B -12- ALS C -N- ALS D, then N cannot be 1 or 2. Anything else is okay.

Adjacency reuse of the dual-linked RCDs for both incoming and outgoing ALSs results (sometimes, not always) in invalid reductions. I'm still looking at the conditions under which the eliminations are valid versus those which produce invalid results.

This "slight" change in adjacency rules generated an astonishing 5X increase in ALS chaining run times in my solver. I don't have the final figures for the top50000 (still running), but the top1465 with the new dual-link adjacency rules only advanced an additional 3 puzzles - 842 unsolved after ALS chaining with the former "new" adjacency rules vs. 839 unsolved after ALS chaining with the "new and improved" dual-link adjacency rules.

New and improved adjacency rules:

1) Non-adjacency reuse of RCDs is permitted.

2) Adjacency reuse of an RCD is only permitted when the predecessor/successor ALS is dual-linked and, in the case of a predecessor dual-linked ALS, the ancestor of the dual-link does not include one of the dual-linked RCDs. Similarly, in the case of a successor dual-linked ALS, the descendant of the dual-link cannot include one of the dual-linked RCDs.

Rule 2 is poorly written, but the given ALS chains listed above should help diagram what's allowed.

I deliberately skipped Allan's 2nd example since I don't want to tackle the issue of allowing ALS chains to include "foreign" objects such as the multitudinous almost thingies and various hinges. However, I am looking at including hidden ALSs since that still seems to be within the spirit of ALS chains.

[DonM]

Don,

Worse, I'm starting to modify my ALS chaining method to include hidden ALSs. Allan Barker presented one in the above thread and I think this warrants further investigation. Every ALS has a "paired" hidden ALS in the same sector, so this would effectively double the search space. A really bad idea for run times, but hopefully a good idea for additional reductions. I'm really speculating on the rules/limitations/conditions of including a mixture of ALSs and HALSs, so any advice or guidance would be greatly appreciated.

Hi Paul,

I think we have different core interests, both useful & of interest- yours in the solver area; mine in the manual solving area so my answer reflects that. I am always looking for new patterns or patterns previously 'discovered', but never utilized to their potential to further my manual solving. I've looked at Allan's 'ALS chain w/hidden ALSs' example and haven't been able to see a benefit from the manual solving point of view. Not that there isn't one- perhaps your study of it will flesh it out.

[PIsaacson]

Don,

I find myself torn between trying to advance my manual skills and trying to implement the latest state-of-the-art algorithms. ALS chains and SDCs are fairly recent additions to my manual processes, and I've found your threads extremely helpful in describing human approaches. Forgive me for hi-jacking your thread with computer solver issues.

Regretfully, I find it easier to write a computer algorithm for advanced techniques and as such, I want it to be as complete and perfect as possible. Hence the intense focus on adjacency rules and again, mea culpa. With that said, here's my finding for the new RCD rule with Allan's dual-link clause:

Code: Select all

top50000 results:

1) Old ALS RCD rules: 35747 solved with 475282 ALS chains resulting in 569390 eliminations at 19 msec/reduction and 1163 size 7, 92 size 8 and 5 size 9.

2) New ALS RCD rules: 41005 solved with 618588 ALS chains resulting in 749733 eliminations at 24 msec/reduction and 3410 size 7, 504 size 8, 87 size 9, 16 size 10, 3 size 11, and 1 size 12.

3) New ALS RCD rules + dual-link extension:  41062 solved with 568799 ALS chains resulting in 726094 eliminations at 69 msec/reduction and 2412 size 7, 307 size 8, 48 size 9, 8 size 10, 2 size 11, and 1 size 12.

Based on the fact that only 57 additional puzzles were advanced to a solution at the cost of tripling the run time, I'm going to default to just the new adjacency rules and make the dual-link adjacency rule optional in my solver. From a manual solving POV, I'll be lucky if I can find ALS chains that even require worrying about adjacency, but at least I'll know the rules!

[DonM]

Don, I find myself torn between trying to advance my manual skills and trying to implement the latest state-of-the-art algorithms. ALS chains and SDCs are fairly recent additions to my manual processes, and I've found your threads extremely helpful in describing human approaches. Forgive me for hi-jacking your thread with computer solver issues.
... Hence the intense focus on adjacency rules and again, mea culpa. With that said, here's my finding for the new RCD rule with Allan's dual-link clause:...

When there is even a remote benefit to manual solving I don't consider it hijacking and in the case of your clarifying & testing the rules for valid re-use of RCs in ALS chains the benefit is very real to manual solving. This was an area that was pretty hazy and unclarified in the past mainly because I don't think very many solvers were using ALS chains to begin with. That may be changing now.

[DonM]

The ALS Chain Tutorial has been revised particularly the part related to Doubly-Linked ALSs. One graphic has been revised and another completely replaced.

[PIsaacson]

Don,

I still think the RCD reuse should be amended to at least reflect the fact that reuse is permitted except in adjacent ALS pairs. I realize that manual solvers probably will never encounter the long/rare chains that require the RCD adjacency reuse clause, but it just feels "wrong" somehow to not include a qualifier about reuse being permitted. The latest "new and improved" adjacency rules that I'm currently using require pseudo-code to state properly, so I don't expect that anyone other than a programmer would be interested in those.

Cheers,
Paul

[DonM]

Don,

I still think the RCD reuse should be amended to at least reflect the fact that reuse is permitted except in adjacent ALS pairs. I realize that manual solvers probably will never encounter the long/rare chains that require the RCD adjacency reuse clause, but it just feels "wrong" somehow to not include a qualifier about reuse being permitted. The latest "new and improved" adjacency rules that I'm currently using require pseudo-code to state properly, so I don't expect that anyone other than a programmer would be interested in those.

Cheers,
Paul

Good point Paul- it was left out only for reasons related to amnesia. It has now been rectified and a well-deserved credit added.

[Bud]

Paul and Don, here is an example of a 4 set ALS-XY chain in which the ends of the chain have the same RCD 7. An important point to make about this case is that it is possible to make eliminations for more than 1 digit as in this example. The 4 ALS's are labeled a, b, c, d. It is easy to show that a not 7 in c forces 7 to be in d and vice versa so the chain is bidirectional. This means that either r4c8 or r6c9 is 19. In either case 1 and 9 cannot be in r9c8. Also note that if only one 7 were in c, we can also make 7 cell eliminations so this is potentially a very powerful ALS-XY-Chain.

4 Set ALS-XY-Chain Example

Code: Select all

 |------------------+--------------------+---------------------|
 |   5     9     8  |  237    37     6   |  127      4    127  |
 |   7     3     2  |    1     4    58   |  689     69     59  |
 |   1     6     4  |  278     9   258   |  278      3    257  |
 |------------------+--------------------+---------------------|
 | 248   248    79a |    5     6    48   |  179c   179c     3  |
 | 489   478     1  | 3789  3478  3489   |    5      2      6  |
 |   6     5     3  |  279    17   129   |  179      8      4  |
 |------------------+--------------------+---------------------|
 | 489  1478    79b |    6     2   189   |    3      5    179d |
 | 239    12     6  |   39     5     7   |    4     19d     8  |
 | 389   178     5  |    4   138  1389   | 12679 -167-9  1279  |
 |------------------+--------------------+---------------------|

The puzzle is Sudoku 9981 Extreme Book 57 #5.

[PIsaacson]

Bud,

Could you please indicate the ordering of the ALS chain? It looks like the chain needs to be c - a - b - d to account for the eliminations. If so, then r9c8 doesn't actually see all the 19s in ALS c and this violates current ALS chaining elimination rules. My solver found these eliminations from a slightly different POV:

Code: Select all

do_alschains - reducing r9c8.<1679> by <1>
do_alschains - reducing r9c8.<679> by <9>
do_alschains - als+[4x3/3] r48c8.<n179> -7- r4c3.<n79> -79- r7c3.<n79> -7- b9x35.<n179>

I think you have a forcing ALS chain or grouped-NL -- something other than a "pure" ALS chain.