ALS-xz with set overlap

Advanced methods and approaches for solving Sudoku puzzles

ALS-xz with set overlap

Postby ronk » Sun Sep 05, 2010 2:37 pm

Without having really thought about it, I had assumed that useful 2-set ALS chains ... aka, the ALS xz-rule and ALS-xz ... with set overlap didn't exist, but here are two examples that seem to prove otherwise.

Code: Select all
 
top1465 #488
9..51...35..3..2....8..2...7.....5.8.96...31....8...9.3.5.7.6.....1.........3..85
 
After SSTS:
 9     2467  247   |  5     1     46    | 8     467   3
 5     1467  147   |  3     4689  4689  | 2     467   1469
 146   3     8     |  7     469   2     | 149   5     1469
-------------------+--------------------+------------------
 7     124   1234  | B2469  469-2 13    | 5     246   8
 8     9     6     |BA24    5     7     | 3     1     24
 124   5     1234  |  8    A246   13    | 47    9     2467
-------------------+--------------------+------------------
 3     148   5     | B49    7     89    | 6     24    1249
 246   24678 2479  |  1     24689 5     | 479   3     479
 1246  12467 12479 |  2469  3     469   | 1479  8     5
 
Sets: A = {r5c4, r6c5} = {246};  B = {r457c4} = {2469}; x,z = 6,2
Elim: r4c5<>2
 
NL: r4c5 -2- als:[r5c4,r6c5] -6- als:r457c4 -2- r4c5 ==> r4c5<>2
 
Note that the overlap cell r5c4 does not contain the restricted-common-candidate (RCC) <6>

Code: Select all
 
 9     2467  247   |  5     1      46    | 8     467   3
 5     1467  147   |  3     4689   4689  | 2     467   1469
 146   3     8     |  7     469    2     | 149   5     1469
-------------------+---------------------+------------------
 7     124   1234  |  2469  2469   13    | 5     246   8
 8     9     6     | B24    5      7     | 3     1     24
 124   5     1234  |  8     246    13    | 47    9     2467
-------------------+---------------------+------------------
 3     148   5     |BA49    7      48-9  | 6     24    1249
 246   24678 2479  |  1     2468-9 5     | 479   3     479
 1246  12467 12479 | B2469  3     A469   | 1479  8     5
 
Sets: A = {r7c4,r9c6} = {469}; B = {r579c4} = {2469}; x,z = 6,9
Elim: r7c6<>9, r8c5<>9
 
NL: [r7c6,r8c5] -9- als:[r7c4,r9c6] -6- als:r579c4 -9- [r7c6,r8c5] ==> r7c6<>9, r8c5<>9
 
As above, note the overlap cell r7c4 does not contain the RCC

1) [edit: Excluding notational preferences, are] there simpler ways to obtain or view these eliminations?

2) The above structures have box and line (row, column) base sets that intersect. Are there examples from real puzzles with an intersecting row and column as well?

[edit: As noted by Luke451 & aran, r8c5<>9 added to 2nd example]
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: ALS-xz with set overlap

Postby denis_berthier » Sun Sep 05, 2010 2:37 pm

ronk wrote:1) Are there simpler ways to obtain or view these eliminations?


ronk wrote:
Code: Select all
 
top1465 #488
9..51...35..3..2....8..2...7.....5.8.96...31....8...9.3.5.7.6.....1.........3..85
 
After SSTS:
 9     2467  247   |  5     1     46    | 8     467   3
 5     1467  147   |  3     4689  4689  | 2     467   1469
 146   3     8     |  7     469   2     | 149   5     1469
-------------------+--------------------+------------------
 7     124   1234  | B2469  469-2 13    | 5     246   8
 8     9     6     |BA24    5     7     | 3     1     24
 124   5     1234  |  8    A246   13    | 47    9     2467
-------------------+--------------------+------------------
 3     148   5     | B49    7     89    | 6     24    1249
 246   24678 2479  |  1     24689 5     | 479   3     479
 1246  12467 12479 |  2469  3     469   | 1479  8     5
 
Sets: A = {r5c4, r6c5} = {246};  B = {r457c4} = {2469}; x,z = 6,2
Elim: r4c5<>2
 
NL: r4c5 -2- als:[r5c4,r6c5] -6- als:r457c4 -2- r4c5 ==> r4c5<>2


nrc-chain[3] n2{r8c5 r9c4} - {n2 n4}r5c4 - {n4 n9}r7c4 ==> r8c5 <> 9
nrc-chain[3] n2{r8c5 r9c4} - n6{r9c4 r4c4} - n9{r4c4 r4c5} ==> r4c5 <> 2


