Aligned Pair Exclusion (APE, no DJ)

Advanced methods and approaches for solving Sudoku puzzles

Postby Graeme » Fri Apr 21, 2006 4:50 pm

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


My comment here isn't clear. I was trying to say there was an error in my XY-Wing code that caused some XY-Wings to be missed, but that the new APE code picked them up. I'm using the traditional XY(Z) wing technique with 2 candidates in the pilot cell for XY, 3 for XYZ.

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


Sure, the puzzle numbers are 472, 533, 703, 1182, 1199 and 1260. Of course, different solvers will find different things. My own solver has the basic techniques, but no UR, ALS, finned fish, and other more advanced techniques.

rgds,
Graeme
Graeme
 
Posts: 18
Joined: 06 February 2006

Dead Thread?

Postby keith » Mon May 01, 2006 2:52 am

I am surprised there have been no replies to my post on the various cases of APE, and no response to my claims on APE vs. XY-wings.

And, I am surprised that the other discussions within this thread have stopped.

In the first post, Ruud wrote:


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



Given the responses in this thread, can Ruud, or someone else, post a summary response to this quote?

I am asking whether we should close or continue this discussion.


Best wishes,

Keith
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Postby Graeme » Mon May 01, 2006 9:52 am

I've since added empty rectangles and uniqueness 1 & 2 to my solver, albiet AFTER the APE tests, and the same 6 puzzles in top1465 use APE. Happy to post the puzzle state used by APE if anyone's interested.

Ruud - everything OK - have we helped? Even if we've totally lost the plot, a response will be appreciated.

:)
Graeme
 
Posts: 18
Joined: 06 February 2006

Postby ronk » Mon May 01, 2006 11:30 am

Graeme wrote:Happy to post the puzzle state used by APE if anyone's interested.
Please do. TIA, Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Graeme » Mon May 01, 2006 12:46 pm

Here you are, Ron:

Code: Select all
top1465 #472
4...1..8...9.2..5.1.......2.3.9.8..7..5.........63......6...4....1.832..7....6..8

after simplification, and XY(Z)-Wing attempts ...

4      2567     237  | 357    1    579   | 3679  8      369
368    678      9    | 3478   2    47    | 1367  5      1346
1      578      378  | 34578  6    4579  | 379   349    2   
---------------------+-------------------+------------------
26     3        24   | 9      45   8     | 156   1246   7   
2689   1246789  5    | 1247   47   1247  | 3689  23469  3469
289    124789   2478 | 6      3    12457 | 589   249    459
---------------------+-------------------+------------------
23589  289      6    | 1257   79   1257  | 4     1379   1359
59     49       1    | 457    8    3     | 2     679    569
7      249      234  | 1245   459  6     | 1359  139    8   

APE (with cell r8c4) removed candidate {9} from cell r7c1
APE (with cell r8c4) removed candidate {9} from cell r7c2

============================================================

top1465 #533
........5.4.....7..761.43...85.6...........51.6.2.......2.....9...4.8.....37...1.

after simplification, and XY(Z)-Wing attempts ...

129   23  189 | 38  7     29  | 4  6  5
2359  4   89  | 56  2359  356 | 1  7  28
25    7   6   | 1   258   4   | 3  9  28
--------------+---------------+---------
7     8   5   | 9   6     1   | 2  3  4
29    23  49  | 38  48    7   | 6  5  1
13    6   14  | 2   345   35  | 9  8  7
--------------+---------------+---------
8     15  2   | 56  135   356 | 7  4  9
6     19  7   | 4   19    8   | 5  2  3
4     59  3   | 7   259   29  | 8  1  6

APE (with cell r2c1) removed candidate {2} from cell r1c1
APE (with cell r1c3) removed candidate {9} from cell r2c1

============================================================

top1465 #703
..2..9....6..31....7.65.4...1.3.....5.......7..8.2...9..19......8..7..95......3.4

after simplification, and XY(Z)-Wing attempts ...

134    345   2    | 478  48     9    | 67    567   13
8      6     45   | 47   3      1    | 9     57    2
139    7     39   | 6    5      2    | 4     8     13
------------------+------------------+---------------
24679  1     4679 | 3    689    4567 | 258   24    68
5      2349  3469 | 48   14689  46   | 268   1234  7
67     34    8    | 15   2      67   | 15    34    9
------------------+------------------+---------------
2347   235   1    | 9    46     3456 | 2678  267   68
346    8     346  | 12   7      346  | 12    9     5
2679   259   5679 | 25   16     8    | 3     1267  4

APE (with cell r5c7) removed candidate {4} from cell r4c6
APE (with cell r5c7) removed candidate {4} from cell r5c8

