TDP versus FORCING BRAIDS

Advanced methods and approaches for solving Sudoku puzzles

Re: TDP versus FORCING BRAIDS

Postby denis_berthier » Wed Aug 19, 2020 3:36 pm

Pupp wrote:Wouldn't be better to use techniques that have been standardidized?
I mean, I'd think the average player would be more comfortable learning techniques that programs such as Sudoku Explainer use.
Truthfully, I haven't had much luck finding information on some of the advanced techniques mentioned by Sudoku Explainer.
I'm still a beginner. I was elated when I got to the "hard" level on Sudoku 10000, but it turns out it doesn't use much in the way of even intermediate level techniques. I'm just about to start the "very hard" levels though.


No technique has been "standardised", except maybe the most elementary ones: Basic Interactions (whips[1]) and Subsets - which have a very low resolution power.

While Sudoku Explainer provides a reference rating, most of the "rules" it contains (especially "chains") are very obscure and I've never seen any description of them in any human-readable form. The way they are classified results from many arbitrary choices. And they don't even provide invariance under isomorphism.

My approach has always been to define precise rules first and only then to implement them. The rules I've kept in SudoRules (and CSP-Rules) result from their good properties and/or their resolution power.
denis_berthier
2010 Supporter
 
Posts: 3970
Joined: 19 June 2007
Location: Paris

Re: TDP versus FORCING BRAIDS

Postby Pupp » Wed Aug 19, 2020 8:49 pm

denis_berthier wrote:
Pupp wrote:Wouldn't be better to use techniques that have been standardidized?
I mean, I'd think the average player would be more comfortable learning techniques that programs such as Sudoku Explainer use.
Truthfully, I haven't had much luck finding information on some of the advanced techniques mentioned by Sudoku Explainer.
I'm still a beginner. I was elated when I got to the "hard" level on Sudoku 10000, but it turns out it doesn't use much in the way of even intermediate level techniques. I'm just about to start the "very hard" levels though.


No technique has been "standardised", except maybe the most elementary ones: Basic Interactions (whips[1]) and Subsets - which have a very low resolution power.

While Sudoku Explainer provides a reference rating, most of the "rules" it contains (especially "chains") are very obscure and I've never seen any description of them in any human-readable form. The way they are classified results from many arbitrary choices. And they don't even provide invariance under isomorphism.

My approach has always been to define precise rules first and only then to implement them. The rules I've kept in SudoRules (and CSP-Rules) result from their good properties and/or their resolution power.


Ahh. I didn't realize that.

I tried looking up some SE techniques it listed on a problem rated 11.9, and I was able to find mention of Dynamic Forcing chain on Sudoku Snake, which gave a single example. It appears there is little help other than definitions for techniques harder than that. I suppose if are talented enough to be able to use a master technique [according to Sudoku Snake], you can figure out the harder stuff on your own.
Pupp
 
Posts: 246
Joined: 18 October 2019

Re: TDP versus FORCING BRAIDS

Postby SpAce » Wed Aug 19, 2020 9:14 pm

Hi Denis,

I'm on my way out, but the recent bumping of this thread made me remember that you'd nicely answered a question of mine in February. Looks like I never came back to it. I hate when people do that, so I want to apologize. My poor excuse is that I was on my way out then also, and it was obvious that the discussion would probably turn into a potentially long debate. I didn't want that because my mind was not in sudoku at the time. For the same reason I don't want any debates now either, but just to wipe the slate cleaner, let me finally thank you for your reply and say a few comments.

denis_berthier wrote:In short, it [the confluence property] says that the final result (all the candidates eliminated or asserted as values) is independent of the order in which you apply the rules of T. As a counter-example, uniqueness techniques generally break the confluence property: if you don't apply them when you can, they may not be applicable later.
SpAce wrote:Do you have a concrete example of your counter-example in mind?

Probably the most famous example on this forum is UR1

Based on your following description, I guess that's a synonym for UR Type 1. I rather use the latter term because it's much more common on this forum and other sources, and UR1 is easily confused with the special UR1.1 (or is that now known as "RW's Rule"?).

UR1: consider the following template
ab ab
ab abc
where the 4 cells span 2 rows, 2 column and 2 blocks
Then c had to be the value of the 4th cell.
Hidden Text: Show
The proof is quite easy and doesn't even involve uniqueness. If c is not the value, we are left with the following template
ab ab
ab ab
But it is then easy to see that a and be can be permuted in any solution.
(Needless to say, there are many actual examples of this pattern in real puzzles. See the thread about "deadly patterns".)
As an aside, I never use uniqueness (though some U-rules are programmed in CSP-Rules), because I consider it better to prove it along with finding the solution.
Now, there are two very interesting things about this pattern:
- the UR1 rule is not provable constructively from the 4 rules of Sudoku

- if you haven't applied it when the above pattern was available and, say, the first a gets eliminated by some other rule, then you have no means of concluding that c has to be in the solution. On the contrary, you get the following remaining pattern, which can in no way forclude b in the 4th cell:
b a
a bc

False. It's true that the latter pattern is no longer a UR Type 1, or any UR pattern for that matter, because three of its cells are solved. It has become an AR Type 1 instead. That can surely forbid b in the fourth cell just as well (better in fact), concluding c there, so your statement is not true. Applying the AR eliminations doesn't even require assuming uniqueness because of "RW's Rule". The same can be generalized to any UR (or more complex uniqueness) patterns. Like I originally said:

