Combined Overlapping Almost Locked Sets Rule (CoALS?)

Advanced methods and approaches for solving Sudoku puzzles

Combined Overlapping Almost Locked Sets Rule (CoALS?)

Postby Myth Jellies » Thu Sep 21, 2006 7:06 am

I've mentioned this in a couple of other threads. Maybe it is time to give this idea its own post.

Most puzzles have an abundance of Almost Locked Sets to consider. Many of these ALS's share overlapped cells. It turns out that you can consider two overlapping ALS's as one large structure, and the digits inside this structure have a potentially useful interrelationship.

You form a Combined Overlapping ALS structure by taking the union of 2 different ALS's that share at least one cell.

The useful relationship is as follows:

Combined Overlapping ALS Rule

For the cells that make up the entire combined ALS structure, either all the digits found in the overlap region are found in the structure, or all the digits not found in the overlap region are found in the structure, or both.

Lets show how you can use this information, first with a hypothetical example.
Code: Select all
 *----------------------------------------------------------------------*
 | .      .      .      |  .      C12347  .      | .     D67     .      |
 | .      .      .      | A125     .      .      | .      .      .      |
 | .      .      .      | A125     .      .      | .      .      .      |
 +----------------------+------------------------+----------------------+
 | .      .      .      |  .      B345    .      | .      .      .      |
 | .      .      .      |  .      B345    .      | .      .      .      |
 | .      .      .      |AB56      .      .      | .     -6*     .      |
 +----------------------+------------------------+----------------------+
 | .      .      .      |  .       .      .      | .      .      .      |
 | .      .      .      |  .       .      .      | .      .      .      |
 | .      .      .      |  .       .      .      | .      .      .      |
*----------------------------------------------------------------------*

Overlapping ALS A: r236c4 containing digits 1256.
Overlapping ALS B: r6c4|r45c5 containing digits 3456.
Combined ALS: r236c4|r45c5 (union of ALS A and B cells)
Overlap Cells: r6c4 (intersection of ALS A and B cells)
Digits in Overlap Cells: 5&6
Digits not in Overlap Cells: 1&2&3&4
CoALS relationship: ((5&6) = (1&2&3&4))r236c4|r45c5 a strong internal link.

Thus you can form this AIC...

((5&6) = (1&2&3&4))r236c4|r45c5 - ((1v2v3v4) = 7)r1c5 - (7=6)r1c8 => r6c8 <> 6

Here are some real world examples. First a simple one:

Code: Select all
+-------------------+-----------------+---------------------+
|     5  3468     2 |   367   78    9 |    146   347   1346 |
| -3678  3469  3679 |  2367    1  368 |  24679     5  23469 |
|     1   369  3679 |     4   25  356 |      8  2379    369 |
+-------------------+-----------------+---------------------+
|    36AB 356     8 |     1  259    4 |     69B   29      7 |
|     9     7     4 |    23    6   35 |     12     8    125 |
|     2     1    56 |     8   59    7 |      3    49   4569 |
+-------------------+-----------------+---------------------+
|   367A 3569     1 |   569    4    2 |     79C  379      8 |
|    78   259  5679 |  5679    3   68 |   2479     1    249 |
|     4  2389   379 |    79   78    1 |      5     6    239 |
+-------------------+-----------------+---------------------+

A and B denote the overlapping ALSs
Overlap digits are 3&6, non-overlap digits are 7&9
Thus have ((3&6) = (7&9))r4c17|r7c1

One can either generate an AIC using r7c7 to show r4c17|r7c1 contains 3&6, or one can just observe that since all the 7s and 9s in the combined ALS see the same 79 cell in r7c7, the (7&9) premise must be false and the combined ALS must contain 3&6. Either way you come up with it, any candidate three seeing all the threes in the combined ALS can be removed.

Code: Select all
 *------------------------------------------------------------------------------*
 |  356     4       1356    | 689     1569    1689    | 578     2       567     |
 |  9       578     567     | 2468    2456    68      | 1       4568    3       |
 |  56      18      2       | 3       14      7       | 9       48      56      |
 |--------------------------+-------------------------+-------------------------|
 |  23567   23579   3567    | 1       23689   4       | 23578   3568    2567    |
 |  8       123579  13567   | 269     2369    369     | 2357    1356    4       |
 |  2346    123     1346    | 7       2368    5       | 238     9       126     |
 |--------------------------+-------------------------+-------------------------|
 |AB347   AB37      8       | 5      -13479   2       | 6      A13     A19      |
 |  1      -2357    9       | 46      3467    36      | 2345    35      8       |
 | B2345    6      B345     | 489     1349    1389    | 2345    7      C1259    |
 *------------------------------------------------------------------------------*

A and B denote the overlapping ALSs
Overlap digits are 3&4&7, non-overlap digits are 1&2&5&9
Thus have ((3&4&7) = (1&2&5&9))r7c1289|r9c13
Since all the 1&2&5&9 candidates in the combined ALS see the r9c9 1259 cell, that cannot be true, therefore r7c1289|r9c13 contains 3&4&7.
We can remove the sevens from r7c5 and r8c2 because they see all the sevens in the combined ALS.

