Is there an ALS that can find this elimination?

Advanced methods and approaches for solving Sudoku puzzles

Is there an ALS that can find this elimination?

Postby 999_Springs » Sun Sep 14, 2008 2:30 pm

It looks like there is one, but I can't find it...

Code: Select all
#12 from the top95

  3478 |     6 |   3478 ||      5 |   238 |     1 ||    478 |     9 |    24
     1 |     2 |     78 ||     46 |     9 |    46 ||     78 |     5 |     3
     9 |    35 |   3458 ||     23 |   238 |     7 ||   1468 | 12468 |  1246
========================||========================||========================
  2356 |     4 |   2359 ||      8 |  1236 |  2369 ||     16 |     7 |   126
  2367 |    39 |   2379 || 123469 | 12346 | 23469 ||      5 |  1246 |     8
    26 |     8 |      1 ||      7 |   246 |     5 ||    469 |     3 |  2469
========================||========================||========================
   348 |   139 |   3489 ||  13469 |     5 |  3469 ||      2 |  1468 |     7
 23458 |  1359 | 234589 || 123469 |     7 | 23469 || 134689 |  1468 | 14569
  2345 |     7 |      6 ||  12349 |  1234 |     8 ||   1349 |    14 |  1459


r6c7<>6 (consider r1234c7 and r14c9)
999_Springs
 
Posts: 591
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Postby daj95376 » Sun Sep 14, 2008 3:47 pm

Code: Select all
 +--------------------------------------------------------------------------------+
 |  3478    6       3478    |  5       238     1       | a478     9       24b     |
 |  1       2       78      |  46      9       46      | a78      5       3       |
 |  9       35      3458    |  23      238     7       | a1468    12468   1246    |
 |--------------------------+--------------------------+--------------------------|
 |  2356    4       2359    |  8       1236    2369    | a16b     7       126b    |
 |  2367    39      2379    |  123469  12346   23469   |  5       1246    8       |
 |  26      8       1       |  7       246     5       |  469     3       2469    |
 |--------------------------+--------------------------+--------------------------|
 |  348     139     3489    |  13469   5       3469    |  2       1468    7       |
 |  23458   1359    234589  |  123469  7       23469   |  134689  1468    14569   |
 |  2345    7       6       |  12349   1234    8       |  1349    14      1459    |
 +--------------------------------------------------------------------------------+
 # 145 eliminations remain

I don't know an ALS from a hole in the ground, but I'm going to have a go at it.

Code: Select all
A=[r1234c7]=14678
B=[r1c9],[r4c79]=1246
x=4
z=6

                         (A) [r123c7]=478
                        /
[r6c7]=6 => [r4c7]=1 =>
                        \
                         (B) [r4c9]=2 => [r1c9]=4

The candidate 4 can not be in [r1c9] and part of the triple in [r123c7] at the same time.

BTW: You don't have to tell me that I'm wrong. I already know that. However, it was fun trying!
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Is there an ALS that can find this elimination?

Postby Luke » Mon Sep 15, 2008 12:07 am

999_Springs wrote:It looks like there is one, but I can't find it...

Code: Select all
#12 from the top95

  3478 |     6 |   3478 ||      5 |   238 |     1 ||    478 |     9 |    24
     1 |     2 |     78 ||     46 |     9 |    46 ||     78 |     5 |     3
     9 |    35 |   3458 ||     23 |   238 |     7 ||   1468 | 12468 |  1246
========================||========================||========================
  2356 |     4 |   2359 ||      8 |  1236 |  2369 ||     16 |     7 |   126
  2367 |    39 |   2379 || 123469 | 12346 | 23469 ||      5 |  1246 |     8
    26 |     8 |      1 ||      7 |   246 |     5 ||    469 |     3 |  2469
========================||========================||========================
   348 |   139 |   3489 ||  13469 |     5 |  3469 ||      2 |  1468 |     7
 23458 |  1359 | 234589 || 123469 |     7 | 23469 || 134689 |  1468 | 14569
  2345 |     7 |      6 ||  12349 |  1234 |     8 ||   1349 |    14 |  1459


r6c7<>6 (consider r1234c7 and r14c9)

I thought both groups in an ALS must satisfy N+1. If you "consider r1234c7 and r14c9," the former group is indeed N+1 (5 candidates in 4 cells), but the latter is N+2 (4 candidates in 2 cells.) So no ALS, if my understanding is correct.
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby Luke » Mon Sep 15, 2008 1:24 am

