Almost locked rules (for now)

Advanced methods and approaches for solving Sudoku puzzles

Postby Bob Hanson » Wed Dec 21, 2005 5:54 pm

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).
Bob Hanson
 
Posts: 75
Joined: 04 December 2005

Postby Mike Barker » Mon Feb 20, 2006 1:05 am

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?
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby bennys » Mon Feb 20, 2006 2:24 am

that "wxy" is not ALS
bennys
 
Posts: 156
Joined: 28 September 2005

Postby tarek » Mon Feb 20, 2006 2:26 am

Mike Barker wrote:"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
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby ronk » Mon Feb 20, 2006 2:39 am

Mike Barker wrote: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
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Sat Mar 04, 2006 2:10 pm

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.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Sat Mar 04, 2006 3:26 pm

Mike Barker wrote: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

Mike Barker wrote: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
Last edited by ronk on Sat Mar 04, 2006 1:23 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Sat Mar 04, 2006 4:07 pm

is there an acronym list somewhere
AFAIK = As Far As I Know
IMO?
etc
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Sat Mar 04, 2006 4:21 pm

Mike Barker wrote: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
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Almost locked rules (for now)

Postby fermat » Fri Aug 11, 2006 1:40 pm

ronk wrote:
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?
fermat
 
Posts: 105
Joined: 29 March 2006

Re: Almost locked rules (for now)

Postby ronk » Fri Aug 11, 2006 2:10 pm

fermat wrote:
ronk wrote: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.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby fermat » Sat Aug 12, 2006 3:59 am

Mike Barker wrote: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
fermat
 
Posts: 105
Joined: 29 March 2006

Re: Almost locked rules (for now)

Postby StrmCkr » Sun Nov 17, 2019 4:16 am

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
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1417
Joined: 05 September 2006

ALS A & B sharing mutal N collection of ALS

Postby StrmCkr » Sat Sep 30, 2023 11:48 pm

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.
Last edited by StrmCkr on Sun Oct 01, 2023 7:57 pm, edited 3 times in total.
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1417
Joined: 05 September 2006

Re: Almost locked rules (for now)

Postby jco » Sun Oct 01, 2023 12:16 pm

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)  .   .     | .   .   .  | .   .   .  |
| .     .   .     | .   .   .  | .   .   .  |
+-----------------+------------+------------+
JCO
jco
 
Posts: 708
Joined: 09 June 2020

PreviousNext

Return to Advanced solving techniques