Code: Select all
+-----------------+-------------------+--------------------+ 
|   4    78   39  |  368     1  3689  | 23679   2378    5  | 
|   6    15   15  |    2   389     7  |    39     38    4  | 
|   2    78   39  | 3468  3489     5  |     1    378   67  | 
+-----------------+-------------------+--------------------+ 
| 357     4   18  |    9  2378A  238AB|   357      6  127  | 
|  37    16-   2  | 1367     5    36AB|     8      4    9  | 
| 357     9  168  |   16   278A    4  |  2357  12357  127  | 
+-----------------+-------------------+--------------------+ 
|   9  2356    7  |  348  2348   238B |  2456    125  126  | 
|   8    26D  46  |    5   279C    1  |  2467    279    3  | 
|   1   235   45  |  347     6   239B |  2457   2579    8  | 
+-----------------+-------------------+--------------------+

A and B denote the overlapping ALSs
Overlap digits are 2&3&6&8, non-overlap digits are 7&9
Thus have
((2&3&6&8) = (7&9))r46c5|r4579c6 - ((7or9) = 2)r8c5 - (2=6)r8c2 => r5c6 <> 6

Proof of the Combined Overlapping ALS (CoALS) rule

Assume two overlapping ALS's.

A digit found in the overlap must be part of both ALS's

If an overlap digit is not present in the combined ALS, then all the remaining digits in both ALS's must be true. This means that all non-overlap digits must be present.

If a non-overlap digit is not present in the combined ALS, then for at least one ALS, all the remaining digits must be present. This has to include all overlap digits, therefore all overlap digits must be present.

Therefore we can state that either all the overlap digits can be found in the combined ALS, or all the non-overlap digits can be found in the ALS.

This translates directly into a strong link between the ANDed overlap digits and the ANDed non-overlap digits over the entirety of the combined ALS cells.

Thanks to ronk and Mike Barker for discussions related to overlapping ALS which helped uncover this relationship.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby tarek » Thu Sep 21, 2006 8:30 am

nice work on this myth,

I haven't put it into practice, but it looks to me that this method would be difficult to spot for a manual solver because you should take into consideration spotting the overlap...

I'm wondering if -because all of the logic is a subset of COUNTING- that in this specific case, looking at it as one large ALS would be easier.

Having different digits makes this one big ALS easier to spot, it becomes more difficult when you have a digit in one section of this ALS that can't see the same digit in another section of this big angulating ALS....

tarek
User avatar
tarek
 
Posts: 2612
Joined: 05 January 2006

Re: Combined Overlapping Almost Locked Sets Rule (CoALS?)

Postby Havard » Mon Sep 25, 2006 12:29 am

Hi Myth, thanks for a nice post!

I have a slightly different view on what is going on in some of your posts though. I have been working quite a bit with locked sets that has "freedom bigger then 1", in other words AALS and even AAALS etc.
I have long thought to present some of these results in this forum, and hope to do so soon.

With an ALS you can do the following reasoning:
"if you can connect two other (chains of) ALS's to one ALS, and the ends of the two ALS's has a candidate in common, any other of that same candidate that both sets can see can be eliminated"
in other words in you have an ALS like this:
[12]

and are able to connect two other ALS's to this one:
[17]-1-[12]-2-[27]

you can now eliminate any 7 that both [17] and [27] can see. (simple XY wing)

now with an AALS the same holds true, except you now need THREE bindings going out of the AALS(yes, this means that you can have one single and one double binding). In it's simplest form this means:
Code: Select all
[17]-1-[123]-2-[27]
          |
          3
          |
         [37]

now any 7 that can see both [17], [27] and [37] can be eliminated!

now of course you can also have long chains of ALS's going out of the AALS, like this:
Code: Select all
[17]-1-[123]-2-[25]-5-[59]-9-[79]
          |
          3
          |
         [37]

now any 7 that can see both [17], [27] and [79] can be eliminated!

now the relevance to overlapping here, is that any of these three chains may be treated as a "separate" chain, and hence can overlap eachother but I think that this overlapping can only happen at the very end of the chains. I have at least only (so far) had any luck with letting chains of ALS's overlap at the endpoints. If we look at your last example in this light:

Code: Select all
+-----------------+-------------------+--------------------+ 
|                 |                   |                    | 
|                 |                   |                    | 
|                 |                   |                    | 
+-----------------+-------------------+--------------------+ 
|                 |       2378A  238AB|                    | 
|        16-      |               36AB|                    | 
|                 |        278A       |                    | 
+-----------------+-------------------+--------------------+ 
|                 |              238B |                    | 
|        26D      |        279C       |                    | 
|                 |              239B |                    |
+-----------------+-------------------+--------------------+


you would get:
Code: Select all
[26]-2-[279]-9-[238][238][239][36]
         |
         7
         |
      [2378]
      [278]
      [238]
      [36]

