APE - Further extendable?

Advanced methods and approaches for solving Sudoku puzzles

Postby ronk » Thu Sep 28, 2006 1:25 am

AndrewStuart wrote:This is a false elimination but it conforms the rules as laid out:
Code: Select all
.....17....4....56.2.73....6..3..1...8..6..4...2..9..5....73.6.95....4....35.....
ALS Aligned Pair (r27c2, r6c1458): : r6c2|r2c1 => r6c2<>4
+-------------------+--------------------+------------------+
|    358    39 5689 |     46    45     1 |    7   289  2489 |
|    *17   #17    4 |    289   289    28 |    3     5     6 |
|     58     2 5689 |      7     3   456 |   89   189  1489 |
+-------------------+--------------------+------------------+
|      6   479  579 |      3  2458 24578 |    1  2789  2789 |
|   1357     8 1579 |     12     6   257 |   29     4  2379 |
|  @1347 -1347    2 |   @148  @148     9 |    6  @378     5 |
+-------------------+--------------------+------------------+
|   1248   #14   18 |  12489     7     3 |    5     6  1289 |
|      9     5  178 |   1268   128   268 |    4 12378 12378 |
|  12478     6    3 |      5 12489   248 |  289 12789 12789 |
+-------------------+--------------------+------------------+

1/7 in the stem can see 1s and 7s in both ALSs and 4 is only common candidate not in the stem but in boths ALSs. However, 4 is the solution to r6c2.

For the * ALS, all the 7s see all the 7s in the # ALS ... but all the 1s don't see all the 1s in the @ ALS. Therefore if r2c1=1, the @ ALS still has five candidates -- 13478 -- for four cells. Four of the five candidates would be used but the digit 4 might not be one of them.

[edit: poor English corrected]
Last edited by ronk on Wed Sep 27, 2006 11:31 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Thu Sep 28, 2006 3:08 am

For DB the regular ALS rules apply - to make a link all of the cells of an ALS which contain the link label must be seen all of the cells of the previous node which contain the link label. In the first example there are 2 links: r1c6-7-r2c479-3- and r1c6-1-r8c36-3-. In the first case r1c6 sees r2c4 which is the only cell in the ALS:r2c479 (3567) with a "7" and r2c3 sees r2c47 which both contain "3". In the second, r1c6 sees the "1" in r8c6 which is the only cell of ALS:r8c36 (137) which contains "1" and r2c3 sees r8c3 which is the only cell of the ALS which contains "3". (This link can also be considered two bivalue links.)

Code: Select all
4-valued Death Blossom (r1c6-1-r8c36-3-, r1c6-7-r2c479-3-): : r2c3|r1c6 => r2c3<>3
+--------------------+----------------+------------------+
|  36789   678     5 |  2367  139 *17 |   1238    4  268 |
|      2    17  -137 |  @367    8   4 |   @356    9  @56 |
|   3689   468  3489 |   236  139   5 |  12368   13    7 |
+--------------------+----------------+------------------+
|      5     3    47 |     9    6   8 |    147    2   14 |
|    789   478   489 |     1    5   2 |     47    6    3 |
|      1     2     6 |     4    7   3 |     89    5   89 |
+--------------------+----------------+------------------+
|   3678  1678     2 |   378    4   9 |    135  137   15 |
|      4     9   #37 |     5   13 #17 |     26    8   26 |
|    378     5  1378 |   378    2   6 |     49  137   49 |
+--------------------+----------------+------------------+ 


In the next example r1c3 sees the "1" in r1c7 so a valid link exists to the ALS: r17c7 (169). The "6" in r7c7 is seen by r7c6 again creating a valid link since r7c7 is the only cell of the ALS containing a "6". On the other hand the "9" in r7c8 sees only the "9" in r7c7, but not the one in r1c7. Thus the link cannont be made since r7c8 doesn't see all the cells of the ALS: r17c7 which contain "9".

In the second link, the "7" in r7c3 of the ALS r7c37 (679) is seen by r1c3 and the "6" of r7c37 is seen by r7c6 again creating valid links. In this case, the "9" can also create a valid link, but all links must be valid for the elimination to occur.

