The New Sudoku Players' Forum

[denis_berthier]

All biv-chains, whips and braids can be re-processed with this procedure.
[...]Of course the lengths can be different

bivalue-chains and whips are special cases of braids. A braid can be mapped straightforwardly to a (small part of a) T&E procedure. It can also be seen as a (small part of a) track ending in a contradiction.
To give you an idea of the difference, a full solution with braids typically takes less than a page; a full solution with T&E will take 20 pages. Moreover, given a full solution with T&E, you can always delete the useless steps and turn the rest into braids, but even after doing so, what you'll get will almost never be the shortest possible braids; in particular, it will not give you the B rating.

[Mauriès Robert]

Hi Denis Berthier,

To give you an idea of the difference, a full solution with braids typically takes less than a page; a full solution with T&E will take 20 pages. Moreover, given a full solution with T&E, you can always delete the useless steps and turn the rest into braids, but even after doing so, what you'll get will almost never be the shortest possible braids; in particular, it will not give you the B rating.

Something escapes me then, because with the TDP procedure explained in my previous post I can reconstruct any of your resolutions with Braids, step by step, therefore with the same number of steps.
I repeat two questions that I have already asked you in another context:
- Do you consider this TDP procedure outlined in my previous post as T&E?
- What logical principle determines the choice of a candidate to be eliminated by Braid (or whip or biv-chain)?
Thank you for your answers and patience,
Sincerely
Robert

[denis_berthier]

To give you an idea of the difference, a full solution with braids typically takes less than a page; a full solution with T&E will take 20 pages. Moreover, given a full solution with T&E, you can always delete the useless steps and turn the rest into braids, but even after doing so, what you'll get will almost never be the shortest possible braids; in particular, it will not give you the B rating.

Something escapes me then, because with the TDP procedure explained in my previous post I can reconstruct any of your resolutions with Braids, step by step, therefore with the same number of steps.

Of course. Starting from braids, I can also produce a short T&E solution. But starting with T&E, there's no reason I'd get the shortest braids.
Replace T&E with tracks and repeat the same answer. In addition, a solution with TDP may lead to sequentially combined tracks, which can't be translated into any braid.

I repeat two questions that I have already asked you in another context:
- Do you consider this TDP procedure outlined in my previous post as T&E?

I think I have already answered. Building a track is close to doing T&E. TDP combines tracks in a "resolution tree" that makes TDP identical to DFS.
TDP has OR-branching and this is totally alien to any of "my" chains.

- What logical principle determines the choice of a candidate to be eliminated by Braid (or whip or biv-chain)?

I think I have already answered also. The choice is random, with a priority given to short patterns: take the simplest (shortest) patterns available and choose randomly among them.
AFAIK, there has never been any accepted smart way of choosing a candidate for consideration. In my experience, preference for bivalue/bilocal candidates is rarely a good choice.

[Mauriès Robert]

Hi Denis Berthier,
Thank you again for the answers and exchanges that have been interesting for me.
In summary, I will make a general comment.
I don't understand all the subtleties of your braid theory well enough to establish all the differences and similarities with the TDP. Your theory is complex for me, who am not a logic specialist like you.
Nor am I sure, with all due respect to you as an eminent scientist (without any sycophancy), that you have fully grasped my conception of PDT. The proof of this is that, at the end of the day, you view the TDP as a DFS. To me, DFS is only one part of the TDP, the TDP contains several types of procedures, as does your theory.
However, what I take from our discussions is that T&E is a procedure that tests all the candidates in the puzzle until no elimination is possible. From this point of view, neither your theory nor the TDP can be reduced to T&E as some people say on this forum.
In fact, for many sudoku "theorists", T&E is simply testing a candidate at random to see what he or she leads to and consider this to be TDP. I imagine they also consider that this is what you do with the braids, which you say "there has never been any accepted smart way of choosing a candidate for consideration".
These same theorists reject the idea of contradiction as a logical means by hiding behind established models (fish, wings and other curiosities) that contradiction has precisely demonstrated! In doing so, the expression of their models by AICs is generally a procedure of (hidden) contradiction, judging by the examples discussed in the "Puzzles" section. Where is the error!
In the end, what is important for me is that a resolution theory correctly poses its concept, properties and methods, and that it is, from a practical point of view, easy to use. I think the TDP meets that definition.
Sincerely.
Robert

NB: I am not sure that my text in English translates exactly what I express in French.

[denis_berthier]

Nor am I sure [...] that you have fully grasped my conception of PDT. The proof of this is that, at the end of the day, you view the TDP as a DFS. To me, DFS is only one part of the TDP, the TDP contains several types of procedures, as does your theory.

