APE - Further extendable?

Advanced methods and approaches for solving Sudoku puzzles

Postby Mike Barker » Mon Sep 11, 2006 1:21 pm

Sorry if I wasn't clear. I agree with the elimination Myth showed. It fits with the requirements that there be more than 2 elements to the AIC. My comment referred to an AIC with only two elements. For example ALS1=r4c1={3,6} and ALS2={r4c1,r7c1}={3,6,7}. You can't link the "6"s in the two ALS and conclude you can eliminate "3" from other cells which can see these two. Elimination is also possible in Myth's example because the two ALS are at the start and end of the loop. What happens if they were in the middle?
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Myth Jellies » Tue Sep 12, 2006 3:22 am

As far as overlaps on consecutive candidate premises, this little illustration may help.

Consider a cell containing candidates, abc. Two overlapping premises would be cell contains (a OR b) and cell contains (b OR c). Since these premises span all the possibilities of the cell, you can potentially use a strong inference between them,

(a OR b) = (b OR c)

However, because of the overlap, there is no weak inference between them. When the overlap is true, both premises are true.

From this, I would conclude that ALSs work the same way. You could use overlapping ALSs when you need a strong inference, but not when you need a weak one?
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Havard » Tue Sep 12, 2006 8:16 am

If I have understood this right, this discussion is about the fact that if you have a open chain of ALSs (discontinous), the first and the last ALS in the chain can actually share one cell, and you can still do eliminations.

Now already we knew this:
Code: Select all
  A(36)----------6---------B(69)
   |                         |
   |                         |
                             |
   *  ---E(36)--6--D(67)     9
                       \     |
                         7   |
                          \  |
                           C(79)

Here the * can't be a 3.

If we now make A and E into the same cell, we get:
Code: Select all
  A(36)----------6---------B(69)
   |                         |
   |                         |
   6                         9
   |                         |
   |                         |
  D(67)----------7---------C(79)


which by the Nice Loop rules means that A have to be a 3, and hence all other 3's around A will be eliminated.

so maybe in one way this could be thought of as:
Code: Select all
5.2..9.......1..5.1..4..8....8..4..7.7..6....2..8..3....1..2..8....3..1.4....156.
3-valued ALS Aligned Pair (r47c1, r4c17): r2c1|r7c7 => r2c1<>3
+-------------------+-----------------+---------------------+
|     5  3468     2 |   367   78    9 |    146   347   1346 |
| -3678  3469  3679 |  2367    1  368 |  24679     5  23469 |
|     1   369  3679 |     4   25  356 |      8  2379    369 |
+-------------------+-----------------+---------------------+
|A&D(36)  356     8 |     1  259    4 |   B(69)   29      7 |
|     9     7     4 |    23    6   35 |     12     8    125 |
|     2     1    56 |     8   59    7 |      3    49   4569 |
+-------------------+-----------------+---------------------+
| D(367) 3569     1 |   569    4    2 |   C(79)  379      8 |
|    78   259  5679 |  5679    3   68 |   2479     1    249 |
|     4  2389   379 |    79   78    1 |      5     6    239 |
+-------------------+-----------------+---------------------+

That this overlap of A and D does not automatically place the 3 (since D is not a bivalue cell), but we do know that the 3 has to go in one of these cells.

Allowing long ALS-chains to overlap in my solver have given me a lot of wrong eliminations before, but it sure looks like as long as the overlap happens only in the ends of the chain, it is very valid!:) I would be very interested to see an example of a succsessful overlap not at the chain-ends.

Havard
Havard
 
Posts: 378
Joined: 25 December 2005

Postby Mike Barker » Sun Sep 17, 2006 11:17 pm

I hope you all don't mind my calling advanced align pair exclusion technique "Death Blossom". Its actually rather appropo especially given that the technique no longer requires alignment or pairs. Anyway, I was looking at some of the older "unsolvables" and found that DB can also lead to a solution of U#14. The critical step is:
Code: Select all
5-valued Death Blossom (r79c1|r9c3|r7c2, r7c289): r9c9 => r7c5<>7,r8c2<>7
+---------------------+------------------+--------------------+
|  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  |
+---------------------+------------------+--------------------+
|   47#    37#%    8  |   5  3479-    2  |     6    13%   19% |
|    1   2357-     9  |  46   467    36  |  2345    35     8  |
| 2345#     6    345# |  89  1349    18  |   234     7   259* |
+---------------------+------------------+--------------------+

Huzzah to SHuisman and the rest of the contributors for developing this idea.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Mon Sep 18, 2006 2:00 am

How about an Almost 'Sue de Coq'?:)

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

Sets: A = {r9c13} = {2345}
      B = {r7c12} = {347}
      C = {r9c9} = {259}
      D = {r7c89} = {139}

