SK-Loops and MSLS's

Advanced methods and approaches for solving Sudoku puzzles

Re: SK-Loops and MSLS's

Postby eleven » Tue Dec 03, 2019 11:53 pm

SpAce wrote:Native sets of candidates (cells, n-rows, n-cols, n-boxes) can be used in either role because they have exactly one true candidate.

Yes. i have no problem with that. I gave a definition (my personal one) and a proof. And it seems to fit to, what i read about the undefined rank 0 MSLS was used for.
If you switch cells, rows, links, naked and hidden sets or whatever in a valid way, the proof will be valid too - and show another point of view.

Concerning the hidden multisets: As you said, we cannot have the ones without the others. So do they need another proof ? If so, i am sure you can do it.

What do you mean? Did you see my horrible 39-truth MSHS transformations in this post?

I just mean, that any "MSLS" will have it'ts more or less horrible "MSHS" counterpart.
eleven
 
Posts: 3105
Joined: 10 February 2008

Re: SK-Loops and MSLS's

Postby SpAce » Wed Dec 04, 2019 1:53 am

Hi Robert,

Mauriès Robert wrote:However, I have difficulty seeing the relationship with Allan Parker's principles.
So I will read the writings of David Bird and Allan Parker to try to understand.

I can't help with your problem directly, but I can give some simple examples of set logic to support your studies. I'll use similar simple examples champagne already mentioned: naked pair, hidden pair, X-Wing, and Sue de Coq, which are all Rank 0 patterns. See my previous post for definitions of "truth" and "link".

Example 1. Naked pair (12)r1c12:

Code: Select all
------------------+-----------------+-------------------
| *12   *12   -12 | -12   -12   -12 | -12   -12   -12  |
| -12   -12   -12 |                 |                  |
| -12   -12   -12 |                 |                  |
------------------+-----------------+-------------------

Here we have two cells with just two shared digits. Thus the cells are obvious truths, because we like them to be as restricted as possible (fewer possibilities to link lead more easily to lower rank). As truths, the cells would be notated as: 1N12 (rows to the left of N and columns to the right of it, i.e. same as r1c12). Capital letters (N,R,C,B) are used for the truth sets, and lower case (n,r,c,b) for link sets.

Next step is to link the truths, i.e. cover all candidates in those cells with some other sets, preferably with as few as possible. For example, we could cover them with column sets for digits 1 and 2, notated as 12c12, but that would require a total of four links (1c1, 1c2, 2c1, 2c2). We only have two truths to feed them, so two links would be left without a true base candidate and we'd be none the wiser. That would be Rank 2 and no eliminations:

2\4 (Rank 2): {1N12 \ 12c12} => nothing

However, we can fortunately cover them with just two row sets (12r1) or two box sets (12b1), either of which would give us rank 0. All non-base candidates can now be eliminated from all links, because the true values in the links are guaranteed to come from the intersecting truths. So:

2\2 (Rank 0): {1N12 \ 12r1} => -12 r1c3456789
2\2 (Rank 0): {1N12 \ 12b1} => -12 b1p3456789

Note that the row eliminations and the box eliminations are two separate operations in (basic) set logic, because if we combine both link sets, we'd get four links, i.e. Rank 2 again. They can be combined but let's not bother with such complications right now.

Our normal (naked) MSLS falls into this category: cell truths and house links.

Example 2. Hidden Pair (12)r1c12

Code: Select all
------------------+-----------------+-------------------
| \12-  \12-   /  |   /    /    /   |   /    /    /    | *12
| -12   -12   -12 |                 |                  |
| -12   -12   -12 |                 |                  |
------------------+-----------------+-------------------

Here we have more candidates (not shown) in the cells r1c12, so they don't work nicely as truths any more. However, digits 1 and 2 are now restricted in row 1 to just those two cells, so we can use those sets as truths: 12R1. Again, we have several possibilities to link them, but only two lead to Rank 0. The first one uses the cells as links and the other the box:

2\2 (Rank 0): {12R1 \ 1n12} => -3456789 r1c12

This is the normal "hidden" operation, using houses as truths and cells as links.

2\2 (Rank 0): {12R1 \ 12b1} => -12 b1p456789

This is basically a fish operation because it's using houses as both truths and links. In fact, it can be seen as two claiming operations (for both 1 an 2), which are Franken 1-fishes.

Example 3. X-Wing.

