The New Sudoku Players' Forum

[Bob Hanson]

OK, all the "bennys" almost-locked set ideas are based on disjoint sets. So
that is what I implemented. These functions are in
http://www.stolaf.edu/people/hansonr/sudoku/almostlocked.js

addAlmostLocked()

1. All almost-locked sets are identified, both in the cell-based form of
bennys (which I refer to as "Y") and in the row/column-based form
extension I seem to have innovated (which I refer to as "X").

Ah -- now, there's one caveat-- I ignore sets that contain naked pairs. This
is a single line in the code -- we could remove it and see if there is any
change -- but I figured that all the naked pair analysis is done already, so
why include them? It just seemed redundant. Correct me if I was wrong
about that. So, for example:

{12 12 54 546} is an almost-locked set, but could there be any
improvement over just using {54 546}? My intuition says no. My intuition is
sometimes wrong, of course....

checkAlmostLocked()

2. All directly weakly-linked almost-locked sets are identified, and any
common weakly associated nodes are eliminated. (basic bennys idea)

3. All mutually doubly-linked almost-locked sets are identified, any
candidates other than the linking candidates themselves that consist of
only a single cell are forced TRUE, and all weakly associated nodes to
either of these sets are eliminated. (my idea?)

checkWeakAlmostLocked()

4. The weakly associated nodes are integrated into the 3D Medusa system
by simply counting weakly associated nodes of an almost-locked set as
weakly associated nodes of any strong chain that is itself weakly
associated with that almost-locked set. (Easier done than said!) This
basically "extends the influence" of all the strong chains that are weakly
associated with almost-locked sets. The real problem here, I think, is that
once this is done, the system works independently of the "source" of the
weak links. So it is NOT easy to trace what exactly caused some more
complex eliminations. That's because the 3D Medusa never actually
calculates or finds any "cycles" -- it just uses relationships to chains.

Not implemented:

A. Any situation where three or more almost-locked sets all of which
involve more than 2-valued cells or conjugate pairs in sequence and
which lead to an elimination. bennys might have shown a few of these.
They would have to involve NO 2-valued cells or conjugage pairs, I think,
because those would be taken care of by 3D Medusa linking to their
component almost-locked "subsets". I can't prove that.

B. (Almost)n-locked sets where n>1. Interesting; where does it end?

C. Strongly linked almost-locked sets that involve more than the original
3D Medusa (simple 2-valued cells and 2-location conjugate pairs). No one
has even suggested this yet; I'm just still trying to figure out if it is of any
real benefit or just a lot of trouble. Could REALLY complicate things, and
it might not even be implementable (by me).

[Mike Barker]

I'm trying to understand ALS, but I'm confused about the following problem. Given

Code: Select all

  . . . |  yz . .
wxy . . | xyz * *
  . . . |  wz . .


If "wxy" is ALS1 and the set {"yz","xyz","wz"} is ALS2, then "x" is a restricted common. Based on the xz-rule the implication is that "w" and "y" can be removed from the "*" cells, but I don't think this is correct. What am I missing?

[bennys]

that "wxy" is not ALS

[tarek]

"wxy" is ALS1

hi Mike Barker,

Your ALS1 is missing a cell,

However, assuming you've got ALS1 right.........

if you have the restricted common x in both sets........

any other common candidate can be your "z", if that means 2 candidates ....so beit.

Tarek

[ronk]

I'm trying to understand ALS, but I'm confused about the following problem. Given

Code: Select all

  . . . |  yz . .
wxy . . | xyz * *
  . . . |  wz . .


If "wxy" is ALS1 and the set {"yz","xyz","wz"} is ALS2, then "x" is a restricted common.

Firstly, one cell and three candidates (the wxy) is not an ALS. It must be N cells and N+1 candidates. For your 1 cell illustration, that would be 2 candidates ... so let's eliminate the 'y'.

Secondly, I know the w,x,y, and z are just placeholders but ... since this is about the xz-rule ... let's use placeholders xz for the ALS in one cell. That effectively means w and z would be swapped in your illustration. We then have ...

Code: Select all

  . . . |  wy . .
 xz . . | wxy * *
  * * * |  wz . .

