The New Sudoku Players' Forum

[SpAce]

Code: Select all

                       ...or.....................or.......
                     /                        /           \or
6r1c2<= -6r3c2<= -4r3c9 <= .............. -2r2c9 <= -1r2c7 <= -7r2c8 <= -7r7c6 <= -4r8c6 <= -4r9c2
                    \                           / or                          /
                     \         <= -6r4c7 <= -79r19c7                         / or
                      \       /                                             /
                       <= -4r4c4 ...........................................


Excellent! As far as I see it matches my diagram, but is more convincing because it does the reversal in-place.
--

So, can we all finally agree that all correctly written chains and nets, regardless of their complexity and manner of expression, are in fact bidirectional? I see no logical reason how the opposite could be true, and no irrefutable counter-example has been presented either. Thus the myth that bidirectionality is somehow a special superpower reserved for AICs only is now busted, as far as I'm concerned. AICs have other advantages but this is not one of them.

The main reason why AICs seem more bidirectional than implication chains is that the latter are usually written without the negative implications, which makes reversal harder. If they're included, there's no difference at all:

Code: Select all

a = b - c = d => a|d

<=>

(a|b) & -(b&c) & (c|d) => a|d

<=>

-a -> b -> -c -> d => a|d

<=>

a <- -b <- c <- -d => a|d


All four expressions contain exactly the same amount of information and can be converted into each other at will, so they're logically equivalent. The symmetrical look of the AIC just makes it seem more bidirectional. Yet it's actually more correct to say that the AIC has no concept of direction at all because the links represent ORs and NANDs (depicted on the second line) instead of implications. It becomes directional only when mentally converted into an implication chain, and then it's no different from any other implication chain -- they all work both ways.

[SpAce]

Hi Robert,

Thank you for your many explanations and the diagrams below very readable for me.

Glad to hear they worked for you!

So I was wrong!

Well, you're not the only one -- but you might be the only one who'll ever admit it! I respect that a lot. It's pretty rare in these woods.

In fact, I'd be really impressed if Gordon did the same -- not for me but for himself. His habit of unquestioning parroting of "authorities" (most recently Phil) is a prime example of what I was talking about here:

Unfortunately some of his most loyal followers have picked up those half-truths at face value and continued spreading them as gospel.

I really wish that no one will ever see me as such an authority that they fail to question what I say, though there's probably no such fear anyway. I also wish that I will never become so arrogant that I would see such questioning as anything but welcome.

Arrogance and fear of losing face are enemies of learning and improvement. So is blind trust in authority figures and established "truths". I try to avoid them all like the plague. In fact, I'm truly grateful when someone manages to convince me that I'm wrong, because it's an opportunity to learn something profound that I've been blind to.

[denis_berthier]

Code: Select all

                       ...or.....................or.......
                     /                        /           \or
6r1c2<= -6r3c2<= -4r3c9 <= .............. -2r2c9 <= -1r2c7 <= -7r2c8 <= -7r7c6 <= -4r8c6 <= -4r9c2
                    \                           / or                          /
                     \         <= -6r4c7 <= -79r19c7                         / or
                      \       /                                             /
                       <= -4r4c4 ...........................................


Excellent! As far as I see it matches my diagram, but is more convincing because it does the reversal in-place.
--
So, can we all finally agree that all correctly written chains and nets, regardless of their complexity and manner of expression, are in fact bidirectional?

No. If everything is reversible, then "reversible" doesn't mean anything.

I see no logical reason how the opposite could be true, and no irrefutable counter-example has been presented either. Thus the myth that bidirectionality is somehow a special superpower reserved for AICs only is now busted, as far as I'm concerned. AICs have other advantages but this is not one of them.