Code: Select all
        \1                \1
------------------+-----------------+-------------------
|  /     1+    /  |   /    1+   /   |   /    /    /    | *1
|       -1        |       -1        |                  |
|       -1        |       -1        |                  |
------------------+-----------------+-------------------
|       -1        |       -1        |                  |
|  /     1+    /  |   /    1+   /   |   /    /    /    | *1
|       -1        |       -1        |                  |
------------------+-----------------+-------------------
|       -1        |       -1        |                  |
|       -1        |       -1        |                  |
|       -1        |       -1        |                  |
------------------+-----------------+-------------------

As said, fishes use houses for both truths and links. In the case of this X-Wing, the truths are the two rows where digit 1 is restricted to the same two columns, allowing them to be linked easily:

2\2 (Rank 0): {1R15 \ 1c25} => -1 r2346789c25

Example 3. Sue de Coq (1234678)r8,b7.

Code: Select all
.----------------------.-----------------.-----------------.
|  13468   468    346  | 2468  5    236  |  168  7     9   |
|  1368    5      67   | 68    17   9    |  4    238   123 |
|  9       4678   2    | 468   17   346  |  168  38    5   |
:----------------------+-----------------+-----------------:
|  2       3      1    | 7     4    8    |  9    5     6   |
|  7       9      5    | 3     6    1    |  2    4     8   |
|  46      46     8    | 9     2    5    |  3    1     7   |
:----------------------+-----------------+-----------------:
|  5       28-6  *36   | 1     9    26   |  7    238   4   |
| *48     *2478   9    | 5     3    47-2 | *18   6    *12  |
| *346     1     *3467 | 246   8    2467 |  5    9     23  |
'----------------------'-----------------'-----------------'

This gets closer to the naked MSLS territory, since Sue de Coq (Two-Sector Disjoint Subset) is a special case of Distributed Disjoint Subsets (DDS) which are special cases of MSNS. What makes them simpler than the general case is that each digit is restricted to a single sector (house). Otherwise the idea is exactly the same as with the first naked pair example: cells are truths and their candidates are linked with houses:

7\7 (Rank 0): {7N3 8N1279 9N13 \ 128r8 3467b7} => -2 r8c2, -6 b7p2

Since it's Rank 0, we can eliminate non-base candidates from each link. Thus 2r8c2 is eliminated due to the 2r8 link, and 6b7b2 (i.e. 6r7c2) due to the 6b7 link. Unfortunately other links don't have any non-base candidates to eliminate.

From that example it should be a short jump to the bigger MSLS logic. The only difference is more cells and more links (also more than one per digit, unlike Sue de Coq and other DDS).
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: SK-Loops and MSLS's

Postby champagne » Wed Dec 04, 2019 3:36 am

eleven wrote:I just mean, that any "MSLS" will have it'ts more or less horrible "MSHS" counterpart.

Hi eleven,
just for fun, using my own words

a naked pair is the simplest MSLS
the counter part is a 7 digits rank 0 logic (multi fish) where

the 7 digits x unit sets are base sets
the 7 cells are links
champagne
2017 Supporter
 
Posts: 7366
Joined: 02 August 2007
Location: France Brittany

Re: SK-Loops and MSLS's

Postby SpAce » Wed Dec 04, 2019 5:57 am

Hi champagne,

champagne wrote:a naked pair is the simplest MSLS

Is it? That would be a bit of an oxymoron, as its digits are covered by a single sector. Similarly, I wouldn't call X-Wing a multi-fish, as it only has a single digit while the latter category clearly implies more. Sorry to be a nitpicker, but naming hierarchies are kind of close to my heart :)

Of course I agree that normal naked subsets and multi-sector naked sets belong to the same family, and so do single-digit fishes and multi-fishes in their own, but to be on the logical side, both cases would need a generic parent level to allow them to be siblings. Any category with "multi" in its name shouldn't include things that are "single", and vice versa. It just doesn't make sense.

(That said, I need to soon update the Rank 0 hierarchy I drew at the beginning of this discussion, as I've learned that it's incorrect in many ways -- as I suspected. However, one thing I still think is correct is that Multi-Fishes and 1-digit-fishes are side by side. Their common parentage is wrong, though.)