... where * indicates locations where z may be eliminated. Note that z may be eliminated from box1 because the z of the wxyz set occurs in one row only.

Ron

[Mike Barker]

I've just implemented the xy rule and, like the xz rule, it is very powerful in solving puzzles (though finding 3 4-cell restricted ALS sets may be a challenge). In actually coding it up I ended up making several assumptions:
1) A, B, and C are disjoint
2) y<>z
3) an x which is to be elimnated is not an element of A, B, or C

Are these all necessary? Note that if y=z then I believe that y=z must be restricted common to A, B, and C, in which case you really have 3 xz rule problems.

[ronk]

In actually coding it up I ended up making several assumptions:
1) A, B, and C are disjoint
2) y<>z
3) an x which is to be elimnated is not an element of A, B, or C

Are these all necessary?

Yes, those are all requirements AFAIK. The following diagram by Bob Hanson here helps clarify that.

Code: Select all

             c
             |
         z---C---y
         :       :
         :       :
         z       y
        /         \
   a---A           B---b
        \         /
         x...*...x
 
   * can be eliminated

Note that if y=z then I believe that y=z must be restricted common to A, B, and C, in which case you really have 3 xz rule problems.

Based on the above diagram, it appears you would then have a single xz-rule problem.

Upon revisiting this, I was surprised that 'x' was selected as the 'token' to represent the elimination possibilities. I remembered it to be 'z' which would then be consistent for all the ALS rules. Bennys, how did [edit: the token] come to be different?

Ron

[Mike Barker]

is there an acronym list somewhere
AFAIK = As Far As I Know
IMO?
etc

[ronk]

is there an acronym list somewhere
AFAIK = As Far As I Know
IMO?
etc

I just use Google to search on "acronym" and "AFAIK", for example ... and take a "consensus" from the 20 or so results shown. I'm sure you can pick a favorite acronym dictionary from those Google results too.

Ron

[fermat]

Code: Select all

+-------------------+-------------------+-------------------+
| 459   1    %479   |%78    3    %89    | 2    %58    6     |
| 59    569   679   | 278   289   4     |^35    1358  13    |
| 8     3     2     | 5     6     1     | 7     9     4     |
+-------------------+-------------------+-------------------+
| 139   7     139   | 6     4     5     | 8     123   1239  |
| 6     28    134   | 9     28    7     |^34    13    5     |
| 24    289   5     | 238   1     238   | 49    6     7     |
+-------------------+-------------------+-------------------+
| 7     4     39    | 23    259   6     | 1     235   8     |
| 12359 2569  1369  | 4     2589  2389  | 3569  7     239   |
| 2359  2569  8     | 1     7     239   | 3569  4     239   |
+-------------------+-------------------+-------------------+

B={R2C7,R5C7}
C={R1C3,R1C4,R1C6,R1C8}
x=?
y=5
z=4

... letting us eliminate candidate 4 from r5c3.

I'm trying to learn from this. Can the 9 in R1C1 be eliminated since it "sees" all the 9s?
Similarly, can the 5 from R2C8 be removed as it "sees" all the 5s?

[ronk]

B={R2C7,R5C7}
C={R1C3,R1C4,R1C6,R1C8}
x=?
y=5
z=4

... letting us eliminate candidate 4 from r5c3.[/code]

I'm trying to learn from this. Can the 9 in R1C1 be eliminated since it "sees" all the 9s?
Similarly, can the 5 from R2C8 be removed as it "sees" all the 5s?

No, and that deduction is actually known as the ALS xz-rule. (I was obviously learning at the time too. )

B={r25c7} = {345}
C={r1c3468} = {45789}
x=5
z=4

Since the 5s in r1c8 and r2c7 share a unit (box 3), at least one of r1c8<>5 and r2c7<>5 must be true. But r1c8=5 might be true ... and the 9 (or 4, or 7, or 8) eliminated from set C. Or r2c7=5 might be true ... and the 4 (or 3) eliminated from set B.

[fermat]

is there an acronym list somewhere
AFAIK = As Far As I Know
IMO?
etc

That question takes me back to 300 baud modem days and BBSing.

This site has most of the common ones listed:
http://alinconstantin.homeip.net/WebDocs/BBS_Acronyms.htm

