TDP versus FORCING BRAIDS

Advanced methods and approaches for solving Sudoku puzzles

TDP versus FORCING BRAIDS

Postby denis_berthier » Wed Feb 12, 2020 4:31 am

TDP versus FORCING BRAIDS

1) Forcing whips and forcing braids
In section "5.9. Forcing whips and braids, a bad idea?" of my book "Pattern-Based Constraint Satisfaction and Logic Puzzles" (PBCS1, 2012, https://denis-berthier.pagesperso-orange.fr/PBCS/index.html, freely available here: https://arxiv.org/abs/1304.1628), I wrote:

PBCS1 wrote:Consider a bivalue variable (in any resolution state), with its two possible values x1 and x2 corresponding to candidates Z1 and Z2 . Suppose there are two partial whips/braids, say W 1 and W2 , one with target Z1 , the other with target Z2 . In case W1 and W2 share a left-linking candidate L [respectively a right-linking candidate R], L can be deleted [resp. R can be asserted]: this is reasoning by cases, which is perfectly valid in intuitionistic logic. Do we get interesting new patterns this way (to be called forcing whips / forcing braids because they force a conclusion that could not be obtained by a single whip/braid pattern)? Obviously, the answer would be negative for reversible chains: it would suffice to reverse one of the chains and to link the two by the bivalue variable in order to obtain a single chain of same type as the two given ones. Notice that in this process the chain thus obtained should be assigned length n1 + n2 +1, where the ni are the lengths of the two chains.

But as whips and braids are not reversible, it seems one could get new patterns, more general than whips and braids. What is the resolution power of such patterns? We have no general answer. But, in the Sudoku case, if these patterns are assigned length n1 + n2 +1 and given smaller priority than whips/braids of same length, we have found no occurrence in a random sample of 1,300 puzzles. As the memory requirements for such combinations are very high, we did not try on larger samples.

There is still the possibility of starting from trivalue variables and considering three whips/braids instead of two, but complexity increases accordingly."

Remember that, in my approach, bivalue means rc-, rn-, cn- or bn- bivalue, i.e. bivalue or bilocal.

2) TDP theory
As far as I understand it, TDP theory consists of taking two candidates as above, separately applying the T&E procedure to each of them, eliminating the candidates that are eliminated by the two procedures and asserting the candidates that are asserted by the two procedures.

3) The T&E vs braids theorem
In section "5.6. The “T&E vs braids” theorem" of PBCS1, I proved the fundamental theorem for braids:
PBCS1 wrote:Theorem 5.7: for any instance of any CSP, any elimination that can be done by T&E can be done by a braid. Any instance of a CSP that can be solved by T&E can be solved by braids.


4) TDP vs forcing braids
It is an immediate consequence of the above that any elimination/assertion done by TDP can be done by forcing braids (and most of the time by forcing whips)

5) Extension
One can consider T&E(T,1) for any resolution theory T with the confluence property - for instance a theory including subsets. In PBCS1, I have proven corresponding generalisations of the T&E vs braids" theorem.

6) Rating
Whereas TDP, like any procedure based on T&E, doesn't come with any notion of rating, this is inherent in the forcing braids approach. The longest forcing whip [resp. braid] necessary to solve a puzzle defines its FW [resp. FB] rating.

7) Open question
The open question I mentioned in the first point above (Are there puzzles that can be solved by forcing braids but not braids?) remains open. In terms of TDP, it becomes: are there puzzles that can be solved by TDP (based only on singles and elementary contradiction propagation) but not by braids - or: are there puzzles that can be solved by TDP but not by (repeated) T&E? A good place to look for would be in the SER 9.4 to 9.5 zone (puzzles with SER ≤ 9.3 are generally solvable by braids).
I tried a few of the puzzles proposed by Robert in the "puzzles" section, but they are very easy (solvable in W5 or W6) and don't allow any conclusion.
Last edited by denis_berthier on Wed Feb 12, 2020 5:40 am, edited 4 times in total.
denis_berthier
2010 Supporter
 
Posts: 1672
Joined: 19 June 2007
Location: Paris

Re: TDP versus FORCING BRAIDS

Postby Mauriès Robert » Wed Feb 12, 2020 7:08 pm

