dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

APE: Aligned Pair Exclusion
Goto page 1, 2  Next
 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology
View previous topic :: View next topic  
Author Message
keith



Joined: 19 Sep 2005
Posts: 3184
Location: near Detroit, Michigan, USA

PostPosted: Mon Feb 28, 2011 2:38 am    Post subject: APE: Aligned Pair Exclusion Reply with quote

This topic, APE, has come up in recent threads on this site.

Here is the Sudopedia article:

http://www.sudopedia.org/wiki/Aligned_Pair_Exclusion

Please be sure to read the "Discussion" tab on that page.

In our previous conversations on the topic, I thought that an APE was mostly a different way of looking at mostly an XYZ-wing, but possibly other wings like XY- and WXYZ-. Look here:

http://forum.enjoysudoku.com/aligned-pair-exclusion-ape-no-dj-t3882.html

Please continue the discussion here.

Keith
Back to top
View user's profile Send private message
daj95376



Joined: 23 Aug 2008
Posts: 3855

PostPosted: Mon Feb 28, 2011 10:40 am    Post subject: Reply with quote

Here is a recent submission to the Patterns Game in another forum. The puzzle cracks with a single APE.

Code:
 +-----------------------+
 | 1 . . | . . . | 2 . . |
 | . 2 . | 1 . . | . . . |
 | 3 . 4 | . . . | . . 1 |
 |-------+-------+-------|
 | 5 . . | 6 . . | . . . |
 | . 4 . | . 2 . | . . . |
 | . . 7 | . . 4 | . 5 . |
 |-------+-------+-------|
 | . 3 . | 8 . . | 1 . . |
 | . . 9 | . 7 . | . 2 . |
 | 6 . . | . . 3 | 9 . 5 |
 +-----------------------+

 APE cells: r9c3 and r8c4<>4; supporting cells r8c1, r9c4, and r9c5
 +--------------------------------------------------------------------------------+
 |  1       56789   568     |  34579   345689  56789   |  2       346789  346789  |
 |  789     2       568     |  1       345689  56789   |  345678  346789  346789  |
 |  3       56789   4       |  2579    5689    256789  |  5678    6789    1       |
 |--------------------------+--------------------------+--------------------------|
 |  5       189     1238    |  6       1389    1789    |  3478    134789  234789  |
 |  89      4       1368    |  3579    2       15789   |  3678    136789  36789   |
 |  289     1689    7       |  39      1389    4       |  368     5       23689   |
 |--------------------------+--------------------------+--------------------------|
 |  247     3       25      |  8       4569    2569    |  1       467     467     |
 | #48      158     9       | *45      7       156     |  3468    2       3468    |
 |  6       178    *128     | #24     #14      3       |  9       478     5       |
 +--------------------------------------------------------------------------------+
 # 173 eliminations remain

The first thing you'll notice is that the APE cells are not in the same line/box. Now, you can perform the traditional APE logic to confirm the elimination, or you can perform a Kraken Cell on r9c3 and limit your streams to (a)X - (a=b)Y - (b)Z:

Code:
(1)r9c3 - (1=4)r9c5 - (4)r8c4
(2)r9c3 - (2=4)r9c4 - (4)r8c4
(8)r9c3 - (8=4)r8c1 - (4)r8c4

If any of your streams are of the form: (a)W - (a=bc)XY - (c)Z, then you have a Type 2 APE.

RonK has an example in another forum where one stream uses an ALS: (a)W - ALS(a=c)XY - (c)Z. I can provide a link if you're interested.

Regards, Danny
Back to top
View user's profile Send private message
Asellus



Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA

PostPosted: Mon Feb 28, 2011 7:15 pm    Post subject: Reply with quote

Whatever the particulars of the APE notions in the preceding example by daj95376, it does not refute Keith's suspicion that APE is an unnecessary technique in the sense that it can always be replicated with 2-ALS ("XZ") methods. In this case we have the ALS 48 in r8c1 and the ALS 1248 in r9c345. The restricted common (X) is <8> and the shared common (Z) is <4>. Or,
(4=8)r8c1 - ALS[(8)r9c3=(4)r9c45]; r8c4<>4

Even in the Sudopedia discussion the resort to the more complicated AALS notion in their example isn't necessary. Here is the grid:
Code:
 -----------------------------------------------------------
