SK-Loops and MSLS's

Advanced methods and approaches for solving Sudoku puzzles

Re: SK-Loops and MSLS's

Postby eleven » Wed Dec 04, 2019 9:40 pm

Mauriès Robert wrote: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.

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

Hi Robert,

i am not sure, if there is still an open question.
In the following post you have listed the disjoint links in your way, where
each candidate is part of a link,
none of 2 links and,
as you mention, there are 20 links for 20 cells.

The first link is 2 in one of r1c2345, then 9r1c23, ... , 6r1248c9.
To get 20 digits to fill all the cells, there must be exactly one 2 out of 2r1c2345, one 9 in r1c23, ..., and one 6 in r1248c9.

Btw for the proof the N cells don't need to be crossing cells of rows and columns, but can be arbitrary ones, as long as you can find N links covering all candidates.
E.g. you can take Sue de Coq cells, where by definition you have as much links as cells.
But to find bigger sets of them manually is probably even a lot harder.
eleven
 
Posts: 3082
Joined: 10 February 2008

Re: SK-Loops and MSLS's

Postby SpAce » Thu Dec 05, 2019 1:05 am

Mauriès Robert wrote: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.

I appreciate that you tried to answer that question, but I already told why it wasn't really helpful.

However, my explanations do not seem more theoretical than anything you have to say on this subject.

Oh please, give me a break. You gave a piece of theory written as a mathematical algorithm with meaningless variable names that weren't even defined anywhere. I wouldn't have accepted such lack of readability even from a computer program, much less from something meant for human consumption. Most importantly, there was not a single illustrating example with it, so there was a zero chance that I was going to waste my time even trying to decipher it. I already did with your TDP but won't do it again. (Btw, you demonstrated here that you can in fact express TDP principles in simpler terms.)

On the other hand, I've provided several detailed examples and explanations of everything I've presented, and they're all in standard sudoku languages. I even gave you a brief tutorial of the set logic notation and principles, even though it should be more or less standard knowledge in this context. However, it looks like I did all that for nothing, if you don't see the difference.

In fact, I manually digged up and presented as many related Rank 0 patterns for the same puzzle state as I could, which is something no one has published before, as far as I know. It's something you can't get out of Phil's (public) solver, for example, because it only shows you the first one of any pattern type it finds -- leaving the impression that nothing else is available. It's enough for getting a working result, but not enough to gain a complete understanding.

But anyway, here's an example to better explain my definition, with this puzzle from Phil's website.

Like I've said, concrete examples are the bare minimum you need to provide if you publish your theories and expect me to read them. So thanks for that, finally. However, I'm still not going to study your mathematical expressions filled with single-letter indexed variables, simply because I don't like to read them. That's why examples are crucial, because they're probably the only things I even look at. From those I can usually see the intended logic without reading the boring theory (and if not, then I might get more interested in the latter).

I do sudoku for entertainment purposes, so in this context I simply refuse to do anything I don't enjoy unless it seems to have an extremely high payoff probability. I'm sorry to say but I don't enjoy reading your mathematical explanations so they're lost on me, just like some of David's were for slightly different reasons. Quite clearly you like to think and express your ideas in those terms, and that's your choice, but I'm just telling that it's also my choice to skip them in that case. I said the same about TDP so it shouldn't come as a surprise for you. (Btw, several people have complained about my style too, so it's not like I'm claiming to be any better. Just different.)

Anyway, about your example, here's the two complementary MSNSs I could easily find manually. The first one is the same as what Phil's solver presents and what your diagram depicts:

Code: Select all
          \457     \37       \346      \45                               \36
.--------------------------.---------------------------.--------------------------.
| 1       *24579   *2379   | *246      *245     4567-2 | 3467    8       *369     | \29
| 3457-8  *4578    *378    | *1468     *1458    9      | 2       3467    *136     | \18
| 4789     289-47   6      |  128-4     3       1247   | 147     479      5       |
:--------------------------+---------------------------+--------------------------:
| 2       *1479    *1379   | *13469    *149     8      | 3567-1  3567-9  *1369    | \19
| 3489     189-4    5      |  129-346   7       12346  | 1368    2369     1289-36 |
| 3789     6        189-37 |  5         129     123    | 1378    2379     4       |
:--------------------------+---------------------------+--------------------------:
| 5689     1289-5   4      |  7         1289-5  1235   | 3568    2356     28-36   |
| 567-8   *2578    *278    | *2348     *2458    345-2  | 9       1       *2368    | \28
| 589      3        1289   |  1289      6       125    | 458     245      7       |
'--------------------------'---------------------------'--------------------------'