Hi Denis Berthier,
First of all, thank you for your interest in TDP.
I'm not in a position to answer the questions you ask in your long topic, because I don't master the techniques you expose in your book that I own.
However through the examples that are treated there, I try to find with TDP the steps of resolution that you do with biv-chain, whip and braid.
You write
As far as I understand it, TDP theory consists of taking two candidates as above, separately applying the T&E procedure to each of them, eliminating the candidates that are eliminated by the two procedures and asserting the candidates that are asserted by the two procedures.

This is a bit reductive, as you can see by consulting, if you haven't already done so, TDP's simplified presentation document.
In particular, I draw your attention to two aspects: the anti-track and the extension, because their properties allow to do the same work as the biv-chain, whip and braid.
Thus, the elimination of a target is done with an anti-track, if necessary extended by an extension, using Theorem 2 part 1.
I remain at your disposal to detail this procedure on examples of your choice.
sincerely
Robert Mauriès
Mauriès Robert
 
Posts: 343
Joined: 07 November 2019
Location: France

Re: TDP versus FORCING BRAIDS

Postby denis_berthier » Thu Feb 13, 2020 3:55 am

Mauriès Robert wrote:
denis_berthier wrote:As far as I understand it, TDP theory consists of taking two candidates as above, separately applying the T&E procedure to each of them, eliminating the candidates that are eliminated by the two procedures and asserting the candidates that are asserted by the two procedures.

This is a bit reductive, as you can see by consulting, if you haven't already done so, TDP's simplified presentation document.