At least one of r7c9<>9 and r9c9<>9 must be true.
If r7c9<>9 then set D = {13} making set B = {47}.
If r9c9<>9 then sets A, B and C form a 'Sue De Coq' which locks the 7 in set B.
Either way, set B contains a 7 and any candidate 7 that sees all the 7s in set B may be excluded.

A nice loop expression:

{ALS:r7c12=7|3=r7c12}-3-{ALS:r7c89=3|9=r7c89}-9-{ASDC:r9c139=9|7=r7c12}

... where ASDC stands for 'Almost Sue de Coq'
... implying r7c12 contains a 7
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Mon Sep 18, 2006 5:19 am

Okay so I don't feel so bad about "Death Blossom". An Almost Sue de Coq? Brilliant observation, but I don't think its going to catch on!
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Mon Sep 18, 2006 1:30 pm

Mike Barker wrote:Okay so I don't feel so bad about "Death Blossom". An Almost Sue de Coq? Brilliant observation, but I don't think its going to catch on!

I wasn't promoting the 'Almost Sue de Coq' name, but rather the method using one AALS and ALSs. The lowest band of the grid could look like ...
Code: Select all
  347B   347B     8  |   5  3479-    2  |     6   139D  139D
    1   2357-     9  |  46   467    36  |  2345    35     8 
 2345A     6   2345A |  89  1349    18  |   234     7   259C


There is no pair in any cell of sets A, B, C and D and yet the same exclusions using nice loop ...

{ALS:r7c12=7|3=r7c12}-3-{ALS:r7c89=3|9=r7c89}-9-{ASDC:r9c139=9|7=r7c12} implying r7c12=7

... remain valid.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Mon Sep 18, 2006 3:32 pm

Another take on it...
Code: Select all
  347AD  347AD    8  |   5  3479-    2  |     6   139B  139B
    1   2357-     9  |  46   467    36  |  2345    35     8 
 2345D     6   2345D |  89  1349    18  |   234     7   259C


Option 1, overlapping end ALS:
(7&4=3)r7c12 - (3=1&9)r7c89 - (9=2or5)r9c9 - (2&5=3&4&7)r7c12|r9c13

Code: Select all
  347AB  347AB    8  |   5  3479-    2  |     6   139B  139B
    1   2357-     9  |  46   467    36  |  2345    35     8 
 2345A     6   2345A |  89  1349    18  |   234     7   259C


Option 2, combined overlapping ALS rule...digits in the overlap anded together are strongly linked to anded digits outside of the overlap. Thus for the combined overlapping A & B ALS we have

((3&4&7) = (1&9&2&5))r7c1289|r9c13

since r9c9 equals 2 or 5 or 9 and it is weakly linked to all the 2's, 5's, and 9's in the combined ALS, we know that (1&9&2&5) is false and therefore (3&4&7) must be true.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Mon Sep 18, 2006 5:21 pm

Myth Jellies wrote:Option 1, overlapping end ALS:
(7&4=3)r7c12 - (3=1&9)r7c89 - (9=2or5)r9c9 - (2&5=3&4&7)r7c12|r9c13

For the portion I highlighted, it took me a while to figure out that "not (2 & 5)" on the left implies either "2&3&4&7" or "5&3&4&7" on the right ... and the 2 and 5 are simply omitted. But I guess that's no different than the "r7c12=7" I wrote ... just less known candidates than cells.

Option 2, combined overlapping ALS rule...digits in the overlap anded together are strongly linked to anded digits outside of the overlap.

Hmmm! I missed that point somewhere. Do you have a link to a prior discussion?

since r9c9 equals 2 or 5 or 9 and it is weakly linked to all the 2's, 5's, and 9's in the combined ALS ...

And the "combined ALS" is _______?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Tue Sep 19, 2006 4:28 am

ronk wrote:
Myth Jellies wrote:Option 1, overlapping end ALS:
(7&4=3)r7c12 - (3=1&9)r7c89 - (9=2or5)r9c9 - (2&5=3&4&7)r7c12|r9c13

For the portion I highlighted, it took me a while to figure out that "not (2 & 5)" on the left implies either "2&3&4&7" or "5&3&4&7" on the right ... and the 2 and 5 are simply omitted.

Yep, for a simple ALS, you can divide those and'ed digits pretty much any way you want to.

ronk wrote:
Option 2, combined overlapping ALS rule...digits in the overlap anded together are strongly linked to anded digits outside of the overlap.

Hmmm! I missed that point somewhere. Do you have a link to a prior discussion?

Surprisingly, the genesis of the theory was an old discussion that you and I had, here! Mike's description of the workings of his Death Blossom in another forum, coupled with the idea of consecutive ALS's discussed here, resulted in my formulation of the rule for combining overlapping ALS's & working with them in this post. Since it was buried in an relatively obscure post there, I thought I would repeat it here and perhaps generate a little more discussion.

And the "combined ALS" is _______?

The cells marked with A and/or B. (r7c1289|r9c13)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Tue Sep 19, 2006 10:19 am