ronk wrote:
Code: Select all
 
 9     2467  247   |  5     1     46    | 8     467   3
 5     1467  147   |  3     4689  4689  | 2     467   1469
 146   3     8     |  7     469   2     | 149   5     1469
-------------------+--------------------+------------------
 7     124   1234  |  2469  2469  13    | 5     246   8
 8     9     6     | B24    5     7     | 3     1     24
 124   5     1234  |  8     246   13    | 47    9     2467
-------------------+--------------------+------------------
 3     148   5     |BA49    7     48-9  | 6     24    1249
 246   24678 2479  |  1     24689 5     | 479   3     479
 1246  12467 12479 | B2469  3    A469   | 1479  8     5
 
Sets: A = {r7c4,r9c6} = {469}; B = {r579c4} = {2469}; x,z = 6,9
Elim: r7c6<>9
 
NL: r7c6 -9- als:[r7c4,r9c6] -6- als:r579c4 -9- r7c6 ==> r7c6<>9

xyzt-chain[4] {n9 n4}r7c4 - {n4 n2}r5c4 - {n2 n6 n4#1 n9*}r9c4 - {n6 n9 n4#1}r9c6 ==> r7c6 <> 9

Edited after Ronk's edition to add the missing elim
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: ALS-xz with set overlap

Postby Luke » Sun Sep 05, 2010 2:37 pm

I've wondered if this could be done. Apparently so, if the RCC isn't in the overlapping cell.

In example 2, also r8c5<>9.
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Re: ALS-xz with set overlap

Postby aran » Sun Sep 05, 2010 2:38 pm

ronk wrote:
Code: Select all
 
top1465 #488
9..51...35..3..2....8..2...7.....5.8.96...31....8...9.3.5.7.6.....1.........3..85
After SSTS:
 9     2467  247   |  5     1     46    | 8     467   3
 5     1467  147   |  3     4689  4689  | 2     467   1469
 146   3     8     |  7     469   2     | 149   5     1469
-------------------+--------------------+------------------
 7     124   1234  | B2469  469-2 13    | 5     246   8
 8     9     6     |BA24    5     7     | 3     1     24
 124   5     1234  |  8    A246   13    | 47    9     2467
-------------------+--------------------+------------------
 3     148   5     | B49    7     89    | 6     24    1249
 246   24678 2479  |  1     24689 5     | 479   3     479
 1246  12467 12479 |  2469  3     469   | 1479  8     5
 
Sets: A = {r5c4, r6c5} = {246};  B = {r457c4} = {2469}; x,z = 6,2
Elim: r4c5<>2


Code: Select all
 
 9     2467  247   |  5     1     46    | 8     467   3
 5     1467  147   |  3     4689  4689  | 2     467   1469
 146   3     8     |  7     469   2     | 149   5     1469
-------------------+--------------------+------------------
 7     124   1234  |  2469  2469  13    | 5     246   8
 8     9     6     | B24    5     7     | 3     1     24
 124   5     1234  |  8     246   13    | 47    9     2467
-------------------+--------------------+------------------
 3     148   5     |BA49    7     48-9  | 6     24    1249
 246   24678 2479  |  1     24689 5     | 479   3     479
 1246  12467 12479 | B2469  3    A469   | 1479  8     5
 
Sets: A = {r7c4,r9c6} = {469}; B = {r579c4} = {2469}; x,z = 6,9
Elim: r7c6<>9

Are there simpler ways to obtain or view these eliminations?

Ronk
Those examples are interesting from a transcriptional point of view.
As follows :
First example :
24(r5c4+r6c5)=6r6c5-6r4c4=249r457c4
at that point the first reflex might be to think that this triple extending into b6 cannot influence r4c5, but the "2" candidate is uniquely in b5 and hence <2>r4c5
So what is the best way to communicate that in chain format ?
Possibly
24(r5c4+r6c5)=6r6c5-6r4c4=triple{249}(49c4 2b5) => <2>r4c5
Second example :
49(r7c4+r9c6)=6r9c6-6r9c4=triple{249}(24c4 9b6) => <9>r7c6 and <9>r8c5

With recourse to a net one could obtain all eliminations :
249r4579c4=
A.6r4c4 etc
B.6r9c4 etc
But that would be a little ugly in the writing...
aran
 
Posts: 334
Joined: 02 March 2007

Re: ALS-xz with set overlap

Postby Allan Barker » Sun Sep 05, 2010 2:38 pm

Ronk wrote:Without having really thought about it, I had assumed that useful 2-set ALS chains ... aka, the ALS xz-rule and ALS-xz ... with set overlap didn't exist, but here are two examples that seem to prove otherwise.

Easy is of course in the eye of the beholder, but I find it easy to understand why these work by the cover sets.

With 4 cells and 5 covers, the logic would normally require a candidate to sit in (or see) 2 covers to be eliminated. In both of these cases, cover sets overlap to form a triplet, which results in a rank 0 set that can eliminate candidates by itself.


In the first case, the overlap is at (4)r57c4, rank 0 cover is (2b6) => r4c5<>2
In the second case, the overlap is at (4)r79c4, rank 0 cover is (9b8) => r7c6<>9, r8c5<>9

Left first, example. Right, second example Note: Rank 0 sets shaded black.

Image.............Image

Ronk wrote:2) The above structures have box and line (row, column) base sets that intersect. Are there examples from real puzzles with an intersecting row and column as well?