Added. Actually, I'm wondering if my hidden pair example above could be considered the simplest kind of a multi-fish? After all, it's using multiple digits for fish-like logic (as I mentioned). Of course it's degenerate because it can be broken into two single-digit fishes, so I don't know if it counts. More of a multi-fish than X-Wing anyway! :)
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: SK-Loops and MSLS's

Postby champagne » Wed Dec 04, 2019 7:29 am

No Comment :lol:
champagne
2017 Supporter
 
Posts: 7366
Joined: 02 August 2007
Location: France Brittany

Re: SK-Loops and MSLS's

Postby Ajò Dimonios » Wed Dec 04, 2019 8:40 am

Hi at all

If we integrate Robert's theorem also with the G1 sets obtained by crossing two rows and two columns (occurrences E1) with four boxes (occurrences E2) we get a complete definition of all the Msls.

thank you all
Paolo
Last edited by Ajò Dimonios on Wed Dec 04, 2019 10:58 am, edited 1 time in total.
Ajò Dimonios
 
Posts: 213
Joined: 07 November 2019

Re: SK-Loops and MSLS's

Postby SpAce » Wed Dec 04, 2019 9:02 am

Here's my new attempt at a Rank 0 pattern hierarchy, updated based on this discussion.

Code: Select all
                                              Alien Fish
                                                   |
                                +------------------+------------------+
                                |                                     |
                             Rank 0                                 Rank 1+
                                |                                     |
                  +-------------+--------------------+---------+     ***
                  |                                  |         |
             Locked Sets                           Fish       other
                  |                                  |
         +--------+--------+                   +-----+----------+
         |                 |                   |                |
   Basic Subsets         MSLS               1-digit          Multi-Fish
         |                 |                    |               |
   +-----+---+        +----+----+        +------+-----+      +--+----+
   |         |        |         |        |      |     |      |       |
Naked     Hidden    MSNS       MSHS     Bsc  Frnkn   Mtnt   Pure    Impure (inc. cells)
                      |                                      |     
          +-----------+---------+                       +----+-----+------+
          |                     |                       |    |     |      |
         DDS                 Non-DDS                    R*   C*   R*C*   other?
          |                     |                                  |
      +---+---+         +-------+-------+                       +--+--+
      |       |         |       |       |                       |     |
     SDC    3+sec     r*c*    r*c*b   other                 SK-Loops  other
                                |
                             +--+--+
                             |     |
                         SK-Loops  other?

Comments are welcome. My definition of MSNS uses only cells as truths and houses as links, while MSHS uses only houses as truths and cells as links, so they mirror the basic naked and hidden disjoint subsets. I don't know any subtypes of MSHS yet since I don't really know what kind of useful patterns it actually includes, if any. (Seems pretty useless in most cases if strictly cell covers are used, but I guess it's the only definition that makes sense if it's meant to be the polar opposite of MSNS.)

Seems like the MSNS-side is mostly what people are interested in and think of as MSLS anyway, and within that almost exclusively the rectangle-shaped large "Non-DDS" subtypes. Most people probably don't even know anything else is included in the MSLS family. That's why I think those best known MSLS patterns would deserve their own name as a distinctive subtype, to avoid confusion with full family. What could it be?

SK-Loops are another interesting case. While they (the real things) would certainly deserve their own section, I think they can always be seen easily as subtypes of MSNS (with rcb-covers) even if found as loops. Besides, I'm listing these patterns from the set logic point of view anyway. The MSNS pov also works for the certain variants which I don't accept as loops of any kind. It seems that at least some SK Loops can also be seen as Multi-Fish, but I need to investigate that more to see how well it holds. MSHS with pure cell covers doesn't seem like a relevant way to see them, though.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: SK-Loops and MSLS's

Postby SpAce » Wed Dec 04, 2019 9:15 am

Ajò Dimonios wrote:If we integrate Robert's theorem also with the G1 sets obtained by crossing two rows and two columns (occurrences E1) with four boxes (occurrences E2) we get a complete picture of all the Msls.

Complete picture? Does it correspond with all the subtypes I just drew above, including things like Sue de Coq (which David included)? Or does this demonstrate what I just wrote:

I wrote:Most people probably don't even know anything else is included in the MSLS family.

Btw, I didn't (even try to) understand anything in Robert's diagram as it seemed once again too theoretical to me. Sorry :) I'll reconsider if someone explains it in plainer language and real examples.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: SK-Loops and MSLS's

Postby champagne » Wed Dec 04, 2019 9:46 am

