The New Sudoku Players' Forum

[Overkill]

Hello!

Note: This has already been posted on Sudoku Programmers...

Implementing yet another sudoku app I implemented several strategies (i found and understood) for a solver/generator/help-system. Reading (E)APE I thought about combining the logic of XY Chains with APE.

Within a chain like AB-BC-CD I call A the unchained candidate of the first cell and D the unchained candidate of the last one. A better naming is welcome.

The logic of Chained APE (CAPE) is: If you can find a XY Chain that
- the first cell of the chain shares its "unchained" candidate A with X and
- the last cell shares its unchained candidate B with Y
then the combination A+B can be excluded for APE on X & Y.
If X would be A, the chain forces its last cell to be B and thus Y can not have Candidate B.

Obviously, the chain can be of odd or even length (different as in pure XY Chains) and the rules of APE and EAPE should be applied, also.

Using Chained APE I could solve #87 and #91 of the top 95 puzzles - see my test case dump:

Code: Select all


example (#87 of top 95) ...5.3.......6.7..5.8....1636..2.......4.1.......3...567....2.8..4.7.......2..5..
using: Hidden Single, Single Candidate, Intersection Removal, Unique Rectangle, Naked Pair, X-Wing, Aligned Pair Exclusion, Y-Wing, Hidden Pair, Naked Triples, Sword Fish, Extended Aligned Pair Exclusion, Single Chain, XY-Chain, Hidden Triples, Naked Quads, Jelly Fish, WXYZ-Wing, Multivalue X-Wing, Multi Colouring, Squirm Bag, Hidden Quads

==>
+----------------+----------------+----------------+
|   7   49    6  |   5    1    3  |  48   489   2  |
| {14}[1349]  2  |   8    6  {49} |   7    5   349 |
|   5  [349]  8  |   7  {49}   2  | {34}   1    6  |
+----------------+----------------+----------------+
|   3    6    7  |   9    2    5  |  148  48   14  |
|   9    2    5  |   4    8    1  |  36   367  37  |
|  48   48    1  |   6    3    7  |   9    2    5  |
+----------------+----------------+----------------+
|   6    7   39  |   1    5   49  |   2   34    8  |
|   2    5    4  |   3    7    8  |  16   69   19  |
|  18   18   39  |   2   49    6  |   5   347  347 |
+----------------+----------------+----------------+

Chained Aligned Pair Exclusion
 R2C2(1349) R3C2(349)
Initial Possible Combiantions (1+3 1+4 1+9 3+4 3+9 4+3 4+9 9+3 9+4)
 R2C1(14)
-(1 4) Possible Combiantions (1+3 1+9 3+4 3+9 4+3 4+9 9+3 9+4)
 R1C2(49)
-(4 9) Possible Combiantions (1+3 1+9 3+4 3+9 4+3 9+3)
 R2C1(14) R1C2(49)
Extended Aligned Pair Exclusion Possible Combiantions (1+3 3+4 3+9 4+3 9+3)
 R2C1(14) R2C6(49) R3C5(49) R3C7(34)
XY Chains 1-4-9-4-3 Possible Combiantions (3+4 3+9 4+3 9+3)
 R2C2(1349)
Remove marks (1)
==>
+-------------+-------------+-------------+
|  7   49  6  |  5   1   3  |  48 489  2  |
|  14 349  2  |  8   6   49 |  7   5  349 |
|  5  349  8  |  7   49  2  |  34  1   6  |
+-------------+-------------+-------------+
|  3   6   7  |  9   2   5  | 148  48  14 |
|  9   2   5  |  4   8   1  |  36 367  37 |
|  48  48  1  |  6   3   7  |  9   2   5  |
+-------------+-------------+-------------+
|  6   7   39 |  1   5   49 |  2   34  8  |
|  2   5   4  |  3   7   8  |  16  69  19 |
|  18  18  39 |  2   49  6  |  5  347 347 |
+-------------+-------------+-------------+
thus the grid can be solved using the given strategies!


Free APE: when APE is not restricted to aligned cells, puzzles #29 #40 & #71 of top 95 can also be solved. But this strategy has a bit of a "trial and error" taste...

Chained APE seems logic to me and using a "does no wrong conclusions" testcase did not reveal any faults/bad reductions within the top95 and other puzzles.

My question is: is the Chained APE logic already covered by any other strategy or has some equal strategy been documented anwhere before?
If not, does anyone agree with my strategy?

Thank You for any comments (and forgive my bad english for I am German)!

[StrmCkr]

im pretty sure what you are doing is also described as a Function in the technique discussed on this site called

B.U.G
(Bivavle universal Grave )

you can find the reference matterial on this link.

http://forum.enjoysudoku.com/viewtopic.php?t=2352

[Mike Barker]

The approach is much more like a Death Blossom/Kraken Blossom except that the latter use Almost Locked Sets and strong links as well. Limiting links to bivalues is useful for tackling simpler problems.

Viewed as a Death Blossom, the puzzle stem is r3c2={349}. The three petals are:

Code: Select all

r3c2-3-r3c7-4-r3c5-9-r2c6-4-r2c1-1- or with ALS r3c2-3-ALS:r3c57-9-ALS:r2c16-1-
r3c2-4-r2c1-1-
r3c2-9-r1c2-4-r2c1-1- or with ALS r3c2-9-ALS:r2c1|r1c2-1-
+----------------+----------------+----------------+
|   7  {49}   6  |   5    1    3  |  48   489   2  |
| {14}[1349]  2  |   8    6  {49} |   7    5   349 |
|   5  [349]  8  |   7  {49}   2  | {34}   1    6  |
+----------------+----------------+----------------+
|   3    6    7  |   9    2    5  |  148  48   14  |
|   9    2    5  |   4    8    1  |  36   367  37  |
|  48   48    1  |   6    3    7  |   9    2    5  |
+----------------+----------------+----------------+
|   6    7   39  |   1    5   49  |   2   34    8  |
|   2    5    4  |   3    7    8  |  16   69   19  |
|  18   18   39  |   2   49    6  |   5   347  347 |
+----------------+----------------+----------------+

Thus "1" can be eliminated from any cell which sees r2c1: r2c2<>1, r9c1<>1. Note that viewing the approach as a stem with petals allows multiple eliminations to be performed.

[Steve K]

Code: Select all

+----------------+----------------+----------------+
|   7  {49}*  6  |   5    1    3  |  48   489   2  |
| 14   1349   2  |   8    6  {49}*|   7    5   349 |
|   5  [349]# 8  |   7  [49]#  2  |  34    1    6  |
+----------------+----------------+----------------+
|   3    6    7  |   9    2    5  |  148  48   14  |
|   9    2    5  |   4    8    1  |  36   367  37  |
|  48   48    1  |   6    3    7  |   9    2    5  |
+----------------+----------------+----------------+
|   6    7   39  |   1    5   49  |   2   34    8  |
|   2    5    4  |   3    7    8  |  16   69   19  |
|  18   18   39  |   2   49    6  |   5   347  347 |
+----------------+----------------+----------------+

In a puzzle such as this one, there are always many sets of complex interactions that one can find. Chaining APE's is easily handled using AIC, and does not require limiting one to only XY chains.
As a point of interest, the immediate elimination that I see while looking at this puzzle is a Ywing style configuration. This is a very common type of very easy to find situation. The number of 49's in this puzzle practically beg the following:
r1c2=4 == r1c2=9 -- r3c2=9 == r3c5=9 -- r2c6=9 == r2c6=4 forbids r2c12=4. This of course solves the cell r2c1=1.

[ronk]

IIRC all APE exclusions may be duplicated with the ALS xz-rule. So it makes sense that some exclusions of a "chained APE" can be duplicated with the ALS xy-rule.

Code: Select all

  7  C49    6  |   5    1    3  |  48   489   2 
 1-4 13-49  2  |   8    6  A49  |   7    5   349
  5  C349   8  |   7  B49    2  | B34    1    6 
---------------+----------------+----------------
  3    6    7  |   9    2    5  |  148  48   14 
  9    2    5  |   4    8    1  |  36   367  37 
 48   48    1  |   6    3    7  |   9    2    5 
---------------+----------------+----------------
  6    7   39  |   1    5   49  |   2   34    8 
  2    5    4  |   3    7    8  |  16   69   19 
 18   18   39  |   2   49    6  |   5   347  347

ALS sets A = {r2c6} = {49}
         B = {r3c57} = {349}
         C = {r13c2} = {349}
         x = 9, y = 3 and z = 4, implies r2c12<>4

A corresponding nice loop expression is:

r2c12-4-r2c6-9-r3c5=9|3=r3c7-3-r3c2=3|4=r13c2-4-r2c12, implies r2c12<>4

[wapati]

Can you look at the markup and say that r2c2 cannot be either 1 or 4 because of a BUG Lite?

Code: Select all

+----------------+----------------+----------------+
|   7   49    6  |   5    1    3  |  48   489   2  |
|  *14*1349   2  |   8    6   49  |   7    5   349 |
|   5   349   8  |   7   49    2  |  34    1    6  |
+----------------+----------------+----------------+
|   3    6    7  |   9    2    5  |  148  48   14  |
|   9    2    5  |   4    8    1  |  36   367  37  |
| *48  *48    1  |   6    3    7  |   9    2    5  |
+----------------+----------------+----------------+
|   6    7   39  |   1    5   49  |   2   34    8  |
|   2    5    4  |   3    7    8  |  16   69   19  |
| *18  *18   39  |   2   49    6  |   5   347  347 |
+----------------+----------------+----------------+

[daj95376]

I'm sorry if this is off-topic, but what about the UR in [r14c78]? Either [r1c8]=9 and/or [r4c7]=1. Unfortunately, I need a contradiction chain/net in [c78] to show [r4c7]<>1 and force [r1c8]=9. Maybe someone else will have better luck.

Code: Select all

[r4c7]=1 => [r8c7]=6 =>                                     [r8c8]=9
                     => [r5c7]=3 => [r3c7]=4 => [r1c7]=8 => [r1c8]=9 contradiction!

[r4c7]<>1 => [r1c8]=9 => solution in singles
 *-----------------------------------------------------------*
 | 7     49    6     | 5     1     3     |*48   *489   2     |
 | 14    1349  2     | 8     6     49    | 7     5     349   |
 | 5     349   8     | 7     49    2     | 34    1     6     |
 |-------------------+-------------------+-------------------|
 | 3     6     7     | 9     2     5     |*148  *48    14    |
 | 9     2     5     | 4     8     1     | 36    367   37    |
 | 48    48    1     | 6     3     7     | 9     2     5     |
 |-------------------+-------------------+-------------------|
 | 6     7     39    | 1     5     49    | 2     34    8     |
 | 2     5     4     | 3     7     8     | 16    69    19    |
 | 18    18    39    | 2     49    6     | 5     347   347   |
 *-----------------------------------------------------------*


[udosuk]

Danny, I can see 3 eliminations from your UR:

Code: Select all

 *-----------------------------------------------------------*
 | 7     49    6     | 5     1     3     |-48   -489   2     |
 | 14    1349  2     | 8     6     49    | 7     5     349   |
 | 5     349   8     | 7     49    2     |#34    1     6     |
 |-------------------+-------------------+-------------------|
 | 3     6     7     | 9     2     5     |*148  -48    14    |
 | 9     2     5     | 4     8     1     | 36    367   37    |
 | 48    48    1     | 6     3     7     | 9     2     5     |
 |-------------------+-------------------+-------------------|
 | 6     7     39    | 1     5     49    | 2     34    8     |
 | 2     5     4     | 3     7     8     | 16    69    19    |
 | 18    18    39    | 2     49    6     | 5     347   347   |
 *-----------------------------------------------------------*

We have an X-wing of 8s in r14c78, and a grouped strong link of 4s:
[r13c4]=4=[r4c4]

r1c7<>4 & r4c8<>4 due to the UR (type 6) property.

r1c8=4 => r13c7<>4 => r4c7=4 => r1c7=r4c8=8 (X-wing) => Deadly pattern {48} in r14c78.

Hence r1c8<>4.

After these 3 eliminations the puzzle can be solved with singles...

Alternately, there is another advanced UR in r59c89:

Code: Select all

 *-----------------------------------------------------------*
 | 7     49    6     | 5     1     3     | 48    489   2     |
 | 14    1349  2     | 8     6     49    | 7     5     349   |
 | 5     349   8     | 7     49    2     | 34    1     6     |
 |-------------------+-------------------+-------------------|
 | 3     6     7     | 9     2     5     | 148   48    14    |
 | 9     2     5     | 4     8     1     | 36   -367  *37    |
 | 48    48    1     | 6     3     7     | 9     2     5     |
 |-------------------+-------------------+-------------------|
 | 6     7     39    | 1     5     49    | 2    #34    8     |
 | 2     5     4     | 3     7     8     | 16    69    19    |
 | 18    18    39    | 2     49    6     | 5    -347  -347   |
 *-----------------------------------------------------------*

We have an X-wing of 7s in r59c89, and 2 grouped strong links of 3s:
[r5c8]=3=[r79c8]=3=[r9c9]

r9c8<>3 due to the UR (type 6) property.

r5c8=3 => r79c8<>3 => r9c9=3 => r5c9=r9c8=7 (X-wing) => Deadly pattern {37} in r59c89.

r9c9=3 => r79c8<>3 => r5c8=3 => r5c9=r9c8=7 (X-wing) => Deadly pattern {37} in r59c89.

Hence r5c8<>3 & r9c9<>3.

After these 3 eliminations the puzzle can also be solved with singles...

BTW, wapati's BUG-lite/2x3 UR works well too...

[ronk]

As long as we're exploring alternative solutions, here is another using "mult-digit coloring."

Code: Select all

 .    .    .    | .    .    .    | .     .     .
 .    .    .    | .    .    .    | .     .     3A9A
 .    .    .    | .    .    .    | 3a    .     .
----------------+----------------+-------------------
 .    .    .    | .    .    .    | .     .     . 
 .    .    .    | .    .    .    | 3A6a  6A    . 
 .    .    .    | .    .    .    | .     .     .
----------------+----------------+-------------------
 .    .    .    | .    .    .    | .     .     .
 .    .    .    | .    .    .    | 1a6A  6a    1A9a
 .    .    .    | .    .    .    | .     .     .   

 3A!6a, 6A!1a, 1A!9a and 9A!3A, implies 3A is false

3A!6a means 3A true excludes 6a true. An equivalent nice loop would be:

r2c9-3-r3c7=3=r5c7=6=r5c8-6-r8c8=6=r8c7=1=r8c9=9=r2c9, implies r2c9<>3

The puzzle is then solved with cascading singles.