Introducing ARCS: Almost Row-Column Subsets

Advanced methods and approaches for solving Sudoku puzzles

Postby Mike Barker » Mon Aug 28, 2006 3:39 am

I was thinking that the primary difference between the two approaches was a question of focus. In the one, the focus is on a nice loop and on the second on links between a cell and the fish (I guess since it distroys fish you could think of it as a Kraken cell). The examples so far have tended to focus on ALS and bivalues. As has been pointed out previously, eliminations can occur via strong links, grouped strong links, direct links, as well as ALS and bivalues. For example a strong link and a "direct link" can be used to reduce the dimension of the covering set:
Code: Select all
.  . . | . . . | . .  .
.  3 . | . 3 . | . .  .
.  | . | . | . | . .  .
---|---+---|---+-------
.  | . | . | . | . .  .
.  3 . | . 3 . | . . -3
.  | . | . . . | . .  .
---|---+-------+-------
.  | 3================3
.  3 . | . . . | . .  .
.  . . | . . . | . .  .

Elimination is also possible using a grouped strong link and a bivalue cell:
Code: Select all
.  . . | . . . | . .  .
.  3 . | . 3 . | . .  .
.  | . | . | . | . .  .
---|---+---|---+-------
.  | . | . | . | . .  .
.  3 . | . 3 . | . . 13
.  | . | . . . | . .  .
---|---+-------+-------
.  | . | . . . | . . -1
. 13=============1 1  .
.  . . | . . . | . .  .

or by an ALS and a bivalue cell:
Code: Select all
.  . . | . . . | . .  .
.  3 . | . 3 . | . .  .
.  | . | . | . | . .  .
---|---+---|---+-------
.  | . | . | . | . .  .
.  3 . | . 3 . | . . 13
.  | . | . . . | . .  .
---|---+-------+-------
.  | . | . . . | . . -1
.  3 . | . . . |34 . 14
.  . . | . . . | . .  .

or many other combinations. Here's an example from Top1465 #281 using a grouped strong link and an ALS where r8c3<>3 and the links are r45c3-9-ALS:r1237c3, GSL:r5c2=3=r78c2:
Code: Select all
+-------------------+---------------------+-----------------------+
|   3478    6  @347 |      5    28      1 |     478      9     24 |
|      1    2   @78 |     46     9     46 |      78      5      3 |
|      9    5   @48 |      3    28      7 |    1468  12468   1246 |
+-------------------+---------------------+-----------------------+
|   2356    4  *259 |      8   136   *239 |      16      7    126 |
|    267 #*39 *2379 |  *1249  1346  *2349 |       5   1246      8 |
|     26    8     1 |      7    46      5 |     469      3   2469 |
+-------------------+---------------------+-----------------------+
|    348 #139 @3489 |   1469     5   3469 |       2   1468      7 |
|  23458 #139 -2358 |  12469     7  23469 |  134689   1468  14569 |
|   2345    7     6 |   1249   134      8 |    1349     14   1459 |
+-------------------+---------------------+-----------------------+

My solver currently can only handle single links between the fish and the cell where the elimination occurs, but this is not necessary. They can be formed from "nice chains" as well. Also more than two links can be used, for example, from Top1465 #287, r3c1<>3 where the links are r4c3-9-ALS:r23c3|r2c2|r1c1, r5c1-9-ALS:r19c1, and SL:r5c2=3=r5c1:
Code: Select all
+---------------------+-------------------+---------------------+
|   #13      2      7 |    135    8     4 |      6    39    359 |
|     8   @136   @346 |  12357    9  1356 |  23457   235  23457 |
| -3469      5  @3469 |    237  267    36 |  23478   238      1 |
+---------------------+-------------------+---------------------+
|     5      4    *89 |    *19  267  *189 |    237   236    237 |
|$*3679 $*3679      1 |  *2479  267  *569 |   2457   256      8 |
|     2    678     68 |    457    3   568 |      9     1    457 |
+---------------------+-------------------+---------------------+
|    34    138   3458 |      6  145    39 |  12358     7   2359 |
|   467  13678  34568 |     39   14     2 |   1358  3589    359 |
|  #139     19      2 |      8   15     7 |    135     4      6 |
+---------------------+-------------------+---------------------+

Anne and Jeff should also be included in the list of those who have contributed.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Myth Jellies » Tue Aug 29, 2006 5:24 am