============================================================

top1465 #1182
8.1.......7..1...45..6.89......63.2....1........7..61..8........1.32..7.3..5.....

after simplification, and XY(Z)-Wing attempts ...

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   

APE (with cell r5c1) removed candidate {9} from cell r5c3

============================================================

top1465 #1199
.1...57.4...7...9...8.....58.4...1...2.14.....9...8.........273..3.8.......5.6...

after simplification, and XY(Z)-Wing attempts ...

2369  1    269 | 8   26   5  | 7     236   4   
4     56   256 | 7   126  3  | 68    9     1268
7     36   8   | 49  129  14 | 36    12    5   
---------------+-------------+-----------------
8     356  4   | 36  7    2  | 1     56    9   
356   2    567 | 1   4    9  | 3568  3568  678
136   9    167 | 36  5    8  | 346   2346  267
---------------+-------------+-----------------
56    8    56  | 49  19   14 | 2     7     3   
19    4    3   | 2   8    7  | 569   156   16 
129   7    129 | 5   3    6  | 489   148   18 

APE (with cell r5c7) removed candidate {6} from cell r6c7

============================================================

top1465 #1260
7.....96......5..13......8...69..3...1...8.4.97..4........6.....24.....5...8.1...

after simplification, and XY(Z)-Wing attempts ...

7     458   1258 | 1234   238    234   | 9     6     234 
2468  4689  289  | 23467  23789  5     | 247   237   1   
3     469   129  | 12467  279    24679 | 5     8     247 
-----------------+---------------------+------------------
2458  458   6    | 9      1      27    | 3     257   78   
25    1     23   | 23567  2357   8     | 267   4     9   
9     7     2358 | 2356   4      236   | 1     25    268 
-----------------+---------------------+------------------
1     3589  5789 | 245    6      24    | 278   2379  237 
68    2     4    | 37     379    379   | 68    1     5   
56    3569  579  | 8      25     1     | 2467  2379  23467

APE (with cell r5c5) removed candidate {2} from cell r5c4


rgds,
Graeme
Graeme
 
Posts: 18
Joined: 06 February 2006

Postby Ruud » Mon May 01, 2006 2:34 pm

Graeme wrote:Ruud - everything OK - have we helped? Even if we've totally lost the plot, a response will be appreciated.

Sure it has helped.

My original intention was to introduce the APE technique to this forum, and see how it fits in with the existing techniques.

Your tests are a great contribution, Graeme. However, the best yield is the link to Subset Counting, which I introduced back in the UK forum. A couple of people are now furiously attacking the remaining "unsolvables" with Subset Counting, which may lead to the discovery of new techniques.

And Keith, these topics often sorta fade away, as our attention is drawn towards other issues. That's life, I guess...

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby Graeme » Mon May 01, 2006 3:00 pm

many thanks for the reply, Ruud

"great contribution" is probably a little too kind, I thinks that's reserved for you and the other gurus around here. I've learned much here, including how far out of my depth I am with some of the advanced techniques, but nevertheless remain fascinated.

Do you have a link to the Subset Counting thread? I'd be interested to follow that also.

kind rgds,
Graeme
Graeme
 
Posts: 18
Joined: 06 February 2006

Postby Ruud » Mon May 01, 2006 3:25 pm

Here is the link to the subset counting topic: http://forum.enjoysudoku.com/viewtopic.php?p=22955#p22955

cheers, Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby ronk » Mon May 01, 2006 9:41 pm

Graeme wrote:Here you are

Thanks for the six candidate grids at the stage of Aligned Pair Exclusions.

After detailed analysis of each, my conclusion is the APE rule is a special case of the ALS xz-rule ... special in the sense that at most one cell of all cells in the two ALS sets does not hold a pair.

I duplicated your grids below and marked the cells of the ALS sets ... and then added xz-rule details below each grid. The only unusual item was a consequential naked triple step for puzzle #533.
Code: Select all
top1465 #472
4...1..8...9.2..5.1.......2.3.9.8..7..5.........63......6...4....1.832..7....6..8

after simplification, and XY(Z)-Wing attempts ...

 4      2567     237  | 357    1    579   | 3679  8      369
 368    678      9    | 3478   2    47    | 1367  5      1346
 1      578      378  | 34578  6    4579  | 379   349    2   
----------------------+-------------------+------------------
 26     3        24   | 9      45   8     | 156   1246   7   
 2689   1246789  5    | 1247   47   1247  | 3689  23469  3469
 289    124789   2478 | 6      3    12457 | 589   249    459
