Aligned Pair Exclusion (APE, no DJ)

Advanced methods and approaches for solving Sudoku puzzles

Postby Myth Jellies » Wed Apr 19, 2006 11:33 pm

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

Postby ronk » Wed Apr 19, 2006 11:40 pm

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

Postby Myth Jellies » Wed Apr 19, 2006 11:50 pm

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

Postby Graeme » Thu Apr 20, 2006 2:01 pm

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 . | . . 4
5 . . | 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  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   

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

Postby tarek » Thu Apr 20, 2006 2:13 pm

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
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby Myth Jellies » Thu Apr 20, 2006 3:01 pm

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  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   

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.


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. 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

Postby tarek » Thu Apr 20, 2006 3:09 pm

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

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

APE eliminations and locked sets

Postby Steve R » Thu Apr 20, 2006 3:20 pm

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

Postby Graeme » Thu Apr 20, 2006 3:33 pm

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 Singles

234568  9     268   | 45     7      3458 | 456    1245  123456
1       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 r6c2
Hidden Single in block 4 set value 8 in cell r5c1
Hidden Single in block 5 set value 1 in cell r5c4
Hidden Single in block 5 set value 2 in cell r4c5
Hidden Single in block 5 set value 3 in cell r4c6
Hidden Single in block 9 set value 1 in cell r8c8
Hidden Single in row 1 set value 1 in cell r1c9
Hidden Single in row 1 set value 3 in cell r1c1
Hidden Single in row 5 set value 7 in cell r5c6
Hidden Single in row 6 set value 7 in cell r6c8
Hidden Single in row 7 set value 7 in cell r7c1
Candidate removal left naked single: set value 6 in cell r4c1
Candidate removal left naked single: set value 7 in cell r4c2
Candidate removal left naked single: set value 5 in cell r8c1
Candidate removal left naked single: set value 2 in cell r9c1
Candidate removal left naked single: set value 4 in cell r3c1
Hidden Single in row 7 set value 8 in cell r7c7
Hidden Single in row 8 set value 3 in cell r8c2
Hidden Single in row 9 set value 7 in cell r9c4
Hidden Single in column 3 set value 7 in cell r2c3
Hidden Single in column 4 set value 6 in cell r6c4
Hidden Single in column 4 set value 4 in cell r1c4
Hidden Single in column 8 set value 4 in cell r2c8

Searching for Block/Line Reduction

3  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 r7c5
Block/Line Reduction (block 8 & column 6) removed candidate {9} from cell r8c5
Block/Line Reduction (block 9 & column 7) removed candidate {4} from cell r9c9

Searching for APE

3  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 r2c7
Candidate removal left naked single: set value 9 in cell r2c7
APE (with cell r1c3) removed candidate {5} from cell r2c9
Candidate removal left naked single: set value 3 in cell r2c9
APE (with cell r1c6) removed candidate {5} from cell r3c4
Candidate removal left naked single: set value 9 in cell r3c4
Candidate removal left naked single: set value 5 in cell r4c4
Candidate removal left naked single: set value 9 in cell r4c8
Candidate removal left naked single: set value 4 in cell r5c9
Candidate removal left naked single: set value 9 in cell r5c5
Candidate removal left naked single: set value 5 in cell r6c9
APE (with cell r1c6) removed candidate {5} from cell r3c5
Candidate removal left naked single: set value 3 in cell r3c5
APE (with cell r3c9) removed candidate {5} from cell r1c6
Candidate removal left naked single: set value 8 in cell r1c6
Candidate removal left naked single: set value 5 in cell r2c5
Candidate removal left naked single: set value 8 in cell r2c2
Candidate removal left naked single: set value 6 in cell r9c2
Candidate removal left naked single: set value 5 in cell r3c2
Candidate removal left naked single: set value 9 in cell r8c3
Candidate removal left naked single: set value 8 in cell r9c3
Candidate removal left naked single: set value 9 in cell r9c9
Candidate removal left naked single: set value 6 in cell r7c5
Candidate removal left naked single: set value 2 in cell r7c9
Candidate removal left naked single: set value 6 in cell r3c9
Candidate removal left naked single: set value 5 in cell r1c7
Candidate removal left naked single: set value 2 in cell r1c8
Candidate removal left naked single: set value 6 in cell r1c3
Candidate removal left naked single: set value 2 in cell r3c3
Candidate removal left naked single: set value 5 in cell r7c8
Candidate removal left naked single: set value 9 in cell r7c6
Candidate removal left naked single: set value 4 in cell r9c7
Candidate removal left naked single: set value 6 in cell r8c7
Candidate removal left naked single: set value 4 in cell r8c5
Candidate removal left naked single: set value 8 in cell r6c5
Candidate removal left naked single: set value 4 in cell r6c6
Candidate removal left naked single: set value 5 in cell r9c6

PUZZLE SOLVED
~~~~~~~~~~~~~
3 9 6 | 4 7 8 | 5 2 1
1 8 7 | 2 5 6 | 9 4 3
4 5 2 | 9 3 1 | 7 8 6
------+-------+------
6 7 4 | 5 2 3 | 1 9 8
8 2 5 | 1 9 7 | 3 6 4
9 1 3 | 6 8 4 | 2 7 5
------+-------+------
7 4 1 | 3 6 9 | 8 5 2
5 3 9 | 8 4 2 | 6 1 7
2 6 8 | 7 1 5 | 4 3 9
Graeme
 
Posts: 18
Joined: 06 February 2006

Postby ronk » Thu Apr 20, 2006 4:30 pm

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

Postby ronk » Thu Apr 20, 2006 6:28 pm

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

Postby tarek » Thu Apr 20, 2006 7:34 pm

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:D )
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
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

QED?

Postby keith » Thu Apr 20, 2006 10:06 pm

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)-Wings


In 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  ac

Result:  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  bc

Result:  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  cd

Result:  APE excludes a from abx

Discussion:  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 abx

Discussion:  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  cde

Result:  APE excludes a from abx

Discussion:  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 abx

Discussion:  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 the
second.



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: 209
Joined: 03 April 2006

Postby Myth Jellies » Fri Apr 21, 2006 1:10 am

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.)

You almost had it, try this...[edit - didn't notice that tarek already answered this]

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

Postby ronk » Fri Apr 21, 2006 1:42 am

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

Return to Advanced solving techniques