APE - Further extendable?

Advanced methods and approaches for solving Sudoku puzzles

APE - Further extendable?

Postby SHuisman » Wed Aug 23, 2006 10:09 am

I know we got the basic APE, and the extended APE. I was wondering if you can further extend this.

APE:
Any two cells aligned on a row or column within the same box CANNOT duplicate the contents of any two-candidate cell they both see.
APE 2:
Says that any two cells with only abc excludes combinations ab, ac and bc from the pair under consideration.
APE 3: ??
Says that any 3 cells with only abcd excludes combinations ab,ac,ad,bc,bd,cd from the pair under consideration.
APE x:
Says that any x cells with only x+1 candidates (an ALS) excludes combinations (2 candidates out of the x+1 candidates collection, (x+1)!/(2!*(x-1)!)=x(x+1)/2 pairs) from the pair under consideration.

Is this valid ? You could make a 'super' APE:D
Last edited by SHuisman on Tue Sep 19, 2006 11:55 am, edited 1 time in total.
SHuisman
 
Posts: 17
Joined: 23 March 2006

Postby Mike Barker » Wed Aug 30, 2006 6:55 pm

The logic is correct. In each case the set you describe is an almost locked set which means it must include n cells for the n+1 values it contains. As long as the pair sees all elements of the ALS then the pair cannot contain 2 elements of the ALS. Do you have any examples of puzzles which utilize this APE extensions?
Last edited by Mike Barker on Fri Sep 01, 2006 3:48 pm, edited 1 time in total.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby tarek » Wed Aug 30, 2006 8:13 pm

It just follows that if only one candidate from the ALS exists outside the ALS cells... that candidate should occupy that cell outside the ALS ....

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

Postby SHuisman » Wed Aug 30, 2006 10:34 pm

Mike Barker wrote:The logic is correct. In each case the set you describe is an almost locked set which means it must include n-1 of the n values it contains. As long as the pair sees all elements of the ALS then the pair cannot contain 2 elements of the ALS. Do you have any examples of puzzles which utilize this APE extensions?


I don't have an example, i haven't coded it yet, but i will try! I was just wondering if it's logically correct! It's quite easy to code i think...
I also heard people about aligned triplet exclusion etc. I was thinking about extending it the other way:)
SHuisman
 
Posts: 17
Joined: 23 March 2006

Re: APE - Further extendable?

Postby udosuk » Thu Aug 31, 2006 3:11 am

SHuisman wrote:APE:
Any two cells aligned on a row or column within the same box CANNOT duplicate the contents of any two-candidate cell they both see.

Did you mean "Any two cells aligned on a row or column OR within the same box"?
Basically, the logic is just that "for any 2 cells seeing each other, if they both see an ALS, then they cannot both contain candidates from the ALS"... Right?:?:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Ruud » Thu Aug 31, 2006 3:46 am

udosuk wrote:Basically, the logic is just that "for any 2 cells seeing each other, if they both see an ALS, then they cannot both contain candidates from the ALS"... Right?


The 2 cells do not need to see each other. The key issue is that they both see the same cells.

A similar suggestion has been made before in this thread.

Pairs in a single house share 7 peers, but you need multiple houses for APE. When the 2 cells share a line AND a box, they have 13 shared peers. When they share a chute, they will have 6 shared peers, otherwise they only have 2 peers in common.

Although theoretically you can expand the rule to size N, it is probably easier to use ALS directly. APE is a very labour-intensive technique, certainly when you also have to look for ALS' of a considerable size.

Ruud
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby udosuk » Thu Aug 31, 2006 4:30 am

Thanks Ruud for the clarification... So I'll rephrase:

Basic concept of APE wrote:For any 2 cells, if they both see an ALS, then they cannot both contain candidates from the ALS, unless they both contain the same candidate.

Is there an inhabitant in the "zoo", which makes use of this technique, with the 2 engaging cells not seeing each other (barring an obvious XY-wing)?
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Mike Barker » Fri Sep 01, 2006 7:23 am

It turns out coding a general "Aligned Pair Exclusion" is fairly straight forward. The trick is realizing that the eliminations occur for a candidate from one cell when each pair formed by that candidate combined with each candidate from the other cell is contained within an ALS seen by both cells. If the cells share a house, then if the candidate is in both cells, it can be ignored. If the cells don't, then the elimination of that candidate is not valid with this technique. Here is an example of a 3-cell ALS "Unaligned Pair Exclusion" using cells r3c7 & r8c9 and two ALS (r789c7, r2c9):