| 239   8     23469 |#46    5     1     | 7     36    39    |
| 39    1     369   |#68    2     7     | 5     4     389   |
| 5     7     46    | 9     3     468   | 168   168   2     |
|-------------------+-------------------+-------------------|
| 4     2     5     | 7     689   689   | 1389  138   138   |
| 7     39    8     | 134   149   2     | 49    5     6     |
| 6     39    1     | 5     489   3489  | 489   2     7     |
|-------------------+-------------------+-------------------|
| 239   6     239   |*1348  14789 5     | 138   1378  1348  |
| 1     5     39    |*348-6 46789 34689 | 2     3678  348   |
| 8     4     7     | 2    #16   #36    | 136   9     5     |
 -----------------------------------------------------------

We have a 13468 ALS in r1257c4 and a 136 ALS in r9c56, with exclusive common <1> and shared common <6>:
ALSr1257c4[(6)r12c4=(1)r7c4] - ALS[(1)r9c5=(6)r9c56]; r8c4<>6

In the Player's Forum discussion there was a desire to restrict the alternate method to the same cells, which the ALS above does not do because it includes r5c4. (That, presumably, led to the AALS approach.) However, I see no compelling reason for that restriction.

Myth Jellies is persuasive that subset counting is the key, especially with the "use the same cells" restriction. ALS "wings" are particular applications of subset counting so that added connection makes sense. Like Keith, I have yet to see an APE elimination that cannot also be accomplished with an ALS "wing", not to mention that additional eliminations often result from the ALS approach.

I guess it's a matter of preference. Me, I prefer to work with ALS so don't find APE to be useful. Also, APE seems to tread mightily close to trial and error. Subset counting is a less T&E way of looking at the same thing.
Back to top
View user's profile Send private message Visit poster's website
keith



Joined: 19 Sep 2005
Posts: 3184
Location: near Detroit, Michigan, USA

PostPosted: Mon Feb 28, 2011 8:52 pm    Post subject: Reply with quote

Asellus,

Thank you. But, I think I am perhaps getting too much credit here.

Ruud's original question was along the lines of: "Should APE be added to our arsenal of techniques?"

In my opinion, if you are a computer programmer, probably not.

If you are a human solver, and you find the APE explanation easier to spot than the ALS, so be it.

Quote:
That, presumably, led to the AALS approach.


I suppose we are all working towards the AAAAAAAAS technique (eight almosts and a single) that will solve any cell in any puzzle. Razz

Keith
Back to top
View user's profile Send private message
ronk



Joined: 07 May 2006
Posts: 397

PostPosted: Mon Feb 28, 2011 9:07 pm    Post subject: Reply with quote

Asellus wrote:
Even in the Sudopedia discussion the resort to the more complicated AALS notion in their example isn't necessary. Here is the grid:
Code:
 -----------------------------------------------------------
| 239   8     23469 |#46    5     1     | 7     36    39    |
| 39    1     369   |#68    2     7     | 5     4     389   |
| 5     7     46    | 9     3     468   | 168   168   2     |
|-------------------+-------------------+-------------------|
| 4     2     5     | 7     689   689   | 1389  138   138   |
| 7     39    8     | 134   149   2     | 49    5     6     |
| 6     39    1     | 5     489   3489  | 489   2     7     |
|-------------------+-------------------+-------------------|
| 239   6     239   |*1348  14789 5     | 138   1378  1348  |
| 1     5     39    |*348-6 46789 34689 | 2     3678  348   |
| 8     4     7     | 2    #16   #36    | 136   9     5     |
 -----------------------------------------------------------

We have a 13468 ALS in r1257c4 and a 136 ALS in r9c56, with exclusive common <1> and shared common <6>:
ALSr1257c4[(6)r12c4=(1)r7c4] - ALS[(1)r9c5=(6)r9c56]; r8c4<>6

In the Player's Forum discussion there was a desire to restrict the alternate method to the same cells, which the ALS above does not do because it includes r5c4. (That, presumably, led to the AALS approach.) However, I see no compelling reason for that restriction.

If one backtests by asserting r8c4=6, it's easy to see that r5c4 plays no part in r7c4 becoming void of candidates. Hence, r5c4 plays no part in the deduction.
Back to top
View user's profile Send private message
Asellus



Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA

PostPosted: Mon Feb 28, 2011 11:16 pm    Post subject: Reply with quote

ronk wrote:
Hence, r5c4 plays no part in the deduction.

Yes, for APE and subset counting r5c4 is unnecessary. For the ALS XZ-Wing that makes the same elimination, r5c4 is necessary since without it there is no useful ALS in r4 that makes the elimination. That was my only point. If one requires the alternate method for making the APE elimination to involve only the same cells, as some were proposing, then an ALS technique is not always available to do so (though subset counting can probably always do so). Without such a requirement, then I suspect that an ALS technique probably always is available.
Back to top
View user's profile Send private message Visit poster's website
ronk