By DFS I mean generalised DFS, as it is usually understood, where two successive choices of hypotheses (candidates) are separated by propagation of constraints. In TDP, propagation of constraints is done along "tracks". Using constraints propagation lowers the depth of DFS. My conclusions are based on your examples below. If there is more to this in TDP, I'm open to learning more.

Code: Select all

                     ->D1---- Contradiction
                   /   ||
          ->B1->---    ||     
        /   ||     \   ||
       /    ||       ->E1---- Solution
A1->---     ||     
       \    ||       ->F1---- Contradiction
        \   ||     /   || 
          ->C1->---    ||         
                   \   ||
                     ->G1---- Contradiction

                   
          ->B2->--- Contradiction   
        /   ||     
       /    ||       
A2->---     ||     
       \    ||       ->F2---- Contradiction
        \   ||     /   || 
          ->C2->---    ||         
                   \   ||
                     ->G2---- Contradiction


Obviously the tree may have more branches than in the diagram depending on the difficulty of the puzzle and may be more asymmetrical.

In terms of scoring, each path can be scored as a product of paths :
P(A1).P(B1).P(D1) contradiction
P(A1).P(B1).P(E1) solution
etc...

For example, here is an AI-escargot resolution tree from 9r6c2 and 9r5c1 :
P(9r6c2).P(4r5c3) contradiction
P(9r6c2).P(3r5c3).P(5r1c2) contradiction
P(9r6c2).P(3r5c3).P(5r2c1).P(8r6c7) contradiction
P(9r6c2).P(3r5c3).P(5r2c1).P(8r6c7) contradiction
P(9r6c2).P(3r5c3).P(5r2c1).P(17r6c7).P(2r3c8) contradiction
P(9r6c2).P(3r5c3).P(5r2c1).P(17r6c7).P(3r3c8) contradiction
P(9r6c2).P(3r5c3).P(5r2c1).P(17r6c7).P(4r3c8) contradiction

P(9r5c1).P(5r2c1).P(2r1c3) solution
P(9r5c1).P(5r2c1).P(8r1c3) contradiction
P(9r5c1).P(5r1c2).P(4r1c47) contradiction
P(9r5c1).P(5r1c2).P(4r1c359).P(1r6c9) contradiction
P(9r5c1).P(5r1c2).P(4r1c359).P(5r6c9) contradiction

In this example, DFS goes to depth 5. But simple T&E needs only depth 2. And T&E(B2) needs only depth 1. For me, this is a big negative point.

However, what I take from our discussions is that T&E is a procedure that tests all the candidates in the puzzle until no elimination is possible. From this point of view, neither your theory nor the TDP can be reduced to T&E as some people say on this forum.

Some people on this forum are unable to have any rational argument and without having any definition of T&E, they use it as disguised insult. But you're lucky: the worst of them have left. My recommendation: don't waste your time arguing with FlatEarthers.

In fact, for many sudoku "theorists", T&E is simply testing a candidate at random to see what he or she leads to

I don't think anyone reduces T&E to this. At the end of T&E(one candidate), either a contradiction is reached and the candidate is eliminated or no conclusion is reached or a solution is reached. In the latter two cases, nothing is done (accepting the solution would be guessing).
In a full T&E solution, this elementary procedure has to be repeated for each remaining candidate until no state change can be obtained. If you want a more detailed definition, read it in PBCS. I don't think I invented the definition there; I just formalised what people called T&E before.
I don't know anyone today that could seriously challenge my definition of T&E.

"there has never been any accepted smart way of choosing a candidate for consideration".

This sentence applies to T&E or to any chain pattern.
AIC guys don't have smarter ways of finding AICs than I have to find whips or braids.

These same theorists reject the idea of contradiction as a logical means by hiding behind established models (fish, wings and other curiosities) that contradiction has precisely demonstrated! In doing so, the expression of their models by AICs is generally a procedure of (hidden) contradiction, judging by the examples discussed in the "Puzzles" section. Where is the error!

Subsets, Fish, AICs are perfectly valid patterns and proof by contradiction is perfectly valid, even in intuitionnistic logic. The advantage often advocated for Subsets, Fish or AICs is not how they are proven. It is reversibility and I accept this as some advantage over my oriented chains. But the main associated disadvantage is their limited solving power, as proven in PBCS. One more disadvantage is, due to the restricted solving power, people tend to include unrestricted inner patterns, making the resulting chain totally illegible, which is emphasised by the awful AIC notation. One further disadvantage is, nobody has ever come with some substantial theory for these reversible chains. As far as I know, the only proof of reversibly for AICs with inner Subsets is in PBCS; this is more subtle than one might think because this entails dual views of Subsets and their links to the chain.