Code: Select all
4-value Aligned Pair (r789c7, r2c9): : r3c7|r8c9 => r3c7<>4
+-------------------+----------------+----------------------+
|  128     18     7 |    4   689   3 |       5  2689    269 |
|    9    358  3458 |    7   568   2 |     348     1    @46 |
|  258      6   345 |  589   589   1 | -234789  2489   2479 |
+-------------------+----------------+----------------------+
|    6    158     2 |    3    14   9 |      48     7     45 |
|   58      4  3589 |  256   257  67 |       1   289   2359 |
|  157  13579   359 |   25    14   8 |       6   249  23459 |
+-------------------+----------------+----------------------+
|    3    789   689 |  289  2789   5 |   #2479  2469      1 |
|  578   5789  5689 |    1  2789   4 |    #279     3  *2679 |
|    4      2     1 |   69     3  67 |     #79     5      8 |
+-------------------+----------------+----------------------+


In this example, based on previous technique descriptions, one would 1) write down the 24 possible pairs between candidates in cells r3c7 & r8c9, 2) eliminate those which are contained in a common ALS or have the same candidate, and 3) determine if eliminations had occurred. What I implemented was to look at each of the 4 possible pairs using one candidate from r3c7 or the 6 possible pairs using one candidate from r8c9, 2) determine if all the pairs are contained in one of the common ALSs or have the same candidate in a common house, and 3) if so then eliminate the candidate. In the above example {(4,2), (4,6), (4,7), (4,9)} are all contained in one or the other of the ALSs so 4 can be eliminated. Its pretty obvious with this approach that not all of the cells of the ALS need to be seen by the candidate cell, only those cells of the ALS which contain the candidate.

Maybe APE should be redefined to be "ALS Pair Exclusion"?

Note that the same exclusion (r3c7<>4) above can be made with a VWXYZ-wing. In the past the conclusion was that APEs were a subset of ALSs exclusions. Maybe I'll look at that in the next couple of days.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Mike Barker » Fri Sep 01, 2006 9:28 pm

Here are a few more examples using ALS with up to 5 values. The first one clearly shows how the two cells do not need to see the entire ALS. In every case there is a similar ALS xy-rule (requires 3 ALSs). If one of the two cells of the APE is a bivalue the corresponding ALS xy-rule uses the same cells as the APE. If neither cell is a bivalue then the ALS xy-rule requires an additional ALS. In this case, the APE rule might be considered the simpler option. I guess my conclusion would be that APE are not required (ALS will pretty much do the same job), however simpler APE using bivalue ALSs may be easier to spot depending on what you are used to.

Code: Select all
..5....4.2...84.9.........7.3.9...2....15...31.6..3.....2.4....49.5...8.....26...
4-valued ALS Aligned Pair (r8c36, r2c479): : r2c3|r1c6 => r2c3<>3
+--------------------+----------------+------------------+
|  36789   678     5 |  2367  139 *17 |   1238    4  268 |
|      2    17  -137 |  @367    8   4 |   @356    9  @56 |
|   3689   468  3489 |   236  139   5 |  12368   13    7 |
+--------------------+----------------+------------------+
|      5     3    47 |     9    6   8 |    147    2   14 |
|    789   478   489 |     1    5   2 |     47    6    3 |
|      1     2     6 |     4    7   3 |     89    5   89 |
+--------------------+----------------+------------------+
|   3678  1678     2 |   378    4   9 |    135  137   15 |
|      4     9   #37 |     5   13 #17 |     26    8   26 |
|    378     5  1378 |   378    2   6 |     49  137   49 |
+--------------------+----------------+------------------+

B=1 cell ALS xy-rule: r8c36-1-r1c6-7-r2c479 => r2c3<>3
+--------------------+----------------+------------------+
|  36789   678     5 |  2367  139 *17 |   1238    4  268 |
|      2    17  -137 |  @367    8   4 |   @356    9  @56 |
|   3689   468  3489 |   236  139   5 |  12368   13    7 |
+--------------------+----------------+------------------+
|      5     3    47 |     9    6   8 |    147    2   14 |
|    789   478   489 |     1    5   2 |     47    6    3 |
|      1     2     6 |     4    7   3 |     89    5   89 |
+--------------------+----------------+------------------+
|   3678  1678     2 |   378    4   9 |    135  137   15 |
|      4     9   #37 |     5   13 #17 |     26    8   26 |
|    378     5  1378 |   378    2   6 |     49  137   49 |
+--------------------+----------------+------------------+