Note that the fact that the two ALS overlap is immaterial. Each short link/chain is established independently which is one of the reasons I think the technique works so well. Its also IMO the strength of the approach since several short chains are constructed instead of one or several long ones. Note also that multiple exclusions can be made (in this case r7c8<>6 as well).
Code: Select all
3-valued Death Blossom (SUM Exclusion) (r1c3-1-r17c7-6-, r1c3-7-r7c37-6-): r1c3 => r7c68<>6
+------------------+--------------------+------------------+
|   6    137   *17 |   39     48     48 |   #19      2   5 |
|  49     18   148 |    5      2      7 |     3     19   6 |
|  39      5     2 |    1      6     39 |     7      8   4 |
+------------------+--------------------+------------------+
|   1    689     3 |   67    458  45689 |     2    467  78 |
|   2     68     5 |   37  13478   3468 |  1468   1467   9 |
|   7      4   689 |  269     18   2689 |     5     16   3 |
+------------------+--------------------+------------------+
|   8     27  @679 |    4    357  -2356 |  #@69  -3679   1 |
|  34  12367   146 |  267      9    236 |   468      5  78 |
|   5   3679  4679 |    8     37      1 |   469  34679   2 |
+------------------+--------------------+------------------+


The last example is the same situation, the "1" in r2c1 doesn't see both "1"s in the ALS r27c2 and so the link can't be made.

So in terms of DB, for the stem to "see" an ALS petal with a given candidate, all of the cells of the ALS which contain the candidate must share a house with the stem. Likewise for a candidate to be eliminated from a cell, that cell must share a house with all of the cells of the petals which contain the candidate.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Myth Jellies » Thu Sep 28, 2006 4:36 am

What I have gleaned so far....

All this really is, is a chain/net. Instead of starting at one endpoint and then coming to a cell and branching multiple directions (or perhaps just continuing on if the cell is bivalued), Mike starts from the potentially branching cell and constructs little chains to endpoints. Mike might be further limiting his search in some cases by only considering ALS's that see each of his branches. Though I think he has indicated that this is not necessary, this helps keep the searching down to something humans can do fairly easily. ALS's also work great for this, because you can enter into them with one or more digit/branches and you have a choice of perhaps several more digits as an endpoint.

Also something that I think Mike has indicated is the fact that the branch point does not have to be all the digits in a cell. It could also be all the sevens in a row, or all the threes in a box, or all the extra candidates in an AUR or BUG grid, or any other collection where you know that at least one element must be true.

I don't believe that this method can do anything above and beyond chains/branching networks, but the way that it does things might be easier for some people to visualize or use when compared to other ways of forming chains and networks, especially those utilizing lots of ALS's.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Myth Jellies » Thu Sep 28, 2006 5:17 am

Doh--double post (how did that happen):)
Last edited by Myth Jellies on Thu Sep 28, 2006 10:37 am, edited 1 time in total.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby AndrewStuart » Thu Sep 28, 2006 9:34 am

Ronk, Mike, just wanted to insert my thanks before the thread grows anymore. Explanations have done a good deal to clarify.
AndrewStuart
 
Posts: 21
Joined: 28 December 2005

Postby Mike Barker » Thu Sep 28, 2006 2:11 pm