----------------------+-------------------+------------------
-23589 -289      6    | 1257  A79   1257  | 4     1379   1359
B59    B49       1    |B457    8    3     | 2     679    569
 7      249      234  | 1245   459  6     | 1359  139    8   

APE (with cell r8c4) removed candidate {9} from cell r7c1
APE (with cell r8c4) removed candidate {9} from cell r7c2

ALS sets: A = {r7c5} = {79}
          B = {r8c124} = {4579}
          x = 7, z = 9, r7c1<>9 and r7c2<>9

============================================================

top1465 #533
........5.4.....7..761.43...85.6...........51.6.2.......2.....9...4.8.....37...1.

after simplification, and XY(Z)-Wing attempts ...

-129  A23  189 | 38  7     29  | 4  6  5
B2359  4   89  | 56  2359  356 | 1  7  28
B25    7   6   | 1   258   4   | 3  9  28
---------------+---------------+---------
 7     8   5   | 9   6     1   | 2  3  4
B29    23  49  | 38  48    7   | 6  5  1
 13    6   14  | 2   345   35  | 9  8  7
---------------+---------------+---------
 8     15  2   | 56  135   356 | 7  4  9
 6     19  7   | 4   19    8   | 5  2  3
 4     59  3   | 7   259   29  | 8  1  6

APE (with cell r2c1) removed candidate {2} from cell r1c1
APE (with cell r1c3) removed candidate {9} from cell r2c1

ALS sets: A = {r1c2} = {23}
          B = {r235c1} = {2359}
          x = 3, z = 2, r1c1<>2, r2c1<>9 follows due to 189 naked triple in box 1

============================================================

top1465 #703
..2..9....6..31....7.65.4...1.3.....5.......7..8.2...9..19......8..7..95......3.4

after simplification, and XY(Z)-Wing attempts ...

 134    345   2    | 478  48     9    | 67    567   13
 8      6     45   | 47   3      1    | 9     57    2
 139    7     39   | 6    5      2    | 4     8     13
-------------------+------------------+---------------
 24679  1     4679 | 3    689   -4567 | 258  A24    68
 5      2349  3469 |B48   14689 B46   |B268  -1234  7
 67     34    8    | 15   2      67   | 15    34    9
-------------------+------------------+---------------
 2347   235   1    | 9    46     3456 | 2678  267   68
 346    8     346  | 12   7      346  | 12    9     5
 2679   259   5679 | 25   16     8    | 3     1267  4

APE (with cell r5c7) removed candidate {4} from cell r4c6
APE (with cell r5c7) removed candidate {4} from cell r5c8

ALS sets: A = {r4c8} = {24}
          B = {r5c467} = {2468}
          x = 2, z = 4, r4c6<>4, r5c8<>4

============================================================

top1465 #1182
8.1.......7..1...45..6.89......63.2....1........7..61..8........1.32..7.3..5.....

after simplification, and XY(Z)-Wing attempts ...

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

APE (with cell r5c1) removed candidate {9} from cell r5c3

ALS sets: A = {r4c3} = {79}
          B = {r5c168} = {2479}
          x = 7, z = 9, r5c3<>9

[edit2: r5c5 was unnecessary part of set B as per Steve R]
============================================================

top1465 #1199
.1...57.4...7...9...8.....58.4...1...2.14.....9...8.........273..3.8.......5.6...

after simplification, and XY(Z)-Wing attempts ...

 2369  1    269 | 8   26   5  | 7     236   4   
 4     56   256 | 7   126  3  |B68    9     1268
 7     36   8   | 49  129  14 |B36    12    5   
----------------+-------------+-----------------
 8     356  4   | 36  7    2  | 1    A56    9   
 356   2    567 | 1   4    9  |B3568  3568  678
 136   9    167 | 36  5    8  |-346   2346  267
----------------+-------------+-----------------
 56    8    56  | 49  19   14 | 2     7     3   
 19    4    3   | 2   8    7  | 569   156   16 
 129   7    129 | 5   3    6  | 489   148   18 

APE (with cell r5c7) removed candidate {6} from cell r6c7

ALS sets: A = {r4c8} = {56}
          B = {r235c7} = {3568}
          x = 5, z = 6, r6c7<>6

============================================================

top1465 #1260
7.....96......5..13......8...69..3...1...8.4.97..4........6.....24.....5...8.1...

after simplification, and XY(Z)-Wing attempts ...

 7     458   1258 | 1234   238    234   | 9     6     234 
 2468  4689  289  | 23467  23789  5     | 247   237   1   
 3     469   129  | 12467  279    24679 | 5     8     247 