Does this mean the cover sets, or other logic with link box bases sets as in hidden AHS etc?
.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Re: ALS-xz with set overlap

Postby ronk » Sun Sep 05, 2010 2:38 pm

Allan Barker wrote:In both of these cases, cover sets overlap to form a triplet, which results in a rank 0 set that can eliminate candidates by itself.

In the first case, the overlap is at (4)r[color=red;]45[/color]c4, rank 0 cover is (2b6) => r4c5<>2

...

Image

I interpret that to mean there are two linkset triples -- r4c4 and r5c4 -- but it's the one at r5c4 that's important, right?

Allan Barker wrote:
Ronk wrote:2) The above structures have box and line (row, column) base sets that intersect. Are there examples from real puzzles with an intersecting row and column as well?

Does this mean the cover sets, or other logic with link box bases sets as in hidden AHS etc?.

Not sure what you mean, but I'm thinking of something like ...
Code: Select all
 
+---------+---------------------+------------+
| .  .  . | .   (3456)   .      | .  .     . |
| .  .  . | .   (3456)   .      | .  .     . |
| .  .  . | .   (3456)   .      | .  .     . |
+---------+---------------------+------------+
| .  .  . | -2  -2       -2     | .  .     . |
| .  .  . | -2  (234)    (1234) | .  (34)  . |
| .  .  . | -2  (123456) -2     | .  .     . |
+---------+---------------------+------------+
| .  .  . | .   .        .      | .  .     . |
| .  .  . | .   .        .      | .  .     . |
| .  .  . | .   .        .      | .  .     . |
+---------+---------------------+------------+

Not all candidates need exist, but would such a structure survive the use of simpler techniques? As of now, I don't know.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: ALS-xz with set overlap

Postby daj95376 » Sun Sep 05, 2010 2:39 pm

Forcing chain on [r7c4]={4,9}

Code: Select all
 [r7c4]=4 [r5c4]=2 [r46c5]<>2 [r8c5]=2 [r7c6]=8 => [r4c5]<>2, [r7c6],[r8c5]<>9
 [r7c4]=9 [r7c6],[r8c5],[r4c4]<>9      [r4c5]=9 => [r4c5]<>2, [r7c6],[r8c5]<>9
 +-----------------------------------------------------------------------+
 |  9      2467   247    |  5      1      46     |  8      467    3      |
 |  5      1467   147    |  3      4689   4689   |  2      467    1469   |
 |  146    3      8      |  7      469    2      |  149    5      1469   |
 |-----------------------+-----------------------+-----------------------|
 |  7      124    1234   |  2469   469-2  13     |  5      246    8      |
 |  8      9      6      |  24     5      7      |  3      1      24     |
 |  124    5      1234   |  8      246    13     |  47     9      2467   |
 |-----------------------+-----------------------+-----------------------|
 |  3      148    5      |  49     7      48-9   |  6      24     1249   |
 |  246    24678  2479   |  1      2468-9 5      |  479    3      479    |
 |  1246   12467  12479  |  2469   3      469    |  1479   8      5      |
 +-----------------------------------------------------------------------+
 # 106 eliminations remain


Yes, I know it's not what you want. Too bad it covers all eliminations.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: ALS-xz with set overlap

Postby David P Bird » Sun Sep 05, 2010 2:39 pm

Code: Select all
 9     2467  247   |  5     1     46    | 8     467   3
 5     1467  147   |  3     4689  4689  | 2     467   1469
 146   3     8     |  7     469   2     | 149   5     1469
-------------------+--------------------+------------------ 
 7     124   1234  |  2469  2469  13    | 5     246   8
 8     9     6     |  24    5     7     | 3     1     24
 124   5     1234  |  8     246   13    | 47    9     2467