Joined: 07 May 2006
Posts: 397

PostPosted: Mon Feb 28, 2011 11:30 pm    Post subject: Reply with quote

Asellus wrote:
ronk wrote:
Hence, r5c4 plays no part in the deduction.

Yes, for APE and subset counting r5c4 is unnecessary. For the ALS XZ-Wing that makes the same elimination, r5c4 is necessary since without it there is no useful ALS in r4 that makes the elimination. That was my only point.

Believe what you wish, but I don't buy bridges from Brooklyn. IOW I believe the results of backtesting to be significant, while you apparently feel free to ignore it.
Back to top
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3184
Location: near Detroit, Michigan, USA

PostPosted: Mon Feb 28, 2011 11:53 pm    Post subject: Reply with quote

ronk wrote:
IOW I believe the results of backtesting to be significant, while you apparently feel free to ignore it.

Question: Is "backtesting" the act of proving a cell used to make a deduction is not necessary if there is another path to that same deduction?

Ron, do you have a definition of "backtesting"? Do you mean a chain that can be traversed in both directions?

Keith
Back to top
View user's profile Send private message
Asellus



Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA

PostPosted: Tue Mar 01, 2011 3:37 am    Post subject: Reply with quote

While I don't know about "backtesting", I am convinced by Ted's offline questioning of my shared exclusive <1>. Due to the <1> in r5c4 I am in error and my ALS solution is not valid Embarassed. I do not see any way to make the <6> elimination with a single "XZ-Wing". There is a valid XZ-Wing using the APE cells, but it eliminates <3> in r8c6:
ALS[(3)r9c6=(1)r9c5] - ALSr1278c4[(1)r7c4=(3)r78c4]; r8c6<>3

However, a 3-node ALS chain does the trick and stays within the APE cells:
(6=3)r9c6 - ALSr1278c4[(3)r78c4=(1)r7c4] - (1=6)r9c5; r8c456|r9c7<>6

As is often the case, the ALS elimination does more than the APE elimination. So, it seems that an ALS chain may be necessary in some cases to replicate an APE elimination.


Keith: I think we agree that, as I said, it is a matter of preference. However, if someone can produce an APE elimination that cannot be accomplished with ALS methods, I'll reconsider. I like ALS because it's dealing purely with alternating inferences. And, as I see it, an AAAAAAAALS would be a single cell in which all 9 digits are valid candidates. Pretty useless! Let's hope it doesn't come to that.
Back to top
View user's profile Send private message Visit poster's website
keith



Joined: 19 Sep 2005
Posts: 3184
Location: near Detroit, Michigan, USA

PostPosted: Tue Mar 01, 2011 4:06 am    Post subject: Reply with quote

keith wrote:
ronk wrote:
IOW I believe the results of backtesting to be significant, while you apparently feel free to ignore it.

Question: Is "backtesting" the act of proving a cell used to make a deduction is not necessary if there is another path to that same deduction?

Ron, do you have a definition of "backtesting"? Do you mean a chain that can be traversed in both directions?

Keith
Now that Asellus has admitted an error, my question is probably moot. My question was based on the thought that Ronk may have been pointing out that certain cells were not needed.

Keith
Back to top
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3184
Location: near Detroit, Michigan, USA

PostPosted: Tue Mar 01, 2011 5:01 am    Post subject: Reply with quote

Asellus wrote:
Keith: I think we agree that, as I said, it is a matter of preference.
And, I think, a matter of practicality. I tend not to use hard-to-find patterns that only yield occasional results. (My swordfish are for eating, not for solving sudoku.)

Asellus wrote:
However, if someone can produce an APE elimination that cannot be accomplished with ALS methods, I'll reconsider.
This challenge has been out there for half a decade.

Asellus wrote:
And, as I see it, an AAAAAAAALS would be a single cell in which all 9 digits are valid candidates. Pretty useless! Let's hope it doesn't come to that.
Yes, and an AAAAAAAALS is certainly possible. But, solving an AAAAAAAALS would solve any puzzle. Don't we indeed hope it does comes to that?

Keith
Back to top
View user's profile Send private message
ronk



Joined: 07 May 2006
Posts: 397

PostPosted: Tue Mar 01, 2011 5:24 am    Post subject: Reply with quote

keith wrote:
Ron, do you have a definition of "backtesting"?

here Jeff wrote:
Backtest a method that validates a network: If a forcing chain technique uses a set of cells "A" to eliminate candidate "x" from cell "B" (which can belong to set A) -- then this implies that the back substitution of B=x will lead to some sort of contradiction amongst [all] the cells of set A.