Code: Select all
..4.3...9........6.1....2.83.9..5...5..89.7......1....6..4..5....8....2....5.3..7
4-valued ALS Aligned Pair (r5c269, r679c8): : r5c8|r8c9 => r5c8<>6
+--------------------+---------------------+------------------+
|   278   2678     4 |   267      3    278 |     1     5    9 |
|  2789  23789    35 |  1279  24578  12478 |    34   347    6 |
|    79      1  3567 |   679   4567   4679 |     2   347    8 |
+--------------------+---------------------+------------------+
|     3   2468     9 |   267   2467      5 |   468     1   24 |
|     5   #246     1 |     8      9   #246 |     7  -346 #234 |
|  2478  24678    67 |     3      1    246 |   689  @689    5 |
+--------------------+---------------------+------------------+
|     6    379    37 |     4    278   2789 |     5   @89    1 |
|   479      5     8 |  1679     67   1679 |  3469     2  *34 |
|     1     49     2 |     5     68      3 |  4689 @4689    7 |
+--------------------+---------------------+------------------+

B=1 cell ALS xy-rule: r5c269-3-r8c9-4-r679c8 => r5c8<>6
+--------------------+---------------------+------------------+
|   278   2678     4 |   267      3    278 |     1     5    9 |
|  2789  23789    35 |  1279  24578  12478 |    34   347    6 |
|    79      1  3567 |   679   4567   4679 |     2   347    8 |
+--------------------+---------------------+------------------+
|     3   2468     9 |   267   2467      5 |   468     1   24 |
|     5   #246     1 |     8      9   #246 |     7  -346 #234 |
|  2478  24678    67 |     3      1    246 |   689  @689    5 |
+--------------------+---------------------+------------------+
|     6    379    37 |     4    278   2789 |     5   @89    1 |
|   479      5     8 |  1679     67   1679 |  3469     2  *34 |
|     1     49     2 |     5     68      3 |  4689 @4689    7 |
+--------------------+---------------------+------------------+

Code: Select all
97...2......86..3.........18..............4232.7..4...73.5.9.......1...9..96....8
5-valued ALS Aligned Pair (r1246c9, r1c789, r3c456): : r3c78 => r3c8<>4
+-------------------+-------------------+---------------------+
|    9     7  14568 |  134   345      2 |   @568  @4568  @456 |
|  145   125   1245 |    8     6    157 |      9      3 #2457 |
|    3   268   2568 | %479 %4579    %57 |  *2678 -45678     1 |
+-------------------+-------------------+---------------------+
|    8     4      3 |  129   259    156 |   1567  15679  #567 |
|  156  1569    156 |  179  5789  15678 |      4      2     3 |
|    2  1569      7 |  139   359      4 |   1568  15689   #56 |
+-------------------+-------------------+---------------------+
|    7     3  12468 |    5   248      9 |    126    146   246 |
|  456  2568  24568 |  247     1    378 |    356   4567     9 |
|  145   125      9 |    6   247     37 |  12357   1457     8 |
+-------------------+-------------------+---------------------+

B=3 cell ALS xy-rule: r1246c9-2-r2c123-1-r3c456|r2c6 => r3c8<>4
+-------------------+-------------------+---------------------+
|    9     7  14568 |  134   345      2 |    568   4568  #456 |
| *145  *125  *1245 |    8     6   @157 |      9      3 #2457 |
|    3   268   2568 | @479 @4579    @57 |   2678 -45678     1 |
+-------------------+-------------------+---------------------+
|    8     4      3 |  129   259    156 |   1567  15679  #567 |
|  156  1569    156 |  179  5789  15678 |      4      2     3 |
|    2  1569      7 |  139   359      4 |   1568  15689   #56 |
+-------------------+-------------------+---------------------+
|    7     3  12468 |    5   248      9 |    126    146   246 |
|  456  2568  24568 |  247     1    378 |    356   4567     9 |
|  145   125      9 |    6   247     37 |  12357   1457     8 |
+-------------------+-------------------+---------------------+