[StrmCkr]

some updates to this thread:

als-xy double/triple linked rules:

first noted here


Postby StrmCkr » 20 Aug 2018 08:21
here's some more complicated stuff that is also missing/lacking and never completed but seen as notes in hodoku

Code: Select all

    +------------------------------+-----------------------+-------------------+
    | 124579     (1579-2)   1579-4 | 2468   246789  24689  | 45679  3    5679  |
    | 6          (279)      (479)  | 5      234-79  234-9  | 1      8    (79)  |
    | 4579       8          3      | 46     1       469    | 45679  2    5679  |
    +------------------------------+-----------------------+-------------------+
    | 248-1      (12)       (14)   | 9      5       7      | 3      46   68-1  |
    | 34578-1    6          57-14  | 148    348     1348   | 4578   9    2     |
    | 2345789-1  (3579-12)  579-14 | 12468  23468   123468 | 45678  467  15678 |
    +------------------------------+-----------------------+-------------------+
    | 1379       (1379)     6      | 18     89      189    | 2      5    4     |
    | 59         4          8      | 7      269     2569   | 69     1    3     |
    | 1579       (1579)     2      | 3      4689    145689 | 6789   67   6789  |
    +------------------------------+-----------------------+-------------------+

double linked Als-XY - rule
{performs Als-xz & als-xz double linked eliminations for each set combination: AB, BC, AC }


A) [2479] @ 10,11,17
B) [124] @ 28,29
C)[123579] @ 1,28,46,55,73
X: 2,4 Y:2 <--- {in hodoku x&y can never have more then 1 restricted common in each}
(A & B) - double linked { both sets are locked sets} perform double linked eliminations {this is not checked in hodoku}
(B & C ) -1 restricted common {peers of common digits that is not = y can be removed} {this is not checked in hodoku }
(A & C ) peers of common digit in A & C are exclude. {only this is is checked in hodoku}

{combined z's}
Z: 1,2,4,7,9
Eliminations:
27,35,36,38,45,46,47 <> 1
1 ,46 <> 2
2,38,47 <> 4
13 <> 7
13,14 <> 9

Code: Select all

  .---------------------------------.---------------------------------.---------------------------------.
    | 123456789  123456789  123456789 | 123456789  123456789  123456789 | 123456789  123456789  123456789 |
    | 123456789  279        479       | 123456789  123456789  123456789 | 123456789  123456789  79        |
    | 123456789  123456789  123456789 | 123456789  123456789  123456789 | 123456789  123456789  123456789 |
    :---------------------------------+---------------------------------+---------------------------------:
    | 123456789  12         14        | 123456789  123456789  123456789 | 123456789  123456789  123456789 |
    | 123456789  123456789  123456789 | 123456789  123456789  123456789 | 123456789  123456789  123456789 |
    | 123456789  123456789  123456789 | 123456789  123456789  123456789 | 123456789  123456789  123456789 |
    :---------------------------------+---------------------------------+---------------------------------:
    | 123456789  123456789  123456789 | 123456789  123456789  123456789 | 123456789  123456789  123456789 |
    | 123456789  123456789  123456789 | 123456789  123456789  123456789 | 123456789  123456789  123456789 |
    | 123456789  123456789  123456789 | 123456789  123456789  123456789 | 123456789  123456789  123456789 |
    '---------------------------------'---------------------------------'---------------------------------'
    '

the third rule missing: {yes i know this is an easy case model but it is the easiest to program and show how it works}

als-xy wings triply linked complex. where A,B,C set each have at least 1 different RC, where by each set is always restricted by 1 regardless of any RC placed

Triply linked Rule:
the peers of all cells for each digit found in all ABC, cannot contain that digit.
the peers of all cells for each digit found in set Ab or AC or BC cannot contain that digit.
the peers of all cells for each digit found exclusively in A or B or C cannot contain that digit.


A) [12] @ R4C2
B) [2479] @ R2C239
C) [14] @ R4C3

X: 2, Y: 4 Z:1 <-- is also a restricted common between A & C
eliminates:
r1356789c3<>4, r1356789c2<>2, r2c145678<>7, r2c145678<>9, r4c1456789,r5c123,r6c123<>1


