The New Sudoku Players' Forum

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

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

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

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

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

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

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

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

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

by **Havard** » Mon May 01, 2006 10:05 pm

Well done Ron!

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

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

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

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

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

The New Sudoku Players' Forum

Aligned Pair Exclusion (APE, no DJ)

Dead Thread?

A rose by any other name ...