What I meant with my description was the essence of TDP. To be clear, I understand that you can use more techniques than the elementary ones I mentioned. But let us stick to those (i.e. Singles and ECP (constraints propagation), without any Subsets). Call it eTDP.
[As an aside, please notice that your general definition including "all the techniques" is meaningless - there is no such set as "all the techniques".
Also notice that, if T is a set of techniques, T&E(T) and therefore TDP(T) may not be unambiguously defined if T doesn't have the confluence property.]

Now, about eTDP, let me reformulate my question without any reference to my chains. You have a solver based on TDP, right? And this solver already includes a T&E subroutine. Can you restrict this solver to eTDP?
Then, do you have any example of a puzzle that can be solved using eTDP but not by using only repeated T&E?

Mauriès Robert wrote:I remain at your disposal to detail this procedure on examples of your choice.

My question was motivated by my vain tries to find a puzzle where forcing braids would be necessary in addition to braids. As a result, I don't have any example that could help answer the previous question. However, as I said before, such examples are most likely to be found in the SER 9.4 to 9.5 range.
denis_berthier
2010 Supporter
 
Posts: 1672
Joined: 19 June 2007
Location: Paris

Re: TDP versus FORCING BRAIDS

Postby Mauriès Robert » Thu Feb 13, 2020 8:01 am

Hi Denis Berthier,
You write:
As an aside, please notice that your general definition including "all the techniques" is meaningless - there is no such set as "all the techniques".

This sentence is inappropriate, I agree, and I prefer to speak of "logical reasoning to respect the rules of sudoku" of which the basic techniques are a part. I'm working on a more rigorous presentation of the TDP than the one from which you got that sentence.

Also notice that, if T is a set of techniques, T&E(T) and therefore TDP(T) may not be unambiguously defined if T doesn't have the confluence property.

Excuse my ignorance, I don't know what the confluence and confluence property you're talking about is? I haven't found the definition of this term in relation to sudoku on the Internet and a little explanation from you would be very useful to answer you.

Now, about eTDP, let me reformulate my question without any reference to my chains. You have a solver based on TDP, right? And this solver already includes a T&E subroutine. Can you restrict this solver to eTDP?
Then, do you have any example of a puzzle that can be solved using eTDP but not by using only repeated T&E?

I don't really understand the meaning of your sentence (translation problem on my part certainly). By "but not only by using repeated T&E" do you mean without making several unsuccessful attempts before finding the right one?

Thank you, Robert.
Mauriès Robert
 
Posts: 343
Joined: 07 November 2019
Location: France

Re: TDP versus FORCING BRAIDS

Postby denis_berthier » Thu Feb 13, 2020 8:24 am

Mauriès Robert wrote:
denis_berthier wrote:Also notice that, if T is a set of techniques, T&E(T) and therefore TDP(T) may not be unambiguously defined if T doesn't have the confluence property.

Excuse my ignorance, I don't know what the confluence and confluence property you're talking about is? I haven't found the definition of this term in relation to sudoku on the Internet and a little explanation from you would be very useful to answer you.

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.

Mauriès Robert wrote:
denis_berthier wrote:Now, about eTDP, let me reformulate my question without any reference to my chains. You have a solver based on TDP, right? And this solver already includes a T&E subroutine. Can you restrict this solver to eTDP?
Then, do you have any example of a puzzle that can be solved using eTDP but not by using only repeated T&E?

I don't really understand the meaning of your sentence (translation problem on my part certainly). By "but not only by using repeated T&E" do you mean without making several unsuccessful attempts before finding the right one?

No. T&E is typically applied to one candidate and it either concludes nothing or finds a contradiction; in the latter case, the original candidate can be eliminated (in the first case, nothing is done). A puzzle can be solved by T&E if a solution can be reached by repeating T&E to all the candidates until it produces no more changes. Notice that a candidate Z1 may have to be tried several times (because eliminations due to other candidates Z2, ... may change the results for Z1).
denis_berthier
2010 Supporter
 
Posts: 1672
Joined: 19 June 2007
Location: Paris

Re: TDP versus FORCING BRAIDS

Postby Mauriès Robert » Thu Feb 13, 2020 10:49 am

Hi,
You have a solver based on TDP, right? Can you restrict this solver to eTDP ?
Then, do you have any example of a puzzle that can be solved using eTDP but not by using only repeated T&E?

I don't have a TDP-based solver, as I'm not a computer scientist, I don't have the skills to develop it and in-fine it's not what I'm interested in. So I won't be able to do the research you're asking me to do.
On the other hand, I have developed with PHP (the only language that I master a little bit) a track tracer. This tracker only uses singles and allows me to find invalid tracks built only with singles.
I didn't go beyond that, because it's enough to exploit TDP.
Indeed, and to make it simple, TDP uses two tracks from two strongly related candidates. Therefore, by using a succession of strongly linked candidates one can build a resolution tree that always leads to the solution of any puzzle, using only singles.
Do you consider this building process to be a process that does not only use repeated T&E, since the repetitions are only done on strongly related candidates?
Robert
Mauriès Robert
 
Posts: 343
Joined: 07 November 2019
Location: France

Re: TDP versus FORCING BRAIDS

Postby denis_berthier » Thu Feb 13, 2020 11:04 am

Mauriès Robert wrote: I have developed with PHP (the only language that I master a little bit) a track tracer. This tracker only uses singles and allows me to find invalid tracks built only with singles.

This looks much like T&E for the starting candidate.

Mauriès Robert wrote:TDP uses two tracks from two strongly related candidates.

This looks much like forcing braids, as I explained in my first post.

Mauriès Robert wrote:Therefore, by using a succession of strongly linked candidates one can build a resolution tree that always leads to the solution of any puzzle, using only singles.

This is where I don't understand. Because forcing braids are not enough to solve all the puzzles.
What do you call a "resolution tree"? Does it imply any recursive construction?
denis_berthier
2010 Supporter
 
Posts: 1672
Joined: 19 June 2007
Location: Paris

Re: TDP versus FORCING BRAIDS

Postby Mauriès Robert » Thu Feb 13, 2020 1:17 pm

denis_berthier wrote:
Mauriès Robert wrote:Therefore, by using a succession of strongly linked candidates one can build a resolution tree that always leads to the solution of any puzzle, using only singles.

This is where I don't understand. Because forcing braids are not enough to solve all the puzzles.
What do you call a "resolution tree"? Does it imply any recursive construction?

It seems to me that building a track is inherently recursive, so is building a resolution tree. But it all depends on what you mean by recursive in the context of what concerns us.

The following diagram simply explains what I mean by a resolution tree derived from two strongly related candidates A1 and A2 and where the candidates connected by || are strongly related in the resolution tree, i.e. taking into account the elements already positioned :

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

Robert
Last edited by Mauriès Robert on Fri Feb 14, 2020 12:06 pm, edited 1 time in total.
Mauriès Robert
 
Posts: 343
Joined: 07 November 2019
Location: France

Re: TDP versus FORCING BRAIDS

Postby denis_berthier » Thu Feb 13, 2020 3:09 pm

OK, this time I understand.
You combine tracks, making successive hypotheses about candidates.
This is DFS - and sure, it can solve any puzzle, whichever number of solutions it has.
denis_berthier
2010 Supporter
 
Posts: 1672
Joined: 19 June 2007
Location: Paris

Re: TDP versus FORCING BRAIDS

Postby Mauriès Robert » Thu Feb 13, 2020 4:41 pm

denis_berthier wrote:OK, this time I understand.
You combine tracks, making successive hypotheses about candidates.
This is DFS - and sure, it can solve any puzzle, whichever number of solutions it has.

What's DFS?
Last edited by Mauriès Robert on Thu Feb 13, 2020 5:14 pm, edited 2 times in total.
Mauriès Robert
 
Posts: 343
Joined: 07 November 2019
Location: France

Re: TDP versus FORCING BRAIDS

Postby denis_berthier » Thu Feb 13, 2020 4:59 pm

DFS : Depth First Search
* choose a candidate; propagate the consequences; * choose another candidate; propagate the consequences; *.... result of each branch is contradiction or solution

* is where the branchings in your tree appear
denis_berthier
2010 Supporter
 
Posts: 1672
Joined: 19 June 2007
Location: Paris

Re: TDP versus FORCING BRAIDS

Postby Mauriès Robert » Thu Feb 13, 2020 5:17 pm

Hi, Thank you for all these explanations.

You haven't answered my question
Do you consider this building process to be a process that does not only use repeated T&E, since the repetitions are only done on strongly related candidates?

That said, I originally described TDP with the aim of offering users (paper or computer players) a simple method of solving that avoids advanced techniques (fishs, wings and other curiosities) and not for solving high level puzzles.
From this point of view, I could have limited myself to a procedure respecting the confluence property you are talking about with only singles. But from a practical point of view this doesn't seem useful to me for users who generally know the basic techniques (single, alignments, closed sets) and whose concern is only to solve.

I then felt the need to formalize a little more this method and I discovered (in a self-taught way) the properties of anti-tracks, which gave the document "Theory of Tracks". A more refined version is in preparation where I became a little more interested in the properties of invalid tracks which leads to prove that a track P(E) from a set E necessarily passes through a candidate of this set with practical consequences. Intuitive but not obvious.

In short, 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, and that consequently I do not understand why the contradiction (invalid track) is badly seen there!

Robert
Mauriès Robert
 
Posts: 343
Joined: 07 November 2019
Location: France

Re: TDP versus FORCING BRAIDS

Postby denis_berthier » Thu Feb 13, 2020 6:10 pm

Mauriès Robert wrote:Do you consider this building process to be a process that does not only use repeated T&E, since the repetitions are only done on strongly related candidates

Now that I understand TDP as DFS, I can answer no. DFS is not equivalent to repeated T&E.

Mauriès Robert wrote: I could have limited myself to a procedure respecting the confluence property you are talking about with only singles. But from a practical point of view this doesn't seem useful to me for users who generally know the basic techniques (single, alignments, closed sets) and whose concern is only to solve.

Don't worry about that: "alignments" and subsets have the confluence property.

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.

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.
denis_berthier
2010 Supporter
 
Posts: 1672
Joined: 19 June 2007
Location: Paris

Re: TDP versus FORCING BRAIDS

Postby Mauriès Robert » Thu Feb 13, 2020 8:48 pm

Thank you for these interesting exchanges from my point of view.
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.
Sincerely
Robert Mauriès
Last edited by Mauriès Robert on Fri Feb 14, 2020 12:08 pm, edited 1 time in total.
Mauriès Robert
 
Posts: 343
Joined: 07 November 2019
Location: France

Re: TDP versus FORCING BRAIDS

Postby SpAce » Fri Feb 14, 2020 1:33 am

Hi Denis,

denis_berthier wrote:[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. Do you have a concrete example of your counter-example in mind? I only know that extra clues can truly break uniqueness patterns and thus make a puzzle harder (for those who accept uniqueness methods). I can't imagine a case where normal solving steps applied in any order would result in the same. 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.)
User avatar
SpAce
 
Posts: 2559
Joined: 22 May 2017

Next

Return to Advanced solving techniques