In the end, what is important for me is that a resolution theory correctly poses its concept, properties and methods, and that it is, from a practical point of view, easy to use.

I'd add two more points:
- it should be pattern-based
- it should make it possible to assess its resolution power - which I have done in very detailed ways for all my rules and which has never been done with AICs.

I think the TDP meets that definition

It also passes the resolution power assessment (all the puzzles).
But if fails the pattern-based additional point.

[Mauriès Robert]

Hi Denis Berthier,
You write

In this example, DFS goes to depth 5. But simple T&E needs only depth 2. And T&E(B2) needs only depth 1. For me, this is a big negative point.

I don't think you've seen my post from February 13th that says:

One result that may be of interest to you is the following:
The depth of a TDP resolution tree is defined by the maximum number of products in the branch construction. The explanation diagram I gave you is a resolution tree with a depth equal to 3. The AI-Escargot tree has a depth of 5.
I am in relation with a person who has developed a solver with TDP and who has established empirically (conjecture) that all puzzles would be solved with trees of depth 3 maximum. You wrote, I believe, that T&E(2) would also suffice.
We also define the solving size of a puzzle which is the number of branches of a tree that leads to contradiction. The solving tree of the above AI-Escargot puzzle with depth 5 corresponds to a size of 11.
I do not believe that there is a correlation between the two quantifications.

The AI-Escragot resolution tree represents the smallest known TDP resolution size and not the smallest possible depth.
One question: have you solved AI-Escargot with braids?
Sincerely
Robert

[denis_berthier]

The depth of a TDP resolution tree is defined by the maximum number of products in the branch construction. The explanation diagram I gave you is a resolution tree with a depth equal to 3. The AI-Escargot tree has a depth of 5.

Did I say anything else?
[Edit] I tried my old DFS procedure on Escargot. Solved at depth 5 without any optimisation.
Depth of DFS is extremely dependent on the order the successive candidates are tried. Finding the smallest possible depth for a puzzle would require trying an undefined number of arrangements.

One question: have you solved AI-Escargot with braids?

Of course not, and nobody will ever solve it with ordinary braids, because it is not in T&E(1). It requires B2-braids.
And the hardest known puzzles require B7-braids - much harder than any snails from Inkaka.

[Mauriès Robert]

Hi Denis,
If I understand the notion of whip well enough, it is not the same for the braids whose writing logic still escapes me in part. So I want to ask you a question about that.
You wrote this in the subject AIC and TDP :

.... whips, braids, g-whips, g-braids, S-whips, S-braids, W-whips and B-braids correspond to pure AND networks. Forcing-whips and forcing-braids correspond to mixed networks, with OR-branching only at the start.

Let's take as an example the case of the puzzle discussed in pargraph 5.10.1 on page 128 of your PBCS book and consider the following braid on page 129 :
braid[4] : r2c4{n7 n2} - r4c1{n7 n2} - c8n2{r2 r5} - c6n2{r5.} => -n7r2c1

Here's how I interprate the writing of this braid:
If we delete n7r2c4, then we place 2r2c4 AND, we eliminate n7r4c1 so we place n2r4c1 OR we eliminate n2r4c1 so we place n7r4c1 .
- If we place n7r4c1, we eliminate n7r2c1.
- If we place n2r4c1, we continue the development of the chain (which partially becomes a whip) to arrive at a contradiction, i.e. n7r2c4 should be placed and therefore n7r2c1 should be eliminated.
In both cases n7r2c1 is eliminated. CQFD.

If my reasoning is a good interpretation of the writing of this braid, it highlights the use of the OR contrary to what you claim.
Where is my reasoning flawed?

Sincerely
Robert

[denis_berthier]

Let's take as an example the case of the puzzle discussed in pargraph 5.10.1 on page 128 of your PBCS book and consider the following braid on page 129 :
braid[4] : r2c4{n7 n2} - r4c1{n7 n2} - c8n2{r2 r5} - c6n2{r5.} => -n7r2c1
Here's how I interprate the writing of this braid:
If we delete n7r2c4, then we place 2r2c4 AND, we eliminate n7r4c1 so we place n2r4c1 OR we eliminate n2r4c1 so we place n7r4c1 .
- If we place n7r4c1, we eliminate n7r2c1.
- If we place n2r4c1, we continue the development of the chain (which partially becomes a whip) to arrive at a contradiction, i.e. n7r2c4 should be placed and therefore n7r2c1 should be eliminated.
In both cases n7r2c1 is eliminated. CQFD.
If my reasoning is a good interpretation of the writing of this braid, it highlights the use of the OR contrary to what you claim.

