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: 2624
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

Previous

Return to Advanced solving techniques