all three "endsets" have a 6 in common, and all these 6es can "see" the 6 in r2c5, and hence it can be eliminated. The fact that several cells in the two "end" ALSs overlap does not matter, since chain-ends are allowed to.

So my question is, can you show me an example of ALS-overlap where the overlap does not happen in the "end" of a chain?:)

(added:)
with your hypothetical example, the logic would go like this:

your C(12347) is an AlmostAlmostAlmostAlmost locked set.:)
Then you will need 5 bindings going out of it if you want to use the "exclude any candidate that can see all occurences of a non-linked candidate in all of the end-sets"-rule...
in this case:

Code: Select all
*----------------------------------------------------------------------*
 | .      .      .      |  .      C12347  .      | .     D67     .      |
 | .      .      .      | A125     .      .      | .      .      .      |
 | .      .      .      | A125     .      .      | .      .      .      |
 +----------------------+------------------------+----------------------+
 | .      .      .      |  .      B345    .      | .      .      .      |
 | .      .      .      |  .      B345    .      | .      .      .      |
 | .      .      .      |AB56      .      .      | .     -6*     .      |
 +----------------------+------------------------+----------------------+
 | .      .      .      |  .       .      .      | .      .      .      |
 | .      .      .      |  .       .      .      | .      .      .      |
 | .      .      .      |  .       .      .      | .      .      .      |
*----------------------------------------------------------------------*


Code: Select all
[56]-5-[125][125]=1,2=[12347]=3,4=[345][345]-5-[56]
                           |
                           7
                           |
                         [67]

any 6 that can see both [56], [56] and [67] can be eliminated. The fact that [56] is the same cell does not matter, since end-sets can overlap!:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Re: Combined Overlapping Almost Locked Sets Rule (CoALS?)

Postby Myth Jellies » Tue Sep 26, 2006 6:13 am

Havard wrote:I have a slightly different view on what is going on in some of your posts though. I have been working quite a bit with locked sets that has "freedom bigger then 1", in other words AALS and even AAALS etc.
I have long thought to present some of these results in this forum, and hope to do so soon.

Absolutely right. Your A*LS approach is spot on, and is basically equivalent to what Mike Barker is doing with his Death Blossom technique. It's also been tossed around a little bit in this thread. My goal in presenting the CoALS alternative is twofold:

1) You can take a branching, or multi-threaded, network and show it in a single-threaded AIC chain or deduction. I like single-threaded logic when I can get it:) .

2) The CoALS relationship is actually pretty prevalent & might be easier to spot and analyze for potential usefulness than running a bunch of chains off of every number in every cell. There are tricks you can apply to the overlapping ALS's (each ALS has to have a non-overlap digit unique to itself, for example) which will allow you to quickly weed out non-productive combinations.

Havard wrote:So my question is, can you show me an example of ALS-overlap where the overlap does not happen in the "end" of a chain?:)

(added:)
with your hypothetical example, the logic would go like this:

your C(12347) is an AlmostAlmostAlmostAlmost locked set.:)
Then you will need 5 bindings going out of it if you want to use the "exclude any candidate that can see all occurences of a non-linked candidate in all of the end-sets"-rule...
in this case:

Code: Select all
*----------------------------------------------------------------------*
 | .      .      .      |  .      C12347  .      | .     D67     .      |
 | .      .      .      | A125     .      .      | .      .      .      |
 | .      .      .      | A125     .      .      | .      .      .      |
 +----------------------+------------------------+----------------------+
 | .      .      .      |  .      B345    .      | .      .      .      |
 | .      .      .      |  .      B345    .      | .      .      .      |
 | .      .      .      |AB56      .      .      | .     -6*     .      |
 +----------------------+------------------------+----------------------+
 | .      .      .      |  .       .      .      | .      .      .      |
 | .      .      .      |  .       .      .      | .      .      .      |
 | .      .      .      |  .       .      .      | .      .      .      |
*----------------------------------------------------------------------*


Code: Select all
[56]-5-[125][125]=1,2=[12347]=3,4=[345][345]-5-[56]
                           |
                           7
                           |
                         [67]

any 6 that can see both [56], [56] and [67] can be eliminated. The fact that [56] is the same cell does not matter, since end-sets can overlap!:)

Would something like this count as an example where the overlap is not at the endpoints?

Code: Select all
*----------------------------------------------------------------------*
 | .      .      .      |  .      C12347  .      | .     D67     .      |
 | .      .      .      | A125     .      .      | .      .      .      |
 | .      .      .      | A125     .      .      | .      .      .      |
 +----------------------+------------------------+----------------------+
 | .      .      .      |  .      B345    .      | .      .      .      |
 | .      .      .      |  .      B345    .      | .      .      .      |
 | 68     .      .      |AB56      .      .      | .      .      .      |
 +----------------------+------------------------+----------------------+
 | .      .      .      |  .       .      .      | .      .      .      |
 | .      .      .      |  .       .      .      | .      .      .      |
 | 68     .      .      |  .       .      .      | .     -6*     .      |