an example in action:
{xsudoku version where the digits displayed are the only things needed to make it work}

Code: Select all

+---------------+------------+-----------------+
| .   -23    .  | .   .   .  | .     -6    .   |
| -1  (123)  -1 | -1  -1  -1 | -1    (16)  -1  |
| .   -23    .  | .   .   .  | .     -6    .   |
+---------------+------------+-----------------+
| .   (23)   .  | .   .   .  | .     -6    .   |
| .   -23    .  | .   .   .  | .     -6    .   |
| .   -23    .  | .   .   .  | .     -6    .   |
+---------------+------------+-----------------+
| .   -23    .  | .   .   .  | -5    (56)  -5  |
| -4  (234)  -4 | -4  -4  -4 | (45)  -456  -45 |
| .   -23    .  | .   .   .  | -5    -56   -5  |
+---------------+------------+-----------------+

updates:
an example:

Code: Select all

2 ALS 2 restricted common rule
------------------------------
If A have degrees of freedom of 2
and B and C are ALS
with
x restricted common to A and B
y restricted common to A and C
and z common to A B C
then you cant have z in a cell that can see all the z candidates in A B C

doubly linked rule : {see 2nd example}
with
 w,x  restricted common to A & B
 y,z   restricted common to A & C
all Restricted commons cannot be in A  as it can only occupy 2 of the 4 thus B,C must contain  at least 1 of each of the RC's
digits of A & B are restricted to A & B
digits of A & C are restricted to A & C
Digis of ABC are restricted to  ABC


Code: Select all

 
        +-----------------+---------+--------------+
        | .     .      .  | .  .  . | .     .   .  |
        | .     (123)  .  | .  .  . | (14)  -2  -2 |
        | (34)  -2     -2 | .  .  . | (24)  .   .  |
        +-----------------+---------+--------------+
        | .     .      .  | .  .  . | .     .   .  |
        | .     .      .  | .  .  . | .     .   .  |
        | .     .      .  | .  .  . | .     .   .  |
        +-----------------+---------+--------------+
        | .     .      .  | .  .  . | .     .   .  |
        | .     .      .  | .  .  . | .     .   .  |
        | .     .      .  | .  .  . | .     .   .  |
        +-----------------+---------+--------------+

AaLS - 2RC

Set a) [123] @ R2C2
Set b) [234] @ R3C17
Set C) [124] @ R23C7
X:3,Y:1
Z:2 => R2C89, R3C23 <> 2

more complicated example: doubly linked

Code: Select all

+----------------------+------------------------+----------------------+
| 12789  3      1489-7 | 5         (278)  (78)  | 6       147    1248  |
| 1278   128    6      | (2378)    4      9     | 1237    5      1238  |
| 5      28     478    | (2367-8)  1      36-78 | 2347    347    9     |
+----------------------+------------------------+----------------------+
| 169    7      159    | 29-36     2356   356   | 123459  8      12345 |
| 1689   1589   2      | 4         35678  35678 | 13579   1379   135   |
| 3      4      589    | 2789      2578   1     | 2579    79     6     |
+----------------------+------------------------+----------------------+
| 4      (159)  (1579) | (367)     356-7  2     | 8       136-9  135   |
| 278-9  28-59  3      | 1         5678   45678 | 459     469    45    |
| (18)   6      (158)  | (38)      9      345-8 | 1345    2      7     |
+----------------------+------------------------+----------------------+

Code: Select all

Aals -2rc
a) 3 6 7 8 @ 57 75
b) 2 3 6 7 8 @ 4 5 12 21
c) 1 5 7 8 9 @ 55 56 72 74
rc: 3 6 7 8
z: 1 2 3 5 6 7 8 9

potential eliminations:
 54 63 64 65 73 <> 1,5
3 13 14 22 23 <> 2
3 30 39 48 66 <> 3,6
54 58 59 60 61 62 <> 7
73 76 77 78 79 80 <> 8
54 58 59 60 61 62 63 64 65 73 <> 9

[StrmCkr]

