The New Sudoku Players' Forum

[ag24ag24]

Many thanks again Denis. I hope you can help me with another question!

I'm trying to fully understand braids (and their variations) and I'm having trouble answering the following question (despite having now read the book that you reference in your previous reply). For context, I am trying to understand the extent to which the power of braids is limited by the requirement that certain sets of candidates should refer to the same CSP-variable, rather than just forming a truth (*** sub-question: is the term "truth" deprecated? I don't see it in your book, and very rarely here.) consisting of candidates all with different variables - which might be the case in, for example, a truth whose members are the guardians of a deadly pattern or a tridagon.

Making the question concrete: suppose we have a system of four candidates c,d,e,f in which {c,d,e} form a truth (i.e. it is known that at least one of them must be true in the completed grid) and each of c,d,e is linked individually to f (i.e. it is known that at most one of {c,f} is true, and likewise for {d,f} and {e,f}), but none of the pairs {c,d}, {c,e}, {d,e} is linked. This system is not compatible with f being true. Can that fact be proved using braids? - or to say it another way, is there a braid representing such a system? I can see that there is if any one of {c,d}, {c,e}, {d,e} is linked, but I can't see it if none of them is.

[denis_berthier]

Hi Aubrey,

For context, I am trying to understand the extent to which the power of braids is limited by the requirement that certain sets of candidates should refer to the same CSP-variable, rather than just forming a truth (*** sub-question: is the term "truth" deprecated? I don't see it in your book, and very rarely here.) consisting of candidates all with different variables - which might be the case in, for example, a truth whose members are the guardians of a deadly pattern or a tridagon.

I formalised the approach of Sudoku as a finite Constraint Satisfaction Problem in [HLS 2007] in the Sudoku context and I generalised the framework to any CSP in [CRT 2010] and in all the subsequent versions of [PBCS]. In this framework, a resolution rule has to be defined based only on the primary concepts of the problem:
- generic ones: CSP-Variables, candidates and links (= direct binary contradictions between the latter);
- and possibly application-specific ones: rows, columns...
Braids (+ whips, t-whips, z-chainns, bivalue-chains and their g- counterparts) are generic chains rules based only on the generic concepts.
Subsets are semi-specific rules based on grid-concepts.
Tridagons are more Sudoku-specific, though a (complex) generic formulation could be written.

Before [HLS], I don't remember seeing the word "Truth" used. And I never use it; it has no place in my approach.
AFAIK, this word was introduced much later by Allan Barker in his set-covering approach, for the main purpose of using a different vocabulary. But, again AFAIK, he never used this word "Truth" to mean any general OR relation. [BTW, you can still occasionally see his approach used in the Puzzles section.]
What was in use before [HLS] (and remained in use for a long time after) was the expressions "weak links" and "strong links". "Weak links" correspond to what I call "links". "Strong links" was very obscure, but could correspond to a general OR relation (depending on people). I don't remember seeing any of these expressions used recently.

Making the question concrete: suppose we have a system of four candidates c,d,e,f in which {c,d,e} form a truth (i.e. it is known that at least one of them must be true in the completed grid) and each of c,d,e is linked individually to f (i.e. it is known that at most one of {c,f} is true, and likewise for {d,f} and {e,f}), but none of the pairs {c,d}, {c,e}, {d,e} is linked. This system is not compatible with f being true. Can that fact be proved using braids? - or to say it another way, is there a braid representing such a system? I can see that there is if any one of {c,d}, {c,e}, {d,e} is linked, but I can't see it if none of them is.

In general, not by braids alone.
In my approach, the resolution rules don't have access to a crystal ball (that would e.g. freely feed them with such a disjunction). Any application of a resolution rule has to be totally justified by what's present in the resolution state at the time when it is applied. The question is, where does the OR relation between your four candidates come from?
In order to deal with such situations, i.e. with OR-relations that could be proven as the result of other (generally non-generic) rules such as Tridagons, I introduced in [UMRN] (https://www.researchgate.net/publication/372364607_User_Manual_and_Research_Notebooks_for_CSP-Rules) parametric generic chains: T-ORk-whips /braids/g.whips... (where T is the pattern allowing to conclude on some ORk relation). The chains themselves are generic, but the parameter T may be application-specific. I've applied them extensively to classify the T&E(3) puzzles.

Note that my original chain rules don't have OR branching. ORk-chain rules introduce some strictly controlled forms of it. The problem of allowing OR branching is one of computational complexity. That's why I allow only one level of OR branching in all my ORk-chains and I reserve them in practice to rare exotic patterns. Note also that I grant ORk-chains a priority that disrupts the normal priorities of the other rules and therefore of all the classifications based on them, which can be justified only because I restrict their use to exotic patterns.
.

[ag24ag24]

Thanks again! Was Barker's set-covering method (which I actually reinvented before discovering him) ever implemented efficiently? My exploration of it only led to algorithms with computational complexity massively dependent on how many truths are needed, and I couldn't find any discussion of software for it.

[denis_berthier]

Was Barker's set-covering method (which I actually reinvented before discovering him) ever implemented efficiently? My exploration of it only led to algorithms with computational complexity massively dependent on how many truths are needed, and I couldn't find any discussion of software for it.

Exponential complexity is a big problem for set covering.
Allan never said anything about his implementation. However, it is clear from our discussions that it was incomplete (he didn't find all the patterns with p truths and q links; and it was somehow based on chains. This allowed him to reduce complexity.
His software was available for Windows only, so I never tried it. I'm sure other people here can tell you more about it.

[champagne]

Thanks again! Was Barker's set-covering method (which I actually reinvented before discovering him) ever implemented efficiently? My exploration of it only led to algorithms with computational complexity massively dependent on how many truths are needed, and I couldn't find any discussion of software for it.

By chance, I met Alan Barker in Bangkok, having first worked with him on his truths/links work.

Alan barker's Xsudo is very good to check what does a truths/links set. He added later the UR threat, a useful tool.
His process to build an active truths/links is all but exhaustive. He had not enough time to spend on the sudoku issues to improve what he had done.

Somehow, he wanted to share his ability to express the truths/links sets in nice charts, what he did

[eleven]

Being on linux, i also never have played with it, but i know from manual solvers, that it is inspiring them, and that you can trust, what it says, though it might not be all, what it could.