*----------------------------------------------------------------------*
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Re: Combined Overlapping Almost Locked Sets Rule (CoALS?)

Postby Havard » Tue Sep 26, 2006 3:02 pm

Myth Jellies wrote:Would something like this count as an example where the overlap is not at the endpoints?

Code: Select all
*----------------------------------------------------------------------*
 | .      .      .      |  .      C12347  .      | .     D67     .      |
 | .      .      .      | A125     .      .      | .      .      .      |
 | .      .      .      | A125     .      .      | .      .      .      |
 +----------------------+------------------------+----------------------+
 | .      .      .      |  .      B345    .      | .      .      .      |
 | .      .      .      |  .      B345    .      | .      .      .      |
 | 68     .      .      |AB56      .      .      | .      .      .      |
 +----------------------+------------------------+----------------------+
 | .      .      .      |  .       .      .      | .      .      .      |
 | .      .      .      |  .       .      .      | .      .      .      |
 | 68     .      .      |  .       .      .      | .     -6*     .      |
*----------------------------------------------------------------------*


ok, so in this example, you would (to prevent going insane) still has to think of it as three different chains, but where two of the chains share three nodes (all at the end). Now can you make me an example where there are three different endpoints for three different chains, but at some stage some of the three chains shares a few cells?:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby Myth Jellies » Thu Sep 28, 2006 6:27 am

Well, I had a chain branch, and then come together again. I could make it split again, but I don't think that is what you are after. Perhaps something more like this...

Code: Select all
A123   .   .  | .     B1457  . | .     .  -9*
 .     .   .  | .      .     . | .     .  -9*
 .     .   .  | .      .     . | .     .  -9*
--------------+----------------+----------------
D257   .   .  | .   BDG457   . |D1457  .  D1457
 .     .   .  | .    BG457   . | .     .  E19
F36    .   .  |G568  BG567   . | .     .  H89
--------------+----------------+----------------
 .     .   .  | .      .     . | .     .  -9*
 .     .   .  | .      .     . | .     .  -9*
 .     .   .  | .     B3456  . | .     .  C39

 (1=4&5&6&7&3)B - (3=9)C
  |
A(123)-(3=6)F - (6=4&5&7&8)G - (8=9)H 
   |
  (2=4&5&7&1)D - (1=9)E

Cell sets B, D, and G represent overlapping ALS's. Chain-network endpoints are the 9s in r5c9, r6c9, and r9c9; which eliminate all other nines in that column.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Re: Combined Overlapping Almost Locked Sets Rule (CoALS?)

Postby ronk » Thu Sep 28, 2006 1:18 pm

Myth Jellies wrote:
Code: Select all
 *-------------------------------------------------------------*
 | .     .     .     |  .     C12347 .     | .    D67    .     |
 | .     .     .     | A125    .     .     | .     .     .     |
 | .     .     .     | A125    .     .     | .     .     .     |
 +-------------------+---------------------+-------------------+
 | .     .     .     |  .     B345   .     | .     .     .     |
 | .     .     .     |  .     B345   .     | .     .     .     |
 | .     .     .     | X56     .     .     | .    -6*    .     |
 +-------------------+---------------------+-------------------+
 | .     .     .     |  .      .     .     | .     .     .     |
 | .     .     .     |  .      .     .     | .     .     .     |
 | .     .     .     |  .      .     .     | .     .     .     |
 *-------------------------------------------------------------*
[edit: label X was your label AB]

Have you considered combining (relabeled) sets A, B and C?

If found this Bob Hanson style diagram helpful.
Code: Select all
                           1 . . . . . . . 1
                          ||                \
                          ||   2 . . . . 2---A---5 .
                          || //                .     .
      6---D---7 . . . 7====C              *5 . . . . . 5---X---6
              .     .     || \\                .   .
              .    .      ||   3 . . . . 3---B---5
              .   .       ||                /
               *7          4 . . . . . . . 4
                    (1 cell AAAALS)

-, |, / and \ denote ALS set
=, ||, // and \\ denote AALS, AAALS, AAALS etc. sets
... denotes weak link
*X denotes exclusion when chain is part of continuous loop

When the 7 is excluded from AAAALS set C, we don't know which of digits 1, 2, 3, or 4 it will contain. But we do know at least one of set A and B will contain a 5. If the combined sets A, B, and C become part of a continuous loop, other 5s that see all of the 5s in the combined sets may be excluded. Ditto for 7s. But no exclusions of the other four digits (1,2,3,4) may be made. So why not just "hide" those digits within a union of sets?

Code: Select all
      6---D---7 . . . 7---ABC---5 . . . 5---X---6
              .     .            .     .
              .    .              .    .
              .   .                .   .
               *7                    *5

Is there a hitch in this get-along? One I guess. The peer cells for digit 5 in the combined sets is the intersection of sets A and B, the same as for overlapped sets A and B.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Havard » Fri Sep 29, 2006 1:21 pm

