The New Sudoku Players' Forum

[Ruud]

I thought that every solving technique ever invented would have found it's way to this forum, but there is one, that I have not found here yet. As many people use this forum as their prime source to learn about solving techniques, this technique deserves to be mentioned here.

The name is Aligned Pair Exclusion. You can call it APE.

As far as I know, Rod Hagglund is the inventor of the technique. It was used a couple of times to solve the 11 unsolvables by Mike Mepham.

A complete description with pictures can be read on http://www.scanraid.com/BasicStrategies.htm

I will attempt to summarize it here:

Take this puzzle:

Code: Select all

39..6..275...8.9.3.6.....5....94.......8.1.......57....2.....7.1.4.7...883..2..19
.------------------.------------------.------------------.
| 3     9     8    | 145   6     45   | 14    2     7    |
| 5     47    1    | 47    8     2    | 9     6     3    |
| 47    6     2    | 147   9     3    | 8     5     14   |
:------------------+------------------+------------------:
| 27    1     35   | 9     4     6    |*357   8    *25   |
| 24679 47    569  | 8     3     1    | 57    49    256  |
| 469   8     369  | 2     5     7    | 13    49    16   |
:------------------+------------------+------------------:
| 69    2     69   | 3     1     8    | 45    7     45   |
| 1     5     4    | 6     7     9    | 2     3     8    |
| 8     3     7    | 45    2     45   | 6     1     9    |
'------------------'------------------'------------------'

I marked 2 cells R4C7 and R4C9. These 2 cells share both a row and a box. There are 13 common peers for these 2 cells.

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.

I think the rule holds for any 2 cells, but that's food for further discussion. The fact that there are 2 shared units makes the rule more effective, not more true.

The candidates for these 2 cells are: {357} & {25}, resulting in the following combinations:

3-2
3-5 (impossible, because no candidates left in R4C2)
5-2
5-5 (impossible)
7-2 (impossible, because no candidates left in R4C1)
7-5 (impossible, because no candidates left in R5C7)

This leaves candidates {35} in R4C7 and a single {2} in R4C9.

For those looking for an alternative, there is an XY-wing eliminating 3 candidates for digit 7. Before I add this technique to my benchmark list, I need an example without such a simple alternative. Help me find one.

Code: Select all

.------------------.------------------.------------------.
| 3     9     8    | 145   6     45   | 14    2     7    |
| 5     47    1    | 47    8     2    | 9     6     3    |
| 47    6     2    | 147   9     3    | 8     5     14   |
:------------------+------------------+------------------:
|#27    1     35   | 9     4     6    |-357   8    *25   |
|-24679-47    569  | 8     3     1    |#57    49    256  |
| 469   8     369  | 2     5     7    | 13    49    16   |
:------------------+------------------+------------------:
| 69    2     69   | 3     1     8    | 45    7     45   |
| 1     5     4    | 6     7     9    | 2     3     8    |
| 8     3     7    | 45    2     45   | 6     1     9    |
'------------------'------------------'------------------'

I think this is a nice and elegant technique that can complement the suite of techniques that we already use.

I look forward to hear some comments.

Ruud.

[Myth Jellies]

It looks to be kind of a special case of Almost Locked Sets, or Subset Counting, so I think there will always be a reduction of that sort associated with the APE.

[MrHamilton]

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.

I think the rule holds for any 2 cells, but that's food for further discussion. The fact that there are 2 shared units makes the rule more effective, not more true.

...
I think this is a nice and elegant technique that can complement the suite of techniques that we already use.

I look forward to hear some comments.

Ruud.

It is rather nice.
But, I would ask, if the "any two cells" are in a box but not in a row/column, surely they cannot both point at any common cell outside of the box?
Are you saying you can use this method within a unit, under all the right circumstances?

[Ruud]

It looks to be kind of a special case of Almost Locked Sets, or Subset Counting, so I think there will always be a reduction of that sort associated with the APE.

If that is true, fine. Then we have established a link between these techniques. I found it quite similar to the elusive "Sue de Coq" technique.

But, I would ask, if the "any two cells" are in a box but not in a row/column, surely they cannot both point at any common cell outside of the box?
Are you saying you can use this method within a unit, under all the right circumstances?

The cells do not need to be in the same unit. Look at the following example: R4C7 and R6C3 also have 6 common peers. In this situation, you cannot use it effectively, but I can imagine that this could be a pair with eliminations based on the APE rule. Here they both see 5 bivalue cells (marked with #)

Code: Select all

.------------------.------------------.------------------.
| 3     9     8    | 145   6     45   | 14    2     7    |
| 5     47    1    | 47    8     2    | 9     6     3    |
| 47    6     2    | 147   9     3    | 8     5     14   |
:------------------+------------------+------------------:
|#27    1    #35   | 9     4     6    |*357   8     25   |
| 24679 47    569  | 8     3     1    | 57    49    256  |
| 469   8    *369  | 2     5     7    |#13   #49   #16   |
:------------------+------------------+------------------:
| 69    2     69   | 3     1     8    | 45    7     45   |
| 1     5     4    | 6     7     9    | 2     3     8    |
| 8     3     7    | 45    2     45   | 6     1     9    |
'------------------'------------------'------------------'

So, I think the rule is more general than Rod suggested.

Ruud.

[keith]

I did a Google search on Aligned Pair Exclusion and other variations, and did not find much.

The basic point seems to be this:

"If any cell (square) has possibilities <ab>, then no pair of two other cells in its group (of peers, buddies) can have solutions <a> and <b>."

(I have written this a little backwards from the original. The original said, pick two cells, then look at their peers with two possibilities.)

I have no problem with that statement. How would it be useful?

Well, in a single element (row, block, column), I think you'd rediscover a triple.

If one cell is <ab>, the simplest possibilities for the other two cells are <ac> and <bc>. One of the other two must be <c>.

Across two elements (block plus line), the above triple is, of course, an XY-wing.

Thinking about this, I am concluding that the APE works if you choose two cells:

1. The first contains a possibility <Z> which can be excluded by an XY-wing.
2. The second is a wingtip, also contains <Z>. Say it is <XZ>.

APE logic will then conclude from the other winged cells <XY> and <YZ> that the first cell cannot be <Z>.

In other words, I think the APE is an XY-wing. I will dig up the evidence tomorrow.

Best wishes,

Keith

[keith]

Actually, in the examples I have found, the APE is an XYZ-wing.

Keith

[lb2064]

The cells do not need to be in the same unit. Look at the following example: R4C7 and R6C3 also have 6 common peers. In this situation, you cannot use it effectively, but I can imagine that this could be a pair with eliminations based on the APE rule. Here they both see 5 bivalue cells (marked with #)

Code: Select all

.------------------.------------------.------------------.
| 3     9     8    | 145   6     45   | 14    2     7    |
| 5     47    1    | 47    8     2    | 9     6     3    |
| 47    6     2    | 147   9     3    | 8     5     14   |
:------------------+------------------+------------------:
|#27    1    #35   | 9     4     6    |*357   8     25   |
| 24679 47    569  | 8     3     1    | 57    49    256  |
| 469   8    *369  | 2     5     7    |#13   #49   #16   |
:------------------+------------------+------------------:
| 69    2     69   | 3     1     8    | 45    7     45   |
| 1     5     4    | 6     7     9    | 2     3     8    |
| 8     3     7    | 45    2     45   | 6     1     9    |
'------------------'------------------'------------------'

So, I think the rule is more general than Rod suggested.

Ruud.

Ruud - I don't think this will work. I beleive that the two cells have to be in the same unit to interact with each other (not just to see the same pairs).

Take a look at this puzzle:

Code: Select all

 *-----------------------------------------------------------*
 | 1     2     9     | 5     3     8     | 6     7     4     |
 | 5     7     3     | #46  *246   26    | 1     8     9     |
 | 4     8     6     | #79   1     79    | 5     2     3     |
 |-------------------+-------------------+-------------------|
 | 9     5     17    | 2     68    16    | 3     4     78    |
 | 3     4     17    | 18    9     5     | 78    6     2     |
 | 2     6     8     | 3     7     4     | 9     5     1     |
 |-------------------+-------------------+-------------------|
 | 8     3     5     | *479  #24   279   | 47    1     6     |
 | 6     9     4     | 178  #58    17    | 2     3     578   |
 | 7     1     2     | 468   4568  3     | 48    9     58    |
 *-----------------------------------------------------------*


Using (246) in [r2c5] and (479) in [r7c4] we have:

24 seen by [r6c5]
27
29
44 impossible
47
49
64 seen by [r2c4]
67
69

Thus [r7c4] <> 4 but this then makes the puzzle invalid.

I hope I have understood this right?
Thanks.

[Ruud]

44 impossible

This would only be impossible when the 2 cells share a house. This is not the case here.

I'm not sure if there are real examples where this would replace more complicated methods. The only claim I make is that the 2 cells do not need to be in the same house to exclude a combination that matches a bivalue cell that they both can see.
Before I can say this is effective, I need to implement it in my solver and run it against a large collection of sudokus.

Ruud.

[Graeme]

Hi Ruud & all,

No proof, but it appears that XY(Z)-Wing *could* be a subset of the expanded definition of APE, using any pair of cells.

I ran the top1465 initially slipping APE into this technique order:

Naked/Hidden-N, Block/Line, XY Chains, APE, Fish, BUG+1, XY(Z)-Wing, Colouring, etc, and found that APE was used in 135 puzzles, and XY(Z)-Wing in none!

So I moved XY(Z)-Wing in before APE:
Naked/Hidden-N, Block/Line, XY Chains, XY(Z)-Wing, APE, Fish, BUG+1, Colouring, etc, and found that XY-Wing was used in 14 puzzles, XYZ-Wing in 98, and APE was still used in 42 puzzles.

Some other observations:
- 23 other sub-techniques were used in an identical number of puzzles for both orders above
- XY Chains were 123 and 125 respectively in the above 2 orders, very close
- No puzzle solving errors with the expanded definition of APE

So it seems APE has nothing to do with other techniques.

regards,
Graeme

[ronk]

I ran the top1465 initially slipping APE into this technique order:
..........................

Did APE advance any puzzles to solution? I mean over and above those already solved without APE. To be meaningful, T&E methods should be disabled for both cases IMO.

TIA, Ron

[r.e.s.]

Before I add this technique to my benchmark list, I need an example without such a simple alternative. Help me find one.

In solving <this puzzle>, there are points along the way where it seems a candidate elimination could have been done with this method more easily than any other. For example, the second candidate grid in that posting is ...

Code: Select all

  12689   689     7       |  3        12569    1256    | 4       1258    258   
  12368   368     1268    |  12578    4        1256    | 1578    9       2578 
  4       5       1289    |  1278     1279     12      | 1378    6       2378 
 -------------------------+----------------------------+------------------------
  1289    489     1289    |  15      [125]     7       | 6       23458   234589
  5       46789   2689    | [24]       3      [46]     | 789     248     1     
  1267    467     3       |  9       [156]     8       | 57      245     2457   
 -------------------------+----------------------------+------------------------
  3689    2       5689    |  145     [15]      1345    | 13589   7       345689
  3679    1       569     |  257      8        2345    | 359     345     34569
  378     378     4       |  6       [157]     9       | 2       1358    358

Instead of RxCy notation, I'll just refer to the candidate sets ...

[125, 156] sees the [15] as well as the [24, 46], so
[125, 156] cannot be [1,5] or [5,1] because of the [15], and
[125, 156] cannot be [2,6] because of the [24, 46]
-- all the other possibilities for [125, 156] imply [157]=7;
therefore, [157]=7.

BTW, this method strikes me as closely related to (or is perhaps a form of) "Sherlocking" ...
http://forum.enjoysudoku.com/viewtopic.php?p=12022#p12022
http://forum.enjoysudoku.com/viewtopic.php?p=12555#p12555
http://forum.enjoysudoku.com/viewtopic.php?p=12697#p12697

[keith]

I have looked at all the examples (five or six) I could find online explaining the APE technique.

Every one of them uses the same squares to make some of the same eliminations that would be made by XY(Z)-wings.

In a couple of cases, APE identifies eliminations made by two (overlaid) XY(Z)-wings. However, the first Wing may make eliminations which kill the second. Then APE seems to identify more eliminations.

Questions for Graeme:

1. Do you scan for all XY(Z)-wings, then make all the eliminations? Or, do you make eliminations as you find each wing?

2. Can you please post two puzzles, if you have them:

a. A puzzle that is solved with no XY(Z)-wings when the wings are turned on, and that includes APE eliminations. How is this puzzle solved if you turn off APE?

b. A puzzle where XY(Z)-wings are used before APE, and where the number of APE exclusions is a minimum. Is there a case with no wings present, where APE excludes only one or two possibilities?

Thanks,

Keith

[ronk]

BTW, this method strikes me as closely related to (or is perhaps a form of) "Sherlocking" ...

I'm not familiar with Sherlocking, but I see the pattern as a "SueDeCoq", aka, Two-Sector Disjoint Subsets.

Code: Select all

 12689   689     7       |  3       -12569    1256    | 4       1258    258   
 12368   368     1268    |  12578    4        1256    | 1578    9       2578 
 4       5       1289    |  1278    -1279     12      | 1378    6       2378 
-------------------------+----------------------------+------------------------
 1289    489     1289    |  15      A125      7       | 6       23458   234589
 5       46789   2689    | B24        3      B46      | 789     248     1     
 1267    467     3       |  9       A156      8       | 57      245     2457   
-------------------------+----------------------------+------------------------
 3689    2       5689    |  145     C15       1345    | 13589   7       345689
 3679    1       569     |  257      8        2345    | 359     345     34569
 378     378     4       |  6       -157      9       | 2       1358    358

SueDeCoq:
 Sets: A = {r46c5} = {1256}
       B = {r5c46} = {246}
       C = {r7c5} = {15}
Eliminations:
 Except for sets A and C, digits 1 and 5 may be excluded from column 5

Except for sets A and B, digits 2, 4, and 6 could also be excluded from box 5 ... if there were any.

[r.e.s.]

Well done, ron! I need more practice spotting those, but I suppose they are relatively rare.

[Ruud]

The similarity with Sherlocking is minimal. Sherlocking is a kind of pattern overlay method, that compares 2 rows or columns. A kind of localized brute force.

I see the pattern as a "SueDeCoq", aka, Two-Sector Disjoint Subsets.

Yes, I found them similar in nature, as I mentioned in an earlier post. However, does this imply that APE and SueDeCoq are the same technique, or is there just an overlap, as with XY(Z) wings? More tests are needed.

I also would like to point out that the overlap with SueDeCoq only exists when the pair is aligned in an intersection. The extended variation is different.

I cannot do any testing myself. Building new techniques into a published solver is soooo much slower than into a private project.

Ruud.