Myth, I agree with you both times. The reason Death Blossom only uses ALS is that it was conceived of prior to its merging with Kraken Fish. The resulting Kraken Blossom is one technique derived from the SUM approach. Other techniques use a house, fish, UR, etc as the restricted subset instead of a cell (a simple Havard's Almost*Locked Set) and have been used to solve some of the Unsolvables. All techniques are essentially easy to understand ways of creating forcing chains or nets. I personally believe that Kraken Blossom and House stand on their own as easy to implement techniques (when used on intermediate problems) slightly more difficult than a finned X-wing and more powerful (see here). Kraken UR greatly simplifies the plethora of UR techniques into one logical technique. Kraken fish is, as you have said, an alternative way to looking into Carcul's Almost Fish forcing chains which helps me to understand what is happening and which possibly makes such an elimination easier, although in the extreme not something most humans could do. Kraken BUG, Kraken ALS, Kraken A*LS, Kraken (insert your favorite restricted subset here) are yet to be explored. A long way of saying I agree with you. I'll put down my horn.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby AndrewStuart » Thu Sep 28, 2006 3:22 pm

Code: Select all
4-value Aligned Pair (r789c7, r2c9): : r3c7|r8c9 => r3c7<>4
+-------------------+----------------+----------------------+
|  128     18     7 |    4   689   3 |       5  2689    269 |
|    9    358  3458 |    7   568   2 |    -348     1    @46 |
|  258      6   345 |  589   589   1 | -234789  2489   2479 |
+-------------------+----------------+----------------------+
|    6    158     2 |    3    14   9 |      48     7     45 |
|   58      4  3589 |  256   257  67 |       1   289   2359 |
|  157  13579   359 |   25    14   8 |       6   249  23459 |
+-------------------+----------------+----------------------+
|    3    789   689 |  289  2789   5 |   #2479  2469      1 |
|  578   5789  5689 |    1  2789   4 |    #279     3  *2679 |
|    4      2     1 |   69     3  67 |     #79     5      8 |
+-------------------+----------------+----------------------+

Mike, am I correct in stating that in your original example above, 4 can also be removed from r2c7 - exactly the same DB formation, two birds with one stone?
AndrewStuart
 
Posts: 21
Joined: 28 December 2005

Postby ronk » Thu Sep 28, 2006 4:13 pm

Mike Barker wrote:Kraken Fish ... Kraken Blossom and House ... Kraken UR ... Kraken BUG ... Kraken ALS ... Kraken A*LS ... Kraken (insert your favorite restricted subset here) ...

Franken kraken kracken smacken ... totally over the top IMO.

Mike Barker wrote:... a simple Havard's Almost*Locked Set ...

As if Havard coined AALS, AAALS, etc.? Not!
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Thu Sep 28, 2006 6:57 pm

Andrew, by george I think you've got it. The elimination is correct.

Ron, I won't deny some of the names may be a little theatrical. I figure only the useful ones will survive, but I enjoy the color they bring to Sudoku whether it be an X-wing, a Franken squirmbag or Death Blossom! Also, I'm always happy to give credit where credit is do. Most of my exposure to A*LS has come through Havard especially with regards to the similarity to the SUM method. I'll try to be more careful in the future.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Havard » Fri Sep 29, 2006 1:36 pm

ronk wrote:
Mike Barker wrote:Kraken Fish ... Kraken Blossom and House ... Kraken UR ... Kraken BUG ... Kraken ALS ... Kraken A*LS ... Kraken (insert your favorite restricted subset here) ...

Franken kraken kracken smacken ... totally over the top IMO.


My grandmother used to say: "If you don't have anything nice to say, don't say it", and for some reason I keep getting reminded of this when I read ronks posts. I happen to think that creativity likes a loving, friendly environment where people can come together and discuss ideas without being afraid of getting blasted by the likes of ronk. I really like your names Mike, and wheter they will become "common terms", only time will tell. In the meantime, please don't take notice of posts like that. A lot of people love the work you are doing, even if they don't say so very often!:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Aligned triplet exclusion - reviewed

Postby claudiarabia » Sun Nov 05, 2006 3:53 am

Code: Select all
 
 *-----------*
 |...|1..|...|
 |.86|.2.|17.|
 |.2.|8.7|.9.|
 |---+---+---|
 |.98|371|.6.|
 |...|956|...|
 |65.|...|93.|
 |---+---+---|
 |..4|.1.|6..|
 |.12|63.|48.|
 |.6.|...|.1.|
 *-----------*
 
 *-----------------------------------------------------------------------------*
 | -34579  -347    @359    | 1       469     @35     | 2358   245    234568    |
 | @349    8       6       | @45     2       3459    | 1       7       345     |
 | 1345    2       135     | 8       46      7       | 35      9       3456    |
 |-------------------------+-------------------------+-------------------------|
 | 24      9       8       | 3       7       1       | 25      6       245     |
 | 12347   347     137     | 9       5       6       | 278     24      12478   |
 | 6       5       17      | 24      48      248     | 9       3       12478   |
 |-------------------------+-------------------------+-------------------------|
 | 35789   37      4       | 257     1       2589    | 6       25      23579   |
 | 579     1       2       | 6       3       59      | 4       8       579     |
 | 35789   6       3579    | 2457    489     24589   | 2357    1       23579   |
 *-----------------------------------------------------------------------------*


With the @ I marked an in SE so called aligned triplet exclusion. While the Explainer excludes only the 3 in A1 I found the 3 in B1 to be eliminated too. Thus the word "triplet exclusion" is void in my eyes. For me it is an enlarged XYZ-wing because the number 3 appears three times in the wing and it has a twin-center. While the center of the xyz-wing has to contain all the candidates of the wing-cells, the cells which shelter the center (the trunk?) of the wing here, i.e. C1 and D2, do exactly that together. They are the only ones who are worth to build comparable candidate-pairs within the @-cells. The rest is defined by the wing-cells A2 and F1. Why take three cells as does the Explainer with A1,C1 and D2?

For me this is an xyz-wing with a twin-center.
May I call it an xyz-wing of the second grade?

Or is there a higher definition with a broader space for Aligned Triplet Exclusion?
Code: Select all
. . . . . . . . .
. 8 6 . 2 . 1 7 .
. 2 . 8 . 7 . 9 .
. 9 . 3 7 1 . 6 .
. . . 9 . 6 . . .
. 5 . . . . . 3 .
. . 4 . 1 . 6 . .
. 1 2 . 3 . 4 8 .
. . . . . . . . .
This is the original puzzle

Claudia
claudiarabia
 
Posts: 288
Joined: 14 May 2006

Re: Aligned triplet exclusion - reviewed

Postby ronk » Sun Nov 05, 2006 12:53 pm

claudiarabia wrote:
Code: Select all
 | -34579  -347    @359    | 1       469     @35     | 2358   245    234568    |
 | @349    8       6       | @45     2       3459    | 1       7       345     |
 | 1345    2       135     | 8       46      7       | 35      9       3456    |
...
With the @ I marked an in SE so called aligned triplet exclusion. While the Explainer excludes only the 3 in A1 I found the 3 in B1 to be eliminated too. Thus the word "triplet exclusion" is void in my eyes.

SE's "Get all hints" shows two different Aligned Triplets, one making the exclusion at A1 and the other at B1. A simpler step is available after A1<>3, so you didn't see the B1<>3.

I like the following interpretation ... somewhat like the ALS xy-rule I think, although there is overlap at F1 in this case.
Code: Select all
     A     B     C       D     E     F       G     H     J
1   -357  -347  *359   | 1     69  @*35    | 28    245   2568
2   @349   8     6     |@45    2     3459  | 1     7     345
3    145   2     135   | 8     46    7     | 35    9     3456
The top floor at the point of SE's Aligned Triplet hints.

At least one of C1<>9 or A2<>9 must be true (a weak link is sufficient)
If C1<>9, then C1=3 or F1=3 (naked pair)
If A2<>9, then A2=3 or F1=3 (xy=wing)
Thus any 3 that sees all of C1, F1 and A2 may be excluded

P.S. This chessboard-like notation is not easy.:(
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Aligned triplet exclusion - reviewed

Postby claudiarabia » Sun Nov 05, 2006 3:09 pm

Ronk wrote:

I like the following interpretation ... somewhat like the ALS xy-rule I think, although there is overlap at F1 in this case.
Code: Select all
     A     B     C       D     E     F       G     H     J
1   -357  -347  *359   | 1     69  @*35    | 28    245   2568
2   @349   8     6     |@45    2     3459  | 1     7     345
3    145   2     135   | 8     46    7     | 35    9     3456
The top floor at the point of SE's Aligned Triplet hints.

At least one of C1<>9 or A2<>9 must be true (a weak link is sufficient)
If C1<>9, then C1=3 or F1=3 (naked pair)
If A2<>9, then A2=3 or F1=3 (xy=wing)
Thus any 3 that sees all of C1, F1 and A2 may be excluded[/quote]

So you can also use a kind of regional forcing chains based on Number 9.

If you set A2<>9 then F1 is definitely 3.

Why you used the stars for C1 and F1 in addition to @ for A2 D2 and F1? What is the difference between them?

Claudia[/quote]
claudiarabia
 
Posts: 288
Joined: 14 May 2006

Re: Aligned triplet exclusion - reviewed

Postby ronk » Sun Nov 05, 2006 7:22 pm

claudiarabia wrote:So you can also use a kind of regional forcing chains based on Number 9.
Sorry, I'm not familiar with the "region forcing chain" term.

claudiarabia wrote:If you set A2<>9 then F1 is definitely 3.
True, but wasn't the object to use the cells of SE's Aligned Triples?

claudiarabia wrote:Why you used the stars for C1 and F1 in addition to @ for A2 D2 and F1? What is the difference between them?
The '*' is for the naked pair ... and the '@' for the xy-wing.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Steve R » Sun Nov 05, 2006 8:03 pm

I should like to add to the mention of bennys’ work by developing a couple of recent examples as I think he might have done in his original paper.
Code: Select all
4-valued Death Blossom (r1c6-1-r8c36-3-, r1c6-7-r2c479-3-): : r2c3|r1c6 => r2c3<>3
+--------------------+----------------+------------------+
|  36789   678     5 |  2367  139 *17 |   1238    4  268 |
|      2    17  -137 |  @367    8   4 |   @356    9  @56 |
|   3689   468  3489 |   236  139   5 |  12368   13    7 |
+--------------------+----------------+------------------+
|      5     3    47 |     9    6   8 |    147    2   14 |
|    789   478   489 |     1    5   2 |     47    6    3 |
|      1     2     6 |     4    7   3 |     89    5   89 |
+--------------------+----------------+------------------+
|   3678  1678     2 |   378    4   9 |    135  137   15 |
|      4     9   #37 |     5   13 #17 |     26    8   26 |
|    378     5  1378 |   378    2   6 |     49  137   49 |
+--------------------+----------------+------------------+

A = {r1c6}, candidates 1 and 7 (als)
B = {r8c36}, candidates 1, 3 and 7 (als)
C = {r2c479}, 3, 5, 6 and 7 (als)
rccs(A, B): 1
rccs(A, C): 7
Eliminate 3 from r2c3.

Code: Select all
  356      4   1356  | 689   159  1689  |   578     2    67 
    9    578    567  |  24   245    68  |     1  4568     3 
   56     18      2  |   3    14     7  |     9    48    56 
---------------------+------------------+--------------------
 2567      9   3567  |   1  2368     4  | 23578   368  2567 
    8  12357  13567  | 269   236    39  |   357  1356     4 
 2346    123    346  |   7  2368     5  |   238     9   126 
---------------------+------------------+--------------------
   47B    37B     8  |   5  3479-    2  |     6    13D   19D
    1   2357-     9  |  46   467    36  |  2345    35     8 
 2345A     6    345A |  89  1349    18  |   234     7   259C

A = {r9c9}, candidates 2, 5 and 9 (two degrees of freedom)
B = {r7c289}, candidates 1, 3, 7 and 9 (als)
C = {r7c1, r7c2, r9c1, r9c3}, candidates 2, 3, 4, 5and 7 (als)
rccs(A, B): 9
rccs(A, C): 2 and 5
Eliminate 7 from r7c5 and r8c2.

Apart from the tribute I think some contributors might not be aware that bennys included sets with more than one degree of freedom. His original example concerned a set A with two degrees of freedom having a restricted common candidate, x, with an als B and a different restricted common candidate, y, with an als C. In these circumstances eliminations may be made on a third candidate, z, common to all three candidate sets. However, more eliminations may be made when A has two (or more) restricted common candidates with one or more of the almost locked sets, as is the case with the last example.

Of course, these sets may well be spotted most easily using APE, ATE or chains.

Steve
Last edited by Steve R on Sun Nov 05, 2006 6:19 pm, edited 1 time in total.
Steve R
 
Posts: 74
Joined: 03 April 2006

PreviousNext

Return to Advanced solving techniques