Hi SpACe,

Don't know if this is of interest for you, but

AIC's are all rank 1 logic
When an AIC loops, it becomes a rank 0 logic.

These are often hybrid (not multi_fish, not MSLS) well identified patterns
champagne
2017 Supporter
 
Posts: 7366
Joined: 02 August 2007
Location: France Brittany

Re: SK-Loops and MSLS's

Postby Ajò Dimonios » Wed Dec 04, 2019 10:31 am

He Space.

]Space Wrote:
Example 1. Naked pair (12)r1c12:

CODE: SELECT ALL
------------------+-----------------+-------------------
| *12 *12 -12 | -12 -12 -12 | -12 -12 -12 |
| -12 -12 -12 | | |
| -12 -12 -12 | | |
------------------+-----------------+-------------------

Here we have two cells with just two shared digits. Thus the cells are obvious truths, because we like them to be as restricted as possible (fewer possibilities to link lead more easily to lower rank). As truths, the cells would be notated as: 1N12 (rows to the left of N and columns to the right of it, i.e. same as r1c12). Capital letters (N,R,C,B) are used for the truth sets, and lower case (n,r,c,b) for link sets.

Next step is to link the truths, i.e. cover all candidates in those cells with some other sets, preferably with as few as possible. For example, we could cover them with column sets for digits 1 and 2, notated as 12c12, but that would require a total of four links (1c1, 1c2, 2c1, 2c2). We only have two truths to feed them, so two links would be left without a true base candidate and we'd be none the wiser. That would be Rank 2 and no eliminations:

2\4 (Rank 2): {1N12 \ 12c12} => nothing

However, we can fortunately cover them with just two row sets (12r1) or two box sets (12b1), either of which would give us rank 0. All non-base candidates can now be eliminated from all links, because the true values in the links are guaranteed to come from the intersecting truths. So:

2\2 (Rank 0): {1N12 \ 12r1} => -12 r1c3456789
2\2 (Rank 0): {1N12 \ 12b1} => -12 b1p3456789

Note that the row eliminations and the box eliminations are two separate operations in (basic) set logic, because if we combine both link sets, we'd get four links, i.e. Rank 2 again. They can be combined but let's not bother with such complications right now.

Our normal (naked) MSLS falls into this category: cell truths and house links.


I think a Naked set can be framed as a very simple MSLS.

I can define this naked set as the G1 obtained by crossing the r1 with the b1. The intersection produces the three cells r1c123. If I have the pair 12 in the box1 and in the line1 it means that the occurrences 1 and 2 are not present in these two zones and admitting that all the others are present (there are no cells occupied in b1 and r1) I can conclude that E1 = ( 1; 2) and E2 = (3; 4; 5; 6; 7; 8; 9) Using Robert's formula (clearly using 1 box and a line) I have the conditions of Msls since I have K1 = 2 and K2 = 1 ; 3 = 3, K1 = 2 because I don't have to count cell r1c3 (the introduction of 1 or 2 in this cell creates a contradiction in r1c1 and r1c2).

Or I can define this naked set as the G1 obtained by crossing the r1 with the c1 and c2. The intersection produces the two cells r1c12. If I have the pair 12 in the row 1 and in the columns 12 it means that the occurrences 1 and 2 are not present in these three zones and admitting that all the others are present (there are no cells occupied in c12 and r1) I can conclude that E1 = (1; 2) and E2 = (3; 4; 5; 6; 7; 8; 9). Using Robert's formula I have the conditions of Msls since I have K1 = 2 and K2 = 0; 2 = 2.

p.s. complete picture is wrong translation of complete definition
Ajò Dimonios
 
Posts: 213
Joined: 07 November 2019

Re: SK-Loops and MSLS's

Postby SpAce » Wed Dec 04, 2019 11:17 am

Hi champagne,

champagne wrote:AIC's are all rank 1 logic
When an AIC loops, it becomes a rank 0 logic.

These are often hybrid (not multi_fish, not MSLS) well identified patterns

Yes, thanks, I'm well aware of that. I'm currently keeping any hybrid patterns in the "other" category because it seems that there's enough to sort out with the two "pure" categories: Locked Sets and Fishes. I'd like to get their hierarchies about right first.