SpAce wrote:Sure, uniqueness patterns might get more difficult to spot if they're partly solved or missing candidates, but their solving powers are still available and applicable.

All that requires is that the uniqueness pattern could have existed at some point without any givens interfering with it. Furthermore, once any pattern candidates are eliminated by non-uniqueness methods (or it's just proved possible), the pattern eliminations become available without assuming uniqueness as per RW's Rule. The same inferences are still available as with the original uniqueness pattern, though a bit harder to spot.

SpAce wrote:I only know that extra clues can truly break uniqueness patterns and thus make a puzzle harder (for those who accept uniqueness methods).

No, extra clues can't make a puzzle harder.

False. A recent counterexample here. For any practical purposes that puzzle is clearly harder than the one with the extra clue(s) removed.

That can only happen in some inconsistent views of solving.

I don't know what that means, but I can only imagine you're talking about uniqueness methods. I don't see anything inconsistent about them, and in any case I already qualified my original statement to assume them in the palette. Thus, your denial was at best misleading.

SpAce wrote:I can't imagine a case where normal solving steps applied in any order would result in the same.

details: Show
And this is now the reason why I was so shocked when I discovered non-confluence. For several months after introducing whips, I believed that whip resolution theories had the confluence property. But I found a counter-example and that led me to find a point I had overlooked in my proof. That also led me to define braids.
Braid resolution theories do have the confluence property; indeed, they have been designed from whips in order to have it; (and braids are related in a very precise way to T&E); braids are the good concept for theoretical analyses. But whips are much simpler than braids. This is where the miracle happens and where I had my second shock: whips are statistically an excellent approximation of braids (i.e. they almost always give the same rating to a puzzle).

Now, if you want a really detailed example of non-confluence for whips, you'll have to open PBCS1 at section 5.10.3
Non-confluence is rarely observed, but it does happen.

No comments on that, but it does sound more intriguing than any uniqueness-based examples. If I find my passion for sudoku again, I might take a deeper look at that then. I still can't imagine anything like that myself.

Added 1. I took a look at the example, but it didn't make me any wiser. The obvious reason is that I don't think in terms of whips. Personally I see a simple AIC, which is perfectly available in both resolution paths, not to mention much more elegant (no ugly contradictions or memories needed). The elimination of 6r9c6 makes no difference because it's not part of the chain at all. Thus no problems with confluence, for what it's worth.

grid: Show
Code: Select all
9817.325.752..19..364.9...8.173...92.43..9.6..9...7...4..1...29.29..8......9..5..
.--------------.------------------------.-----------------.
| 9     8   1  |  7       46       3    | 2    5     46   |
| 7     5   2  |  468     468      1    | 9    34    346  |
| 3     6   4  |  25      9        25   | 17   17    8    |
:--------------+------------------------+-----------------:
| 568   1   7  |  3      d4568    a46-5 | 48   9     2    |
| 258   4   3  |  258    d1258     9    | 17   6     157  |
| 2568  9   56 |  24568  d124568   7    | 348  1348  135  |
:--------------+------------------------+-----------------:
| 4     37  58 |  1      c357     b56   | 368  2     9    |
| 15    2   9  | b456    c357      8    | 346  1347  1347 |
| 16    37  68 |  9       2347    b24/6 | 5    1378  1347 |
'--------------'------------------------'-----------------'

(4)r4c6 = (465)b8p934 - r78c5 = (5)r456c5 => -5 r4c6

vs. the unavailable (and unreadable) whip:

whip[4]: c6n4{r4 r9} – c6n6{r9 r7} – r8c4{n6 n5} – c5n5{r8 .} ==> r4c6 ≠ 5

SpAce wrote:Sure, uniqueness patterns might get more difficult to spot if they're partly solved or missing candidates, but their solving powers are still available and applicable. In fact, some of such degenerate patterns can even be used without assuming uniqueness. What am I missing? (I'm assuming we're talking about single-solution puzzles.)

You got your counter-example with UR1.

I don't think so. Instead, it's the simplest example of what I said in that quote. If a UR Type 1 is partly solved, it becomes an AR Type 1 with three solved corners and the same eliminations still available in the fourth corner.

Conclusion. What you've said hasn't convinced me that uniqueness patterns are examples of a missing confluence property. I can't say anything about the other examples you referred to, because I haven't looked at them (edit: I now have). Somehow I just can't imagine a situation where that can happen. That said, it's quite likely that I still don't fully understand what you even mean by the confluence property, because this is a bit open for interpretation:

In short, it says that the final result (all the candidates eliminated or asserted as values) is independent of the order in which you apply the rules of T.

In a single-solution puzzle the final result is obviously the same no matter how it's solved, so I guess you can't mean that. Instead, I presume that actually means a partial solve path in which two (or more) techniques, which are originally available simultaneously, are applied in different orders and then those partial results are compared? It's quite ambiguous even then.

For example, let's assume that the application of two rules (R1,R2) produces a set of eliminations E = {E1 E2}. Does confluence mean that the reversed order (R2,R1) should produce the same E? What if the application of R2 produces the full E directly? Then the order (R2,R1) doesn't exist, strictly speaking, because it's reduced to just R2. Obviously that's both desirable and very normal even with basic techniques, so it probably doesn't have anything to do with the confluence property. What exactly does? When is it really broken?

I would assume that confluence is really broken if applying R2 first only produces E2 and makes R1 (and thus E1) unavailable. In that case the reversed order would really change the partial result. How the hell can that ever happen in reality? (Like I already said, it doesn't really happen with uniqueness methods, so those examples aren't interesting. I'm not particularly interested in debating that either.) What is, of course, possible is that the E2 eliminations could include some parts of the R1 pattern, breaking its original form, but it should only simplify it -- not make its base logic and eliminations unavailable.

So, obviously I'm still missing something.

--
Added 2. I took another look at the PBCS1 example as a whip, too. Seems to me that the only thing breaking the confluence even in that case is how the whip is written:

whip[4]: c6n4{r4 r9} – c6n6{r9 r7} – r8c4{n6 n5} – c5n5{r8 .} ==> r4c6 ≠ 5

If it actually showed the real logic instead of hiding all the relevant details (which makes it incomprehensible anyway), there wouldn't be any problem. The same internal logic is available if 6r9c6 is eliminated, and it only gets simpler, just like I suspected above. It's easily seen if the logic is written as two contradiction matrices, one with and the other without 6r9c6:

Code: Select all
 5r4c6
 4r4c6   4r9c6                  | c6n4
 6r4c6   6r9c6 6r7c6            | c6n6
         4r8c4 6r8c4 5r8c4      | r8c4
 5r456c5             5r78c5 (!) | c5n5
===============================
-5r4c6

Code: Select all
 5r4c6
 4r4c6   4r9c6                  | c6n4
 6r4c6         6r7c6            | c6n6
         4r8c4 6r8c4 5r8c4      | r8c4
 5r456c5             5r78c5 (!) | c5n4
===============================
-5r4c6

The only difference is the empty hole in the latter because the c6n6 CSP-variable has two instead of three candidates. Both matrices prove that if 5r4c6 is assumed, then all 5s in column 5 get eliminated, hence a contradiction. It's exactly the same logic as your whip's, except that it actually shows what's really going on. Apparently the latter matrix just can't be written as a whip due to the whip propagation rules, but that's an artificial problem relating to how whips are written in the first place. The same logic is still available, only a bit simpler. If written as a contradiction memory chain, the same exact chain works with or without 6r9c6:

(5*-4|6)r4c6 = (46)r97c6 - (4|6=5)r8c4 - (5)r78*456c5 = ! => -5 r4c6

Of course neither contradictions nor memories are necessary, but I already showed that preferable option earlier. Unlike that AIC, this contradiction memory chain has precisely the same logic as the whip, except that it doesn't hide any details and it's confluent (at least in this scenario). Btw, it's also easy to turn into a different AIC:

(4|6)r4c6 = (46)r97c6 - (4|6=5)r8c4 - r78c5 = (5)r456c5 => -5 r4c6

--
Conjecture. I don't think there are any valid solving techniques, uniqueness or not, that really break the confluence property in any significantly destructive way. If a set of eliminations E1 is available through a rule R1, there's no way to make them unavailable by applying another rule R2 with eliminations E2 first. I see three possibilities that can happen if the reverse order (R2,R1) is applied:

One, if R1, R2, E1, E2 share no candidates, nothing changes. Two, if E1 is a subset of E2, then R1 becomes redundant and the solve path loses one step. Three, if E2 includes parts of the R1 pattern, then R1 gets transformed into R1' but its underlying elimination logic remains valid (it might need a slight rewrite, because it just got simpler).

In all cases the same eliminations are available through the same (or simpler) logic regardless of the order of the rules, though perhaps not with the exact same rules. Even if a rule must be changed because parts of its pattern have been eliminated by a previous rule, the underlying logic remains the same (or gets simpler).

The reason why that conjecture doesn't appear to always work with whips is that they hide details of the actual logic. That's why eliminating a candidate from a whip pattern might make it impossible to write the same logic as a whip, even though the full logic is still the same (or simpler). It's a price for masquerading something as simpler and more elegant than it is.
-SpAce-: Show
Code: Select all
   *             |    |               |    |    *
        *        |=()=|    /  _  \    |=()=|               *
            *    |    |   |-=( )=-|   |    |      *
     *                     \  ¯  /                   *   

"If one is to understand the great mystery, one must study all its aspects, not just the dogmatic narrow view of the Jedi."
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: TDP versus FORCING BRAIDS

Postby eleven » Thu Aug 20, 2020 7:29 pm

Agreed. Thanks for diving into that, SpAce (why comes ACE2 into my mind ?).
Have a good time, here or elsewhere.
eleven
 
Posts: 3094
Joined: 10 February 2008

Re: TDP versus FORCING BRAIDS

Postby denis_berthier » Fri Aug 21, 2020 1:57 am

Confluence is not about replacing one rule by any other possible rule; it's about having the same elimination available with the chosen rules.
denis_berthier
2010 Supporter
 
Posts: 3970
Joined: 19 June 2007
Location: Paris

Re: TDP versus FORCING BRAIDS

Postby SpAce » Fri Aug 21, 2020 7:14 am

eleven wrote:Agreed. Thanks for diving into that, SpAce (why comes ACE2 into my mind ?).

That's a strange association, considering that ACE2 lowers blood pressure :lol:

Have a good time, here or elsewhere.

Thanks, you too! I doubt I'll be willing to abandon sudoku for very long, but right now I need a break.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: TDP versus FORCING BRAIDS

Postby SpAce » Fri Aug 21, 2020 9:13 am

denis_berthier wrote:Confluence is not about replacing one rule by any other possible rule; it's about having the same elimination available with the chosen rules.

That still doesn't give me any idea what it actually means. In the (R1,R2) => E scenario, is confluence broken if (R2,R1) => E doesn't work with exactly the same R1? Or is there any leeway? To me it seems that any rule can be made confluent by using a more generalized version that can survive if parts of the pattern are missing.

For example, you're right that in its strictest form 'UR Type 1' can't survive if any pattern candidate is eliminated. Thus it's not confluent as such. However, if the underlying logic behind the rule is considered, there's no problem. An example:

Code: Select all
.-------------.-----------.------------------.
| 36  458  68 | 2  1   35 |  45   9      7   |
| 1   35   7  | 4  35  9  |  2    68^    68^ |
| 29  245  49 | 8  6   7  |  1    45     3   |
:-------------+-----------+------------------:
| 26  24   46 | 3  58  58 |  7    1      9   |
| 8   7    1  | 9  4   2  | *36  *36     5   |
| 5   9    3  | 6  7   1  |  8    2      4   |
:-------------+-----------+------------------:
| 37  1    2  | 5  9   4  | *36  *3678^  68^ |
| 79  38   5  | 1  38  6  |  49   47     2   |
| 4   6    89 | 7  2   38 |  59   35     1   |
'-------------'-----------'------------------'

Clearly we have two simultaneous UR Type 1s:

1. UR (36)r57c78 => -36 r7c8
2. UR (68)r27c89 => -68 r7c8

Since both URs are valid, both sets of eliminations should be too, solving +7r7c8 (stte). However, if taken in sequence as usual, the eliminations of either UR destroy the other's pattern, specifically by eliminating 6r7c8 which is part of both patterns (in the strictest definition). Thus, using either one of the URs first preempts the other. Should that really make the other's remaining elimination invalid? Or is there a problem with the rule?

I vote for the latter. In this case the problem is solved by excluding the elimination cell from the UR Type 1 pattern definition, which makes more sense anyway, since it avoids cannibal eliminations. However, that's not all. What if we apply the UR(68) first (-68 r7c8) and then execute basics before applying the other UR? This happens:

Code: Select all
.-------------.-----------.-------------.
| 36  458  68 | 2  1   35 |  45   9   7 |
| 1   35   7  | 4  35  9  |  2    8   6 |
| 29  245  49 | 8  6   7  |  1    45  3 |
:-------------+-----------+-------------:
| 26  24   46 | 3  58  58 |  7    1   9 |
| 8   7    1  | 9  4   2  | *3   *6   5 |
| 5   9    3  | 6  7   1  |  8    2   4 |
:-------------+-----------+-------------:
| 37  1    2  | 5  9   4  | *6   *37  8 |
| 79  38   5  | 1  38  6  |  49   47  2 |
| 4   6    89 | 7  2   38 |  59   35  1 |
'-------------'-----------'-------------'

Now what? There's no longer any UR pattern at all in r57c78. Should we let that stop us from concluding +7r7c8? Or is there still a problem with the rule? Again, I vote for the latter. What we have now is an AR Type 1 allowing the elimination of 3r7c8, but that's technically a different rule. Should it be?

I don't think so. The underlying logic in both URs and ARs is based on the fact that two digits can't be in such a formation in the (assumed single) solution unless at least one of them is a given. Thus they're really just subtypes of the same rule. With that generalization there's no problem with confluence at all. Are such generalizations allowed in your definition of confluence or not?

(Btw, of course the best way to solve this particular scenario is with MUG (368)r257c789 => +7 r7c8, but that's not the point.)
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: TDP versus FORCING BRAIDS

Postby denis_berthier » Fri Aug 21, 2020 11:17 am

Yep, I know: everything is in everything and conversely.
denis_berthier
2010 Supporter
 
Posts: 3970
Joined: 19 June 2007
Location: Paris

Re: TDP versus FORCING BRAIDS

Postby SpAce » Sat Aug 22, 2020 2:46 am

denis_berthier wrote:Yep, I know: everything is in everything and conversely.

Apparently we agree on something. Looks like the confluent generalization of a whip is a braid, so I guess I had the right idea. It's also quite obvious why that generalization is rather not used if a corresponding whip is available, as braids are even more unreadable. That said, I don't get it why you choose to overuse even whips so much. In most cases they could be replaced with more readable (and confluent) chains that don't need contradictions or memories, probably even using your notations (with group and subset extensions). I'd rather use whips only when more elegant options have dried out, but obviously we have different preferences.

In any case, I think I now understand just about enough of confluence. I guess its main value is in allowing standard ratings that don't change depending on the order of the applied rules. I can agree with that value proposition, no problem. However, it probably makes no difference to a manual solver who understands the fundamentals behind each resolution rule. Such a solver can always adjust and find the corresponding logic, even if it doesn't look exactly the same as some predefined pattern that might have existed in an earlier resolution state.

--
Btw, since you've been freely bashing our notations, you shouldn't mind a bit of feedback on yours now that I have a bit better understanding of them. Leaving everything else aside, I think it's an awful design flaw that symbols in your notations change meanings depending on the type. It also makes it mandatory to always attach a prefix to a chain, or it's not possible to interpret the notation correctly. In particular, I can't think of anything more confusing than a "sequence" that looks like a "chain" but isn't, resulting in links that don't really link adjacent elements. I'm obviously talking about braids and their extremely unintuitive notation. They make even whips look pretty and understandable.

Whatever minor faults Eureka has, its standard symbols don't change meanings, and AICs (etc) contain the full logic within the notation making any prefixes redundant. Well-written Eureka chains and nets can be read without even seeing the grid, and they're rather intuitive too (except for the awful '=' which yields a point to you). Obviously that can't be said about your whips and much less braids, because they hide so much information in an attempt to make things look simpler than they are. (Yes, I know that missing information can be at least partly included, but the way it's implemented is a terrible hack that only worsens the readability.)

Perhaps this is why you didn't want to help me understand your notations in the first place? I guess you knew that judgment was coming. (You know, I could be more diplomatic, but I see no point when I've seen no such effort the other way.)

--
A few random comments to earlier claims:

denis_berthier wrote:
Mauriès Robert wrote:what I notice through the examples treated on this forum and in your book, is that (it seems to me) all the chain techniques (AIC, Whip, biv-chain, etc...) are chains of contradiction

Yes, of course.

No. All of them are not chains of contradiction. Only whips and braids (and our contradiction chains, i.e. Nishios) are. AICs, Krakens, AIC-Nets, (normal) memory chains, and your biv-chains are not. Sure, every one of those can be turned into a corresponding contradiction pattern, but it's completely misleading to claim they're that to begin with. In fact, they're totally opposite points of view, both in theory and in practice.

The obvious differences are that the target eliminations are not parts of those patterns, and the eliminations are not proved via contradictions but verities. It also means those patterns can be found directly without assuming any target, and they survive after the eliminations (unless cannibal eliminations are included). This has been extensively covered elsewhere, though it has been a very difficult topic for some who are used to seeing everything as contradictions.

Mauriès Robert wrote:I do not understand why the contradiction (invalid track) is badly seen there!

I don't care about what's badly seen or not. My only interest is what each technique allows.

I guess that answers my earlier questioning about why you overuse whips, even though more elegant and readable options would be available.

denis_berthier wrote:
Mauriès Robert wrote:why are whips and braids not used on this forum?

This is an AIC addicts forum. One doesn't take their toys!

Yeah, that's probably the only reason. Or not. There's nothing special about the logic contained in whips and braids, and many players surely use that even here (including myself, as a last resort). You didn't invent it, unless you invented T&E. The real question is: does any manual solver actually find and report their steps as whips and braids? I doubt that, because pretty much any other notation is more intuitive to write and read.

Besides, (at least here) most prefer to report their steps as verities even if they were found as contradictions, giving the presentation a bit more class (though perhaps less honesty). That said, personally I find most of my steps as direct verities, never seeing any contradictions. That's related to this:

AIC guys don't have smarter ways of finding AICs than I have to find whips or braids.

How do you know? That's an interesting claim considering that I haven't seen a single puzzle solved manually by you. I don't think I've seen you even describe a manual procedure to find whips and braids (or anything). It's quite obvious, though. Just assume a target candidate and see if it results in a contradiction. Then write it as a whip, if possible, or otherwise as a braid. (Though probably no one writes them as such, for the reasons explained above.) Or is there a more sophisticated way to find them? I find it hard to imagine. On the other hand, there are definitely more sophisticated ways to find AICs.

Of course the same simple T&E procedure can be used to find AICs etc, and I'm sure some do it exclusively like that. In harder puzzles it might even be the only (obvious) way to proceed. However, in normal levels there are much better ways to do it. Personally I rather find the chains first and let the eliminations come as a side product, using verity logic. Is it smarter?

Yeah, I think so, because it doesn't bind me to a single predefined elimination target, and it gives me verity chains directly without having to reverse-engineer them from contradictions. The process usually gives me several simultaneously available chains and eliminations, from which I can then prioritize whatever seems to fit my current strategy best (shortest solve path / simplest steps / whatever).
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: TDP versus FORCING BRAIDS

Postby denis_berthier » Sat Aug 22, 2020 4:18 am

Again finding cantankerous Space's logorrhoea in some thread. Quite funny when I remember he proposed to be the ambassador of whips. Typical reaction of a dismissed lover turned into a hater ?

Space has already largely proven in his previous posts that he doesn't understand what the confluence property means, so I need not make more comments on this point.

Obviously, he doesn't understand either the difference between a braid and T&E. My fundamental theorem stating that any elimination done by one can be done by the other doesn't imply that they are the same thing. A solution with braids will generally take less than a page. A solution with T&E will take 20 pages and will not give the shortest possible braids when one tries to translate it into braids.

The purpose of a language, be it natural or formal, is to communicate. Prefixing every step of my resolution paths with the name of the pattern involved fits this purpose. (Sure, it doesn't fit the absurd purpose of having the most possible compact illegible notation.)

Symbols in my nrc notation always have the same meaning:
X{x y} always denotes the left-linking and right-linking values for CSP-variable X in a chain.
X{x .} always denotes the absence of a right-linking candidate for the last CSP-variable X of a chain.
— always denotes a direct link between two candidates; the only thing that may change is, in braids, this direct link can be to the target or to a previous rlc (as is announced in the name of the pattern and its definition).

And nothing is hidden: the t- and z- candidates are not part of my chains. But, obviously, one has to read the definitions in order to understand them before criticising them. If a t- or z- candidate disappears during solving, the whip/braid.. containing it is unchanged! (And this is not an abstraction. It is coded this way in CSP-Rules.) There is a very good reason for this: these candidates play no role in the rest of the chain.

Finally, as to which rules appear in the resolution paths, a manual solver can look for whatever type of chains he wants. Similarly, the user of CSP-Rules is totally free to activate whichever intermediate chains (bivalue-chains, z-chains, t-whips) he wants, with or without their typed versions. I've given sufficiently varied versions of resolution paths on this forum.
denis_berthier
2010 Supporter
 
Posts: 3970
Joined: 19 June 2007
Location: Paris

Re: TDP versus FORCING BRAIDS

Postby eleven » Sun Aug 23, 2020 10:34 pm

All i can find about your definition of the confluence property is, what SpAce quoted above, and i (mis)understood in the same way.
So please provide a more precise definition or explanation.
eleven
 
Posts: 3094
Joined: 10 February 2008

Re: TDP versus FORCING BRAIDS

Postby denis_berthier » Mon Aug 24, 2020 2:04 am

eleven wrote:All i can find about your definition of the confluence property is, what SpAce quoted above, and i (mis)understood in the same way.
So please provide a more precise definition or explanation.

The confluence property has been one of my oldest and most useful ideas.
- first definition in [HLS1], May 2007, p. 348
- still in [PBCS2], July 2015, p. 89
It has never changed and it's quite simple:
PBCS2, p. 89 wrote:Definition: a CSP Resolution Theory T has the confluence property if, for any instance P of the CSP, any two resolution paths in T can be extended in T to meet in a common resolution state."


It obviously implies that if an elimination that might have been done by some rule in T is no longer available (because the pattern for this is no longer present), then there must be another set of rules in T able to lead to this elimination.

An equivalent definition is: for any instance P, all the resolution paths in T lead to a unique final resolution state.
denis_berthier
2010 Supporter
 
Posts: 3970
Joined: 19 June 2007
Location: Paris

Re: TDP versus FORCING BRAIDS

Postby SpAce » Tue Aug 25, 2020 1:45 am

denis_berthier wrote:Again finding cantankerous Space's logorrhoea in some thread.

That's underwhelming. I'm disappointed that you couldn't come up with a fresh insult despite your impressive vocabulary. You've now twice in a row used the same fancy word to imply that I have brain damage or a mental illness. That's getting repetitive. (I've been banned for much less but who's counting.)

Misspelling my handle is getting old too. Speaking in third person? Come on, that's not even trying. You should work on your insults to compensate for the lacking arguments.

Quite funny when I remember he proposed to be the ambassador of whips. Typical reaction of a dismissed lover turned into a hater ?

It's taken me this long to respond because I haven't been able to stop laughing after I read that. I didn't know you had such a vivid imagination and a great sense of humor!

Did I lead you on? Did I make you think I was in love with whips (or you)? I'm so sorry! Now I know what it's like to be a woman and accidentally smile at a guy who reads too much into it. This is what I actually said:

SpAce wrote:In fact I find it a bit interesting that you're not exactly eager to help, even though it should be in your own interest. If I learn and happen to like your system, I'll probably start spreading the gospel.

I meant that too. Too bad I haven't found much to like as a manual solver, so looks like I'm spared of missionary duty. That said, it wasn't exactly easy to wade through the heavy smokescreens to be able to pass judgment.

There are two recurring themes that make learning your system very hard. One is that simple concepts are hidden behind very complex theory. The other is that complex logic is hidden behind deceptively simple chains. Both result in massive failures to communicate.

Later I also said this this:

Btw, now that I apparently understand what a whip is, I must say that I really like the name! It's actually very descriptive.

I still like the name, but please don't read too much into it.

Space has already largely proven in his previous posts that he doesn't understand what the confluence property means

What an impressive deduction! I never claimed that I'd understood confluence perfectly. You shouldn't be too proud of that either. If my cognitive skills (and apparently eleven's too) aren't enough to get an accurate picture of such a simple concept, there just might be a bit of a problem with the presentation. (Of course that's not possible; what am I even suggesting?)

Nevertheless, I probably did figure out its practical worth, which is absolutely zero for a manual solver. (If you disagree, I suggest you produce evidence that proves me wrong.) That doesn't mean it's necessarily useless for other purposes, such as rating systems and research.

My focus is solely on manual solving, so anything I say should be understood in that context only, unless otherwise specified. In general, it's obvious that the possible strengths of your system lie elsewhere.

Obviously, he doesn't understand either the difference between a braid and T&E.

You wish. T&E is a procedure to find contradictions, while braids (like whips) are found contradiction patterns. Apples and oranges. You really think I don't understand such fundamental differences? Lol. You can't find any evidence in what I wrote to support such an idiotic conclusion, except by intentionally misreading it (which you seem very capable of when it serves your agenda).

My fundamental theorem stating that any elimination done by one can be done by the other doesn't imply that they are the same thing.

And I never claimed anything else (see above) because I'm not an idiot. In fact, it seems to me that you don't see the boundary quite as clearly yourself.

That said, there's no manually applicable procedure that can find complex braids without applying some form of T&E, so it's fair to say that all of them are products of T&E. They're certainly not patterns that can be just seen in the grid, unless they're simple enough to be seen as something more elegant anyway.

Whatever pattern-matching magic your software might do to find braids directly is inapplicable in manual solving, so don't even bring it up. If you claim otherwise, you're either a genius manual solver or you don't know what you're talking about. I've seen no evidence of the former possibility.

Personally I consider any contradiction step to be a form of T&E, because that's what making an assumption and running into a contradiction is, by definition. I only count directly found verities as non-T&E steps, which means that no braids nor whips could ever qualify.

A solution with braids will generally take less than a page. A solution with T&E will take 20 pages

Now you're comparing apples and oranges yourself. T&E is not a notation, nor does it have any standard one. Thus, that claim makes zero sense.

That said, if a T&E solution is presented in any legible notation, it will surely take more space than the corresponding braid notation. The simple reason is that the latter hides all the details that would make it understandable. That's in direct violation of your own self-righteous claims about the purpose of notation.

and will not give the shortest possible braids when one tries to translate it into braids.

There's absolutely no logical basis for that claim. Since every braid is findable through T&E (and there's no other manual way to find them), it's just a matter of doing it systematically and picking the shortest ones before actually applying them. Thus, a thorough enough T&E process will certainly find the shortest possible braids eventually, though perhaps not as efficiently as your pattern-matching software.

Of course none of that is relevant for a manual solver who'd probably use whatever they find first, or otherwise focus on picking the most effective or elegant steps, instead of obsessing about the shortest ones. It's unlikely that they'd document those T&E eliminations as braids either, unless they're more concerned about saving space or licking your boots than presenting understandable logic.

The purpose of a language, be it natural or formal, is to communicate.

Considering your notations, that's pretty funny.

Prefixing every step of my resolution paths with the name of the pattern involved fits this purpose.

Including the prefix as an optional component just for communication purposes would be ok, but making it actually necessary to interpret a chain correctly is absolutely horrible. It's an architectural flaw that makes the notation complex and brittle.

(Sure, it doesn't fit the absurd purpose of having the most possible compact illegible notation.)

Fortunately your braid and whip notations fill that gap. In both cases, but especially braids, the logic is compacted beyond recognition. I'm a fan of compactness but not when if it's done by removing relevant information and writing links that aren't real. Your chains have no resemblance to what's actually in the grid, and that makes them unreadable.

Symbols in my nrc notation always have the same meaning:

Except the most important one:

— always denotes a direct link between two candidates; the only thing that may change is, in braids, this direct link can be to the target or to a previous rlc (as is announced in the name of the pattern and its definition).

Just a minor foot note. Lol. The only intuitive interpretation of a link a-b is that a and b are linked, but with braids it doesn't necessarily mean that at all. There's simply no excuse for that. Then again, it's obvious that you don't much care about intuitiveness or learning curves anyway. Your only answer to any related criticism is that one has to read the prefix and its definition. Like I said, complex and brittle.

And nothing is hidden: the t- and z- candidates are not part of my chains.

In other words your chains don't contain the full logic, which makes them both unreadable and deceptively simple-looking. Sure, they can be deciphered when one knows the exact rules governing each prefix, but that's exactly what it takes: deciphering.

It's funny that you emphasize the "simplest first" strategy so much, yet the only measures of complexity you use are the prefix and the length. Did it ever occur to you that those t- and z-candidates add a lot of real complexity for a manual solver, and it's impossible to evaluate that just by looking at your chains because the information simply isn't there. That complexity doesn't disappear from the grid even if you hide it in your chains. It's much more relevant than the length.

On the other hand, if you look at a Eureka chain/net, you get immediately a very good idea of the level of complexity and what the chain looks like in the grid. In most cases the logic can be easily traced without even seeing the grid. There's not even a remote chance of that with your tz-chains/whips/braids, because they're so far removed from the grid reality.

If a t- or z- candidate disappears during solving, the whip/braid.. containing it is unchanged!

Sounds like an extremely valuable feature, well-worth sacrificing readability! Just to be sure, that was sarcasm. I can't imagine how that would be relevant for a manual solver at all. I'm guessing it's related to your software optimizations and nothing else.

But, obviously, one has to read the definitions in order to understand them before criticising them.

That (and this whole discussion) reminds me of a classic joke by Ronald Reagan. What's the definition of a communist? One who's read the works of Marx and Lenin. What's the definition of an anti-communist? One who's understood the works of Marx and Lenin.
-SpAce-: Show
Code: Select all
   *             |    |               |    |    *
        *        |=()=|    /  _  \    |=()=|               *
            *    |    |   |-=( )=-|   |    |      *
     *                     \  ¯  /                   *   

"If one is to understand the great mystery, one must study all its aspects, not just the dogmatic narrow view of the Jedi."
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: TDP versus FORCING BRAIDS

Postby denis_berthier » Tue Aug 25, 2020 1:59 am

I have no time to waste answering the same repeated rantings, based on the refusal of any precise definitions.
denis_berthier
2010 Supporter
 
Posts: 3970
Joined: 19 June 2007
Location: Paris

Re: TDP versus FORCING BRAIDS

Postby SpAce » Tue Aug 25, 2020 2:38 pm

denis_berthier wrote:I have no time to waste answering the same repeated rantings, based on the refusal of any precise definitions.

So we're done here? Good. I'm not interested in your evasive non-answers anyway, much less in what comes attached. Thus the following isn't meant for you but for anyone who might not have the slightest idea of what I meant by the hidden information in braids and whips etc. The example is just a simple whip, but it exemplifies the concept pretty well. With braids it's worse.

This is the same whip Robert used as an example:

Code: Select all
.--------------------.--------------------.------------------------.
| 4       569   1268 | 5789   3     15789 |  259    2567    25679  |
| 1237   c359   12   | 6      127  b459   |  8     d2357   a3459-7 |
| 23678   3569  268  | 45789  278   45789 | g3459  f23567   1      |
:--------------------+--------------------+------------------------:
| 1236    346   1246 | 378    5     13678 |  23     9       2378   |
| 123     8     59   | 3479   17    13479 |  6      12357   2357   |
| 136     7     59   | 2      168   13689 |  345    1358    3458   |
:--------------------+--------------------+------------------------:
| 68      46    468  | 1      9     2     |  7     e35      35     |
| 5       12    3    | 78     678   678   |  129    4       29     |
| 9       12    7    | 35     4     35    |  12     68      68     |
'--------------------'--------------------'------------------------'

whip [6]: r2n4{c9 c6} - r2n9{c6 c2} - r2n5{c2 c8} - r7c8{n5 n3} - b3n3{r3c8 r3c7} - r3n4{c7 .} ==> r2c9 ≠ 7

The same written in Eureka just to make it readable for a larger audience:

Code: Select all
whip [6]: (4)r2c9 = (4-9)r2c6 = (9-5)r2c2 = (5)r2c8 - (5=3)r7c8 - (3)r3c8 = (3-4)r3c7 = ! => -7 r2c9

Looks like a very simple contradiction chain, right? However, it's obvious to anyone who looks at the grid that a lot of information is missing, because the links simply can't work as per our normal rules. The only way to interpret it correctly is to know that the whip-prefix implies hidden magic that makes those links work. Without it, it would have to be written explicitly as a contradiction memory chain (for example):

Code: Select all
(7*-4)r2c9 = (4^)r2c6 - (9)r2c6*9 = (9)r2c2 - (5)r2c2^6*9 = (5%)r2c8 - (5=3)r7c8 - (3)b3p8%5*6 = (3)b3p7 - (4)b3p7*6 = ! => -7 r2c9

Now it actually contains the two missing t-candidates (5r2c6, 3r2c8) and three z-candidates (359r2c9). Of course it's ugly as hell, but that's in line with the actual logic so at least it's honest. The full logic can now be read from the chain without even consulting the grid. Btw, it's perfectly reversible too. The actual complexity facing a manual solver is also obvious, giving a much better idea of what it takes to find the elimination that way. Hardly a directly spottable pattern as such, I would say.

The stark difference is easiest to see if the two are compared as matrices (both 6x6 TM):

Code: Select all
 4r2c9 4r2c6
       9r2c6 9r2c2
             5r2c2 5r2c8
                   5r7c8 3r7c8
                         3r3c8 3r3c7
 4r2c9                         4r3c7
====================================
-7r2c9


 4r2c9 4r2c6
 9r2c9 9r2c6 9r2c2
 5r2c9 5r2c6 5r2c2 5r2c8
                   5r7c8 3r7c8
 3r2c9             3r2c8 3r3c8 3r3c7
 4r2c9                         4r3c7
====================================
-7r2c9

One of them is a simple and pretty abstraction. The other is the reality.

As a programmer I fully understand the usefulness of abstractions. Irrelevant information, such as implementation details, should be hidden from public interfaces. That practice provides clarity and ease of use. Most importantly it avoids unnecessary dependencies that would make it very hard to change anything.

In some ways those concepts are true here as well, so I actually understand Denis' intention. It's not a bad idea per se. Problem is, the missing information is NOT irrelevant. It's necessary for the reader to trace the logic in the grid, and it's needed to get an accurate picture of the complexity of the logic. Thus the abstraction, while nice in theory, causes a real loss of information in this case. For me it's too big of a price.

The same exact logic (second matrix) written as an AIC without any loss of (relevant) information:

Code: Select all
(495)r2c269 = (5,3)r27c8 - r23c8 = (34)b3p67 => -7 r2c9

That's actually a pattern that a good manual solver might be able to spot directly. The same is not very likely for the whip, even though both use the same candidates. The difference is that the AIC logic is abstracted into bigger chunks (almost hidden subsets), while the whip is a low-level chain dealing with individual candidates. The latter is an example of how irrelevant implementation details can make it hard to see the big picture. Thus, good abstractions are indeed useful in sudoku as well.

a sidenote: Show
Some people like to hide information on the Eureka side as well, and I don't like it either (though it's not even close to as severe). For example, here's the same elimination as an ALS-XY-Wing:

Code: Select all
(7123=5)r2c1358 - (5=3)r7c8 - (3=25697)b3p12358 => -7 r2c9

Some would write that:

Code: Select all
(7=5)r2c1358 - (5=3)r7c8 - (3=7)b3p12358 => -7 r2c9

While the latter is a fully valid AIC and very neat, it has a couple of problems because the bystander digits are missing. One, it's a bit slower to verify against the grid. Two, it doesn't exactly hide but it makes the complexity harder to see, because at first glance it looks like a basic XY-Wing. That's deceptive simplicity. With the bystander digits included, it's obvious that the pattern is much more complex and way harder to spot for a manual solver, which is more informative. That's why I'm not a fan of the abbreviated style even though (or because) it looks much nicer.

--
Added. Denis, this is actually a friendly suggestion for you. There's obviously an easy way to fix part of the problem. You could simply attach the counts of t- and z-candidates to the prefix, next to the length. For example: whip [6,t2,z3]. That alone would give the reader a much better idea of what to expect, as long as they know what t and z mean. It would also give a natural simplest-first sorting within chains of the same type and length (t being more significant than z). Length alone is a very poor measure of complexity.

It's not perfect, but I think it might be the optimal compromise for your notation. Cluttering the chain with the actual tz-candidates is worse than not having them, at least the way it's currently implemented.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

PreviousNext

Return to Advanced solving techniques

cron