Myth Jellies wrote:Well, I had a chain branch, and then come together again. I could make it split again, but I don't think that is what you are after. Perhaps something more like this...

Code: Select all
A123   .   .  | .     B1457  . | .     .  -9*
 .     .   .  | .      .     . | .     .  -9*
 .     .   .  | .      .     . | .     .  -9*
--------------+----------------+----------------
D257   .   .  | .   BDG457   . |D1457  .  D1457
 .     .   .  | .    BG457   . | .     .  E19
F36    .   .  |G568  BG567   . | .     .  H89
--------------+----------------+----------------
 .     .   .  | .      .     . | .     .  -9*
 .     .   .  | .      .     . | .     .  -9*
 .     .   .  | .     B3456  . | .     .  C39

 (1=4&5&6&7&3)B - (3=9)C
  |
A(123)-(3=6)F - (6=4&5&7&8)G - (8=9)H 
   |
  (2=4&5&7&1)D - (1=9)E

Cell sets B, D, and G represent overlapping ALS's. Chain-network endpoints are the 9s in r5c9, r6c9, and r9c9; which eliminate all other nines in that column.


Hi Myth! I have spent quite some time on this one now, and I can't find anything to object to... This does not mean that I distrust your wise words, but the fact that I have been working with ALS-chains for quite some time now, and always when I have tried to make the chains overlap, I have gotten errors, and has then concluded that overlapping is bad.:) However, in your example the overlapping is working like a charm, so I guess my question is wheter there are some exceptions to the overlap-rules, and how these can be formulated? When I get some time I will try and make my program allow overlapping, and then report back any errors I get here!:) Thanks for your great example by the way!

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby Mike Barker » Fri Sep 29, 2006 8:01 pm

Myth, actually what you have here is an excellent example of a Kraken Blossom which is known to have excellent overlap properties since each chain is defined independently (see a solution to U#23). You've already made a great contribution just by showing that ALS can overlap at the end of a nice loop. The question is, as Havard stated, what are the conditions for which ALS can overlap in the middle of a nice loop? Maybe the Kraken Blossom paradigm is the right way to understand the answer.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Mike Barker » Fri Oct 20, 2006 11:57 pm

So far I've had success with overlapping ALS when they are
    1) at the ends of a nice loop and the elimination is not part of the nodes (see here) and
    2) part of separate chains in a SUM technique elimination (eg a Kraken Cell such as Myth's example above). Note that any link in a nice loop can be thought of as a restricted subset so a nice loop can be broken up into two "nice chains" and overlapping can occur between the two chains.
I'm still working on understanding use of CoALS within a nice loop/chain since clearly not all ALS/bivalues within a chain may be able to overlap. I have, however, made some progress understanding overlap between strong links in a nice loop/chain. This may not be the best place to post this, but I'd like to keep posts regarding overlapping nice loop nodes in a common place.

The standard nice loop architecture allows for the end of one strong link to be the same node as the start of the next as long as the labels are different and the nodes are a single cell. The can be expanded. Consider Rod Hagglund's solution to Unsolvable#1 which can be formulated as a Kraken cell. What is interesting is that one chain consists of two strong links which overlap: R3C4-1-R3C89=1=R2C9=4=R3c9-4-. The generalization is pretty straight forward:
    1) the starting node of one stong link and the ending node of a second strong link can share a cell in a nice loop if the two nodes have different labels
    2) the starting (or ending) nodes of two strong links can share a cell in a nice loop if the two nodes have the same label (this may not be very useful since the loop created at the common node is not required for the nice loop)
    3) this can be expanded to grouped strong link nodes with possibly multiple overlaps as long as the first two rules are followed at the common nodes. Note this applies only to overlapping of non-contiguous nodes in a nice loop, not direct links which require the node be a single cell.
Note that even though this can result in one node with more than two links, the loop remains a double implication loop since we are not forking at the common node.

Code: Select all
Kraken Cell (R3C4-4-, R3C4-1-R3C89=1=R2C9=4=R3c9-4-, R3C4-3-R58C4-6-R5C3-2-R12C3|R1C2-4-): R3C4=134 => R3C2<>4
+------------------+---------------------+------------------+
|    1   46@ 2456@ |    9  24568      7  | 258   258     3  |
|   36    8  2456@ | 1346  23456   1235  |   9     7   124# |
|   37  2-4     9  |  134* 23458  12358  |   6  1258# 1248# |
+------------------+---------------------+------------------+
|    5    3     7  |    2    168      9  |   4   168   168  |
|    4    1    26@ |  367@  3678     38  |  28     9     5  |
|   69  269     8  |    5     16      4  |   3   126     7  |
+------------------+---------------------+------------------+
|  689  469     3  |   14   2459    125  |   7  2568   268  |
| 6789    5    16  |   37@  2379     23  |  18     4   268  |
|    2   47    14  |    8    457      6  |  15     3     9  |
+------------------+---------------------+------------------+


