The New Sudoku Players' Forum

[denis_berthier]

[about the confluence property]

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. 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.

That's intriguing.

Yes, I know. And I can tell you it has been a shock to me when I first discovered a case of non-confluence, years ago.

Do you have a concrete example of your counter-example in mind?

Probably the most famous example on this forum is UR1:

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.

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

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. That can only happen in some inconsistent views of solving.

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

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.

The good news is, most of the usual rules do not disrupt the confluence property. This includes pointing/claiming (i.e. whips[1]) and Subsets (naked, hidden and super-hidden) and probably most of the aquarium (but I never checked). This also includes properly defined reversible chains, S-braids and B-braids. I have proven all this in detail in PBCS.

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.

[StrmCkr]

Backdoor size three is the largest size we know of with reduction to singles only and size 2 with blr so yes that matches your thoughts. (placing three singles at specific locations breaks the grid to all singles )

Now again in have posted to you examples of how your tdp is exactly. T&E were you follow full chains both both guesses and perform elimination based on both sides being equivalent in eliminations ignoring the identical placements.

Identical placements are also truths from t&e from the bi-local starting choices every example given so far from you can when fully traced shows full solutions and near completed but they are ignored.

Ive also given examples of muti linked starting locations for a digit and how complicated the subbranches would be from finned sword fish or higher

Making tdp even more complicated then the fish logic your saying it replicates, showing that it flukes out via trial and error mimicking other techniques.

But this happens with all forward based logic: construct proves, however elimination wont prove the constructs invalid in all cases.

Everything tdp. Gives is t&e, "memory chains" via twined DFS, via single chains, subsets, aic extensions with cause effect taking into account. Before the next node is used.

Which different then on/off or off/on seen in logic gate constructs and zero semblance to setwise logic.

My 2 sents.

[Ajò Dimonios]

Hi everyone

It is possible to demonstrate that any elimination of a candidate using expert techniques (fish, complex fish, aic, als, chains etc ...) can be obtained with T&E (hypothesis => contradiction => elimination of candidate supposedly true), using only singles, intersections, hidden subsets and naked subsets? The only methodologies that, in my opinion, do not respect this rule are exocets, msls, multifish and sk loops, (which are generally techniques that produce many eliminations simultaneously).

Paul

[denis_berthier]

It is possible to demonstrate that any elimination of a candidate using expert techniques (fish, complex fish, aic, als, chains etc ...) can be obtained with T&E (hypothesis => contradiction => elimination of candidate supposedly true), using only singles, intersections, hidden subsets and naked subsets?

As I have proven in PBCS, a candidate can be eliminated by T&E(T) if and only if it can be eliminated by a T- braid, where T is any set of rules with the confluence property.
So, the answer to your vague question is roughly yes (but the interesting part is the reverse theorem).

[Ajò Dimonios]

Hi Denis_Berthier

Code: Select all

Denis Berthier wrote:

As I have proven in PBCS, a candidate can be eliminated by T&E(T) if and only if it can be eliminated by a T- braid, where T is any set of rules with the confluence property.
So, the answer to your vague question is roughly yes (but the interesting part is the reverse theorem).

If I don't get it wrong, since (singles, intersections, hidden subsets and naked subsets) are rules with the confluence property,
the use of any expert technique that is obtained through the consecutive application of logical inferences related exclusively to the basic technique, see the classic AIC and the fish technique, which produces one or more eliminations can easily be reproduced with an inverse mechanism in which the supposed candidate true always produces, after application of the basic technique, a contradiction. It is clear that when the contradiction produced by T&E is profound, that is, it is obtained after a large number of TB applications, it is practically impossible to translate the contradiction into an expert technique (it is a complex network of inferences). It is like that every single human solver finds a new expert method suitable for that particular candidate. The case in which the technique used (exocet, msls, multifish) cannot be translated into an application of logical inferences linked exclusively to the basic technique is different.

Paolo

[Mauriès Robert]

Hi StrmCkr
Who is your comment addressed to?
If it's to me, I must tell you that I don't understand much of what you want to explain to me, probably because of my bad English and the fact that I use an automatic translator.
Sincerely
Robert
NB: I like to know who I'm talking to, and at least a first name would be more user-friendly. What is yours?

[denis_berthier]

As I have proven in PBCS, a candidate can be eliminated by T&E(T) if and only if it can be eliminated by a T- braid, where T is any set of rules with the confluence property.
So, the answer to your vague question is roughly yes (but the interesting part is the reverse theorem).

If I don't get it wrong, since (singles, intersections, hidden subsets and naked subsets [and fish]) [make a set of rules] with the confluence property,
the use of any expert technique that is obtained through the consecutive application of logical inferences related exclusively to the basic technique, see the classic AIC [], which produces one or more eliminations can easily be reproduced with an inverse mechanism in which the supposed candidate true always produces, after application of the basic technique, a contradiction.

Yes. Eliminations done with AICs or more general chains (whips or braids) with inner Subsets can be done by T&E(S). But, once again, expressing such chain rules as T&E(S) is trivial. The hard and interesting part proven in PBCS, is, one has some converse, i.e. any elimination obtained with T&E(S) can be obtained by using S-braids or S-whips.

It is clear that when the contradiction produced by T&E is profound, that is, it is obtained after a large number of TB applications, it is practically impossible to translate the contradiction into an expert technique (it is a complex network of inferences).