------------------+---------------------+------------------
 2458  458   6    | 9      1     A27    | 3     257   78   
B25    1    B23   |-23567 B2357   8     | 267   4     9   
 9     7     2358 | 2356   4      236   | 1     25    268 
------------------+---------------------+------------------
 1     3589  5789 | 245    6      24    | 278   2379  237 
 68    2     4    | 37     379    379   | 68    1     5   
 56    3569  579  | 8      25     1     | 2467  2379  23467

APE (with cell r5c5) removed candidate {2} from cell r5c4

ALS sets: A = {r4c6} = {27}
          B = {r5c135} = {2357}
          x = 7, z = 2, r5c4<>2
[edit: added missing exclusion marks ('-') in #1182 and #1260]
Last edited by ronk on Tue May 02, 2006 12:30 am, edited 2 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Havard » Mon May 01, 2006 10:05 pm

Well done Ron!:)
Havard
 
Posts: 377
Joined: 25 December 2005

A rose by any other name ...

Postby keith » Mon May 01, 2006 10:18 pm

Graeme wrote:


Here you are, Ron:

Code:

top1465 #472
4...1..8...9.2..5.1.......2.3.9.8..7..5.........63......6...4....1.832..7....6..8

after simplification, and XY(Z)-Wing attempts ...

4 2567 237 | 357 1 579 | 3679 8 369
368 678 9 | 3478 2 47 | 1367 5 1346
1 578 378 | 34578 6 4579 | 379 349 2
---------------------+-------------------+------------------
26 3 24 | 9 45 8 | 156 1246 7
2689 1246789 5 | 1247 47 1247 | 3689 23469 3469
289 124789 2478 | 6 3 12457 | 589 249 459
---------------------+-------------------+------------------
23589 289 6 | 1257 79 1257 | 4 1379 1359
59 49 1 | 457 8 3 | 2 679 569
7 249 234 | 1245 459 6 | 1359 139 8

APE (with cell r8c4) removed candidate {9} from cell r7c1
APE (with cell r8c4) removed candidate {9} from cell r7c2

============================================================


I rest my case. This is a WXYZ-wing on <9> centered on R8C4. The buddies of <79>, <59>, <49> cannot be <9>. This excludes <9> from R7C1 and R7C2.

I'll take a look at the other cases later in the week.

Keith
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Postby Steve R » Tue May 02, 2006 3:28 am

Good stuff, Ron! A couple of observations.

In the second example a triple was used to eliminate 9. It fits the general theory better to take account of the first elimination. Then:

A = {r1c1} containing (19); B = {r12c3} containing (189) with rcc 1.

In the fourth example, cannot r5c5 be omitted from set B? If it can, I think all the examples are in line with my “proof” of 20 April that APE is a subcategory of ALS.

Steve
Steve R
 
Posts: 74
Joined: 03 April 2006

Postby ronk » Tue May 02, 2006 5:08 am

Steve R wrote:In the second example a triple was used to eliminate 9. It fits the general theory better to take account of the first elimination. Then:

A = {r1c1} containing (19); B = {r12c3} containing (189) with rcc 1.

No doubt, as even a naked pair can be considered an application of the ALS xz-rule. But an ALS description is rarely used when both sets A & B are in the same unit (row, col, 3x3 box, sector, etc.)

Steve R wrote:In the fourth example, cannot r5c5 be omitted from set B?

Thanks, digit 5 is not a necessary part of the set as I thought. I'll edit my post accordingly.

Steve R wrote:If it can, I think all the examples are in line with my “proof” of 20 April that APE is a subcategory of ALS.

Probably so, but it takes a few examples before some of us can understand a symbolic proof. Perhaps you should "bring life" to your symbols by correlating to the digits of an example or two.

P.S. Graeme deserves the credit for empirically proving the ALS theory expressed by others. He's the one who did the coding, testing, and reporting of results. I merely interpreted some of his results.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Graeme » Tue May 02, 2006 10:00 am

thanks for the link, Ruud - this does indeed look promising.

and thanks also for the credit Ron. I don't have ALS in my solver yet, and definitely couldn't have picked out the sets as you did - so I'll consider it a team effort.
:D
Graeme
 
Posts: 18
Joined: 06 February 2006

Postby Myth Jellies » Thu May 04, 2006 5:54 am

One last nugget for the APE die-hards. You don't have to have bivalue cells to apply APE. For example, if you have two cells in the same group that contain 'abc', then it is fairly easy to show that you can eliminate the ab, ac, and the bc combinations from your APE pair. I imagine any almost locked set would work in a similar fashion.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

PreviousNext

Return to Advanced solving techniques