Here's an example with a grouped nice loop:
Code: Select all
Common 4-element Grouped Nice Loop: r8c7=2=r8c6=9=r56c6-9-ALS:r45c5|r4c4-8-r6c6=8=r6c7~8~r8c7 => r8c7<>8
+-----------------+--------------------+-------------------+
|   8    47   13  | 3579    379     6  |   123  124   345  |
|  47     5   36  |  378      2     1  |     9   48  3468  |
|   9     2  136  |  358      4    58  | 13568    7  3568  |
+-----------------+--------------------+-------------------+
| 345   349    2  | 138*# 1389*#    7  |   158    6  4589  |
|   6  1349    8  |  259   139*# 259*@ |     7  149   459  |
|  15    19    7  |    4      6  589*@ |   158*   3     2  |
+-----------------+--------------------+-------------------+
| 137  1378    9  |  128      5     4  |  2368   28  3678  |
| 137  1378    4  |    6    189    29* |  23-8*   5  3789  |
|   2     6    5  |  789    789     3  |     4   89     1  |
+-----------------+--------------------+-------------------+
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Myth Jellies » Sat Oct 21, 2006 5:39 pm

Mike Barker wrote:I'm still working on understanding use of CoALS within a nice loop/chain since clearly not all ALS/bivalues within a chain may be able to overlap.


The CoALS rule always holds, but I don't think it will be useful above and beyond a regular ALS unless the two ALS's being combined have the following properties.
    1) The two ALS's to be combined cannot both lie entirely within the same group. In other words, each ALS will need some piece of itself that is outside of the intersection of the two ALS's. Otherwise the two ALS's could just be trivially combined into a single ALS.

    2) Both of the ALS to be combined must bring one or more unique digits to the party. If they don't both have a unique digit, then the CoALS rule will provide no useful linking relationships above and beyond what you could get from just one of the combined ALS's.

    3) The link out from the non-overlap digits must be a combined link involving at least one unique digit from both component ALS's. Again, if this is not the case, then the CoALS rule will provide nothing above and beyond what could be found from one of your component ALS's

Mike Barker wrote:The standard nice loop architecture allows for the end of one strong link to be the same node as the start of the next as long as the labels are different and the nodes are a single cell. The can be expanded. Consider Rod Hagglund's solution to Unsolvable#1 which can be formulated as a Kraken cell. What is interesting is that one chain consists of two strong links which overlap: R3C4-1-R3C89=1=R2C9=4=R3c9-4-. The generalization is pretty straight forward:
    1) the starting node of one stong link and the ending node of a second strong link can share a cell in a nice loop if the two nodes have different labels
    2) the starting (or ending) nodes of two strong links can share a cell in a nice loop if the two nodes have the same label (this may not be very useful since the loop created at the common node is not required for the nice loop)
    3) this can be expanded to grouped strong link nodes with possibly multiple overlaps as long as the first two rules are followed at the common nodes. Note this applies only to overlapping of non-contiguous nodes in a nice loop, not direct links which require the node be a single cell.
Note that even though this can result in one node with more than two links, the loop remains a double implication loop since we are not forking at the common node.

Code: Select all
Kraken Cell (R3C4-4-, R3C4-1-R3C89=1=R2C9=4=R3c9-4-, R3C4-3-R58C4-6-R5C3-2-R12C3|R1C2-4-): R3C4=134 => R3C2<>4
+------------------+---------------------+------------------+
|    1   46@ 2456@ |    9  24568      7  | 258   258     3  |
|   36    8  2456@ | 1346  23456   1235  |   9     7   124# |
|   37  2-4     9  |  134* 23458  12358  |   6  1258# 1248# |
+------------------+---------------------+------------------+
|    5    3     7  |    2    168      9  |   4   168   168  |
|    4    1    26@ |  367@  3678     38  |  28     9     5  |
|   69  269     8  |    5     16      4  |   3   126     7  |
+------------------+---------------------+------------------+
|  689  469     3  |   14   2459    125  |   7  2568   268  |
| 6789    5    16  |   37@  2379     23  |  18     4   268  |
|    2   47    14  |    8    457      6  |  15     3     9  |
+------------------+---------------------+------------------+


Here's an example with a grouped nice loop:
Code: Select all
Common 4-element Grouped Nice Loop: r8c7=2=r8c6=9=r56c6-9-ALS:r45c5|r4c4-8-r6c6=8=r6c7~8~r8c7 => r8c7<>8
+-----------------+--------------------+-------------------+
|   8    47   13  | 3579    379     6  |   123  124   345  |
|  47     5   36  |  378      2     1  |     9   48  3468  |
|   9     2  136  |  358      4    58  | 13568    7  3568  |
+-----------------+--------------------+-------------------+
| 345   349    2  | 138*# 1389*#    7  |   158    6  4589  |
|   6  1349    8  |  259   139*# 259*@ |     7  149   459  |
|  15    19    7  |    4      6  589*@ |   158*   3     2  |
+-----------------+--------------------+-------------------+
| 137  1378    9  |  128      5     4  |  2368   28  3678  |
| 137  1378    4  |    6    189    29* |  23-8*   5  3789  |
|   2     6    5  |  789    789     3  |     4   89     1  |
+-----------------+--------------------+-------------------+