4x5 MSNS: (1289)r1248 x (34567)c23459

20\20 (Rank 0): {1248N23459 \ 29r1 18r2 19r4 28r8 457c2 37c3 346c4 45c5 36c9} => 21 elims

If you look at the row and column markings (similar to David's), they're the same pairs as what you have within the cells in your diagram. So, just based on that observation, your algorithm is probably equivalent (though I haven't read it, for reasons explained above). It just seems more tedious to use if it requires drawing a separate grid.

This took me a few minutes, including spotting the MSLS, confirming Rank 0 status, finding the eliminations, and writing it with unambiguous set logic notation. Marking the grid for presentation took longer.

Here's the complementary MSNS that Phil's solver doesn't show:

Code: Select all
  \89                                        \12       \18      \29
.-------------------------.--------------------------.---------------------------.
|  1       24579   2379   | 246      245      4567-2 |  3467     8       369     |
|  3457-8  4578    378    | 1468     1458     9      |  2        3467    136     |
| *4789    289-47  6      | 128-4    3       *1247   | *147     *479     5       | \47
:-------------------------+--------------------------+---------------------------:
|  2       1479    1379   | 13469    149      8      |  3567-1   3567-9  1369    |
| *3489    189-4   5      | 129-346  7       *12346  | *1368    *2369    1289-36 | \346
| *3789    6       189-37 | 5        129     *123    | *1378    *2379    4       | \37
:-------------------------+--------------------------+---------------------------:
| *5689    1289-5  4      | 7        1289-5  *1235   | *3568    *2356    28-36   | \356
|  567-8   2578    278    | 2348     2458     345-2  |  9        1       2368    |
| *589     3       1289   | 1289     6       *125    | *458     *245     7       | \45
'-------------------------'--------------------------'---------------------------'

5x4 MSNS: (34567)r35679 x (1289)c1678

20\20 (Rank 0): {35679N1678 \ 47r3 346r5 37r6 356r7 45r9 89c1 12c6 18c7 29c8} => 21 elims

The same digit sets can also produce multi-fishes, but I don't bother with them now.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: SK-Loops and MSLS's

Postby Mauriès Robert » Thu Dec 05, 2019 8:13 am

Hi Champagne,
champagne wrote: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

I'm not arguing about the accuracy of Phil's result, there is an MSLS according to my criteria.
My question to Eleven was about the disjointed links that I didn't see, but Eleven answered me very clearly.
On the other hand, I don't understand your reasoning.
Friendly
Robert
Mauriès Robert
 
Posts: 585
Joined: 07 November 2019
Location: France

Re: SK-Loops and MSLS's

Postby Mauriès Robert » Thu Dec 05, 2019 8:27 am

Hi Eleven,

Thank you for your explanations, which are very clear and with which I believe I have understood your reasoning.
One more question despite everything.
eleven wrote:The first link is 2 in one of r1c2345, then 9r1c23, ... , 6r1248c9.

I understand that the links 2r1c2345, 9r1c23 and 6r1248c9 are disjoined, but then you also consider that 2r1Cc2345 and 2r8c12459 are also disjoined links because the 2 are not in the same lines. The same applies to 6r1248c9 and 6r1248c4 because the 6 are not in the same columns. If that's right, then I understood everything....
Sincerely
Robert
Mauriès Robert
 
Posts: 585
Joined: 07 November 2019
Location: France

Re: SK-Loops and MSLS's

Postby champagne » Thu Dec 05, 2019 8:37 am

Mauriès Robert wrote:Hi Champagne,
champagne wrote: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

I'm not arguing about the accuracy of Phil's result, there is an MSLS according to my criteria.
My question to Eleven was about the disjointed links that I didn't see, but Eleven answered me very clearly.
On the other hand, I don't understand your reasoning.
Friendly
Robert

Hi Robert,
It could be that having your own definition of the MSLS you just create trouble in a very simple agreed pattern.

all "digit x unit" sets of the same digit are disjoint if they all are in rows or in columns.

The agreed definition of the MSLS (even if it can appear implicit for anybody) is quite simple

It is a rank0 logic
cells are at the crossing of rows and columns
digits sets (links) are all row or all column in general for a given digit and anyway must be disjoint

if the number of links is equal to the number of cells, the rank 0 logic is there

what else do you expect
champagne
2017 Supporter
 
Posts: 7334
Joined: 02 August 2007
Location: France Brittany

Re: SK-Loops and MSLS's

Postby Mauriès Robert » Thu Dec 05, 2019 9:02 am

SpAce wrote:Quite clearly you like to think and express your ideas in those terms, and that's your choice, but I'm just telling that it's also my choice to skip them in that case. I said the same about TDP so it shouldn't come as a surprise for you. (Btw, several people have complained about my style too, so it's not like I'm claiming to be any better. Just different.)


Indeed, like you, I am different in my perception of sudoku. It's respectable for both of them. When I came to this forum, I thought I was addressing theorists, which is why I presented the TDP in a theoretical way. I could have done it differently.
As I am interested in your opinion, I will do my best to get it by trying to get your attention a little more than I have so far.

If you look at the row and column markings (similar to David's), they're the same pairs as what you have within the cells in your diagram. So, just based on that observation, your algorithm is probably equivalent (though I haven't read it, for reasons explained above). It just seems more tedious to use if it requires drawing a separate grid.


I only gave this separate grid to explain myself better, but in practice I don't do it and notations like yours around the puzzle are enough to identify the groups of occurrences.

This took me a few minutes, including spotting the MSLS, confirming Rank 0 status, finding the eliminations, and writing it with unambiguous set logic notation. Marking the grid for presentation took longer.


I noticed that Phil's application doesn't give you all the possibilities of resolution, but this application is very useful because hodoku doesn't do everything either.
Why do you write MSNS instead of MSLS?

Sincerely
Robert
Last edited by Mauriès Robert on Thu Dec 05, 2019 9:47 am, edited 1 time in total.
Mauriès Robert
 
Posts: 585
Joined: 07 November 2019
Location: France

Re: SK-Loops and MSLS's

Postby Mauriès Robert » Thu Dec 05, 2019 9:17 am

Hi Champagne,
With Eleven's explanations, I think I understood the MSLS well.
What I don't understand in your explanation is your counts: "7 digits are covered in 2 rows or 2 columns
for the 2 missing digits, we need 3 rows/columns"
Can you list them precisely?
Sincerely
Robert
Mauriès Robert
 
Posts: 585
Joined: 07 November 2019
Location: France

Re: SK-Loops and MSLS's

Postby Ajò Dimonios » Thu Dec 05, 2019 10:05 am

Hi Space


Robert's criterion is not opposed to the general logic of rank 0. It is in perfect agreement with the criterion of Allan Barker. It is useful for easily identifying cellular truths (subset G1, cross between rows and columns and possibly between rows, columns and boxes) without having to identify all the links that cover these truths but simply counting in the rows and columns and possibly also in the boxes the missing occurrences and verifying that their sum corresponds to the number of truths (equal to the number of cells). Then later, once you are sure you have a Msls you can transcribe all the links present and write down the deletions.

Ciao a Tutti
Ajò Dimonios
 
Posts: 213
Joined: 07 November 2019

Re: SK-Loops and MSLS's

Postby champagne » Thu Dec 05, 2019 10:33 am

Mauriès Robert wrote:Hi Champagne,
With Eleven's explanations, I think I understood the MSLS well.
What I don't understand in your explanation is your counts: "7 digits are covered in 2 rows or 2 columns
for the 2 missing digits, we need 3 rows/columns"
Can you list them precisely?
Sincerely
Robert

I Hope that I did not make any mistake in my quick check that phil's example was "basic",

I got the following cover

1x2 r
2x2 r
3x3 c
4x3 c
5x2 c
6x2 c
7x2 c
8x2 r
9x2 r

that you can read

digit 1 best cover 2 rows
digit 2 best cover 2 rows ...

giving the 20 link sets
champagne
2017 Supporter
 
Posts: 7334
Joined: 02 August 2007
Location: France Brittany

Re: SK-Loops and MSLS's

Postby Mauriès Robert » Thu Dec 05, 2019 12:19 pm

Thank you Champagne, I understood your way of doing things.
Robert
Mauriès Robert
 
Posts: 585
Joined: 07 November 2019
Location: France

Re: SK-Loops and MSLS's

Postby SpAce » Thu Dec 05, 2019 2:54 pm

Hi champagne,

Hope you don't mind that I'm nitpicking again :)

champagne wrote:The agreed definition of the MSLS (even if it can appear implicit for anybody) is quite simple

I didn't know we had one! That's what I've been complaining about the whole time :) However, now that you've published yours, I think it only covers one limited subtype of MSLS. First, David talked about two top level types: naked and hidden, i.e. MSNS and MSHS, just like ALSs come in two types: ANS and AHS. Yours clearly covers MSNS only. Secondly, even those can come in any shape or form (like Sue de Coqs) and not just rectangular patterns.

cells are at the crossing of rows and columns

Not necessarily, if box links are used (e.g. Sue de Coq). (Of course all cells are at the crossings or rows and columns, but you obviously meant the linking rows and columns.)

digits sets (links) are all row or all column in general for a given digit and anyway must be disjoint

That's generally true for the rectangular patterns, as long as it's understood that links can be boxes as well.

Here's my attempt at a wider and simpler definition of MSLS and its two top-level subtypes:

MSNS: truths are all cells, links are all houses (rows, cols, boxes).
MSHS: truths are all houses, links are all cells.

And of course these are true for all types of MSLS as you wrote:

It is a rank0 logic
if the number of links is equal to the number of cells, the rank 0 logic is there

I think that should cover every possible MSLS. The rectangular patterns people usually call MSLS are thus subtypes of MSNS. It's a misconception that they're the only MSLS types, however.

That's why I think those rectangular patterns should have their own specific name. Naming hierarchies where a top-level family name is used for a specific subtype are awful. We used to have the same problem with the Turbot Fish family where one of the subtypes was also Turbot Fish (now Turbot Crane). I simply hate crap like that because it makes accurate communication impossible or at least difficult.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: SK-Loops and MSLS's

Postby champagne » Thu Dec 05, 2019 3:53 pm

SpAce wrote:Hi champagne,
Hope you don't mind that I'm nitpicking again :) ...


Not at all, I am just trying to stay on a practical view for big rank 0 logic.

I wrote earlier that we have clearly a family of such logic with only cells as truths (and any group of disjointed links).
But if you take this as target, you have no clue to start the search.

I use the general multi fish definition as I wrote earlier just because you can easily apply the brute force to a given set of digits and because the number of cases to study is limited (36 pairs; 84 triplets, 126 quads,...).

Then you have a limited number of cases giving eliminations where it is worth to start the search of a rank 0 logic.
But the search itself on my side, is done on a limited number of sub patterns (truths row oriented, truths columns oriented, 2row x 2 columns basis for truths ) patterns where we have several examples of a rank 0 logic.

You could in the same way test big groups of cells and try to focus on part of them, I never worked in that direction.

Examples of big rank 0 logic based on cells truths came with cells on the crossing of rows and columns and then the best chance to build links leading to a rank 0 logic is to consider rows and columns digit sets.

No theory and no attempt to classify rank 0 families here, just a practical way to find some of them (and I have also the corresponding software).

I don't want to disturb your classification work, but at the end, in my view, this work is of interest for a player if it reinforces its potential to solve hard puzzles. Several contributions of David were in this direction (MSLS, but also JExocets) but with the evidence that the scope is reduced. JExocets is a subfamily of Exocets.

It is just by chance that I start in the case of multi-fish with a very general case.
champagne
2017 Supporter
 
Posts: 7334
Joined: 02 August 2007
Location: France Brittany

Re: SK-Loops and MSLS's

Postby SpAce » Fri Dec 06, 2019 5:50 am

Hi Robert (and Paolo; see below),

Mauriès Robert wrote:When I came to this forum, I thought I was addressing theorists, which is why I presented the TDP in a theoretical way. I could have done it differently.

I'm sure there are theorists too who like it presented that way. I'm just giving my personal perspective, and even I think both approaches have their merits. I think it's good that you've thought things through theoretically and are able to express your ideas in those terms. I just think you should have a popularized version as well for those who aren't interested in the full theory. Either way, examples are always necessary.

As I am interested in your opinion, I will do my best to get it by trying to get your attention a little more than I have so far.

Thanks for that, and it goes both ways. I truly hope you understand that what I said didn't mean that I wasn't interested in your ideas. I am. It's just that being time-constrained and lazy, I don't want to spend extra effort in deciphering something that I think could be expressed more simply and clearly. (Well, that's not entirely true, because I actually enjoy deciphering some types of notations, but only if they're powerful enough to express a piece of logic both accurately and concisely.)

Ajò Dimonios wrote:Robert's criterion is not opposed to the general logic of rank 0. It is in perfect agreement with the criterion of Allan Barker. It is useful for easily identifying cellular truths (subset G1, cross between rows and columns and possibly between rows, columns and boxes) without having to identify all the links that cover these truths but simply counting in the rows and columns and possibly also in the boxes the missing occurrences and verifying that their sum corresponds to the number of truths (equal to the number of cells). Then later, once you are sure you have a Msls you can transcribe all the links present and write down the deletions.

Mauriès Robert wrote:I only gave this separate grid to explain myself better, but in practice I don't do it and notations like yours around the puzzle are enough to identify the groups of occurrences.

So, it seems to me that there's in fact little if any practical difference in the approaches and results. Would you both agree with that?

I noticed that Phil's application doesn't give you all the possibilities of resolution, but this application is very useful because hodoku doesn't do everything either.

I certainly didn't say it wasn't. I just pointed out its limits. As long as it's practically the only public solver that can find advanced patterns (JE, MSLS, SK) at all, and has many examples of them too, it's of course extremely useful. That said, if Hodoku (or similar) had those patterns as well, it would be near perfect. Looks like this project is actually trying to do exactly that.

Why do you write MSNS instead of MSLS?

Because it's more specific and more in line with David's idea (despite my criticism, I actually agree with him a lot too). MLSL is a large pattern-family with two main branches: MSNS and MSHS, as evidenced by David's writings (as well as just thinking about the logic of the name). These big rectangular patterns we're now talking about belong to the first branch, i.e. they're naked types using cell truths, just like normal (single-sector) disjoint naked subsets. That said, even MSNS is not specific enough a name for them because there are other patterns in that subfamily as well (like Sue de Coqs).

That's why I'd like have a more descriptive and accurate name for these big patterns because they're the most interesting ones. Calling them just "MSLS" is clearly too generic and only causes confusion, because most people probably never realize that they're not the only MSLS types out there. Many simpler patterns could be called MSLS too, and I sometimes do just to raise awareness to the fact. For example here. Does it make sense? I think it does, because it makes it easier to understand the logic of the big patterns if you can see the same exact logic work with something much simpler.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: SK-Loops and MSLS's

Postby SpAce » Fri Dec 06, 2019 7:54 am

Hi champagne,

champagne wrote:I am just trying to stay on a practical view for big rank 0 logic.
...
No theory and no attempt to classify rank 0 families here, just a practical way to find some of them
...
I don't want to disturb your classification work, but at the end, in my view, this work is of interest for a player if it reinforces its potential to solve hard puzzles. Several contributions of David were in this direction (MSLS, but also JExocets) but with the evidence that the scope is reduced.

I fully understand your practical point of view. However, what I've been saying all along is that we have a case of separate concerns here, and they shouldn't be mixed. One is the practical process of finding useful patterns in live puzzles, whether manually or by software. The other is the actual classification and understanding of those patterns. It makes sense to reduce the scope for the former, but it makes absolutely no sense to reduce it for the latter. Both are important aspects for me, because I like to have practical solving tools, but I also want to understand the big picture. In fact, I can't really even have one without the other.

The big picture is essential to my learning style. I have no interest in memorizing specific tricks whose generalizations and relationships to the whole I don't understand. I need to understand the complete picture and how they all relate to each other, even if only parts of it are practically useful. If I can see that, then I can usually understand and apply those useful special cases as well without any extra effort. In my experience, that approach results in deeper learning and actually better skills at applying any techniques as well. It's also much easier to add new tricks to the tool bag when you can easily see how they relate to what you already know.

JExocets is a subfamily of Exocets.

Exactly. If you remember, it was crucial for me to understand that relationship before I even got interested in studying JExocets. It's the big picture I'm talking about. That said, I never doubted that JExocets are probably the only type of Exocets most manual players have a chance to find. That's the practical side. It doesn't change the fact that the concept itself is bigger and more general, and even generic Exocets are part of something bigger and more general type of logic.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: SK-Loops and MSLS's

Postby Ajò Dimonios » Fri Dec 06, 2019 8:35 am

Hi Space

So, it seems to me that there's in fact little if any practical difference in the approaches and results. Would you both agree with that?


It seems to me that any resolution technique can be explained by the general logic that is stated in the text by Allan Barker. The purpose of every single technique of resolution is to solve or attempt to solve a scheme with a clear and simple tool. The more a technique is simple and powerful, the more useful it is to achieve its purpose. What I notice is that in the universe of various resolution methods there is a lot of redundancy and repetition. For this reason, anyone who manages to simplify in a few essential methods does a job that everyone likes. Robert's method (TDP) has these characteristics, despite the apparently complex theoretical aspects, the technique is simple and uses only the basic technique.

Ciao a Tutti
Paolo
Ajò Dimonios
 
Posts: 213
Joined: 07 November 2019

PreviousNext

Return to Advanced solving techniques