AIC-loops aren't necessarily their own type in this categorization anyway, as it's just one way to express a Rank 0 pattern (those that can be easily written as such, which doesn't include the more complex fishes and MSLS). For example, all the Sue de Coqs and probably all DDS-types can be expressed as AIC-loops (with ALS). So, there would be a lot of overlap if all the different expressions for the same patterns were included.

That's why I'm focusing more on the intrinsic differences in the patterns themselves, in terms of truths and links because it's the most general way to compare them (any AIC can be expressed with set logic too, but not vice versa). The main categorization is based primarily on the truth types and secondarily on the links. For example, the Locked Sets category includes only patterns that can be expressed as pure cell-truths\house-links (naked) or house-truths\cell-links (hidden) patterns. In the Fish category the single-digit fishes are purely house-truths\house-links types (of course), while the multi-fishes have more variance yet being mostly house-truths\house-links types with some cells mixed in (if in truths, then I call it "Impure").

Any other types would be hybrids, having mixed combos of cells and houses as both truths and links, and they would be in the "other" category, possibly with some meaningful subgroups. Of course those mixes include many recognizable patterns as well, such as various wings etc, but almost all of them are Rank 1 (or higher, like Death Blossom), and thus excluded from this discussion. I can only think of one well-known mixed-type Rank 0 pattern off-hand and it's the M-Ring. I think almost all the others are just generic AIC-Loops.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: SK-Loops and MSLS's

Postby SpAce » Wed Dec 04, 2019 11:46 am

Hi Paolo,

Ajò Dimonios wrote:I think a Naked set can be framed as a very simple MSLS.

I think not, and I already explained why: MSLS = Multi-Sector Locked Set.

I also said that I have no intention of reading complicated theoretical explanations. So, unless you have a simpler way to explain that idea, I won't entertain it. Maybe it's my loss but that's the way it is.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: SK-Loops and MSLS's

Postby Mauriès Robert » Wed Dec 04, 2019 3:55 pm

Hi Eleven,
eleven wrote:If you can group all candidates of the sub-puzzle into disjoint links, and get as much links as you have cells, you have, what we talk about here.
(This is the hard part, when you want to find one)


I don't understand that.
Here is an example of a puzzle with MSLS from Phil's website.

Image

The sub-puzzle is in red. I don't see any disjointed links in the sense you define.
Thank you for your additional explanations.
Robert
Mauriès Robert
 
Posts: 585
Joined: 07 November 2019
Location: France

Re: SK-Loops and MSLS's

Postby Mauriès Robert » Wed Dec 04, 2019 4:34 pm

Hi SpAce,

SpAce wrote:Btw, I didn't (even try to) understand anything in Robert's diagram as it seemed once again too theoretical to me. Sorry :) I'll reconsider if someone explains it in plainer language and real examples.


I am surprised that you do not try to understand my definition of MSLS even when you ask me ( "May I ask what kind of notion of MSLS you do have then?" ), if only to tell me if it is good or bad.
However, my explanations do not seem more theoretical than anything you have to say on this subject.
But anyway, here's an example to better explain my definition, with this puzzle from Phil's website.

Image

E1=1289, E2=34567
G1=r1248-c23459 (in red) => NxP=20
The Aij parts of the G1 cells contain the occurrences of E1.
The Bij parts of G1 cells contain the occurrences of E2.

Image

So condition 1) is satisfied.
I count the number K1 of occurrences of E1 that I could place in the lines of G1 => K1=8
I count the number K2 of occurrences of E2 that I could place in the columns of G1 => K2=12
K1+K2=20=NxM
So condition 2) is satisfied
=> MSLS => Eliminations.
Sincerely
Robert
Mauriès Robert
 
Posts: 585
Joined: 07 November 2019
Location: France

Re: SK-Loops and MSLS's

Postby champagne » Wed Dec 04, 2019 8:20 pm

Mauriès Robert wrote:Hi Eleven,
The sub-puzzle is in red. I don't see any disjointed links in the sense you define.
Thank you for your additional explanations.
Robert

I am very surprised.
First of all, although a bug is always possible, Phil's results are reliable.
If I check quickly this MSLS (20 thruths)
7 digits are covered in 2 rows or 2 columns
for the 2 missing digits, we need 3 rows/columns
at the end, 7x2 + 2x3= 20 links.
where is your problem
champagne
2017 Supporter
 
Posts: 7366
Joined: 02 August 2007
Location: France Brittany

PreviousNext

Return to Advanced solving techniques

cron