New technique: Almost Locked Sub-Sets

Advanced methods and approaches for solving Sudoku puzzles

New technique: Almost Locked Sub-Sets

Postby omerosler » Tue May 31, 2016 10:35 pm

EDIT: Changed the description and proof; added inline grid for simple example

This is the first time I am posting to this forum, I hope I'm in the right place.
The method I'm about to present is a generalization of ALS-Chain which is much rarer but could be spotted much more easily (like XY-Wing -> XYZ-Wing).
I looked and couldn't find it in popular websites of sudoku solving techniques so I'm posting it here.
First a definition:

An almost locked subset (ALSS) of a set A of N(>1) cells is a set of appearances of candidates in A such that at most 1 cell of A can contain a candidate NOT from the subset.

Observations:
1. If we take an ALS (which is not a bi-value cell) and choose all candidates but one they from an ALSS.
2. The key property of ALSSes: If we remove all appearances of a candidate of the ALSS then a subset of A of size N-1 forms a locked set on the remaining candidates of the ALSS (hence the name).

The method - ALSS-Chain (Loosely speaking, take the definition of singely linked ALS-Chain and every time you seethe word "ALS" replace it with "ALSS", that is actually exactly what I did):
ALSS-Chains are a series of ALSSes connected by restricted common candidates (RCCs from now on). The first and the last ALSS must contain a common candidate Z which is not the first nor last RCCS ((not Z=first RCC) and (not RCC=last RCC)), Z is eliminated from all cells that see all appearances of Z in both ends of the ALSS-Chain. Some restrictions are put on the RCCs: No two adjacent RCCs may be the same.