daj95376 wrote:I don't know an ALS from a hole in the ground, but I'm going to have a go at it.
Code: Select all
#12 from the top95

  3478 |     6 |   3478 ||      5 |   238 |     1 ||    478 |     9 |    24
     1 |     2 |     78 ||     46 |     9 |    46 ||     78 |     5 |     3
     9 |    35 |   3458 ||     23 |   238 |     7 ||   1468 | 12468 |  1246
========================||========================||========================
  2356 |     4 |   2359 ||      8 |  1236 |  2369 ||     16 |     7 |   126
  2367 |    39 |   2379 || 123469 | 12346 | 23469 ||      5 |  1246 |     8
    26 |     8 |      1 ||      7 |   246 |     5 ||    469 |     3 |  2469
========================||========================||========================
   348 |   139 |   3489 ||  13469 |     5 |  3469 ||      2 |  1468 |     7
 23458 |  1359 | 234589 || 123469 |     7 | 23469 || 134689 |  1468 | 14569
  2345 |     7 |      6 ||  12349 |  1234 |     8 ||   1349 |    14 |  1459

A=[r1234c7]=14678
B=[r1c9],[r4c79]=1246
x=4
z=6

                         (A) [r123c7]=478
                        /
[r6c7]=6 => [r4c7]=1 =>
                        \
                         (B) [r4c9]=2 => [r1c9]=4

The candidate 4 can not be in [r1c9] and part of the triple in [r123c7] at the same time.

BTW: You don't have to tell me that I'm wrong. I already know that. However, it was fun trying!

I'm sure you're not wrong at all in your deduction. Still, I wonder if it qualifies as an ALS.

In every basic ALS I've ever seen, all of the cells in Group A share a single house, and all of the cells in Group B share another. The cells in your Group A all share one unit [c7]. The cells in your group B shack up in 2 houses.

Here's a valid ALS as an example:
Code: Select all
+---------------+-------------------+----------------+
|  1279 A12   6 |     8  1247     5 |  A27   3   479 |
|  1279   3   4 |     6   127   279 |    8   5   279 |
|     5   8 279 |   347  2347  2479 |  267   1 24679 |
+---------------+-------------------+----------------+
|     8   9   3 |     1  2567   267 |    4  27    56 |
|  1247  56 127 |    47     9  2478 |   56 278     3 |
|   247  56  27 |  3457 23468 24678 |    9 278     1 |
+---------------+-------------------+----------------+
|     3 B12 129 |   579  B678  B678 |    257 4  B278 |
|    29   7   5 |    49    48     3 |    1   6    28 |
|     6   4   8 |     2    57     1 |    3   9    57 |
+---------------+-------------------+----------------+

All of the cells in Group A are in [r1]. [127] in 2 cells=N+1.
All of the cells in Group B are in [r7]. [12678] in 4 cells = N+1.
x=1.
z=7.
[r7c7]<>7.
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby ttt » Mon Sep 15, 2008 2:05 am

Hi 999_Springs,
Nice find, I thinks that is AALS
I present as Kraken :
Code: Select all
AALS(14678)r123c7  => r6c7<>6 
 ||
(6)r3c7
 ||
(1)r3c7-(1=6)r4c7
 ||
(478)r123c7-(4=2)r1c9-(2=hp16)r4c79

Other AALS
Code: Select all
AALS(12368)r134c5 => r569c5<>2
 ||
(238)r134c5
 ||
(6)r4c5-(hp16=2)r4c79-(2)r13c9=(2)r3c8-(2=3)r3c4-(3=hp28)r13c5
 ||
(1)r4c5-(hp16=2)r4c79-(2)r13c9=(2)r3c8-(2=3)r3c4-(3=hp28)r13c5  (edited)


The AALS (12368)r134c5 meant :
1- If (triple 238)r134c5 => r569c5<>2
2- If r4c5=6 => r4c9=2 => r3c8=2 => r3c4=3 => (pair 28)r13c5 => r569c5<>2
3- If r4c5=1 => r4c9=2 => r3c8=2 => r3c4=3 => (pair 28)r13c5 => r569c5<>2 (edited)

Edit again : I studied more and see that the second AALS can eliminate more (r9c5<>2). It's also writen as AIC (I'm not sure for presenting "Group" by NL notation - sorry about that) :
Code: Select all
(hp28)r13c5=(2)r3c4-(2)r89c3=(2)r1c9-(2=hp16)r4c79-(16=ht238)r134c5 => r569c5<>2


ttt
ttt
 