Ruud, look at the cool thing you can do with the 5's in your Aug 28, 2006 nightmare!
Code: Select all
 *-----------*
 |8..|...|..4|
 |.6.|1.8|.3.|
 |..7|.3.|8..|
 |---+---+---|
 |2..|6.9|..3|
 |.9.|2.7|.1.|
 |...|...|...|
 |---+---+---|
 |7.9|...|4.8|
 |.8.|...|.2.|
 |63.|...|.97|
 *-----------*
 *--------------------------------------------------------------------*
 | 8      125    3      | 59     256    256    | 12569  7      4      |
 | 459    6      245    | 1      7      8      | 259    3      259    |
 | 159    125    7      | 459    3      2456   | 8      56     12569  |
 |----------------------+----------------------+----------------------|
 | 2      4      15     | 6      15     9      | 7      8      3      |
 | 3      9      8      | 2      4      7      | 56     1      56     |
 | 15     7      6      | 358    158    135    | 29     4      29     |
 |----------------------+----------------------+----------------------|
 | 7      125    9      | 35     1256   12356  | 4      56     8      |
 | 145    8      145    | 7      9      1456   | 3      2      156    |
 | 6      3      1245   | 458    1258   1245   | 15     9      7      |
 *--------------------------------------------------------------------*

Basic methods up to coloring get you to here. I know there is a good simple color deduction on the sixes, but ignore that and focus on the fives. Note that the cells colored 'X' below form an r37c28 x-wing with the starred cells. A little grouped coloring and we have...
Code: Select all
 *--------------------------------------------------------------------*
 | 8     x125    3      |b59    b256   b256    | 12569  7      4      |
 | 459    6      245    | 1      7      8      | 259    3      259    |
 |-159   X125    7      |B459    3     B2456   | 8    *a56    -12569  |
 |----------------------+----------------------+----------------------|
 | 2      4      15     | 6      15     9      | 7      8      3      |
 | 3      9      8      | 2      4      7      | 56     1      56     |
 | 15     7      6      | 358    158    135    | 29     4      29     |
 |----------------------+----------------------+----------------------|
 | 7     X125    9      |-35    -1256  -12356  | 4    *A56     8      |
 | 145    8      145    | 7      9      1456   | 3      2      156    |
 | 6      3      1245   | 458    1258   1245   | 15     9      7      |
 *--------------------------------------------------------------------*
 X=x-b=B => r3c19 <> 5
 and
 X=x-b=B-a=A => r7c456 <> 5

The first multicoloring equation shows that either the X-wing is true or r3c46 (color B) contains a five. In either case, all other fives in r3 can be removed. The second multicolor equation shows that either the X-wing or color 'A' is true. Thus we can get rid of all X-wing elimination candidates that also see r7c8. Now we can perform some more basics and extend the grouped coloring on fives a little further...
Code: Select all
 *--------------------------------------------------------------------*
 | 8     A125    3      | 59     256    256    |-12569  7      4      |
 |a459    6     a245    | 1      7      8      |A259*   3     A259*   |
 | 19    A125    7      | 459    3      2456   | 8     a56     1269   |
 |----------------------+----------------------+----------------------|
 | 2      4      15     | 6      15     9      | 7      8      3      |
 | 3      9      8      | 2      4      7      | 56     1      56     |
 | 15     7      6      | 58     158    3      | 29*    4      29*    |
 |----------------------+----------------------+----------------------|
 | 7     a125    9      | 3      26     126    | 4     A56     8      |
 | 145    8      145    | 7      9      1456   | 3      2      156    |
 | 6      3      1245   | 458    258    1245   | 15     9      7      |
 *--------------------------------------------------------------------*
r1c7 sees all the 'a's and 'A's in box 3, and thus cannot be a 5 as well. Not really a required step, but a nice illustration of grouped coloring nonetheless. The simple UR+2 in r26c79 tells you color 5A is true and finishes things off quite nicely.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Ruud » Tue Aug 29, 2006 8:48 am

Thanks for the examples, everyone!

I'm impressed by the excellent posts by Havard and Mike. They clearly show how these "almost fish" patterns can be integrated in existing strategies.

MJ, the first GC+ARCS step clearly shows how you can expand a simple finned X-Wing (which would only eliminate r3c1) into a structure that eliminates 5 candidates.

When I use David's weak colouring, starting with the conjugate pair in column 7, there is one additional candidate in r1c7 that can be eliminated.

Here is the colored grid:

Image

Since all other eliminations are the same, I wonder if this extra elimination would be possible with the GC+ARCS strategy.

Ruud
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby Myth Jellies » Tue Aug 29, 2006 8:42 pm