Here is the AICs for the one's pathway in the first example:
(3or4=1)r3c4 - (1)r3c89 = (1-4)r2c9 = (4)r3c9

Here is the AIC for the second example:
(2)r8c7 = (2-9)r8c6 = (9)r56c6 - (9=1&3&8)r45c5|r4c4 - (8)r6c6 = (8)r6c7 => r8c7 <> 8

I'm not sure that I would characterize these two examples as overlaps. It is true that they pass through the same cell more than once, but when they pass through, they use different candidates. On a candidate-to-candidate linking basis, no candidate gets used or is needed in the chain more than once.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Mike Barker » Sun Nov 26, 2006 7:44 pm

I posted the next installment in the study of common cells within nodes of basic and grouped nice loops in a separate thread because the study is different than COALS. That doesn't mean there isn't overlap:) between the two topics. In checking out some of my latest code changes and looking at Carcul's observation and Steve's question I came across a couple of interesting COALS:

Code: Select all
Overlap 2-element Grouped Nice Loop: ALS:r6c459-7-ALS:r6c89|r5c79~16~ => r6c7<>1,r6c7<>6
+---------------------+------------------+---------------------+
|    2  13469   1349  |   139    139  8  |   1467  1467     5  |
|  157   1478   1458  |   125    125  6  |      9     3  1248  |
| 1356  13689  13589  |     4  12359  7  |    126   126  1268  |
+---------------------+------------------+---------------------+
|   13      2      6  |   179     19  5  |   1347     8    14  |
|   15     18      7  |   168      4  3  |   1256@    9   126@ |
|    9   1348  13458  |  1678*   168* 2  | 357-16   157@  16*@ |
+---------------------+------------------+---------------------+
|    8    369    239  |  2356   2356  1  |   2456  2456     7  |
|    4      5     12  |    26      7  9  |      8   126     3  |
| 1367   1367    123  | 23568   3568  4  |   1256  1256     9  |
+---------------------+------------------+---------------------+

Overlap 2-element Grouped Nice Loop: ALS:r9c4|r78c5-7-ALS:r346789c4~5~ => r5c4<>5
+-------------------+---------------------+-------------------+
|  28  2348   2348  |      1    5     46  |   7  2368      9  |
|   1     6  23458  |      9  478     47  | 358   238    258  |
|  58     7      9  |    368@   2     36  |   1     4    568  |
+-------------------+---------------------+-------------------+
|   4     5    238  |    238@ 389      1  |  68   689      7  |
|   6    28      1  |  278-5  789    257  |   4   589      3  |
|   9    38      7  |    345@   6    345  |   2    58      1  |
+-------------------+---------------------+-------------------+
|   3     9    245  |  24567@  47*     8  |  56     1   2456  |
|   7     1    458  |  23456@  34* 23456  |   9  2368  24568  |
| 258   248      6  |   345*@   1      9  |  38     7   2458  |
+-------------------+---------------------+-------------------+

Overlap 2-element Grouped Nice Loop: ALS:r1c2348-6-ALS:r1c45|r3c46|r2c4~3~ => r3c5<>3
+-----------------+----------------------+--------------------+
| 34   789*   78* | 3789*@  34679@    2  |     1   678*    5  |
| 34  2789     6  |  3789@      1     5  |  2348   278   237  |
|  5  1278  1278  |   378@  467-3   347@ | 23468     9  2367  |
+-----------------+----------------------+--------------------+
|  2  1357     9  |     6     357     8  |    35     4    13  |
| 16  4567  3457  | 12379   23579  1379  |  2359   126     8  |
|  8   356    35  |     4    2359    19  |     7   126  2369  |
+-----------------+----------------------+--------------------+
|  7    45    45  |   129       8     6  |    29     3   129  |
| 16  2368   238  |     5    2349   349  |  2689  1278  2679  |
|  9  1368  1238  |  1237     237   137  |   268     5     4  |
+-----------------+----------------------+--------------------+
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Havard » Sun Nov 26, 2006 10:27 pm

I have come to that as long as the overlapping ALS cells does not contain the "restricted common" of the two sets, they are legal. Is this the rule you use too Mike? I am having a bit of trouble proving why it is like this, but all the examples I have tried out point to this. Take your first example. If you add a "7" (the restricted common) in the overlap cell (r6c9) the eliminations are no longer valid. This would certainly add a lot to the power of ALS!:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby Mike Barker » Sun Nov 26, 2006 10:52 pm

For the case of the above examples, that is sufficient. In the case of longer grouped nice loops I'm claiming in the common cell thread, that it is also possible for ALS to share cells if the "input" link label to each ALS is the same and the ALS are internal to the loop. If the ALS are at the start and end of the loop (which is which is arbitrary) and the loop is at least 3 nodes long, then there are no restrictions on which cells can be shared. Unfortunately I don't have mathematical proofs of any of the statements either.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Myth Jellies » Mon Nov 27, 2006 7:21 am