Posts: 185
Joined: 20 October 2006
Location: vietnam

Postby Mike Barker » Mon Sep 15, 2008 8:30 pm

Another option is an ALS with three instead of just two links (a Kraken ALS). The idea is that a normal ALS links into a chain with all candidates of one digit linking to the predecessor node and all candidates of a second digit to the successor. One can look at an ALS as a Strong Inference Set where all candidates in the SIS (all the candidates of any two digits) must link to the target cell(s) by an appropriate number of chains. In this case the ALS r4c579 contains the SIS (r4c59=2, r4c5=3). This can be linked to the target cells by the links shown below, one of which is a direct link where the cells share a house.
Code: Select all
Kraken ALS: r4c579=23 => r569c5<>2
r4c5 -2-
r4c9 -2- r1c9 =2= r1c5 -2-
r4c5 -3- ALS:r13c5 -2-
 +----------------------+------------------------+-----------------------+
|  3478     6    3478  |      5    238bc     1  |    478      9     24b |
|     1     2      78  |     46       9     46  |     78      5      3  |
|     9    35    3458  |     23     238c     7  |   1468  12468   1246  |
+----------------------+------------------------+-----------------------+
|  2356     4    2359  |      8    1236*  2369  |     16*     7    126* |
|  2367    39    2379  | 123469  1346-2  23469  |      5   1246      8  |
|    26     8       1  |      7    46-2      5  |    469      3   2469  |
+----------------------+------------------------+-----------------------+
|   348   139    3489  |  13469       5   3469  |      2   1468      7  |
| 23458  1359  234589  | 123469       7  23469  | 134689   1468  14569  |
|  2345     7       6  |  12349   134-2      8  |   1349     14   1459  |
+----------------------+------------------------+-----------------------+
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Allan Barker » Tue Sep 16, 2008 10:37 am

I'm not very expert at what is what but the below looks like two small ALS at either end of a small chain. The candidate is at the overlap of the two ALS. It uses only 5 sets and is located in r345-c789.

Code: Select all
----------------------------------------------------------------------------

       1r3c7================1r3c9=========1r3c8
         |                    |             |     ALS1   16r3
         |     6r3c7========6r3c9=========6r3c8
         |      |                            |
  +---1r4c7A===6r4c7B                        |    ALS2   r4c79
  |             .   |                        |
  |             .   |               2r5c8==2r3c8
  |             .   |                 |
1r4c9==============6r4c9============2r4c9         ALS2 .....
                .   .
                .   .
                 \ /
                  X

X = 6r6c7   (sees column 6c7 and box 6b6)

  +-----------------------------------------------------------------------------+
  | 3478    6       3478    | 5       238     1       | 478     9       24      |
  | 1       2       78      | 46      9       46      | 78      5       3       |
  | 9       35      3458    | 23      238     7       | 48(16)  48(126) 24(16)  |
  +-----------------------------------------------------------------------------+
  | 2356    4       2359    | 8       1236    2369    | (16)    7       (126)   |
  | 2367    39      2379    | 123469  12346   23469   | 5       146(2)  8       |
  | 26      8       1       | 7       246     5       | 469     3       2469    |
  +-----------------------------------------------------------------------------+
  | 348     139     3489    | 13469   5       3469    | 2       1468    7       |
  | 23458   1359    234589  | 123469  7       23469   | 134689  1468    14569   |
  | 2345    7       6       | 12349   1234    8       | 1349    14      1459    |
  +-----------------------------------------------------------------------------+

(12...) Included candidates
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby Steve R » Tue Sep 16, 2008 11:08 am

daj95376 came within a whisker of what bennys called the xy wing rule:

Code: Select all
  3478 |     6 |   3478 |      5 |   238 |     1 |    478B  |     9 |    24A
     1 |     2 |     78 |     46 |     9 |    46 |     78B  |     5 |     3
     9 |    35 |   3458 |     23 |   238 |     7 |   1468B  | 12468 |  1246
-------------------------------------------------------------------------
  2356 |     4 |   2359 |      8 |  1236 |  2369 |     16BC |     7 |   126C
  2367 |    39 |   2379 | 123469 | 12346 | 23469 |      5   |  1246 |     8
    26 |     8 |      1 |      7 |   246 |     5 |    469   |     3 |  2469
-------------------------------------------------------------------------
   348 |   139 |   3489 |  13469 |     5 |  3469 |      2   |  1468 |     7
 23458 |  1359 | 234589 | 123469 |     7 | 23469 | 134689   |  1468 | 14569
  2345 |     7 |      6 |  12349 |  1234 |     8 |   1349   |    14 |  1459