This is not the right way of reading a braid. The right way is to start from the target (n7r2c1) and to follow the logical structure of the braid to reach a contradiction:
n7r2c1 -> -n7r2c4 => n2r2c4 -> -n7r4c1 => n2r4c1 -> -n2r2c8 => n2r5c8 -> -n7r2c1 and no remaining possibility for cn-cell c6n2.
(I've used different implication symbols here to show what people call weak and strong implications, but logically speaking they are the same logical implication.)
The conclusion is: if n7r2c1 was true, then we'd reach a contradiction. Therefore, n7r2c1 is false and this candidate can be retracted.
There is no OR-branching anywhere: there is never any possibility that a => symbol concludes that two candidates remain possible for the relevant CSP-Variable and that two different cases must be considered (one for each of them).
There is AND-branching however, because the 2D-cells enclosed in curly brackets may contain more candidates (z- and t- candidates) than those displayed; and these candidates are made impossible by the target or by the previously positively asserted ones. So an implication displayed as "-n7r2c4 => n2r2c4" may in reality mean "not n7r2c4 and not some-other-nxr2c4 => n2r2c4", where some-other-nxr2c4 may be discarded because it is linked to the target or a previously positively asserted candidate.

Notice that the braid elimination theorem has been proven once and for all; no one has to re-prove it every time a braid is found. The presence of a braid-pattern allows the elimination of its target, in the same way as the presence of a Subsets allows some eliminations that no one has to prove again.
My above explanation is just a special case of the general proof that you can find in PBCS - which is quite trivial.
Alll this also apply to whips; the only difference in whips is the continuity property (see PBCS) that makes less simpler.

[Mauriès Robert]

Thank you Denis for these explanations.
But then, if I understand well, braid being a logical structure associated with a target, the principle of use consists in choosing a target and looking for a braid structure associated with it. If this structure is highlighted we eliminate this target, otherwise we change target.
If this is the case, I do not see much difference in procedure with that of TDP which consists in choosing a candidate (target) and constructing the track coming from this candidate (track which is a logical structure) which if it leads to contradiction eliminates this target.
Cordially
Robert

[denis_berthier]

Thank you Denis for these explanations.
But then, if I understand well, braid being a logical structure associated with a target, the principle of use consists in choosing a target and looking for a braid structure associated with it. If this structure is highlighted we eliminate this target, otherwise we change target.
If this is the case, I do not see much difference in procedure with that of TDP which consists in choosing a candidate (target) and constructing the track coming from this candidate (track which is a logical structure) which if it leads to contradiction eliminates this target.

Mmmm That's what I've been saying since the beginning, where "not much difference" can't be changed into "no difference". To be precise:
- whips/braids don't exist as patterns
- what exists as patterns is whips[n] or braids[n], for any n; said otherwise, a whip/braid always has some pre-defined length
- whips/braids constitute a hierarchy for a universal rating system
- whips/braids don't contain all the possible inferences available form the target, only the useful ones
- contrary to a whip/braid, a track is not a logical structure in the sense of "a pattern". It is a net of inferences, which makes it identical to T&E. Of course, there's a relation between braids and T&E, as per my braids vs T&E theorem. But this doesn't mean they are the same thing.
- a whip/braid is defined by a logical formula; a track and T&E are defined by a procedure.

[Mauriès Robert]

Ok Denis, I have to work on your book again to understand this difference motive/procedure.
Thank you for your patience in answering me.
One last question: why are whips and braids not used on this forum?
Robert

[denis_berthier]

why are whips and braids not used on this forum?

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

[Mauriès Robert]

Hello Denis,
I choose this thread to ask you a question about what you call procedures (T&E, DFS), among which I assume you include TDP, which are not resolution rules.
Do you consider what are called advanced techniques (fishs, wings, etc...) to be procedures or resolution rules.
Maybe you have already answered such a question, but if you have, I haven't found the related comment.
Cordially
Robert

[denis_berthier]

Do you consider what are called advanced techniques (fishs, wings, etc...) to be procedures or resolution rules.

The techniques you mention are not particularly advanced.
All the classical Subsets - Naked, Hidden or Super-Hidden (i.e. Fish) - and the Finned, Sushi, Sashimi Fish are resolution rules. You can see most of them in HLS and in PBCS (in a more general setting).