Code: Select all
5.9...2.6.2...5.1481.2.....2..6.1.9...1.3.........83....4..2.3.3..4.9..8.5.3...4.
5-valued ALS Aligned Pair (r8c2358, r8c23|r9c3): : r7c2|r9c5 => r7c2<>6
+---------------+-----------------+------------------+
|   5    4    9 |  178     17   3 |     2    78    6 |
|  67    2    3 |   78     69   5 |   789     1    4 |
|   8    1   67 |    2     49  46 |   579    57    3 |
+---------------+-----------------+------------------+
|   2    3   58 |    6    457   1 |  4578     9   57 |
|  67  689    1 |   59      3  47 |   458  2568   25 |
|   4  679   57 |  579      2   8 |     3    67    1 |
+---------------+-----------------+------------------+
|  19 -678    4 |  157  15678   2 |  1567     3  579 |
|   3 #@67 #@267|    4   #157   9 |  1567  #257    8 |
|  19    5 @278 |    3    *18  67 |   167     4  279 |
+---------------+-----------------+------------------+

B=2 cell ALS xy-rule: r8c2358-1-r19c5-8-r7c14579 => r7c2<>6
+---------------+-----------------+------------------+
|   5    4    9 |  178    *17   3 |     2    78    6 |
|  67    2    3 |   78     69   5 |   789     1    4 |
|   8    1   67 |    2     49  46 |   579    57    3 |
+---------------+-----------------+------------------+
|   2    3   58 |    6    457   1 |  4578     9   57 |
|  67  689    1 |   59      3  47 |   458  2568   25 |
|   4  679   57 |  579      2   8 |     3    67    1 |
+---------------+-----------------+------------------+
| @19 -678    4 | @157 @15678   2 | @1567     3 @579 |
|   3  #67 #267 |    4   #157   9 |  1567  #257    8 |
|  19    5  278 |    3    *18  67 |   167     4  279 |
+---------------+-----------------+------------------+


Code: Select all
.5....6....6..5....8.3.....5.3..7..1..7..9..2.1..3.7.....712.9...9.46.3.4.1...2..
5-valued ALS Aligned Pair (r7c127, r4569c8): : r4c7|r9c2 => r4c7<>4
+---------------+--------------+------------------+
|  137    5  24 |  249  279  8 |    6   127   347 |
|  137  379   6 |   24   27  5 |   89  1278  3478 |
|   79    8  24 |    3    6  1 |    5   247   479 |
+---------------+--------------+------------------+
|    5   29   3 |  268   28  7 | -489   @46     1 |
|    6    4   7 |    1   58  9 |    3   @58     2 |
|   29    1   8 |  256    3  4 |    7   @56    59 |
+---------------+--------------+------------------+
|  #38  #36   5 |    7    1  2 |  #48     9   468 |
|  278   27   9 |   58    4  6 |    1     3   578 |
|    4  *67   1 |  589  589  3 |    2  @578  5678 |
+---------------+--------------+------------------+

B=2 cell ALS xy-rule: r7c17-3-r79c2-7-r4569c8 => r4c7<>4
+---------------+--------------+------------------+
|  137    5  24 |  249  279  8 |    6   127   347 |
|  137  379   6 |   24   27  5 |   89  1278  3478 |
|   79    8  24 |    3    6  1 |    5   247   479 |
+---------------+--------------+------------------+
|    5   29   3 |  268   28  7 | -489   @46     1 |
|    6    4   7 |    1   58  9 |    3   @58     2 |
|   29    1   8 |  256    3  4 |    7   @56    59 |
+---------------+--------------+------------------+
|  #38  *36   5 |    7    1  2 |  #48     9   468 |
|  278   27   9 |   58    4  6 |    1     3   578 |
|    4  *67   1 |  589  589  3 |    2  @578  5678 |
+---------------+--------------+------------------+



Code: Select all
6............273...5..6.78.1.3...2....5.....974.......8..4....1....9..5....8.1..2
3-valued ALS Aligned Pair (r25c2, r7c37): : r7c2|r1c3 => r7c2<>6
+------------------+--------------------+------------------+
|   6    137   *17 |   39     48     48 |    19      2   5 |
|  49    #18   148 |    5      2      7 |     3     19   6 |
|  39      5     2 |    1      6     39 |     7      8   4 |
+------------------+--------------------+------------------+
|   1    689     3 |   67    458  45689 |     2    467  78 |
|   2    #68     5 |   37  13478   3468 |  1468   1467   9 |
|   7      4   689 |  269     18   2689 |     5     16   3 |
+------------------+--------------------+------------------+
|   8   -267  @679 |    4    357   2356 |   @69   3679   1 |
|  34  12367   146 |  267      9    236 |   468      5  78 |
|   5   3679  4679 |    8     37      1 |   469  34679   2 |
+------------------+--------------------+------------------+