Code: Select all
  *--------------------------------------------------------------------*
 | 8     B125    3      | 59     256    256    |-12569  7      4      |
 |c459    6     c245    | 1      7      8      |C259    3     C259    |
 |-159   B125    7      | 459    3      2456   | 8     a56    -12569  |
 |----------------------+----------------------+----------------------|
 | 2      4      15     | 6      15     9      | 7      8      3      |
 | 3      9      8      | 2      4      7      | 56     1      56     |
 | 15     7      6      | 358    158    135    | 29     4      29     |
 |----------------------+----------------------+----------------------|
 | 7     b125    9      |-35    -1256  -12356  | 4     A56     8      |
 | 145    8      145    | 7      9      1456   | 3      2      156    |
 | 6      3      1245   | 458    1258   1245   | 15     9      7      |
 *--------------------------------------------------------------------*
 a = A - b = B - c = C - a...

I don't really want to get into weak coloring, but you can eliminate all the candidates using a grouped multicolor/x-cycle/AIC (pick your favorite) continuous loop, which basically allows you to treat each link as a conjugate link.

But I don't think it matters too much if the ARCS/almost fish coloring catches all of these, and here is why.

I originally looked at the mess of candidate fives and pretty much bailed out on it. The only reason I gave it a second glance is because I noted the almost x-wing in columns 2 & 8. Once you see that, the potential for reductions just pops out at you. The grouped continuous loop is fairly obvious once you know it is there, but it buried particularly well in the morass of potential candidates and can be easily missed otherwise. So I'd submit that one of the primary features of ARCS is its ability to focus your search for reductions.

...Oh, alright, here is a shady little ARCS reduction for r1c7:)

Code: Select all
  *---------------------------------------------------------------------*
 | 8     b125    3      | 59     256    256    | -12569  7      4      |
 |x459    6     x245    | 1      7      8      | X259    3     X259    |
 | 159   b125    7      | 459    3      2456   |  8      56    -12569  |
 |----------------------+----------------------+-----------------------|
 | 2      4      15     | 6      15     9      |  7      8      3      |
 | 3      9      8      | 2      4      7      |*a56     1    *A56     |
 | 15     7      6      | 358    158    135    |  29     4      29     |
 |----------------------+----------------------+-----------------------|
 | 7     B125    9      | 35     1256   12356  |  4     c56     8      |
 | 145    8      145    | 7      9      1456   |  3      2     C156    |
 | 6      3      1245   | 458    1258   1245   | C15     9      7      |
 *---------------------------------------------------------------------*

Color groups X & C threaten an x-wing/box-box with the starred cells

X = x - b = B - c = C => you can eliminate the remaining 5s in columns 7 & 9.

Just for grins and giggles, here is an ARCS which eliminates a 1 in the same grid...
Code: Select all
  *---------------------------------------------------------------------*
 | 8     X125    3      | 59     256    256    | A12569  7      4      |
 | 459    6      245    | 1      7      8      |  259    3      259    |
 |x159   X125    7      | 459    3      2456   |  8      56    a12569  |
 |----------------------+----------------------+-----------------------|
 | 2      4      15     | 6      15     9      |  7      8      3      |
 | 3      9      8      | 2      4      7      |  56     1      56     |
 | 15     7      6      | 358    158    135    |  29     4      29     |
 |----------------------+----------------------+-----------------------|
 | 7     x125    9      | 35     1256   12356  |  4      56     8      |
 |X145    8     X145    | 7      9     -1456   |  3      2    *A156    |
 | 6      3     X1245   | 458    1258   1245   |*a15     9      7      |
 *---------------------------------------------------------------------*

Note that color group X threatens a box/box interaction using the starred cells in rows 8 & 9.
X = x - a = A => r8c6 <> 1
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Myth Jellies » Fri Sep 15, 2006 8:27 am

Similar to Havard, I see these rules...

A potential "fish" pattern is strongly linked to the cell or group of cells in one dimension (rows, columns) that prevent that pattern from manifesting. In other words, either the fish pattern is true, or at least one of the candidates preventing the fish pattern is true.

The potential "fish" pattern is weakly linked to any candidate that would be attacked and removed if the "fish" pattern was true.


One can easily make use of these links in a nice loop or AIC.

Personally, I like seeing the entire fish pattern mapped out and separated from the cells which prevent it. This covering stuff is a bit much for me at times.

Code: Select all
+--------------------+-------------------+---------------------+
|  3589  X589  35689 | X2579  2379     1 |     X4  3689   2358 |
|     7  X589  34589 |  X259     6   345 | X23589     1   2358 |
|     1     2  34569 |     8   359   345 |      7   369     35 |
+--------------------+-------------------+---------------------+
|     4    X3   B589 | X1569   B59     2 |  X1568   -78   1578 |
|     6    17      2 |   157     8   357 |    135     4      9 |
|   589    17    589 |     4  3579  3567 |  13568     2   1358 |
+--------------------+-------------------+---------------------+
|   238    68      1 |   267   247     9 |    238     5  23478 |
|  2359     4    359 |   257     1   578 |  x2389  3789      6 |
|  2589 x5689      7 |     3   245  4568 |    128   A89   1248 |
+--------------------+-------------------+---------------------+