The edit in red is mine. Backtesting is a way to look at an elimination from both a deductive and inductive point of view. The two viewpoints should be using the same candidates. Said validation using backtesting may be confusing, especially when many "patterns" lead to the same elimination.

Asellus wrote:
I do not see any way to make the <6> elimination with a single "XZ-Wing". There is a valid XZ-Wing using the APE cells, but it eliminates <3> in r8c6:
ALS[(3)r9c6=(1)r9c5] - ALSr1278c4[(1)r7c4=(3)r78c4]; r8c6<>3

However, a 3-node ALS chain does the trick and stays within the APE cells:
(6=3)r9c6 - ALSr1278c4[(3)r78c4=(1)r7c4] - (1=6)r9c5; r8c456|r9c7<>6

As is often the case, the ALS elimination does more than the APE elimination.

This set of 6 cells forms a doubly-linked als-xz, which may be viewed as a continuous loop.

(3468=4681)als:r1278c4 - (16=63)als:r9c56 - loop ==> r7c5<>1, r8c6<>3, r5c4<>4, r8c456<>6

Due to the continuous loop, each weak inference becomes conjugate (a strong inference too) for the eliminations r7c5<>1 and r8c6<>3. Also, each ALS becomes an LS causing eliminations r5c4<>4 and r8c456<>6. This leads to locked candidate eliminations 6c4\b2 => r3c6<>6 and 6b8\r9 => r9c7<>6.

Asellus wrote:
So, it seems that an ALS chain may be necessary in some cases to replicate an APE elimination.

Possibly, although aals-xz constructs may suffice, at least for APE.

[edit: After another read, I now see your "3-node ALS chain" is essentially the same continuous loop as my doubly-linked als-xz.]
Back to top
View user's profile Send private message
Asellus



Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA

PostPosted: Tue Mar 01, 2011 5:38 pm    Post subject: Reply with quote

Quote:
After another read, I now see your "3-node ALS chain" is essentially the same continuous loop as my doubly-linked als-xz.

I agree. However, I suspect that the "double linking" is a way of sneaking the candidate combinations approach of APE back into the technique, which was what I was seeking to avoid.
Back to top
View user's profile Send private message Visit poster's website
ronk



Joined: 07 May 2006
Posts: 397

PostPosted: Tue Mar 01, 2011 6:13 pm    Post subject: Reply with quote

Asellus wrote:
Quote:
After another read, I now see your "3-node ALS chain" is essentially the same continuous loop as my doubly-linked als-xz.

I agree. However, I suspect that the "double linking" is a way of sneaking the candidate combinations approach of APE back into the technique, which was what I was seeking to avoid.

As I see it, what you're trying to avoid is double-linking. If you agree it's OK between two ALSs, then you've weakened your argument that iit's not OK between an ALS and an AALS.
Back to top
View user's profile Send private message
Asellus



Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA

PostPosted: Wed Mar 02, 2011 8:44 am    Post subject: Reply with quote

ronk wrote:
As I see it, what you're trying to avoid is double-linking. If you agree it's OK between two ALSs, then you've weakened your argument that iit's not OK between an ALS and an AALS.

Perhaps I was too generous in conceding that our loops are essentially equivalent because they are not exactly equivalent. First, they don't make exactly the same eliminations. Considered as a continuous loop, my 3-ALS loop also eliminates <3> from r8c6 and <1> from r7c5. It does not immediately eliminate <4> from r5c4. And your loop does not appear to eliminate <6> from r9c7 as mine does.

I am also not making any sort of argument about anything "doubly linked" for two reasons. First, I don't have clarity as to precisely what you mean by the term. Second, I don't see myself as using anything I would describe as "doubly linked" in my chain/loop. I also don't use or make any claims for AALS.

Going strictly by the notation of your loop, I see that you put forward strong inferences between groups of multiple digits (as opposed to groups of a single digit). The issue is: how do you determine the existence of those strong inferences? Maybe you can look at the grid and see the existence of those inferences immediately and, if so, you have my adulation and I await similar enlightenment. But for me to see them I have to do some "what if" thinking based on the weakly linked <1>s in b8 and the fact that the <3>s in the c4 ALS are restricted to b8. Most critically, I need to see that if <1> is not true in the c4 ALS then <3> cannot be true in the r9 ALS. But I don't like this "if-then" approach to spotting inferences. And that's what I meant about the candidate combinations of APE leaking back in.

My 3-node ALS chain/loop does not require any "if-then" thinking. (And maybe your chain doesn't either but I can't say without appropriate enlightenment.) I rely only on the fact that all instances of any one digit in an ALS have a strong inference with all instances of any other digit in that ALS. There is absolutely no "what-if"-ing involved.