There's only one way out of all the nonsense around reversibility: define a pattern to be reversible if the reversed pattern belongs to the same family, as I do in PBCS.
xy-chains, bivalue-chains, g-bivalue-chains, basic AICs, AICs with inner whips[1], AICs with inner Subsets, AICs with inner whips[1] and innerSubsets, are reversible in this sense. (The latter three cases are not obvious at all, in particular how to define the reversed patterns, but I've proven all this in detail in PBCS.)

Whips, braids, g-whips, g-braids, S-whips, S-braids, W-whips, B-braids, forcing-whips and forcing-braids are NOT reversible in this sense.

Now, about about general networks of inferences.
The main point about such a network is whether it is an AND, an OR or a mixed network. When considering forward inferences, an AND network is much simpler than an OR or a mixed network. An AND network corresponds to a single stream of reasoning. An OR network corresponds to reasoning by cases.
As an aside, all the above mentioned non-reversible patterns (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.
There is a permanent confusion on this forum and often a deliberate will to obliterate the difference between AND and OR networks.

AND-networks become OR-netwokks after reversion (and conversely). So, neither AND- nor OR- networks are reversible.
Mixed networks (which are the most complex of all) are obviously reversible in my sense - which suddenly makes the property of being reversible, even as restricted as I made it, much less enticing in and of itself, if a pattern is not further restricted by other properties.
The natural further property that comes to mind is: no OR-branching (but this must somehow be further refined, so that for instance inner g-candidates or inner Subsets are not consider as OR-branching).


After these necessary preliminaries aimed at clearing the background, let's go back to the topic of this thread. What about TDP? After the discussion in the tdp-versus-forcing-braids thread (http://forum.enjoysudoku.com/tdp-versus-forcing-braids-t37379.html), it appears that TDP is basically DFS (Depth-First-Search, with propagation of constraints between two choices of candidates before deepening the search). Obviously, DFS relies on a mixed network (but it is not a pattern).
As a result, TDP can be said reversible, but obviously not in the positive sense usually associated with this word.
DFS is the fastest known algorithm for solving a puzzle and, as such, it is very important in Sudoku (especially when generating puzzles). But I can hardly see it as a basis for the type of pattern-based resolution that most players are looking for. A player usually doesn't want to use T&E. DFS cumulates the disadvantages of recursive T&E and those of OR-branching.

[Mauriès Robert]

Hi Denis Berthier,
Nothing to say about the aspects of reversibility that you comment on, but I'll comment on the next point.

What about TDP? After the discussion in the tdp-versus-forcing-braids thread (tdp-versus-forcing-braids-t37379.html), it appears that TDP is basically DFS (Depth-First-Search, with propagation of constraints between two choices of candidates before deepening the search).

No, TDP is not essentially DFS, it's reductive. The notion of anti-track and the properties that come with it allow you to solve a lot of puzzles, including all the ones you can solve with biv-chains and whips, even some that require braids. Nothing to do with DFS.
Certainly for very difficult grids, the notion of a solving tree that you assimilate to DFS becomes indispensable.
Cordially
Robert Mauriès

[denis_berthier]

What about TDP? After the discussion in the tdp-versus-forcing-braids thread (tdp-versus-forcing-braids-t37379.html), it appears that TDP is basically DFS (Depth-First-Search, with propagation of constraints between two choices of candidates before deepening the search).

No, TDP is not essentially DFS, it's reductive. The notion of anti-track and the properties that come with it allow you to solve a lot of puzzles, including all the ones you can solve with biv-chains and whips, even some that require braids. Nothing to do with DFS.
Certainly for very difficult grids, the notion of a solving tree that you assimilate to DFS becomes indispensable.

It seems you're playing on words when you speak of TDP. Sometimes, it's only tracks and anti-tracks and sometimes it includes your search tree.

Tracks and anti-tracks are forms of T&E. Using them simultaneously may lightly increase the resolution power of T&E (in the same way as forcing braids may increase the power of braids), but I have no example of this and, apparently, neither do you.
T&E can solve almost all the puzzles. There are only 1/70,000,000 puzzles requiring T&E(2) (estimate from Eleven).
So, it's no wonder that you don't actually need DFS after T&E in most cases.

And it's no wonder that you can solve all the puzzles with your "solving tree", because DFS can. Why do I say that your search tree is basically DFS? I answered in the other thread. You provided a very clear search tree (with OR branching). And when such a tree needs to go to depth 5 for a puzzle like Escargot, exactly like my rudimentary DFS procedure, there is little room for another interpretation.

[Mauriès Robert]

Hi Denis Berthier,
You write

It seems you're playing on words when you speak of TDP. Sometimes, it's only tracks and anti-tracks and sometimes it includes your search tree.

No, I'm not playing with words, I simply consider TDP as a "whole" based on a principle (PR): if we place some candidates and/or eliminate others on a G0 puzzle (hypothesis H) and apply so-called basic solving techniques (TB), we obtain a G1 puzzle which, depending on the case, is valid or invalid. Defining a track (H=placement only) or an anti-track (H=eliminations only) amounts to this.
From then on, it is possible to establish properties (theorems) linked to this principle that allow to solve a puzzle by modulating H.
I agree that track and anti-track are two procedures that are not independent, since placing candidates means eliminating others. But both procedures, on a practical level, can be more or less easy to implement. That is why I am presenting them separately.

At this point, I'm not mentioning the notion of a resolution tree (DFS for you) at all, and if I stuck to this presentation of TDP we wouldn't say it's DFS. Unless you consider a single branch to be a tree!
Then, to go further in the resolution capabilities, OR is used by defining the extension of a track (or antitrack) which I note P1.P2 based on the same principle (PR). This makes it possible to realize bifurcations like for example the one in this diagram of a track coming from A1 :

Code: Select all

         ->B1->B2
       /          \
A1->A2              ->A3->A4
       \          /
         ->C1->--


Should I consider it a DFS?
Ultimately, the resolution tree is not the most useful part (in practice) of the resolution method I propose, hence my reaction that calling TDP as DFS is reductive. You see, I use the term method here so as not to risk saying that TDP is a resolution theory.
Sincerely
Robert Mauriès

[denis_berthier]

Hi Robert,
I didn't mean you were deliberately playing with words, but there is an ambiguity.

OR is used by defining the extension of a track (or antitrack) which I note P1.P2 based on the same principle (PR). This makes it possible to realize bifurcations like for example the one in this diagram of a track coming from A1 :

Code: Select all

         ->B1->B2
       /          \
A1->A2              ->A3->A4
       \          /
         ->C1->--


Should I consider it a DFS?

Basically, yes.
I don't see by which stretching of meaning, the word "extension" could be used to refer to the OR branching part. You make two different hypotheses (in addition to the first hypothesis for the first track) and you explore each of them according to PR. At the point of the branching, you are not using PR.
There are several ways in which you could explore the resulting search tree. What makes me say you use DFS is the depth you reach in your examples.

[Ajò Dimonios]

Goodmorning everyone

I have always thought, as described in various publications, that the reversibility of AICs is linked to the demonstration that alternating strong inferences with weak inferences in a logical chain that begins with a strong inference and ends with a strong inference proves that the head and the tail of a chain are always tied together by a strong inference.This example raises my doubts: 200381005853906000009052380000008057005000408680500000526190800000800500308205001

Code: Select all

                     - - - - - - - - - - - - - -                 
                   /     /                        \
-6r1c2->6r3c2->4r3c9->2r2c9- - - - - - - - ->1r2c7->7r2c8->7r7c6->4r8c6->4r9c2
                   \                      /                     /
                    \         >6r4c7>79r19c7                   /
                     \      /                                 /
                       >4r4c4- - - - - - - - - - - - - - - - -



In this case the chain shows that there is a strong link between 6r1c2 and 4r9c2 (6r1c2 = 4r9c2) which leads to the elimination of r1c2 = 4. The conclusion is certainly correct but in my opinion the logic that starts from r1c2 = 6 false which leads to r9c2 = 4 true is not correct since being the anti-track P '(6r1c2) an invalid track it is possible to arrive, always with logic formally corrected to establish that when r1c2 = 6 is false then r9c2 = 7 is true and consequently r9c2 = 4 is false. In fact, when building a track invalidates the results obtained depend on the order in which the inferences in the chain are applied. In this case, in fact, it is possible to arrive at a different conclusion, for example it is possible to demonstrate that when r1c2 = 6 is false, we arrive at the conclusion that r9c2 = 7. The result is that the proof is incorrect even if the conclusion is correct. It is true that r1c2 = 6 is strongly linked to r9c2 = 7 or r9c7 = 4, generating the eliminations of 4 and 7 in r1c2, but in my opinion not for the logic of the chain but simply because the anti-track P '(6r1c2) is proves invalid and consequently it is true r1c2 = 6. My question at this point is follow it: Is it correct to use a logical chain that starts from an incorrect premise and justify the correct conclusion as due to the logical chain, while it is certainly due to the wrong premise?

[Mauriès Robert]

Hi Paolo,
I know very well what you are talking about since it concerns the invalid leads (or anti-runways) that I have studied.
But I prefer you to give a simpler example with an AIC so that the answer to your question is not related to TDP.
For example with tarek puzzle of the following 12/02:
4.......7.2..8..4..79...31..4..2..3.1.......2..61.47....32468...6.7.8.5..........
Clement uses the following ACI :
(6=85)r4c41 - (5=7)r7c1 - (7=96)r75c8 => - 6r5c4,r4c7; stte
With TDP notations, the equivalent of this AIC is written as
P'(6r4c4) : -6r4c4->8r4c4->5r4c1->7r7c1->9r7c8->6r5c8 => - 6r5c4,r4c7; stte
This AIC and this anti-track P'(6r4c4), are chains of contradiction, both of which raise your question.
Sincerely
Robert

[Ajò Dimonios]

Hi Robert,

Code: Select all

[code]
+----------+------------+------------+
| 4  58 58 | 3  6   1   | 29  29  7  |
| 3  2  1  | 9  8   7   | 5   4   6  |
| 6  7  9  | 4  5   2   | 3   1   8  |
+----------+------------+------------+
| 58 4  7  | 68 2   59  | 169 3   19 |
| 1  39 58 | 68 7   359 | 4   69  2  |
| 2  39 6  | 1  39  4   | 7   8   5  |
+----------+------------+------------+
| 57 15 3  | 2  4   6   | 8   79  19 |
| 9  6  24 | 7  13  8   | 12  5   34 |
| 78 18 24 | 5  139 39  | 126 267 34 |
+----------+------------+------------+

P'(6r4c4) : -6r4c4->8r4c4->5r4c1->7r7c1->9r7c8->6r5c8 => - 6r5c4,r4c7; stte



(6=85)r4c41 - (5=7)r7c1 - (7=96)r75c8 => - 6r5c4,r4c7; stte



It is true in this example it is easier to explain what I said in the previous post. The AIC : (6 = 85) r4c41 - (5 = 7) r7c1 - (7 = 96) r75c8 => - 6r5c4, r4c7; stte
 it is a chain of contradiction. In this case, the demonstration that a strong inference exists between r4c4 = 6 and r5c8 = 6, practically that at least one of the two candidates is true, is also invalidated in this case by the first inference that starts from a false premise r4c4 ≠ 6. It is clear that the chain that starts from a false premise leads to a true conclusion r5c8 = 6. It is useful to highlight that both r4c4 = 6 and r5c8 = 6 are backdoors. That there is a contradiction in the chain is evident because from the same premise I can build a chain that shows that if r4c4 = 6 is false then r5c8 = 6 is also false: (6r4c4 = r4c7-6r5c8). So even in this case I repeat the question from the previous post. Is it correct to use a logical chain that starts from an incorrect premise and justify the correct conclusion as due to the logical chain, while it is certainly due to the wrong premise?


Sincerely
Paolo

[Mauriès Robert]

Hi Paolo,
You ask the following question:

So even in this case I repeat the question from the previous post. Is it correct to use a logical chain that starts from an incorrect premise and justify the correct conclusion as due to the logical chain, while it is certainly due to the wrong premise?

For me, it is correct to write a logical chain that starts from a "possibly" erroneous postulate such as the "supposed" elimination of a candidate. But if the postulate turns out to be actually wrong, the conclusion must be justified by the invalidity found.
But others will doubtless not agree with me and the debate will be open.
Sincerely
Robert