X marks the potential swordfish (9)
x marks the candidates preventing the swordfish
A sees both x's
8[r9c8]=9[r9c8]-9[r8c7|r9c2]=9[r124c247]-9[r4c35]=(5&8)[r4c35] => r4c8 <> 8

This one here had me puzzled, as it was described as an almost X-wing...

Code: Select all
+--------------------+-------------------+---------------------+
|  3589   589  35689 |  2579  2379     1 |      4  3689  D2358 |
|     7   589  34589 |   259     6   345 | -23589     1  D2358 |
|     1     2  34569 |     8  3459   345 |      7   369    D35 |
+--------------------+-------------------+---------------------+
|     4     3    589 |  1569    59     2 |   1568    78   1578 |
|     6    17      2 |   157     8  *357 |   B135     4      9 |
|   589    17    589 |     4 *3579 *3567 | B13568     2  C1358 |
+--------------------+-------------------+---------------------+
|   238    68      1 |   267   247     9 |   A238     5 -23478 |
|  2359     4    359 |   257     1   578 |  A2389  3789      6 |
|  2589  5689      7 |     3   245  4568 |    128   A89  -1248 |
+--------------------+-------------------+---------------------+

(2&8&9)[A]=3[A]-3[B]=3[C]-3[D]=(5&8&2)[D] => r2c7 <> 2, r79c9 <> 2 or 8

...In this case, the program appeared to see the shape combining the B and * sets which attacks column 7 and is prevented by C (2 rows covered by a box and column, instead of an X-wing). I just saw two ALSs connected by a grouped chain.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Fri Sep 15, 2006 11:51 am

A mere style suggestion: The tagged cells in candidate grids with right-justified columns are easier to spot when the tags are placed to the right.

For example:
Mike Barker wrote:
Code: Select all
+--------------------+-------------------+---------------------+
|  3589  *589  35689 | *2579  2379     1 |      4  3689   2358 |
|     7  *589  34589 |  *259     6   345 | *23589     1   2358 |
|     1     2  34569 |     8   359   345 |      7   369     35 |
+--------------------+-------------------+---------------------+
|     4     3   @589 | *1569   @59     2 |   1568   -78   1578 |
|     6    17      2 |   157     8   357 |    135     4      9 |
|   589    17    589 |     4  3579  3567 |  13568     2   1358 |
+--------------------+-------------------+---------------------+
|   238    68      1 |   267   247     9 |    238     5  23478 |
|  2359     4    359 |   257     1   578 |  *2389  3789      6 |
|  2589 *5689      7 |     3   245  4568 |    128   #89   1248 |
+--------------------+-------------------+---------------------+


Myth Jellies wrote:
Code: Select all
+--------------------+-------------------+---------------------+
|  3589  X589  35689 | X2579  2379     1 |     X4  3689   2358 |
|     7  X589  34589 |  X259     6   345 | X23589     1   2358 |
|     1     2  34569 |     8   359   345 |      7   369     35 |
+--------------------+-------------------+---------------------+
|     4    X3   B589 | X1569   B59     2 |  X1568   -78   1578 |
|     6    17      2 |   157     8   357 |    135     4      9 |
|   589    17    589 |     4  3579  3567 |  13568     2   1358 |
+--------------------+-------------------+---------------------+
|   238    68      1 |   267   247     9 |    238     5  23478 |
|  2359     4    359 |   257     1   578 |  x2389  3789      6 |
|  2589 x5689      7 |     3   245  4568 |    128   A89   1248 |
+--------------------+-------------------+---------------------+

Suggestion wrote:
Code: Select all
+--------------------+-------------------+---------------------+
|  3589   589X 35689 |  2579X 2379     1 |      4X 3689   2358 |
|     7   589X 34589 |   259X    6   345 |  23589X    1   2358 |
|     1     2  34569 |     8   359   345 |      7   369     35 |
+--------------------+-------------------+---------------------+
|     4     3X   589B|  1569X   59B    2 |   1568X   78-  1578 |
|     6    17      2 |   157     8   357 |    135     4      9 |
|   589    17    589 |     4  3579  3567 |  13568     2   1358 |
+--------------------+-------------------+---------------------+
|   238    68      1 |   267   247     9 |    238     5  23478 |
|  2359     4    359 |   257     1   578 |   2389x 3789      6 |
|  2589  5689x     7 |     3   245  4568 |    128    89A  1248 |
+--------------------+-------------------+---------------------+
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Fri Sep 15, 2006 3:02 pm

Good point, Ron. I'd say the labels stick out the best on the side that the numbers are justified to--in this case that is, as you say, on the right side.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Previous

Return to Advanced solving techniques