It is so unclear that all the puzzles ever generated by a bottom-up, top-down or controlled-bias generator can be solved by whips.
Whips don't make a complex network of inferences. In particular, they have no OR-branching. And they are not a "network of inferences", they are a logical pattern.
Solving a puzzle with them is not inventing a new technique, it's finding a predefined pattern on the grid - exactly as when finding Subsets.

It is like that every single human solver finds a new expert method suitable for that particular candidate.

Absolutely not. Whips or braids have a universal pure logic definition (and they can be applied much beyond Sudoku).

The case in which the technique used (exocet, msls, multifish) cannot be translated into an application of logical inferences linked exclusively to the basic technique is different.

Yes, very different. Basically, these techniques have never been precisely defined. They involve undefined amounts of hidden reasoning. (For Exocets, however, a real pattern has been introduced, the J-Exocet.)
And don't forget these techniques are called "exotic". Their resolution power is very limited, even if someone here has been trying to oversell them.

[Ajò Dimonios]

Hi Denis_Berthier

Thanks for the explanations and clarifications.

Paolo

[denis_berthier]

Paolo, you're welcome

[Mauriès Robert]

Hi Denis Berthier,

As I told you before in this subject, without really understanding the subtleties of whips and braids, I have been working with TDP to find every step of the resolution of the examples in your book. For me, one question remains. What criteria do you use to determine that such and such a target is targeted first, then second, etc.?
For example, for the puzzle in paragraph 5.10.2 (fig 5.3) what justifies the whip [2] first rather than another.

Sincerely
Robert Mauriès

[denis_berthier]

What criteria do you use to determine that such and such a target is targeted first, then second, etc.?
For example, for the puzzle in paragraph 5.10.2 (fig 5.3) what justifies the whip [2] first rather than another.

The choice is conceptually random (among all the rule instantiations with the same priority). That's why the confluence property is so important: with it, the final result doesn't depend on the choices.

[Mauriès Robert]

Hi,

What criteria do you use to determine that such and such a target is targeted first, then second, etc.?
For example, for the puzzle in paragraph 5.10.2 (fig 5.3) what justifies the whip [2] first rather than another.

The choice is conceptually random (among all the rule instantiations with the same priority). That's why the confluence property is so important: with it, the final result doesn't depend on the choices.

So, if I understand correctly, because of the respect of the confluence property by the whips and the braids, the order of the steps is not important, the important thing being to eliminate all targets to reach the solution.
The same can be said of TDP that step by step exploits the pairs of the puzzle, since the basic techniques used in TDP respect the confluence property.
Sincerely
Robert Mauriès

[denis_berthier]

So, if I understand correctly, because of the respect of the confluence property by the whips and the braids

Actually, whips don't have the confluence property; but they are not far from having it (non-confluence occurs seldom). Braids do have it.

the order of the steps is not important, the important thing being to eliminate all targets to reach the solution.

We could use whips and braids that way. But what I always want is the simplest solution, in the sense that it uses the shortest chains.
So, a priority is assigned to each rule according to the length of its pattern and each step chooses one of the simplest patterns available. Thanks to confluence, assigning priorities doesn't change the final result.

The same can be said of TDP that step by step exploits the pairs of the puzzle, since the basic techniques used in TDP respect the confluence property.

Because the basic techniques have the confluence property, each track is well defined. As for the whole TDP, as it is DFS and it can solve any puzzle, even with multiple solutions, I can't see the point.

[StrmCkr]

Both of you technically, i am agreeing with Denis that tdp is a trial and error process

Ill edit my many typos so its legible.

Track one and track two
Identical solved sells are true from both states
As are eliminations.

You seem ignore the first part, remember singles are 8 eliminations in a cell.
Many of your track grids have a full solved grid and a partial then you use the identical eliminationa of the two.

I remain anonymous by choice i go by strmckr

[Mauriès Robert]

The same can be said of TDP that step by step exploits the pairs of the puzzle, since the basic techniques used in TDP respect the confluence property.

Because the basic techniques have the confluence property, each track is well defined. As for the whole TDP, as it is DFS and it can solve any puzzle, even with multiple solutions, I can't see the point.

Ok, but it is possible to solve the puzzles by limiting the procedures to using only anti-tracks and looking for the shortest length of chain.
This is based on : (see here)
- the definition of an anti-track and its construction procedure using only basic techniques (TB).
- the theorem 1: if a candidate C sees all the candidates of set E generating an invalid anti-track P'(E), C can be eliminated.
- the theorem 2: if a candidate C sees all the candidates of set E generating an anti-track P'(E) and a candidate B of P'(E), C can be eliminated.
All biv-chains, whips and braids can be re-processed with this procedure.
For example, the braid [4] on page 129 of your book is written :
E={7r4c1, 7r2c4}, P'(E) -> invalide (see diagram) => -7r2c1 (th .1)

Code: Select all

      ->2r2c4->2r8c5
    /               \
-E->                 ->2r5c5 => no 2 on C8, contradiction
    \               /
      ->2r4c1->----


and the following whip[2] is written
P'(7r3c1) : -7r4c1->7r3c1->7r2c4->7r9c6 =>-7r4c6 (th. 2)
etc...
Of course the lengths can be different.
Robert