And my ultimate point has nothing to do with these minutiae. It is merely that, as far as I have yet seen, the eliminations resulting from APE can be achieved by alternate techniques (especially involving ALS) that usually not only perform the APE elimination but provide even more eliminations. Even your "double linky" thing, even if "leaky", does more than APE.

I rest my case... I hope!
Back to top
View user's profile Send private message Visit poster's website
ronk



Joined: 07 May 2006
Posts: 397

PostPosted: Wed Mar 02, 2011 11:46 am    Post subject: Reply with quote

Asellus wrote:
But for me to see them I have to do some "what if" thinking based on the weakly linked <1>s in b8 and the fact that the <3>s in the c4 ALS are restricted to b8. Most critically, I need to see that if <1> is not true in the c4 ALS then <3> cannot be true in the r9 ALS. But I don't like this "if-then" approach to spotting inferences. And that's what I meant about the candidate combinations of APE leaking back in.

Just like a naked pair, the simplest and earliest of all doubly-linked ALSs, in a box. Smile

Code:
 ab .  .  | .
 .  .  .  | .
 .  .  ab | .
----------+---
 .  .  .  | .
Back to top
View user's profile Send private message
Asellus



Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA

PostPosted: Wed Mar 02, 2011 5:29 pm    Post subject: Reply with quote

Even before reading the response, I awoke this morning realizing I should have slept on this another night! It is the notation that got in my way. Rather than those inferences between grouped multi-digits, which are too many trees and not enough forest, one could just write the forest:
[(3)r78c4=(1)r7c4]als:r1278c4 - [(1)r9c5=(3)r9c56]als - loop

I concur that this is obvious even though I didn't see it. And, with a little more thought, it also occurs to me that the inferences within and between ALS becoming conjugate produce the r5c4<>4, r7c5<>1, r9c7<>6 and r8c6<>3 eliminations in the cases of both loops. So, they are, indeed, equivalent. Some enlightenment after all!

[Edit to add the following, and to include r7c5 in the listed eliminations above:]
Perhaps I somehow missed it, though I don't believe so: it appears that ronk's original post of the doubly-linked loop above was edited to add in additional resulting eliminations that were not noted when I wrote my responses. Not knowing this makes some of my responses appear even more incoherent than they might otherwise be.

[One more edit... sorry!]
Just to be crystal clear, there was never any dispute about the r8c456<>6 eliminations so I didn't include them in the list above.
Back to top
View user's profile Send private message Visit poster's website
keith



Joined: 19 Sep 2005
Posts: 3184
Location: near Detroit, Michigan, USA

PostPosted: Thu Mar 03, 2011 1:41 am    Post subject: Reply with quote

> original post of the doubly-linked loop above was edited to add in ...

Asellus,

That is possible. Here are the rules as I understand them.

If you post a message, you may edit it without trace until another message is posted in the same thread.

After another message has been posted, you may still edit your message. The edits will not be tracked, but a message showing the number of edits and the time of the last edit will be included.

I think that is why some use "Quote" to reply to messages. It preserves the exact message they are replying to. I personally don't like to use "Quote", for I think it displays some level of mistrust.

But, if you are involved in a discussion of minutiae and details, you might consider using "Quote". It's not always a question of trust: If you point out an honest typo, the author may correct the original message. Once that is done, your correction becomes moot.

Administrators can edit (and delete) messages at any time without a trace. I rarely edit others' messages. If I do, I leave a note as to exactly what was changed, unless it is some simple formatting issue like removing an unintended smiley emoticon or fixing the use of "code".

Best wishes,

Keith


Last edited by keith on Fri Mar 04, 2011 4:36 am; edited 2 times in total
Back to top
View user's profile Send private message
Asellus



Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA

PostPosted: Thu Mar 03, 2011 2:07 am    Post subject: Reply with quote

Thanks Keith for the comments. However, I hasten to add that I didn't mean to suggest I was upset in any way or to imply any ill intent on anyone's part.
Back to top
View user's profile Send private message Visit poster's website
keith



Joined: 19 Sep 2005
Posts: 3184
Location: near Detroit, Michigan, USA

PostPosted: Thu Mar 03, 2011 3:30 am    Post subject: Reply with quote

Asellus wrote:
Thanks Keith for the comments. However, I hasten to add that I didn't mean to suggest I was upset in any way or to imply any ill intent on anyone's part.
Not at all.

But, if the original message is changed, the logic of the thread can become nonsensical.

Keith
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group