The New Sudoku Players' Forum

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

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

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

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

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

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

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

tarek

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

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

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

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

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

)

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

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

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

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

The New Sudoku Players' Forum

Aligned Pair Exclusion (APE, no DJ)

APE eliminations and locked sets

QED?