-------------------+--------------------+------------------ 
 3     148   5     |  49    7     489   | 6     24    1249
 246   24678 2479  |  1     24689 5     | 479   3     479
 1246  12467 12479 |  2469  3     469   | 1479  8     5

Ron, this AIC seems the most straightforward way to JUSTIFY your exclusions if not to FIND them:

(8)r7c6[a] = (8-2)r8c5[b] = (2)r9c4 - (2=4)r5c4 - (4=9)r7c4[c] - (9)r4c4 = (9)r4c5[d] - (9)r23c5 = (9)r2c6[e]
[ac] => r7c6 <> 9, [bc] => r8c5 <> 9, [bd] => r4c5 <> 2, [ae] => r2c6 <> 8

Like your ALSs, this relies heavily on the bivalues in r57c4, the overlaps, which can't contain 6.

A long time ago I dismissed navigating through ALSs composed of all the unsolved cells in a house less one as I thought a link through the missing cell would always achieve the same effect. Your examples here mean I'm going to have to re-evaluate that!
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Re: ALS-xz with set overlap

Postby DonM » Sun Sep 05, 2010 2:39 pm

Image

I run into 2-set ALS Chains with overlap occasionally. Here's a more recent one from UK Extreme #141, but with the added wrinkle of an rc thru a conjugate link (overlap cell: r8c6):
Green set (23457) r8c456/r9c4 -> rc=2 via 2-conjugate r2c46 -> Blue set (1247) r158c6 => r9c6<>7
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Re: ALS-xz with set overlap

Postby David P Bird » Sun Sep 05, 2010 2:40 pm

ronk wrote:but I'm thinking of something like ...
Code: Select all
 
 
+---------+---------------------+------------+ 
| .  .  . | .   (3456)   .      | .  .     . | 
| .  .  . | .   (3456)   .      | .  .     . | 
| .  .  . | .   (3456)   .      | .  .     . | 
+---------+---------------------+------------+ 
| .  .  . | -2  -2       -2     | .  .     . | 
| .  .  . | -2  (234)    (1234) | .  (34)  . | 
| .  .  . | -2  (123456) -2     | .  .     . | 
+---------+---------------------+------------+ 
| .  .  . | .   .        .      | .  .     . | 
| .  .  . | .   .        .      | .  .     . | 
| .  .  . | .   .        .      | .  .     . | 
+---------+---------------------+------------+

Not all candidates need exist, but would such a structure survive the use of simpler techniques? As of now, I don't know.

As I see it, to support the weak link (RCC)row - (RCC)column, the RCC must be confined to the box in both the row and the column ALSs and be absent from their intersection cell.

We then can extend this to the locked sets that would be created in the absence of the RCC in the row and column:
(a)node - (abcd)LS:row = (RCC)row - (RCC)column = (efg)LS:column - (g)node

When the end nodes are identical we get an instant exclusion, otherwise the AIC can be propagated further.

For exclusions, we need the instances of the candidate in the ALSs as well as the RCC to be confined to the box, when the victims will all be in the box too.

I think that only if the pattern is partially populated will it be possible to express these exclusions without using ALS logic. However this pattern will be rare and will generally only be available after several cells have been resolved in the intersecting row and column when it's more than likely it won't be fully populated. It should occur far more frequently as a means of propagating AICs when there is much greater freedom regarding the continuation nodes.

[edit] Looking further I realised that the RCC can exist outside the box in the row or the column in a cell which isn't part of the ALS.

It's also not necessary to have one row and one column, parallel rows or columns intersecting the same box will do.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Re: ALS-xz with set overlap

Postby Allan Barker » Sun Sep 05, 2010 2:40 pm

RonK wrote:Not all candidates need exist, but would such a structure survive the use of simpler techniques? As of now, I don't know.

Ronk Nice work, I assume your gray matter must be throbbing.

I don't see any simpler techniques that would necessarily cause eliminations.

However, there is one exception that leads to a restriction.

As David pointed out, the RCC, here digit 1, cannot be outside the box , or else it's not an RCC. However, it can also not appear elsewhere in the box (edit: with the digit 2). If it does, then the pattern will form a Sue de Coq, which will remove all the 2s, among other things.

Code: Select all
Sue de Coq (1234){r6c4,r5c568}
+---------------+------------------------+----------------+
| .    .    .   | .      3456     .      | .    .     .   |
| .    .    .   | .      3456     .      | .    .     .   |
| .    .    .   | .      3456     .      | .    .     .   |
+---------------+------------------------+----------------+
| .    .    .   | -12    -12      -12    | .    .     .   |
| -34  -34  -34 | -1234  (234)    (1234) | -34  (34)  -34 |
| .    .    .   | (12)   3456-12  -12    | .    .     .   |
+---------------+------------------------+----------------+
| .    .    .   | .      .        .      | .    .     .   |
| .    .    .   | .      .        .      | .    .     .   |
| .    .    .   | .      .        .      | .    .     .   |
+---------------+------------------------+----------------+