Code: Select all

 
initial ALS with DOF =x,
 has a collection of N als with a total of X RCC:   disjointedly to the initial ALS  with z common to all N and the initial als

 the collection of N als  is also a Collection of N als for a 2nd AlS with DoF = x, with a total >X RCC  disjointedly to the 2nd ALS.
         each with z common to all N and 2ndary ALS   

whereby the known Z digit  is limited by the 2nd als to be within all of N or the initial ALS & als2  else the 2nd als is reduced to holding n-1 digits in n cells.

 thus the eliminations is the z digit:
  as combinations  of
          peers of the initial ALs + each individual als of the collection of n

i'll post proof shortly.

and maybe some one with better written language can clean this advanced ALS rule up for me.

Code: Select all

+-----------------+------------+------------+
| .     -1  -1    | .   .   .  | .   .   .  |
| .     -1  -1    | .   .   .  | .   .   .  |
| (15)  -1  (125) | -1  -1  -1 | -1  -1  -1 |
+-----------------+------------+------------+
| .     .   .     | .   .   .  | .   .   .  |
| .     .   (16)  | .   .   .  | .   .   .  |
| (15)  .   (26)  | .   .   .  | .   .   .  |
+-----------------+------------+------------+
| .     .   .     | .   .   .  | .   .   .  |
| .     .   .     | .   .   .  | .   .   .  |
| .     .   .     | .   .   .  | .   .   .  |
+-----------------+------------+------------+

Edit for clarity consider all the "." as having every digit.
The naked pair is obvious so the eliminations are excluded in the diagram, but could be considered as part of the set operation.

Start) aals 125 @ r3c3 : a) als 126 @ r56c3 RCC (12) B) 15 @ r3c5 RCC (15)
C) 15 als @ r6c1 : RCC (AC : 1) & RCC (CB: 15) (edited)

if A & B is 1& 5 : C is empty
which creates an internal fixed clause
A&B <> 1 or A&B = 1 => C=5
that leaves use with the main aaLS containing 1
which is what splits 2& 5 into A B which limits c as 1.

(125) a b c
(1) 2 5 1
(2) 1 1 5
(5) 1 1 5

from the AALS & collection of x RCC we can deduce that 1 is in Start or A or B
with the internal limit of A & B is 1. or A & B is not 1
the 3 cells possibilities for 1 is reduced to AALS or (A&B), which allows us to use AAls &a , aals & B as the elimination points of the structure.

[jco]

My view on the example:

Code: Select all

+-----------------+------------+------------+
| .     -1  -1    | .   .   .  | .   .   .  |
| .     -1  -1    | .   .   .  | .   .   .  |
| (15)  -1  (125) | -1  -1  -1 | -1  -1  -1 |
+-----------------+------------+------------+
| .     .   .     | .   .   .  | .   .   .  |
| .     .   (16)  | .   .   .  | .   .   .  |
| (15)  .   (26)  | .   .   .  | .   .   .  |
+-----------------+------------+------------+
| .     .   .     | .   .   .  | .   .   .  |
| .     .   .     | .   .   .  | .   .   .  |
| .     .   .     | .   .   .  | .   .   .  |
+-----------------+------------+------------+

(1)r3c1 = (1)r6c1 - (1=62)r56c3 - (2=51)r3c13 => implies all those eliminations

The (15) r3c1 is needed: almost naked pair (15)r3c13, but the BVC (15)r6c1 isn't needed because only the strong
link (1)r3c1 = (1)r6c1 is at work in that column. See for instance, the configuration below where the same chain applies.

Code: Select all

+-----------------+------------+------------+
| .     -1  -1    | .   .   .  | .   .   .  |
| .     -1  -1    | .   .   .  | .   .   .  |
| (15)  -1  (125) | -1  -1  -1 | -1  -1  -1 |
+-----------------+------------+------------+
| .     .   .     | .   .   .  | .   .   .  |
| .     .   (16)  | .   .   .  | .   .   .  |
| (17)  .   (26)  | .   .   .  | .   .   .  |
+-----------------+------------+------------+
| .     .   .     | .   .   .  | .   .   .  |
| (57)  .   .     | .   .   .  | .   .   .  |
| .     .   .     | .   .   .  | .   .   .  |
+-----------------+------------+------------+