B=1 cell ALS xy-rule: r7c37-7-r1c3-1-r25c2 => r7c2<>6
+------------------+--------------------+------------------+
|   6    137   *17 |   39     48     48 |    19      2   5 |
|  49    @18   148 |    5      2      7 |     3     19   6 |
|  39      5     2 |    1      6     39 |     7      8   4 |
+------------------+--------------------+------------------+
|   1    689     3 |   67    458  45689 |     2    467  78 |
|   2    @68     5 |   37  13478   3468 |  1468   1467   9 |
|   7      4   689 |  269     18   2689 |     5     16   3 |
+------------------+--------------------+------------------+
|   8   -267  #679 |    4    357   2356 |   #69   3679   1 |
|  34  12367   146 |  267      9    236 |   468      5  78 |
|   5   3679  4679 |    8     37      1 |   469  34679   2 |
+------------------+--------------------+------------------+


3-valued ALS Aligned Pair (r17c7, r7c37): : r7c6|r1c3 => r7c6<>6
+------------------+--------------------+------------------+
|   6    137   *17 |   39     48     48 |   #19      2   5 |
|  49     18   148 |    5      2      7 |     3     19   6 |
|  39      5     2 |    1      6     39 |     7      8   4 |
+------------------+--------------------+------------------+
|   1    689     3 |   67    458  45689 |     2    467  78 |
|   2     68     5 |   37  13478   3468 |  1468   1467   9 |
|   7      4   689 |  269     18   2689 |     5     16   3 |
+------------------+--------------------+------------------+
|   8     27  @679 |    4    357  -2356 |   @69   3679   1 |
|  34  12367   146 |  267      9    236 |   468      5  78 |
|   5   3679  4679 |    8     37      1 |   469  34679   2 |
+------------------+--------------------+------------------+

B=2 cell ALS xy-rule: r7c37-7-r1c37-9-r26c8 => r7c8<>6
+------------------+--------------------+------------------+
|   6    137   *17 |   39     48     48 |   *19      2   5 |
|  49     18   148 |    5      2      7 |     3    @19   6 |
|  39      5     2 |    1      6     39 |     7      8   4 |
+------------------+--------------------+------------------+
|   1    689     3 |   67    458  45689 |     2    467  78 |
|   2     68     5 |   37  13478   3468 |  1468   1467   9 |
|   7      4   689 |  269     18   2689 |     5    @16   3 |
+------------------+--------------------+------------------+
|   8     27  #679 |    4    357   2356 |   #69  -3679   1 |
|  34  12367   146 |  267      9    236 |   468      5  78 |
|   5   3679  4679 |    8     37      1 |   469  34679   2 |
+------------------+--------------------+------------------+
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Mike Barker » Sat Sep 02, 2006 3:22 am

It looks like I need to reassess the usefulness of APE. I was checking out the new algorithms against a set of puzzles that my solver has not been able to solve and with the addition of APE one puzzle originally posted by Coloin was solved. I think the thing that surprised me most was how simple the elimination is. To the best of my knowledge there are no corresponding ALS xz or xy rule eliminations. If not, then it appears as if APE stand alone apart from ALS. I'd be interested to know what other techniques could be used (I could easily have a bug in my solver which is missing something).

Code: Select all
5.2..9.......1..5.1..4..8....8..4..7.7..6....2..8..3....1..2..8....3..1.4....156.
3-valued ALS Aligned Pair (r47c1, r4c17): r2c1|r7c7 => r2c1<>3
+-------------------+-----------------+---------------------+
|     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 |
+-------------------+-----------------+---------------------+
|   @36   356     8 |     1  259    4 |    @69    29      7 |
|     9     7     4 |    23    6   35 |     12     8    125 |
|     2     1    56 |     8   59    7 |      3    49   4569 |
+-------------------+-----------------+---------------------+
|  #367  3569     1 |   569    4    2 |    *79   379      8 |
|    78   259  5679 |  5679    3   68 |   2479     1    249 |
|     4  2389   379 |    79   78    1 |      5     6    239 |
+-------------------+-----------------+---------------------+
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Myth Jellies » Sat Sep 02, 2006 5:17 am

Some excellent examples you've found, Mike. The APE reductions can all be mimicked with the same or fewer cells rather easily with AICs using ALS. A couple of the interesting ones.
Code: Select all
+-------------------+----------------+----------------------+
|  128     18     7 |    4   689   3 |       5  2689    269 |
|    9    358  3458 |    7   568   2 |    -348     1    B46 |
|  258      6   345 |  589   589   1 | -234789  2489   2479 |
+-------------------+----------------+----------------------+
|    6    158     2 |    3    14   9 |      48     7     45 |
|   58      4  3589 |  256   257  67 |       1   289   2359 |
|  157  13579   359 |   25    14   8 |       6   249  23459 |
+-------------------+----------------+----------------------+
|    3    789   689 |  289  2789   5 |   A2479  2469      1 |
|  578   5789  5689 |    1  2789   4 |    A279     3  A2679 |
|    4      2     1 |   69     3  67 |     A79     5      8 |
+-------------------+----------------+----------------------+

ALS/AIC: 4[A] = (2&6&7&9)[A] - 6[B] = 4[B] => r23c7 <> 4.
APE tends to miss these multiple reduction scenarios. My opinion is that APEish looking scenarios work much better as a marker for potential ALS work, rather than using it stand-alone. It also sidesteps the question of whether APE, which uses the candidates being eliminated in some significant deductions, is a brute force method. I do appreciate that it is easier to code up, though.

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 |
+-------------------+-----------------+---------------------+
|  AD36   356     8 |     1  259    4 |    C69    29      7 |
|     9     7     4 |    23    6   35 |     12     8    125 |
|     2     1    56 |     8   59    7 |      3    49   4569 |
+-------------------+-----------------+---------------------+
|  A367  3569     1 |   569    4    2 |    B79   379      8 |
|    78   259  5679 |  5679    3   68 |   2479     1    249 |
|     4  2389   379 |    79   78    1 |      5     6    239 |
+-------------------+-----------------+---------------------+

ALS/AIC: 3[A]=(6&7)[A]-7[B]=9[B]-9[C]=6[C]-6[D]=3[D] => set A or D (or both) must contain a 3, therefore r2c1 <> 3. I suspect the ALS program did not let you use one cell, r4c1, in two different ALSs.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Mike Barker » Sat Sep 02, 2006 3:39 pm

Thanks Myth. This won't be the first time that I've been able to improve my solver based on feedback like yours. I think that there is an arguement that APE is brute force given the historical definitions of the technique, but I think the modifications developed here eliminate that issue. Specifically the approach can be considered to be locate a cell which can see ALS which together contain all of the candidates of the cell and all of which contain one other candidate. This candidate can be eliminated from any cell which sees all of the ALS, but is not part of the ALS or the original cell. A candidate which is part of the original cell can be eliminated if the cell can see ALS which together contain all of the candidates of the cell and all of the ALS contain this candidate. This candidate can be eliminated from any cell which sees all of the ALS and the original cell, but is not part of the ALS or the original cell. This POV corrects the problem of a single elimination for example from one of the above examples:
Code: Select all
3-valued ALS Aligned Pair (r17c7, r7c37): : r1c3 => r7c68<>6
+------------------+--------------------+------------------+
|   6    137   *17 |   39     48     48 |   #19      2   5 |
|  49     18   148 |    5      2      7 |     3     19   6 |
|  39      5     2 |    1      6     39 |     7      8   4 |
+------------------+--------------------+------------------+
|   1    689     3 |   67    458  45689 |     2    467  78 |
|   2     68     5 |   37  13478   3468 |  1468   1467   9 |
|   7      4   689 |  269     18   2689 |     5     16   3 |
+------------------+--------------------+------------------+
|   8     27  @679 |    4    357  -2356 |   @69  -3679   1 |
|  34  12367   146 |  267      9    236 |   468      5  78 |
|   5   3679  4679 |    8     37      1 |   469  34679   2 |
+------------------+--------------------+------------------+
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Mike Barker » Sat Sep 09, 2006 3:16 pm

I've been thinking about the issue that Myth brought up regarding the fact that there can be overlap in the cells making up an AIC or nice loop. Its clear that this is possible in the cells which make up the starting and ending nodes in a loop as long as there are more than two nodes in the puzzle, for example, two ALS can't overlap. Allowable overlap is seen in the puzzle Myth evaluated using ALS and can also be seen in the following strong link (Turbot Fish) puzzle:
Code: Select all
Overlap 3-strong links: r1c2=3=r1c5-3-r4c5=3=r4c3-3-r3c3=3=r1c2~3~ => r1c5<>3,r6c2<>3,r3c3<>3
+------------+----------------+----------+
|  7 *36   5 |   4  -*36    9 |  1  8  2 |
|  8   4   9 |   7     2    1 |  5  6  3 |
|  1   2 -*36|  68  3568  356 |  7  4  9 |
+------------+----------------+----------+
|  9   1 *38 |   5   *38    2 |  6  7  4 |
|  2   5  68 |  68     4    7 |  9  3  1 |
|  4 -36   7 |   1     9   36 |  8  2  5 |
+------------+----------------+----------+
|  6   9   1 |   2     7    4 |  3  5  8 |
|  3   8   2 |   9    56   56 |  4  1  7 |
|  5   7   4 |   3     1    8 |  2  9  6 |
+------------+----------------+----------+

Its also possible for an ALS and grouped strong link to overlap:
Code: Select all
Overlap 4-element Grouped Nice Loop: ALS:r13c7|r3c8-4-r3c2-6-r7c2=6=r7c89-6-r9c7=6=r13c7~6~ => r2c9<>6
+----------------------+-----------------+------------------+
|  23679  23469      8 |   5  3467  2346 |  *67    49     1 |
|   3679  13469    139 |  39  3467     8 |    5     2  -679 |
|      5    *46     29 |  29   467     1 | *678  *468     3 |
+----------------------+-----------------+------------------+
|      4      8      7 |   6     2     9 |    3     1     5 |
|     39    359      6 |   8     1    35 |    2     7     4 |
|      1    235    235 |   7   345   345 |    9    68    68 |
+----------------------+-----------------+------------------+
|      8  *2356    235 |   1     9     7 |    4  *356   *26 |
|   2369      7      4 |  23  3568  2356 |    1  3589  2689 |
|   2369  12359  12359 |   4  3568  2356 | *678   358   789 |
+----------------------+-----------------+------------------+

The question is under what other conditions can there be overlap between two nodes in an AIC or nice loop?
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Myth Jellies » Sun Sep 10, 2006 8:38 am

Mike Barker wrote:The question is under what other conditions can there be overlap between two nodes in an AIC or nice loop?


From an AIC perspective, I'd say the ultimate overlap is nothing more than a closed or continuous loop.

Aside from that, I imagine anything goes so long as the alternating inferences hold.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Steve R » Mon Sep 11, 2006 11:59 am

I see that, in a passing remark, Mike suggested that almost locked sets cannot overlap.

The als argument is that, if two almost locked sets have a restricted common candidate, x, a second common candidate, z, cannot be eliminated from both of them. If it were, x would be required for both sets, contradicting the definition of “restricted.” Nothing here assumes the two sets of cells to be disjoint.

As Myth Jellies pointed out, the elimination

Code: Select all
5.2..9.......1..5.1..4..8....8..4..7.7..6....2..8..3....1..2..8....3..1.4....156.
3-valued ALS Aligned Pair (r47c1, r4c17): r2c1|r7c7 => r2c1<>3
+-------------------+-----------------+---------------------+
|     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 |
+-------------------+-----------------+---------------------+
|   @#36   356     8 |     1  259    4 |    @69    29      7 |
|     9     7     4 |    23    6   35 |     12     8    125 |
|     2     1    56 |     8   59    7 |      3    49   4569 |
+-------------------+-----------------+---------------------+
|  #367  3569     1 |   569    4    2 |    *79   379      8 |
|    78   259  5679 |  5679    3   68 |   2479     1    249 |
|     4  2389   379 |    79   78    1 |      5     6    239 |
+-------------------+-----------------+---------------------+

can be made via

ALS * = {r7c7}
ALS @ = {r4c1, r4c7}
ALS # = {r4c1, r7c1}

rcc(*, @) = 9
rcc(*, #) = 7

A 3 placed in r2c1 would require @ to contain the entry 9 and # to contain the entry 7, leaving * short of an entry.

Examples involving just two almost locked sets are also common.

Steve
Steve R
 
Posts: 74
Joined: 03 April 2006

Next

Return to Advanced solving techniques