Proof:
Assume one end of the chain contains the common digit, then the elimination is immediate.
Otherwise, we just removed the common candidate from the ALSS in an end of the chain, so by observation 2 some subset of it is locked and contains the first RCC of the chain (since it's different from the common digit) so the same thing happens to the next ALSS.
We can continue all the way to the last ALSS, all of them (including the last and excluding the first) contain a locked subset of their size - 1 of all candidates but the previous RCC (we can view Z as a "before first" RCC and include the first in the last sentance).
If a cell can see all apperances of the common candidate in the last ALSS, it sees all of it's apperances in it's locked subset (there are appearances because (not Z = last RCC) so we didn't remove Z), which exists by observation 2; and therefore the common candidate can be eliminated from it.

Disscussion about finding ALSSes:

Note that an ALSS which is not an ALS is quite rare, in fact from the methods I know of it can appear in exactly two forms:
1. There is an ALSS to avoid a deadly pattern (different solutions to the sudoku).
2. The ALSS comes from two colors of 3D-Medusa (also in this case all ALSS-XZ eliminations are already made as part of the normal 3D-Medusa eliminations so those chains are of length > 1).
I actually came across both of these in Diabolical puzzles (unfortunately I didn't record it at the time) and only later generalized the pattern.
How I think one searches for it: You don't!
You can integrate it into other solving techniques as a "last resort":
When you search for a unique rectangle, unique rectangle type 2 is a locked subset. If you only find an ALSS, only then you look for a chain of ALS(S)'s that contains it.
When you do a 3D-coloring and find N cells in the same house with N colored candidates such that every color is spread across N-1 cells of this set it's an ALSS, so now you search for others to complete a chain.

Examples (click on the mini-images for a link to a normal size image):

1. A simple example with a deadly pattern:
Code: Select all

 +---------------------------------------------------------------------------+
 |  -        -         -      |  -     -     -     |  -        -        -    |
 |  -        -         -      |  -     -     -     |  -        -        -    |
 |  -        -         -      |  -     -     -     |  -        -        -    |
 |----------------------------+--------------------+-------------------------|
 |  4-       ab12347   4-     |  -     -     -     |  -        ab1247   a47  |
 |  c3456    c3456     -      |  -     c56   -     |  -        -        -    |
 |  -        b12       -      |  -     -     -     |  -        b12      -    |
 |----------------------------+--------------------+-------------------------|
 |  -        -         -      |  -     -     -     |  -        -        -    |
 |  -        -         -      |  -     -     -     |  -        -        -    |
 |  -        -         -      |  -     -     -     |  -        -        -    |
 +---------------------------------------------------------------------------+

Image
Anything in the grid that's marked with '-' can be anything.
The cells marked with b (blue candidates in the pic) are what is a potential deadly pattern, what's stopping it are the other candidates in those cell, taht together with the candidates in R4C9 (all marked with a or yellow candidates in the pic) form an ALSS.
The cells marked with c (yellow cells) form an ALS which is an ALSS by throwing away the 5.
The RCC is 3 and 4 is another common candidate so it can be eliminated from R4C1 and R4C3.
This rule is ALSS-XZ

2. A complicated example with 3D-Medusa:
I'm not adding code here since I couldn't explain add the 3D-Medusa markings inside the grid without making it unreadable, so you'll have to click on the image, sorry.
Image
The colors (of candidates) obtained via the 3D-Medusa are yellow and green.
The first ALSS is a subset of the red squares that are colored = {12378}.
It is an ALSS because we have 4 candidates of both colors in the red squares => if 2 cells are not from the ALSS then both colors are wrong which is a contradiction to their definition (using inference of 3D-Medusa).
The second ALSS is the ALS colored in blue (minus 4) and the RCC is 1.
The third ALSS is the ALS colored in yellow (minus 8) and the RCC is 5.
R2C2 can see both ends of the ALSS chain so 3 can be eliminated from it.

Note:
You don't have to know which candidate to remove from an ALS to make it an ALSS that fits some ALSS-chain, the point is there is always one (because for the chain we need the previous RCC[common candidate for first] and the next RCC [common candidate for last] and the ALS contains at least 2 cells and 3 candidates, so one of them is neither and it doesn't affect the chain).
I don't think normal human beings (that know ALS-chains :P) can find an ALSS chain with no ALSes in it (solvers probably can, but I assume this situation is super-rare).

I'd love your comments, suggestions and critique,
Omer Rosler
Last edited by omerosler on Thu Jun 02, 2016 1:28 am, edited 1 time in total.
omerosler
 
Posts: 16
Joined: 31 May 2016

Re: New technique: Almost Locked Sub-Sets

Postby David P Bird » Wed Jun 01, 2016 2:27 pm

Hi Omer and welcome to the forum.

Like many contributors here I'm far from a qualified mathematician and heve therefore struggled to understand the the notations in your post. It would be a great help to me to know if I have intepreted the terms in your expressions correctly if you were to follow each statement with an real or hypothetical example.

In Sudoku there are often different ways of arriving at the same eliminations and that could be the case with the ones you have described. It would therefore help to have real world examples if you can provide them. Try to remember where you got that diabolical puzzle from if you can!

I suspect that to reach your eliminations you have used branched paths and/or a pure network approach. However it might be possible to avoid that if a strong pattern defintition can be produced together with the inferences it provides. This would allow it to be used as a component in an alternating inference chain.

In the ALS-XZ rule the restricted common candidates are weakly linked - is that the same for your pattern or do you ever require a conjugate link?

Finally, the way you displayed your grids created difficulties.
Code: Select all
They are best prepared using a fixed width font and then pasted into your post.

Click the quote control on this post to see how I inserted the control codes to get this to work on the previous line.
Before submitting a post you can always preview it to check that you have formatted it correctly.

David P Bird
David P Bird
2010 Supporter
 
Posts: 935
Joined: 16 September 2008
Location: Middle England

Re: New technique: Almost Locked Sub-Sets

Postby omerosler » Wed Jun 01, 2016 11:50 pm

David P Bird wrote:Hi Omer and welcome to the forum.

Thank you!
Like many contributors here I'm far from a qualified mathematician and heve therefore struggled to understand the the notations in your post. It would be a great help to me to know if I have intepreted the terms in your expressions correctly if you were to follow each statement with an real or hypothetical example.


Sorry about that, I'm using latex so often I didn't even think about it. I'll change it in an edit.

In Sudoku there are often different ways of arriving at the same eliminations and that could be the case with the ones you have described. It would therefore help to have real world examples if you can provide them. Try to remember where you got that diabolical puzzle from if you can!

Well, it was a random puzzles in the enjoy sudoku android app and I didn't save it :(
I think hacking an open-source (hackable) solver (is there one?) to find it is the easiest way to find examples (and some statistics about the commonness of the method), but I have zero knowledge on how to do that.
Perhaps someone can give me some pointers?

I suspect that to reach your eliminations you have used branched paths and/or a pure network approach. However it might be possible to avoid that if a strong pattern defintition can be produced together with the inferences it provides. This would allow it to be used as a component in an alternating inference chain.



Maybe my explanation of the pattern wasn't clear enough, I'll tidy it up in the edit.
The idea is quite simple:
ALS-Chains work based on the logic that if you remove the RCC from one ALS it gets locked and "takes control" of the next RCC from the next ALS in the chain.
With ALSS almost the same logic applies:
When you remove the RCC from one ALSS (with N candidates) it lockes a subset of N-1 cells and candidates (we don't nescessery know which one) and since that's all the other candidates of the ALSS (there were N to begin with) it includes the next RCC and it can be excluded from the next ALSS and so on.

After showing the method and proof I moved to a discussion about when the puzzle contains ALSS which is not ALS and how to find those (not as easy or common as plain ALSes).

In the ALS-XZ rule the restricted common candidates are weakly linked - is that the same for your pattern or do you ever require a conjugate link?


Basically I just added an "S" to the ALS-Chain rule:
ALS-Chain can be described as "if a group of ALSes satisfies some conditions (RCCs and a common candidate of both ends of the chain) then some eliminations happen"
ALSS-Chain can be described as "if a group of ALSSes satisfies the same conditions then the same eliminations happen"

So yeah, it's the same rule - weakly linked.

Finally, the way you displayed your grids created difficulties.
Code: Select all
They are best prepared using a fixed width font and then pasted into your post.

Click the quote control on this post to see how I inserted the control codes to get this to work on the previous line.
Before submitting a post you can always preview it to check that you have formatted it correctly.

David P Bird


Sorry about the formatting, but I wanted the examples with the different colors and I couldn't change the size of the display of the image, I'll add (not change since if you click the images it shows them in normal size) the grid as you described.
omerosler
 
Posts: 16
Joined: 31 May 2016


Re: New technique: Almost Locked Sub-Sets

Postby David P Bird » Thu Jun 02, 2016 7:43 pm

Omer, thanks for your edits which make your thinking clearer to me, but not quite completely. It seems to be a generalisation of the ALS-XZ rule.

Concentrating on your ingenious first example, here are the Boolean nodes that I need to provide your proof.

Code: Select all
 +---------------------------------------------------------------------------+
 |  -        -         -      |  -     -     -     |  -        -        -    |
 |  -        -         -      |  -     -     -     |  -        -        -    |
 |  -        -         -      |  -     -     -     |  -        -        -    |
 |----------------------------+--------------------+-------------------------|
 |  4-       ab12347   4-     |  -     -     -     |  -        ab1247   a47  |
 |  c3456    c3456     -      |  -     c56   -     |  -        -        -    |
 |  -        b12       -      |  -     -     -     |  -        b12      -    |
 |----------------------------+--------------------+-------------------------|
 |  -        -         -      |  -     -     -     |  -        -        -    |
 |  -        -         -      |  -     -     -     |  -        -        -    |
 |  -        -         -      |  -     -     -     |  -        -        -    |
 +---------------------------------------------------------------------------+

                                         / (3)r4c2 – (3=456)r5c125 \
(47)r4c89 = (12)r46c8 -[DP]- (12)r46c2 =                             => r4c13 <> 4
                                         \ (47)r4c29               / 

The (12) pairs can't both be true as that would make the deadly pattern.
The first strong link is novel but simple to understand.
The second strong link splits into two cases though so the eliminations are the result of three potential outcomes.

I can't see how these inferences can be packaged into a pattern but that's not to say it's always impossible but the right conditions might be rare. Nevertheless your approach is a clever technique.

Clicking on your second picture the link gets intercepted and I see spam images. However if you're relying on 3DMedusa colouring, then as likely as not, that will have involved a network path. I'll therefore leave that example for now.

There is a 'Hodoku' Java solver on < SourceForge > that could serve your purposes.

This grid (generated by Hoduku) may interest you.

..8.3..6.6.....934...6..7...1..6..92.........48..2..7...1..2...849.....3.3..8.1..
After basics and some simple AICs the grid reduces to
Code: Select all
*--------------*------------------*---------------*
| 1   9    8   | 47     3    47   | 2     6    5  |
| 6   57   57  | 2      1    8    | 9     3    4  |
| 3   2    4   | 6      59   59   | 7     1    8  |
*--------------*------------------*---------------*
| 57  1    3   | 4578   6    457  | 458   9    2  |
| 9   567  2   | 14578  457  1347 | 3458  58   16 |
| 4   8    56  | 59     2    1359 | 35    7    16 |
*--------------*------------------*---------------*
| 57  67   1   | 3      49   2    | 568   458  79 |
| 8   4    9   | 157    57   1567 | 56    2    3  |
| 2   3    567 | 459    8    69   | 1     45   79 |
*--------------*------------------*---------------*

Hoduku gives the following steps
(457=9)r358c5 – (9=457)r134c6 => r5c6 <> 4 (ALS-XZ rule)
(57=9)r38c5 – (9=457)r1346 => r8c6 <> 7 (ALS-XZ rule)
(5=478)r4c167 – (8=45)r59c8 – (4=59)r69c4 => r4c4 <> r4c4 <> 5 (ALS chain)

But note there's a (47)r14c46 DP threat that you can play with.

And here's a contribution of mine on <nested ALSs> to add to your reading list.
David P Bird
2010 Supporter
 
Posts: 935
Joined: 16 September 2008
Location: Middle England

Re: New technique: Almost Locked Sub-Sets

Postby omerosler » Fri Jun 03, 2016 5:42 am

tarek wrote:Hi all,

more reading

almost-locked-sets-xz-rule-doubly-linked-t3979-115.html
subset-counting-t3479.html
almost-locked-sets-als-for-beginners-t3403-15.html


tarek



Thanks for those tarek!
Right now I'm concentrating on finding useful examples and statistics, I'll get to all of them in time.
The reason I didn't include a doubly-linked ALS is because I think this case gets trickier with ALSSes, some of it ,ight still hold in this case, I'll think about it and add another post in this thread.

I can imagine this method could be explained using subset counting (in a similar way to ALS-{XZ,XY-Wing, Chain}) but I'm not exactly sure how right now.
omerosler
 
Posts: 16
Joined: 31 May 2016

Re: New technique: Almost Locked Sub-Sets

Postby omerosler » Fri Jun 03, 2016 11:30 am

David P Bird wrote:Omer, thanks for your edits which make your thinking clearer to me, but not quite completely. It seems to be a generalisation of the ALS-XZ rule.

Concentrating on your ingenious first example, here are the Boolean nodes that I need to provide your proof.

Code: Select all
 +---------------------------------------------------------------------------+
 |  -        -         -      |  -     -     -     |  -        -        -    |
 |  -        -         -      |  -     -     -     |  -        -        -    |
 |  -        -         -      |  -     -     -     |  -        -        -    |
 |----------------------------+--------------------+-------------------------|
 |  4-       ab12347   4-     |  -     -     -     |  -        ab1247   a47  |
 |  c3456    c3456     -      |  -     c56   -     |  -        -        -    |
 |  -        b12       -      |  -     -     -     |  -        b12      -    |
 |----------------------------+--------------------+-------------------------|
 |  -        -         -      |  -     -     -     |  -        -        -    |
 |  -        -         -      |  -     -     -     |  -        -        -    |
 |  -        -         -      |  -     -     -     |  -        -        -    |
 +---------------------------------------------------------------------------+

                                         / (3)r4c2 – (3=456)r5c125 \
(47)r4c89 = (12)r46c8 -[DP]- (12)r46c2 =                             => r4c13 <> 4
                                         \ (47)r4c29               / 

The (12) pairs can't both be true as that would make the deadly pattern.
The first strong link is novel but simple to understand.
The second strong link splits into two cases though so the eliminations are the result of three potential outcomes.

I can't see how these inferences can be packaged into a pattern but that's not to say it's always impossible but the right conditions might be rare. Nevertheless your approach is a clever technique.


Well, the technique is based on two steps: Prooving that some subset is an ALSS (the hard part) and then using it like an ALS (to find XZ/Chain Pattern).
Avoiding a DP is the "proof" part here.
To avoid DP, at least two cells of the set A=r4c289 must be {3,4,7} => if we remove 3 from all cells of A it contains a locked subset of {4,7}
Otherwise, A must contain 3, and because it's an RCC with B= r5c128 (which is an ALS) it locks B and the elimination happen always.

Clicking on your second picture the link gets intercepted and I see spam images. However if you're relying on 3DMedusa colouring, then as likely as not, that will have involved a network path. I'll therefore leave that example for now.


Sorry about that, I was using a free website to upload the pics so ads/spam are a given, I will not do that again.
You are of course right about relying on network paths here, as this is what 3D-Medusa is. I was just trying to give an example on an ALSS which is not from a deadly pattern, it could be shown with an AIC, more on this below.

There is a 'Hodoku' Java solver on < SourceForge > that could serve your purposes.


Thanks!
This solver looks great and I can definetly imagine a small PR to add ALSS chains (and it's a great opportunity to refresh my Java!)
I found a github repository of this solver which I forked: https://github.com/OmerRosler/hodoku
However I see some problems:
It's written in Java which is very slow in my experience, and if I want statistics on the method, I'll need to run it through a large puzzle database and I'm afraid it'll take weeks, how fast exactly is this solver?
Also a development problem (which I only have because I haven't used Java in three years):
When the uniqueness solver (solver\UniquenessSolver.java) finds an ALSS based on a DP it will need to update it in the ALSS solver which will probably be a part of the normal ALS solver (solver\AlsSolver.java) and that creates a dependency (which doesn't exist now) which is not nesscessery when ALSS is not needed at all (Hard to Fiendish puzzles; or some custom solver configuration like practicing). How can I make a conditional dependency (something like #if in C/C++)?

This grid (generated by Hoduku) may interest you.

..8.3..6.6.....934...6..7...1..6..92.........48..2..7...1..2...849.....3.3..8.1..
After basics and some simple AICs the grid reduces to
Code: Select all
*--------------*------------------*---------------*
| 1   9    8   | 47     3    47   | 2     6    5  |
| 6   57   57  | 2      1    8    | 9     3    4  |
| 3   2    4   | 6      59   59   | 7     1    8  |
*--------------*------------------*---------------*
| 57  1    3   | 4578   6    457  | 458   9    2  |
| 9   567  2   | 14578  457  1347 | 3458  58   16 |
| 4   8    56  | 59     2    1359 | 35    7    16 |
*--------------*------------------*---------------*
| 57  67   1   | 3      49   2    | 568   458  79 |
| 8   4    9   | 157    57   1567 | 56    2    3  |
| 2   3    567 | 459    8    69   | 1     45   79 |
*--------------*------------------*---------------*

Hoduku gives the following steps
(457=9)r358c5 – (9=457)r134c6 => r5c6 <> 4 (ALS-XZ rule)
(57=9)r38c5 – (9=457)r1346 => r8c6 <> 7 (ALS-XZ rule)
(5=478)r4c167 – (8=45)r59c8 – (4=59)r69c4 => r4c4 <> r4c4 <> 5 (ALS chain)

But note there's a (47)r14c46 DP threat that you can play with.


Interesting example indeed.
However I couldn't find any ALSS-Chain containing this potential DP, but I stopped looking at length 3 (I'm only human) so the ALS chain seems like the easiest path here.

And here's a contribution of mine on <nested ALSs> to add to your reading list.


Wow, this is indeed very interesting!
Your nested ALS is infact a very weird example of the ALSS-XZ rule:
It is equivelent to two different ALSS-XZ patterns (just like 2-Skyscrapper and Sashimi X-Wing) where each patterns have two ALSS which share cells.
I wrote a complete (long) proof of this and when I submitted it I found my internet was dead and it was lost;
I'm not going to repeat it here, it's very long but if you have understanding of how ALSS-XZ works you can find a proof yourself (it's just long; not hard).
omerosler
 
Posts: 16
Joined: 31 May 2016

Re: New technique: Almost Locked Sub-Sets

Postby omerosler » Fri Jun 03, 2016 11:46 am

A (not so good) example Diabolical puzzle taken from the enjoy sudoku app (found by accident):
Code: Select all

 *-----------------------------------------------------------*
 | 15    35    78    | 6     2348  248   | 14    9     478   |
 | 4     19    38    | 589   7     3589  | 2     15    6     |
 | 2     69    678   | 1     489   4589  | 3     57    478   |
 *-------------------+-------------------+-------------------|
 | 6     2     5     | 3     49    49    | 7     8     1     |
 | 8     4     1     | 57    6     57    | 9     3     2     |
 | 3     7     9     | 28    28    1     | 6     4     5     |
 *-------------------+-------------------+-------------------|
 | 15    35    4     | 278   238   6     | 18    27    9     |
 | 7     16    2     | 489   5     89    | 48    16    3     |
 | 9     8     36    | 247   1     237   | 5     267   47    |
 *-----------------------------------------------------------*

To avoid a DP in R34C56 we must have {5 8} as an ALSS of R3C56
The next ALSSes of the following chain are simply ALSs:
R3C56 (8=5) - R3C8 (5=7) - (R79C8) (72=6) - R29C3 (638) => R2C46 <> 8 - ALSS-Chain

The ALSS-Chain elimination renders the puzzle trivial, but in this case it could be solved using a few XY-Chains (which makes this ALSS-Chain an ALS-Chain which is not needed anymore) and then a Sue de Coq pattern (which is actually a special case of ALSS-XZ!), I'll try to find better examples soon (now that I was shown an open-source solver/generator).
omerosler
 
Posts: 16
Joined: 31 May 2016

Re: New technique: Almost Locked Sub-Sets

Postby omerosler » Fri Jun 03, 2016 12:34 pm

In this post I'll show how Sue de Coq is a special (complicated) case of ALSS-XZ
I'll do this with the most complicated example in the Hudoku page on Sue de Coq (link: http://hodoku.sourceforge.net/en/tech_misc.php)
Code: Select all
.--------------.-------------.---------------------.

| 3  2     4   | 8  6    1   | 5     9      7      |

| 6  5     7   | 9  4    3   | 8     2      1      |

| 9  1     8   | 5  2    7   | 3     6      4      |

:--------------+-------------+---------------------:

| 2  6789  1   | 4  3    589 | a79    b578    5689   |

| 5  789   3   | 2  18   6   | 1479  478    c89     |

| 4  689   69  | 7  158  589 | 129   d358    235689 |

:--------------+-------------+---------------------:

| 1  349   259 | 6  58   258 | 2479  34578  23589  |

| 8  39    259 | 1  7    4   | 6     e35     2359   |

| 7  46    256 | 3  9    258 | 24    1      258    |

'--------------'-------------'---------------------'


First defining some ALSSes:
1. {789} of the cells abc = r4c4 r4c8 r5c9
2. {789} of the cells adc = r4c4 r6c8 r5c9
3. {53} of the cells be = r4c8 r8c8
4. {53} of the cells de = r6c8 r8c8

Seeing those are ALSSes is because if we have two cells of the set of cells not of the respective ALSS then we have a locked set of (3,3,2,2) resp. cells with (2, 2, 1, 1) reps. candidates which is obviously a contradiction.
Now we have a new rule which I forgot to mention before: two ALSSes can share candidates iff their union still preserves the "key property of ALSS" which is that at most one cell of the union is not a candidate from the subset.
This is also key in the proof that nested ALS is also a special case of ALSS-XZ.
This does not mean that every union like this is an ALSS because the size doesn't match (for example the ALSSes 1 and 2 here can have shared candidates - all of them - but their union is {789} of 4 cells which is NOT an ALSS).
Using this rule
1+2 with any RCC yields the elimination of the other two digits => 1+2 with another RCC yield the elimination of the RCC as well
same with 3+4
=>
All possible eliminations of the Sue de Coq
A Sue de Coq is a very unique example of 4 ALSS-XZ packed in a very special way (ALSS-XZ is pretty rare as it is, this is another explanation why Sue de Coq is SUPER-RARE).
omerosler
 
Posts: 16
Joined: 31 May 2016

Re: New technique: Almost Locked Sub-Sets

Postby omerosler » Fri Jun 03, 2016 12:47 pm

Note that if we have an ALSS which is not an ALS we must have some proof of it, that's the hard part, the rest is just like ALS-XZ/Chain (infact when I integrate it to a solver I don't have to change the chain finding part [maybe except the part where ALSSes share candidates/cells], only the ALS finding part).
Instead of looking for this proof we might reach one by looking at other methods:
1. Avoiding a Deadly Pattern (When looking for Unique/Avoidable Rectangles).
2. Finding an Alternating Inference Chain that you found anyway (a subchain of some chain that gave eliminations for example, or if you're a computer you find all of them anyway :P ), like the example given in the nested ANS thread.
3. If you already used a network approach like 3D-Medusa, subsets of colored candidates could easily turn into ALSSes.
4. 'Weird' Subset Counting examples like Sue de Coq.
5. Anything else you can think of...
omerosler
 
Posts: 16
Joined: 31 May 2016

Re: New technique: Almost Locked Sub-Sets

Postby David P Bird » Sat Jun 04, 2016 9:11 am

Hi Omer,
I now believe I understand what you are doing (thanks!) but want to probe deeper into the advantages you consider your approach provides. I'm therefore going to play devil's advocate here so you can point them out.

All you do is to give a new ALSS name to any source of a strong link that can be employed in an elimination chain or net.

It's really a bit of the classic systems analysis approach when marshalling together the individual tasks that a new program must perform:
1. Identify ALSS – the sources of strong links available
2. Scan for weak links to connect them together into elimination chains or nets.
As such it just amounts to a technique to help players organise their thoughts regarding what they have perhaps been doing instinctively before.

David
.
David P Bird
2010 Supporter
 
Posts: 935
Joined: 16 September 2008
Location: Middle England

Re: New technique: Almost Locked Sub-Sets

Postby omerosler » Sat Jun 04, 2016 8:46 pm

Hi David,

David P Bird wrote:Hi Omer,
I now believe I understand what you are doing (thanks!) but want to probe deeper into the advantages you consider your approach provides. I'm therefore going to play devil's advocate here so you can point them out.

All you do is to give a new ALSS name to any source of a strong link that can be employed in an elimination chain or net.

It's really a bit of the classic systems analysis approach when marshalling together the individual tasks that a new program must perform:
1. Identify ALSS – the sources of strong links available
2. Scan for weak links to connect them together into elimination chains or nets.
As such it just amounts to a technique to help players organise their thoughts regarding what they have perhaps been doing instinctively before.

David
.


Well, this technique is of course (I've forgot to mention it before) some subset of Forcing nets.
This is exactly as you say,
a technique to help players organise their thoughts

Well, that statement is true for all classical methods I know (except perhaps Brute Search/Templates) as they are all in the end a sub-type of Forcing chains/nets as they are based on some logic (I at least think so; I don't know the super-advanced ones [yet] like what I just found in this forum [like JE]).

To me, until some stage of the sudoku everything is mechanical (well, computer solvers do exactly that, only in different order or in parallel)-
Basic -> Fishes/X-chains + UR and friends -> XYZ+Wing+XY-Chains -> WXYZ+ALS-XZ -> Sue de Coq+3D-Medusa (I try to avoid that one as it is essentially T&E of one cell)+ER ->AIC ->ALS-Chains (some methods I still haven't mastered but I'm getting to those as well)
Once all of those are exhausted and the puzzle still isn't solved (Exteme+, best kind of puzzles :geek: ), I'm trying to find more subtle logic in the puzzle (which is 100% some kind of forcing net), and if that logic is a very natural extension of the 'standadrd' methods I start to axiomize it as a strategy (this is the first one I'm sharing, more to come) and integrate it with my mechanical solving.
The ALSS-Chain is a natural extension of ALS-Chain that is based on the same logic (and the most general one that I could find).
The only thing one needs to do when looking for ALSS-Chains once she already knows ALS-chains is finding ALSSes which aren't ALSes, and those come from techniques already exhausted - AICs, potential DPs, similar things to Sue De Coq (your nested ALS is a perfect example) based on subset counting (or similar logic), 3D-Medusa (if a net is already cast - why not use it again?) and anything else she has already done the legwork for.
So the only step needed to take from mastering ALS-Chains to mastering ALSS-Chains (or ALS-XZ to ALSS-XZ) is taking a note to self while applying another method that you found an ALSS to use later (or maybe try it right now like in the example I gave four posts ago, but maybe that's too early as more yet-to-be-uncovered ALSSes are required). That's it; no new logic and more eliminations.
omerosler
 
Posts: 16
Joined: 31 May 2016

Re: New technique: Almost Locked Sub-Sets

Postby David P Bird » Sat Jun 04, 2016 10:45 pm

Hi again Omer

Thanks for your response which confirms that what you have developed is a technique for spotting connections between strong links that are internal to our various patterns. How much this will help improving and experienced players will depend on the solving disciplines they follow.

Players (such as me) who confine themselves to only using bidirectional chains until they can progress no further should be pretty familiar with the variety of these internal inferences that are available – they have to be because that's virtually all they've got!

But players that use forcing chains and/or nets may find that the ALSS concept will open their eyes in some cases. The survey that you intend to conduct should be useful in identifying the most frequently occurring ones.

As you said, unfortunately the really exotic show stoppers that could exist will be extremely rare. (Braid Analysis has this problem too – most of the eliminations can be found more simply, and those that can't take a lot of searching to find.)

I also think it would also be wise to consider a more distinguishable name and a notation format for ALSS based eliminations.

Finally try posting your programming queries in the Software section - I haven't done any programming for over 20 years!

David
David P Bird
2010 Supporter
 
Posts: 935
Joined: 16 September 2008
Location: Middle England

Re: New technique: Almost Locked Sub-Sets

Postby JasonLion » Sun Jun 05, 2016 1:10 am

I also support the notion of using a new name for this. I don't see any relationship to ALSs in particular beyond their place in your personal voyage of discovery. An ALS is just one of many such patterns that can serve as links. The majority of solving techniques can serve the same role (as a link in a chain/net, rather than a direct solving step) if you look at them in the right way.
User avatar
JasonLion
2017 Supporter
 
Posts: 604
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: New technique: Almost Locked Sub-Sets

Postby omerosler » Sun Jun 05, 2016 8:10 pm

Hi David, Jason
If you think a better name is appropriate, by all means suggest one;
However, it does have a conncetion to ALS more then how I discovered it:
ALS-based chain work because when you remove the RCC from one ALS it locks all other cnadidates in the rest of the cells of the ALS to exculde the next part of the chain the next weak link.
ALSS-based chain work because when you remove the RCC from one ALSS it locks a subset (of all cells but one) containing all the other candidates and the same applies.
It's a generalization of ALS that allows 1 cell from the set to not contain the candidates of the subset.
Another generalization of ALS which is more common is N cells with N+2 candidates called AALS; in those we must have 2 candidates as a weak link to next part of the chain instead of one.
We can generalize ALS to both direction: number of additional candidates and the maximal number of 'external' candidates and call all of those by the same name: Generalized ALS (or Extended or whatever...)
The definition should be:
A Generalized ALS named A is a subset of candidates of a set named B, of N cells with the following properties:
1. At most k>=0 cells of A can be non-B candidates.
2. B contains N+r-k different candidates for some r>=0.
ALS is r=1, k=0
AALS is r=2, k=0
ALSS is r=1, k=1
Those GALSes however don't cover all forcing chains as subset counting can't be explained like this (and vica versa), but I believe subset counting could be extended in this wierd 'dimension' of external candidates (and might that cover all types of forcing chains which are not nets and give us a new way to look at forcing?)
Genral Method with GALSes:
If a weak link can be established from a subset of B of size r to a GALS of different cells then any other common candidate Z can be eliminated from cells that sees all apperances Z in both GALSes.
This is GALS-XZ (or any better name you may suggest), and can similarly be extended to a chain rule and be a part of a forcing chain.
Any thoughts (or names)?
omerosler
 
Posts: 16
Joined: 31 May 2016

Next

Return to Advanced solving techniques

cron