Although I doubt any one would look for one, there is also a complementary hidden form that has base set overlap where the ALS analogue has cover set overlap. I don't think I have seen this kind of analog relationship before.

Left, as overlap ALS 'X' marks the overlap positions.
Right, as AHS .
ImageImage
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Re: ALS-xz with set overlap

Postby aran » Sun Sep 05, 2010 2:40 pm

Allan Barker wrote:
Code: Select all
Sue de Coq (1234){r6c4,r5c568}
+---------------+------------------------+----------------+
| .    .    .   | .      3456     .      | .    .     .   |
| .    .    .   | .      3456     .      | .    .     .   |
| .    .    .   | .      3456     .      | .    .     .   |
+---------------+------------------------+----------------+
| .    .    .   | -12    -12      -12    | .    .     .   |
| -34  -34  -34 | -1234  (234)    (1234) | -34  (34)  -34 |
| .    .    .   | (12)   3456-12  -12    | .    .     .   |
+---------------+------------------------+----------------+
| .    .    .   | .      .        .      | .    .     .   |
| .    .    .   | .      .        .      | .    .     .   |
| .    .    .   | .      .        .      | .    .     .   |
+---------------+------------------------+----------------+


Allan
Just looking at the above as posted :
base 8 cells ie original 7+4n6(ie r6c4)
cover 8 sets : 6c5 5c5 2b5 1b5 3c5+3r5 4c5+4r5
=>rank 0.
Now there are two potential overlaps (at r5c5) on 3 and 4.
Either true=>rank -1. Impossible.
Hence r5c5=2.
Agreed ?
aran
 
Posts: 334
Joined: 02 March 2007

Re: ALS-xz with set overlap

Postby Allan Barker » Sun Sep 05, 2010 2:40 pm

Allan
Just looking at the above as posted :
base 8 cells ie original 7+4n6(ie r6c4)
cover 8 sets : 6c5 5c5 2b5 1b5 3c5+3r5 4c5+4r5
=>rank 0.
Now there are two potential overlaps (at r5c5) on 3 and 4.
Either true=>rank -1. Impossible.
Hence r5c5=2.
Agreed ?

Agreed, and well put. The additional truth in r6c4 forces the entire logic to rank 0, not only the Sue de Coq. With 8 truths for 8 covers, no truth can occupy an overlap (i.e., 2 covers) because there would be no way to place the other 7.

Thus it would seem rank -1 means cannibal. :idea:
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Re: ALS-xz with set overlap

Postby ronk » Sun Sep 05, 2010 2:41 pm

David P Bird wrote:We then can extend this to the locked sets that would be created in the absence of the RCC in the row and column:
(a)node - (abcd)LS:row = (RCC)row - (RCC)column = (efg)LS:column - (g)node

When the end nodes are identical we get an instant exclusion ...

Which leads me to this ...
Code: Select all
 
+---------+-----------------+-------------+
| .  .  . | .  .      .     | .  .      . |
| .  .  . | .  (234)  .     | .  -2     . |
| .  .  . | .  .      .     | .  .      . |
+---------+-----------------+-------------+
| .  .  . | .  .      .     | .  .      . |
| .  .  . | .  (34)   (134) | .  (234)  . |
| .  .  . | .  (134)  .     | .  .      . |
+---------+-----------------+-------------+
| .  .  . | .  .      .     | .  .      . |
| .  .  . | .  .      .     | .  .      . |
| .  .  . | .  .      .     | .  .      . |
+---------+-----------------+-------------+

The sets in r5 and c5 intersect and overlap at r5c5. While the RCC (the 'x') of the ALs-xz must reside in b5, but not in the overlap, the same is not true for the 'z'. The same result is possible with one or both sets larger than shown above.

David P Bird wrote:It's also not necessary to have one row and one column, parallel rows or columns intersecting the same box will do.

If an ALS-xz is to have set overlap (this thread's topic), the two base sets must be in units (sectors) that intersect.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: ALS-xz with set overlap

Postby David P Bird » Sun Sep 05, 2010 2:41 pm

Sorry Ronk, I was only trying to answer the questions you posed in your opening post and took my eye off the ball for a second.

Considering the tone of your reply, I'm sorry I bothered.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Next

Return to Advanced solving techniques