Mike Barker wrote:I posted the next installment in the study of common cells within nodes of basic and grouped nice loops in a separate thread because the study is different than COALS. That doesn't mean there isn't overlap:) between the two topics. In checking out some of my latest code changes and looking at Carcul's observation and Steve's question I came across a couple of interesting COALS:

Code: Select all
Overlap 2-element Grouped Nice Loop: ALS:r6c459-7-ALS:r6c89|r5c79~16~ => r6c7<>1,r6c7<>6
+---------------------+------------------+---------------------+
|    2  13469   1349  |   139    139  8  |   1467  1467     5  |
|  157   1478   1458  |   125    125  6  |      9     3  1248  |
| 1356  13689  13589  |     4  12359  7  |    126   126  1268  |
+---------------------+------------------+---------------------+
|   13      2      6  |   179     19  5  |   1347     8    14  |
|   15     18      7  |   168      4  3  |   1256@    9   126@ |
|    9   1348  13458  |  1678*   168* 2  | 357-16   157@  16*@ |
+---------------------+------------------+---------------------+
|    8    369    239  |  2356   2356  1  |   2456  2456     7  |
|    4      5     12  |    26      7  9  |      8   126     3  |
| 1367   1367    123  | 23568   3568  4  |   1256  1256     9  |
+---------------------+------------------+---------------------+

My AIC representation for this would be...

(1&6&8=7)r6c459 - (7=2&5&1&6)r5c79|r6c89

Thus all 1's and 6's which see all of the 1's and 6's in the two ALS's can be removed. It is easy to see that if you tried to include r6c8 in the *ALS (in order to eliminate the 5 from r6c7 as well) then the weak link between 7's in the two ALS's would no longer be valid--the shared 7 would allow both ALS's to contain a 7 and the weak link disappears.

Even though there is plenty of overlap here, this does not use the CoALS relationship. Here, CoALS gives you the following...

(1&6 = 2&5&7&8)r5c79|r6c4589

To use this, you would need something like a 28 cell in r5c456. That would be enough to show (2&5&7&8) cannot be true, therefore (1&6) must be true, and then you could make the same reduction. The remaining reductions do not use CoALS either. They are just two-ALS-element chains with significant overlap and a weak link between them.

Code: Select all
Overlap 2-element Grouped Nice Loop: ALS:r9c4|r78c5-7-ALS:r346789c4~5~ => r5c4<>5
+-------------------+---------------------+-------------------+
|  28  2348   2348  |      1    5     46  |   7  2368      9  |
|   1     6  23458  |      9  478     47  | 358   238    258  |
|  58     7      9  |    368@   2     36  |   1     4    568  |
+-------------------+---------------------+-------------------+
|   4     5    238  |    238@ 389      1  |  68   689      7  |
|   6    28      1  |  278-5  789    257  |   4   589      3  |
|   9    38      7  |    345@   6    345  |   2    58      1  |
+-------------------+---------------------+-------------------+
|   3     9    245  |  24567@  47*     8  |  56     1   2456  |
|   7     1    458  |  23456@  34* 23456  |   9  2368  24568  |
| 258   248      6  |   345*@   1      9  |  38     7   2458  |
+-------------------+---------------------+-------------------+

AIC rep

(5&2&3&4&6&8 = 7)r346789c4 - (7 = 3&4&5)r78c5|r9c4 => r5c4 <> 5

another way to do this is

(5&2&3&4&6&8 = 7)r346789c4 - (7 = 3&4)r78c5 - (3v4 = 5)r9c4

Code: Select all
Overlap 2-element Grouped Nice Loop: ALS:r1c2348-6-ALS:r1c45|r3c46|r2c4~3~ => r3c5<>3
+-----------------+----------------------+--------------------+
| 34   789*   78* | 3789*@  34679@    2  |     1   678*    5  |
| 34  2789     6  |  3789@      1     5  |  2348   278   237  |
|  5  1278  1278  |   378@  467-3   347@ | 23468     9  2367  |
+-----------------+----------------------+--------------------+
|  2  1357     9  |     6     357     8  |    35     4    13  |
| 16  4567  3457  | 12379   23579  1379  |  2359   126     8  |
|  8   356    35  |     4    2359    19  |     7   126  2369  |
+-----------------+----------------------+--------------------+
|  7    45    45  |   129       8     6  |    29     3   129  |
| 16  2368   238  |     5    2349   349  |  2689  1278  2679  |
|  9  1368  1238  |  1237     237   137  |   268     5     4  |
+-----------------+----------------------+--------------------+

AIC is

(3&7&8&9 = 6)r1c2348 - (6 = 4&7&8&9&3)r123c4|r1c5|r3c6 => r3c5 <> 3

So even though these do not use CoALS, They likely are quite useful. The AIC representation is actually all the proof you need that you just need to avoid using overlap digits as your weak link (restricted common digit?) between the two ALS's
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Next

Return to Advanced solving techniques