rccs(A, B) = 4
rccs(A, C) = 2

Any other common candidate, x, of B and C may be eliminated from common associates of all the x-cells in BυC.

Here x could be 1 or 6. Only the latter makes an elimination.

Steve
Steve R
 
Posts: 74
Joined: 03 April 2006

Postby Myth Jellies » Tue Sep 16, 2008 7:18 pm

Another option that some people might be interested in is the CoALS Rule. The CoALS Rule states that when you have two intersecting ALS's, you can treat all of the cells of the two ALS's as one combined ALS structure. Within that structure, you then know that either all of the intersection cells digits must be represented, or all of the digits not in the intersection cells must be represented.

Sort of hard to explain, so it is good we have this example...

Code: Select all
  +-----------------------------------------------------------------------------+
  | 3478    6       3478    | 5       238     1       | A478     9      *24     |
  | 1       2       78      | 46      9       46      | A78      5       3      |
  | 9       35      3458    | 23      238     7       | A1468    12468   1246   |
  +------------------------------------------------------------------------------+
  | 2356    4       2359    | 8       1236    2369    |AB16      7      B126    |
  | 2367    39      2379    | 123469  12346   23469   |  5       1246    8      |
  | 26      8       1       | 7       246     5       |  469     3       2469   |
  +-----------------------------------------------------------------------------+
  | 348     139     3489    | 13469   5       3469    |  2       1468    7      |
  | 23458   1359    234589  | 123469  7       23469   |  134689  1468    14569  |
  | 2345    7       6       | 12349   1234    8       |  1349    14      1459   |
  +-----------------------------------------------------------------------------+

ALS A: (14678)r1234c7
ALS B: (126)r4c79

Intersection digits: 1&6
Non-intersection digits: 2&4&7&8

CoALS rule: (1&6 = 2&4&7&8)r1234c7|r4c9

Noting that the 24-cell in r1c9 sees all of the 2's and 4's in the combined ALS, we know that the Non-intersection digits cannot all be true. Therefore (1&6)r1234c7|r4c9 must be true which eliminates (6)r6c7. Add a 7 & 8 in r1c9 and the deduction still holds.

An AIC can be written as...
CoALS:(1&6 = 2&4&7&8)r1234c7|r4c9 - (2=4)r1c9 - (2&4&7&8 = 1&6)r1234c7|r4c9
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby daj95376 » Tue Sep 16, 2008 10:51 pm

This is fascinating, but I'll stick to a modest SIN:

Code: Select all
                    [r1c9]<>2                    => [r1c9]=4 (side effect)
[r6c7]=6  [r4c7]=1  [r4c9]=2  [r1c5]=2 [r3c5]=8           |                => [r6c7]<>6
[r3c7]<>6 [r3c7]<>1                    [r3c7]<>8 => [r3c7]=4 (side effect)
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby David P Bird » Wed Sep 17, 2008 7:43 am

Interesting post Myth, but in this case there is a simpler way:

(1678=4)ALS:r1234c7 - (4=2)r1c9 - (2=16)ALS:r4c79 => r6c7 <> 6

I've no idea if this generalises for other overlapping ALSs though.
David P Bird
2010 Supporter
 
Posts: 1043
Joined: 16 September 2008
Location: Middle England

Postby ttt » Wed Sep 17, 2008 9:27 am

Hi David,
Very, very... very nice & happy to see you (and DonM, of course) here, long time does not see Steve. I think that SP keeps Steve at his works...
SP : Silver Plate...

ttt
ttt
 
Posts: 185
Joined: 20 October 2006
Location: vietnam

Postby Myth Jellies » Wed Sep 17, 2008 11:37 pm

David P Bird wrote:Interesting post Myth, but in this case there is a simpler way:

(1678=4)ALS:r1234c7 - (4=2)r1c9 - (2=16)ALS:r4c79 => r6c7 <> 6

I've no idea if this generalises for other overlapping ALSs though.


Actually, your are right--I think it does. For example, if you pretend there is a 2478 in r1c9; then you still have

(1&6=4&7&8)r1234c7 - (4|7|8 = 2)r1c9 - (2=1&6)r4c79

Thus, it seems CoALS is redundant and is really nothing more than a potential marker for some of these deductions involving two ALS with shared cells. The combining really isn't needed except as an aid for a quick deduction check.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005


Return to Advanced solving techniques