[edit: This analysis and the additional exclusions shown are incorrect ... but I'll let it stand for now.]

Myth Jellies wrote:Another take on it...
Code: Select all
   347AD    347AD      8  |   5  3(47)9     2  |     6   139B  139B
     1    235(7)       9  |  46     467    36  |  2345    35     8 
23(4)5D       6   23(4)5D |  89    1349    18  |   234     7   259C

Option 1, overlapping end ALS:
(7&4=3)r7c12 - (3=1&9)r7c89 - (9=2or5)r9c9 - (2&5=3&4&7)r7c12|r9c13
Modified to show additional exclusions and show exclusions in parentheses

Except for empty rectangles I've avoided overlaps, but this puzzle is causing me to reconsider because ...

At least one of r7c9<>9 and r9c9<>9 must be true.
If r7c9<>9, then set A = {47}.
If r9c9<>9, then set D = {347}.
In this case the intersection of sets A and D is set A.

[edit: However, the intersection doesn't apply because EITHER r7c9<>9 OR r9c9<>9 OR both must be true.]

Since A = {47], two candidates for two cells, both digits 4 and 7 are locked to set A.
Therefore, in addition to r7c5<>7 and r8c2<>7, we have r7c5<>4 and r9c13<>4.

Havard can again proclaim cannibalism, since two of the exclusions are within set D.:D
Last edited by ronk on Tue Sep 19, 2006 12:13 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Tue Sep 19, 2006 3:04 pm

Hmmm

Ronk, I read it that either A contains 4 & 7 or D contains 3 & 4 & 7. The sevens are locked in A, but the fours aren't. You could use this to eliminate any fours from r8c2, but not from r9c13 or r7c5. (i.e. B could contain the 9 and A may contain 3 & 7 and D contain the 4)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby SHuisman » Tue Sep 19, 2006 3:53 pm

Mike Barker wrote:I hope you all don't mind my calling advanced align pair exclusion technique "Death Blossom".
Huzzah to SHuisman and the rest of the contributors for developing this idea.

I created the idea, you worked it out with a lot of examples! Huzzah to you as well !
Last edited by SHuisman on Tue Sep 19, 2006 1:32 pm, edited 3 times in total.
SHuisman
 
Posts: 17
Joined: 23 March 2006

Postby ronk » Tue Sep 19, 2006 4:03 pm

Myth Jellies wrote:I read it that either A contains 4 & 7 or D contains 3 & 4 & 7.

You are correct. For the time being, I'll continue not using overlaps.:(
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby AndrewStuart » Wed Sep 27, 2006 10:10 pm

Great name Death Blossom, and it looks like a neat strategy. I'd be grateful for a little help on the finer points of detecting them. At the moment I get too many eliminiations (false as well as true) or none at all depending on the constraints I put in. Mainly its to do with not seeing all the ALS. quoting Mike Baker
Here are a few more examples using ALS with up to 5 values. The first one clearly shows how the two cells do not need to see the entire ALS.

Taking one of Mike's examples
Code: Select all
..5....4.2...84.9.........7.3.9...2....15...31.6..3.....2.4....49.5...8.....26...
4-valued ALS Aligned Pair (r8c36, r2c479): : 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 |
+--------------------+----------------+------------------+ 

The stem is the 1/7 in r1c6 and the common candidates in the two ALSs is 3, so 3 can go from r2c3. Fine. But the stem cant see the 7 in r8c3. Is it sufficient it can see ANY 7 in the ALS r8c36? If so then it widens the constraints such that I get too many DBs.

Taking a step back I've re-written Mike's approach to be a little more clear (in my mind):
Code: Select all
Specifically the approach can be considered to be
 
 - locate a cell (the stem) X which can see ALSs (plural) (the petals) which together contain all of the candidates of the cell X and all of which contain the same one other candidate Z (X+Z).
 
 - This candidate Z can be eliminated from any cell which sees all of the ALSs, but is not part of the ALSs or cell X.

but in this example of Mikes:
Code: Select all
6............273...5..6.78.1.3...2....5.....974.......8..4....1....9..5....8.1..2
3-valued ALS Aligned Pair (r17c7, r7c37): : r7c6|r1c3 => r7c6<>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 |
+------------------+--------------------+------------------+

There are two common candidates for Z - 6 and 9. Mike only eliminates the 6 in r7c8. Isn't 9 also common to both ALSs and not part of the stem. Couldn't 9 be removed from r7c9? Is "contain the same one other candidate" actually "all other candidates not in the stem", or is there some reason 9 is a false elimination in my analysis?

Here is a case in point. 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.

Basically, I think the detection definition ought to include whats and whys about which parts of the ALSs must be or need not been seen by the stem and the elimination cell. Any help appreciated.
AndrewStuart
 
Posts: 21
Joined: 28 December 2005

PreviousNext

Return to Advanced solving techniques