Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Combined Overlapping Almost Locked Sets Rule (CoALS?)

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Myth Jellies

Joined: 20 Sep 2005
Posts: 14
:

Items
PostPosted: Thu Sep 21, 2006 7:33 am    Post subject: Combined Overlapping Almost Locked Sets Rule (CoALS?) Reply with quote

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:
 *----------------------------------------------------------------------*
 | .      .      .      |  .      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:
+-------------------+-----------------+---------------------+
|     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:
 *------------------------------------------------------------------------------*
 |  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:
+-----------------+-------------------+--------------------+ 
|   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 overlapping ALS, or all the non-overlap digits can be found in the combined overlapping 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.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron