## Aligned Pair Exclusion (APE, no DJ)

Advanced methods and approaches for solving Sudoku puzzles
Graeme wrote: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.

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

XY(Z...)-Wing, Sue de Coq, XZ-Rule, and I will bet APE as well, are all specific implementations of the more general Almost Locked Sets/Subset Counting Technique. If you move ALS ahead of APE, I don't think you would get any APE hits. The logic behind the eliminations is very similar. In the setup, you can't have any digit with a multiplicity greater than 2, and you are eliminating digit selections that would drop the total digit multiplicity to less than the number of cells in a subset selection.

Show a couple of the APE eliminations not covered by XYZ-Wings and let's see if an ALS restricted to using a subset of the same cells will cover it.
Myth Jellies

Posts: 593
Joined: 19 September 2005

Ruud wrote:
Ron wrote: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.

Definitely not the same technique IMO. I've seen APE elims (on this thread) that I was unable to explain with a SueDeCoq.

I actually meant my post to show that r.e.s.' puzzle was not a good examplar for the APE ... and forgot to say so.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

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 `

Even r.e.s's APE-ish example falls to subset counting. The 5 starred cells have the digits 12456 with respective multiplicities of 11111 for a total of 5. Thus any outside placement of a digit which prevents placement of one of those five digits in all of the starred cells will reduce the total multiplicity by 1 and must therefore be illegal. Thus we can eliminate all 1's and 5's in column 5, and 2's, 4's, and 6's in box 5, and the 4's in row 5, that do not lie in starred cells.
Myth Jellies

Posts: 593
Joined: 19 September 2005

Firstly let me say I found the APE code I added last night picked up some XY-Wings missed within that code. I've re-run the test on top1465 and found that with XY(Z)-Wing first, APE still finds more exlcusions in 6 puzzles.

I think APE finds exclusions where the number of cell candidates exceeds the current definitions of XY-Wing (3 bi-values) and XYZ-Wing (bi-value <-> tri-value <-> bi-value).

Ron wrote: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.

T&E was still enabled, but no, APE didn't use other techniques, including T&E, any less. But given it appears to be rare after XY(Z)-Wing, with a small number of candidate removals, I'm not surprised.

Keith wrote: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?

1. Interesting question thanks, Keith - My code removes candidates when found, but I'd like to find out if a full scan reduces the need for more complicated or T&E techniques. Which leads to the question: should every puzzle state be fullly examined by every technique before making changes? Any opinions, anyone?

2 See below (1 example for now ;-). With APE disabled, the same following Forcing Chain Error step still occurred, leading to the solution.

Myth wrote:... If you move ALS ahead of APE, I don't think you would get any APE hits. The logic behind the eliminations is very similar...

I should have listed all my current solve techniques, which don't yet include ALS.

Here's an example that uses APE only, with XY(Z)-Wing before APE and enabled.

top1465 #1182
8·1·······7··1···45··6·89······63·2····1········7··61··8········1·32··7·3··5·····

Code: Select all
`8 . 1 | . . . | . . .. 7 . | . 1 . | . . 45 . . | 6 . 8 | 9 . .------+-------+------. . . | . 6 3 | . 2 .. . . | 1 . . | . . .. . . | 7 . . | 6 1 .------+-------+------. 8 . | . . . | . . .. 1 . | 3 2 . | . 7 .3 . . | 5 . . | . . .after basic techniques, and a little Nishio ...8     9      1      | 2  3   4  | 7     5   6    6     7      3      | 9  1   5  | 2     8   4    5     24     24     | 6  7   8  | 9     3   1    --------------------+-----------+----------------1     45     79     | 8  6   3  | 45    2   79   2479  23456  246789 | 1  45  29 | 3458  49  35789249   2345   2489   | 7  45  29 | 6     1   3589 --------------------+-----------+----------------27    8      5      | 4  9   17 | 13    6   23   49    1      49     | 3  2   6  | 58    7   58   3     26     267    | 5  8   17 | 14    49  29   then APE (with cell r5c1) removed candidate {9} from cell r5c3`

All pair combinations with a 9 in r5c3 (2-9, 4-9, 7-9, 9-9) are invalid within block 4 and row 5, using the APE definition.
Graeme

Posts: 18
Joined: 06 February 2006

With finned fish (colouring as a replacement/no need for Nishio)....
you have this position....
Code: Select all
`*-----------------------------------------------------------------*| 8      9      1     | 2      3      4     | 7      5      6     || 6      7      3     | 9      1      5     | 2      8      4     || 5      24     24    | 6      7      8     | 9      3      1     ||---------------------+---------------------+---------------------|| 1      45    -79    | 8      6      3     | 45     2     *79    || 2479   23456  246789| 1      45     29    | 3458   49     35789 || 249    2345   2489  | 7      45     29    | 6      1      3589  ||---------------------+---------------------+---------------------|| 27     8      5     | 4      9      17    | 13     6      23    || 49     1      49    | 3      2      6     | 58     7      58    || 3     %26    %267   | 5      8      17    | 14     49    *29    |*-----------------------------------------------------------------*Eliminating 7 from r4c3(ALS-XZ A=279 in r4c9, r9c9 B=267 in r9c2, r9c3  x=2 z=7)`

tarek

tarek

Posts: 2650
Joined: 05 January 2006

Graeme wrote:I should have listed all my current solve techniques, which don't yet include ALS.

Here's an example that uses APE only, with XY(Z)-Wing before APE and enabled.

top1465 #1182
8·1·······7··1···45··6·89······63·2····1········7··61··8········1·32··7·3··5·····
Code: Select all
`8     9      1      | 2  3   4  | 7     5   6    6     7      3      | 9  1   5  | 2     8   4    5     24     24     | 6  7   8  | 9     3   1    --------------------+-----------+----------------1     45     79     | 8  6   3  | 45    2   79   2479  23456  246789 | 1  45  29 | 3458  49  35789249   2345   2489   | 7  45  29 | 6     1   3589 --------------------+-----------+----------------27    8      5      | 4  9   17 | 13    6   23   49    1      49     | 3  2   6  | 58    7   58   3     26     267    | 5  8   17 | 14    49  29   then APE (with cell r5c1) removed candidate {9} from cell r5c3`

All pair combinations with a 9 in r5c3 (2-9, 4-9, 7-9, 9-9) are invalid within block 4 and row 5, using the APE definition.

Code: Select all
` 8     9      1      | 2  3   4  | 7     5   6     6     7      3      | 9  1   5  | 2     8   4     5     24     24     | 6  7   8  | 9     3   1    ---------------------+-----------+---------------- 1     45    *79     | 8  6   3  | 45    2   79   *2479 -23456 -246789 | 1  45 *29 | 3458 *49  35789 249   2345   2489   | 7  45  29 | 6     1   3589 ---------------------+-----------+---------------- 27    8      5      | 4  9   17 | 13    6   23    49    1      49     | 3  2   6  | 58    7   58    3     26     267    | 5  8   17 | 14    49  29   `

Four starred cells contain digits 2479 with multiplicity 1112. Total multiplicity is 5 for 4 cells, therefore any outside candidate which reduces the multiplicity by 2 is invalid. The most obvious way to reduce the multiplicity by 2 is to kill all the 9's in the starred cells. Only the cells marked with '-' see all the starred 9's, therefore there can be no 9's in the cells marked with '-'. Subset counting catches this one too.
Myth Jellies

Posts: 593
Joined: 19 September 2005

I think my example is simpler MythJellies as you used an Almost locked Quad compared to my almost locked triples

tarek

tarek

Posts: 2650
Joined: 05 January 2006

### APE eliminations and locked sets

Try this.

A and B are cells from one of which APE permits a candidate X to be eliminated. Say A is the cell from which X is eliminated and that B has candidates B1, B2, …, Bn other than X.

As I understand APE, the requirement is that there are bivalue cells
(X B1), (X B2), …, (X Bn)
which are common associates of A and B. If this is right, then
- the set {(X B1)} is an ALS (order 1, 2 candidates)
- the set {B, (X B2), … (X Bn)} is an ALS (order n, n + 1 candidates)
and B1 is a restricted common candidate for both these sets. Hence ALS eliminates X from cell A

Steve
Last edited by Steve R on Thu Apr 20, 2006 3:30 pm, edited 1 time in total.
Steve R

Posts: 74
Joined: 03 April 2006

Looks like there are many approaches. I think Ruud's just looking for an example without a simple alternative. Here's another one that makes heavy use of APE, from Ruud's own puzzle collection:

Code: Select all
`PUZZLE START~~~~~~~~~~~~. 9 . | . 7 . | . . .1 . . | 2 . 6 | . . .. . . | . . 1 | 7 8 .------+-------+------. . 4 | . . . | 1 . 8. 2 5 | . . . | 3 6 .9 . 3 | . . . | 2 . .------+-------+------. 4 1 | 3 . . | . . .. . . | 8 . 2 | . . 7. . . | . 1 . | . 3 ..9..7....1..2.6........178...4...1.8.25...36.9.3...2...413........8.2..7....1..3.Searching for Hidden Singles234568  9     268   | 45     7      3458 | 456    1245  1234561       3578  78    | 2      34589  6    | 459    459   3459  23456   356   26    | 459    3459   1    | 7      8     234569--------------------+--------------------+--------------------67      67    4     | 5679   23569  3579 | 1      579   8     78      2     5     | 1479   489    4789 | 3      6     49    9       1678  3     | 14567  4568   4578 | 2      457   45    --------------------+--------------------+--------------------25678   4     1     | 3      569    579  | 5689   259   2569  356     356   69    | 8      4569   2    | 4569   1459  7     25678   5678  26789 | 45679  1      4579 | 45689  3     24569 Hidden Single in block 4 set value 1 in cell r6c2Hidden Single in block 4 set value 8 in cell r5c1Hidden Single in block 5 set value 1 in cell r5c4Hidden Single in block 5 set value 2 in cell r4c5Hidden Single in block 5 set value 3 in cell r4c6Hidden Single in block 9 set value 1 in cell r8c8Hidden Single in row 1 set value 1 in cell r1c9Hidden Single in row 1 set value 3 in cell r1c1Hidden Single in row 5 set value 7 in cell r5c6Hidden Single in row 6 set value 7 in cell r6c8Hidden Single in row 7 set value 7 in cell r7c1Candidate removal left naked single: set value 6 in cell r4c1Candidate removal left naked single: set value 7 in cell r4c2Candidate removal left naked single: set value 5 in cell r8c1Candidate removal left naked single: set value 2 in cell r9c1Candidate removal left naked single: set value 4 in cell r3c1Hidden Single in row 7 set value 8 in cell r7c7Hidden Single in row 8 set value 3 in cell r8c2Hidden Single in row 9 set value 7 in cell r9c4Hidden Single in column 3 set value 7 in cell r2c3Hidden Single in column 4 set value 6 in cell r6c4Hidden Single in column 4 set value 4 in cell r1c4Hidden Single in column 8 set value 4 in cell r2c8Searching for Block/Line Reduction3  9   268 | 4   7     58  | 56    25   1    1  58  7   | 2   3589  6   | 59    4    359  4  56  26  | 59  359   1   | 7     8    23569-----------+---------------+-----------------6  7   4   | 59  2     3   | 1     59   8    8  2   5   | 1   49    7   | 3     6    49   9  1   3   | 6   458   458 | 2     7    45   -----------+---------------+-----------------7  4   1   | 3   569   59  | 8     259  2569 5  3   69  | 8   469   2   | 469   1    7    2  68  689 | 7   1     459 | 4569  3    4569 Block/Line Reduction (block 8 & column 6) removed candidate {9} from cell r7c5Block/Line Reduction (block 8 & column 6) removed candidate {9} from cell r8c5Block/Line Reduction (block 9 & column 7) removed candidate {4} from cell r9c9Searching for APE3  9   268 | 4   7     58  | 56    25   1    1  58  7   | 2   3589  6   | 59    4    359  4  56  26  | 59  359   1   | 7     8    23569-----------+---------------+-----------------6  7   4   | 59  2     3   | 1     59   8    8  2   5   | 1   49    7   | 3     6    49   9  1   3   | 6   458   458 | 2     7    45   -----------+---------------+-----------------7  4   1   | 3   56    59  | 8     259  2569 5  3   69  | 8   46    2   | 469   1    7    2  68  689 | 7   1     459 | 4569  3    569  APE (with cell r1c3) removed candidate {5} from cell r2c7Candidate removal left naked single: set value 9 in cell r2c7APE (with cell r1c3) removed candidate {5} from cell r2c9Candidate removal left naked single: set value 3 in cell r2c9APE (with cell r1c6) removed candidate {5} from cell r3c4Candidate removal left naked single: set value 9 in cell r3c4Candidate removal left naked single: set value 5 in cell r4c4Candidate removal left naked single: set value 9 in cell r4c8Candidate removal left naked single: set value 4 in cell r5c9Candidate removal left naked single: set value 9 in cell r5c5Candidate removal left naked single: set value 5 in cell r6c9APE (with cell r1c6) removed candidate {5} from cell r3c5Candidate removal left naked single: set value 3 in cell r3c5APE (with cell r3c9) removed candidate {5} from cell r1c6Candidate removal left naked single: set value 8 in cell r1c6Candidate removal left naked single: set value 5 in cell r2c5Candidate removal left naked single: set value 8 in cell r2c2Candidate removal left naked single: set value 6 in cell r9c2Candidate removal left naked single: set value 5 in cell r3c2Candidate removal left naked single: set value 9 in cell r8c3Candidate removal left naked single: set value 8 in cell r9c3Candidate removal left naked single: set value 9 in cell r9c9Candidate removal left naked single: set value 6 in cell r7c5Candidate removal left naked single: set value 2 in cell r7c9Candidate removal left naked single: set value 6 in cell r3c9Candidate removal left naked single: set value 5 in cell r1c7Candidate removal left naked single: set value 2 in cell r1c8Candidate removal left naked single: set value 6 in cell r1c3Candidate removal left naked single: set value 2 in cell r3c3Candidate removal left naked single: set value 5 in cell r7c8Candidate removal left naked single: set value 9 in cell r7c6Candidate removal left naked single: set value 4 in cell r9c7Candidate removal left naked single: set value 6 in cell r8c7Candidate removal left naked single: set value 4 in cell r8c5Candidate removal left naked single: set value 8 in cell r6c5Candidate removal left naked single: set value 4 in cell r6c6Candidate removal left naked single: set value 5 in cell r9c6PUZZLE SOLVED~~~~~~~~~~~~~3 9 6 | 4 7 8 | 5 2 11 8 7 | 2 5 6 | 9 4 34 5 2 | 9 3 1 | 7 8 6------+-------+------6 7 4 | 5 2 3 | 1 9 88 2 5 | 1 9 7 | 3 6 49 1 3 | 6 8 4 | 2 7 5------+-------+------7 4 1 | 3 6 9 | 8 5 25 3 9 | 8 4 2 | 6 1 72 6 8 | 7 1 5 | 4 3 9`
Graeme

Posts: 18
Joined: 06 February 2006

Graeme wrote:Firstly let me say I found the APE code I added last night picked up some XY-Wings missed within that code.

Are you using the traditional or "generalized" xyz-wing technique? The difference IIRC is that the traditional technique requires the "pilot-cell" to have 3 candidates, whereas the "generalized" technique does not.

Graeme wrote:I've re-run the test on top1465 and found that with XY(Z)-Wing first, APE still finds more exlcusions in 6 puzzles.

If it's not too much trouble, would you please post the puzzles numbers? A clue or two -- without giving away the APE deduction -- would be appreciated too.

TIA, Ron
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Myth Jellies wrote:Using just your cells...
Code: Select all
` 8     9      1      | 2  3   4  | 7     5   6     6     7      3      | 9  1   5  | 2     8   4     5     24     24     | 6  7   8  | 9     3   1    ---------------------+-----------+---------------- 1     45    *79     | 8  6   3  | 45    2   79   *2479 -23456 -246789 | 1  45 *29 | 3458 *49  35789 249   2345   2489   | 7  45  29 | 6     1   3589 ---------------------+-----------+---------------- 27    8      5      | 4  9   17 | 13    6   23    49    1      49     | 3  2   6  | 58    7   58    3     26     267    | 5  8   17 | 14    49  29 `

Four starred cells contain digits 2479 with multiplicity 1112. Total multiplicity is 5 for 4 cells, therefore any outside candidate which reduces the multiplicity by 2 is invalid. ....

Nice post. Here's an (almost)-almost-locked-set POV ...

[edit: The following deduction is invalid. See Myth Jellies' post here for the reason.]
Code: Select all
` 8     9      1      | 2  3   4  | 7     5   6     6     7      3      | 9  1   5  | 2     8   4     5     24     24     | 6  7   8  | 9     3   1    ---------------------+-----------+---------------- 1     45    A79     | 8  6   3  | 45    2   79   A2479 -23456 -246789 | 1 -45 B29 |-3458 B49  35789 249   2345   2489   | 7  45  29 | 6     1   3589 ---------------------+-----------+---------------- 27    8      5      | 4  9   17 | 13    6   23    49    1      49     | 3  2   6  | 58    7   58    3     26     267    | 5  8   17 | 14    49  29  r5c2357<>2,4`

AALS set A = {r5c1,r4c3} = {2479} is doubly-linked to ALS set B ={r5c6,r5c8}={249} via digits 2 and 4. Therefore, candidates 2 and 4 in row 5 (except for sets A and B) may also be excluded. How would you describe those exclusions in "set counting" terms?

(While I'm reasonably sure it's possible, I can't yet explain your r5c3<>9 exclusion with those (A)ALS sets. Perhaps someone else can.)

Myth Jellies wrote:Subset counting catches this one too.

Hmmm. With properly described sets, I think ALL exclusions can be explained in set counting terms. The trick is to develop efficient algorithms to describe those sets ... and in a way that is applicable for human solvers too.
Last edited by ronk on Thu Apr 20, 2006 9:49 pm, edited 1 time in total.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

I'm not sure if this is what you're after ron, but an ALS-XZ rule:

Code: Select all
` 8     9      1      | 2  3   4  | 7     5   6     6     7      3      | 9  1   5  | 2     8   4     5     24     24     | 6  7   8  | 9     3   1    ---------------------+-----------+----------------  1     45    %79     | 8  6   3  | 45    2   79    *2479 -23456 -246789 | 1  45 *29 | 3458 *49  35789  249   2345   2489   | 7  45  29 | 6     1   3589 ---------------------+-----------+----------------  27    8      5      | 4  9   17 | 13    6   23     49    1      49     | 3  2   6  | 58    7   58     3     26     267    | 5  8   17 | 14    49  29 `

Eliminating 9 in r5c3 & in (r5c2 if there was a 9 there9)
A=79 in r4c3, B=2479 in r5c168 x=7 z=9

ALS rules are definitely a subset of the Counting method.......

Imagine the subset in question as a long Snake, if that snake has one corner then yiu can express it as an ALS-xz rule if it was 2 corners then it is an xy-rule if 3 then xx rule (or whatever the name is) & so on......

ex: (I hope this is valid )
Code: Select all
`75 . . | . . * | . .79   . . . | . . . | . . .   . . . | . . . | . . .  -------+-------+------  . . . | . .49 | . . *   . . . | . . . | . . .   . . . | .46 . | . . .  -------+-------+------  . . . | . . . | . . .   . . . | . . . | . . .  35 . . | .36 . | . . .  `

Look at this hypothetical subset, imagine it as a snake........345679 multplicities of 111112 = 7 in 6 cells anything reducing multiplicities by 2 can be eliminated so 9s from the starred cells can be eliminated...
This can be explained by ALS but would be a very complicated rule as this one has 4 corners.........so this is where Counting would be very useful when ALS rules become very complicated to take over.... (3 corners or more)

tarek

tarek

Posts: 2650
Joined: 05 January 2006

### QED?

Code: Select all
`All,Here is a draft.  I expect to edit (or withdraw) it based on comments, and I intend to embellish it to make it stand alone.  Right now, it needs to be read in the context of this thread.A Comparison of APE and XY(Z)-WingsIn the following:a is a candidate to be eliminated by APE.b, c, d, e are other candidates.x is a list of candidates.  If x represents no candidates, it is “empty”.Case 1.Candidate Profiles:  abx  acResult:  APE excludes a from ax.Discussion:  This is not a feasible result.  (There must be another cell, ac. a is not a valid candidate in abx.)Case 2.Candidate Profiles:  abx  bcResult:  APE excludes a from abx.Discussion:  There must be two other cells, ab and ac.  x may not be empty.  (If x is empty, this is not a feasible pattern.  There are 4 cells containing only 3 candidates.) Diagram:  +----------+----------||abx  * bc |  - ab  - ||  -  -  - |  -  -  - ||  - ac  - |  *  *  * |+----------+----------|This is an XY-wing centered on bc with wingtips ab and ac.  Note that APE does not exclude any candidates in the cells labeled *, while the XY-wing does.  Case 3.Candidate Profiles:  abx  cdResult:  APE excludes a from abxDiscussion:  There must be two other cells, ac and ad. x may be empty.Diagram:  +----------+----------||abx  * cd |  - ac  - ||  -  -  - |  -  -  - ||  - ad  - |  *  *  * |+----------+----------|This is an XY-wing centered on cd with wingtips ac and ad.  Note that APE does not exclude any candidates in the cells labeled *, while the XY-wing does.  Case 4.Candidate Profiles:  abx  acd.Result:  APE excludes a from abxDiscussion:  There must be two other cells, ac and ad. x may be empty.Diagram:  +----------+----------||abx  - acd|  - ac  - ||  -  -  - |  -  -  - ||  - ad  - |  -  -  - |+----------+----------|This is an XYZ-wing centered on acd with wingtips ac and ad.Case 5 (an extension of case 3).Candidate Profiles:  abx  cdeResult:  APE excludes a from abxDiscussion:  There must be three other cells, ac, ad, and ae. x may be empty.Diagram 5.1:  +-----------+----------||abx  * cde |  - ac  - ||  -  -   - |  -  -  - || ae ad   - |  *  *  * |+-----------+----------|This is an XYZ-propellor (??) centered on cde with tips ac, ad, and ae.  Note that APE does not exclude any candidates in the cells labeled *, while the XYZ-propellor does.  Diagram 5.2 (others are possible):  |----------+-----------+----------||  - ae  - |abx  - cde |  - ac  - ||  -  -  - |  -  -   - |  -  -  - ||  -  -  - |  - ad   - |  -  -  - ||----------+-----------+----------|This is an XYZ-propellor (??) centered on cde with tips ac, ad, and ae. Case 6. (An extension of Case 4) Candidate Profiles:  abx  acde.Result:  APE excludes a from abxDiscussion:  There must be three other cells, ac, ad, and ae. x may be empty.Diagram (Others are possible):|----------+-----------+----------||  - ae  - |abx  - acde|  - ac  - ||  -  -  - |  -  -   - |  -  -  - ||  -  -  - |  - ad   - |  -  -  - ||----------+-----------+----------|This is a WXYZ-wing (??) centered on acd with wingtips ac, ad, and ae.Case 7. (Overlays) Candidate Profiles:  ab  cd.Result:  APE excludes a from ab, and c from cd.Discussion:  There must be three other cells, ac, ad, and bc.Diagram:+----------+----------|| ab *# cd |  - ac  - || bc  -  - |  #  #  # ||  - ad  - |  *  *  * |+----------+----------|There are two XY-wings:  (Dare I say we have twin two-bladed propellers!!)One is centered on cd with wingtips ac and ad.  Note that APE does not exclude any candidates in the cells labeled *, while the XY-wing does.  The other is centered on ab with wingtips ac and bc.  Note that APE does not exclude any candidates in the cells labeled #, while the XY-wing does.  Also, the reduction of the first XY-wing destroys thesecond.Conclusions:APE and XY(Z)-wings use the same cells to arrive at the same elimination.A single XY-wing has up to five elimination opportunities; there are possibly five corresponding APE’s with one elimination each.XY(Z)-wings are essentially triples which are not in a single box or line.  APE’s potentially extend this to quads, etc.The patterns may overlay, which leads to algorithmic issues for computer solvers.  A solver might use an XY(Z)-wing to find a single elimination, and then revert back to its hierarchy of heuristics (starting at naked singles).  Another solver may scan the entire puzzle for all APE eliminations before applying any.  These are absolutely not comparable.APE is regarded by some as trial-and-error (T&E).  And, some APE proponents regard XY(Z)-wings with disdain.  But, both techniques use the same relevant information to obtain the same useful result.Best wishes,Keith`
keith
2017 Supporter

Posts: 215
Joined: 03 April 2006

tarek wrote:I think my example is simpler MythJellies as you used an Almost locked Quad compared to my almost locked triples

That may be, but I was restricting myself to the same cells Graeme used to show how all APE reductions are covered by ALS/Subset Counting reductions. [edit - Steve has provided a rudimentary proof above of this]
ronk wrote:...Here's an (almost)-almost-locked-set POV ...
Code: Select all
` 8     9      1      | 2  3   4  | 7     5   6     6     7      3      | 9  1   5  | 2     8   4     5     24     24     | 6  7   8  | 9     3   1    ---------------------+-----------+---------------- 1     45    A79     | 8  6   3  | 45    2   79   A2479 -23456 -246789 | 1 -45 B29 |-3458 B49  35789 249   2345   2489   | 7  45  29 | 6     1   3589 ---------------------+-----------+---------------- 27    8      5      | 4  9   17 | 13    6   23    49    1      49     | 3  2   6  | 58    7   58    3     26     267    | 5  8   17 | 14    49  29  r5c2357<>2,4`

AALS set A = {r5c1,r4c3} = {2479} is doubly-linked to ALS set B ={r5c6,r5c8}={249} via digits 2 and 4. Therefore, candidates 2 and 4 in row 5 (except for sets A and B) may also be excluded. How would you describe those exclusions in "set counting" terms?

Heh, I almost made that same mistake when I posted. I'm afraid those are not valid reductions. Isolating on boxes 456 to save space, here are some counterexamples...
Code: Select all
` 1     45    A9      | 8  6   3  | 45    2   79   A7    -23456 -246789 | 1 -4  B2  |-3458 B9   35789 249   2345   2489   | 7  45  29 | 6     1   3589 ....... 1     45    A9      | 8  6   3  | 45    2   79   A7    -2     -246789 | 1 -45 B9  |-3458 B4   35789 249   2345   2489   | 7  45  29 | 6     1   3589 `

Your labelled cells do not prevent either of the above which puts either a two or a four in your proscribed cells (r5c2357<>2,4).
ronk wrote:(While I'm reasonably sure it's possible, I can't yet explain your r5c3<>9 exclusion with those (A)ALS sets. Perhaps someone else can.)

ronk wrote:Hmmm. With properly described sets, I think ALL exclusions can be explained in set counting terms. The trick is to develop efficient algorithms to describe those sets ... and in a way that is applicable for human solvers too.

Well the subset total multiplicity check and reduction is really identical to all of the ALS rules taken in total. I find it much much easier to use the one simple subset counting technique than remember and use all the more complicated ALS rules (I can never remember which is x and which is z), along with Sue de Coq's and perhaps APEs. I use my knowledge of those other rules to help guide me to fertile ground where subset counting will likely succeed though.
Myth Jellies

Posts: 593
Joined: 19 September 2005

Myth Jellies wrote:Heh, I almost made that same mistake when I posted. I'm afraid those are not valid reductions. Isolating on boxes 456 to save space, here are some counterexamples...
Code: Select all
` 1     45    A9      | 8  6   3  | 45    2   79   A7    -23456 -246789 | 1 -4  B2  |-3458 B9   35789 249   2345   2489   | 7  45  29 | 6     1   3589 ....... 1     45    A9      | 8  6   3  | 45    2   79   A7    -2     -246789 | 1 -45 B9  |-3458 B4   35789 249   2345   2489   | 7  45  29 | 6     1   3589 `

Your labelled cells do not prevent either of the above which puts either a two or a four in your proscribed cells (r5c2357<>2,4).

You are quite right. Exclusions based on doubly-linked x znd z of the ALS xz-rule are only valid when both sets are ALSs ... not one an ALS and the other an AALS. Well, duh ... I'm off to edit another OOPS.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext