The New Sudoku Players' Forum

[Mino21]

Hi P.O.
Is yours an answer to my previous question

About strong link, why OR and not XOR?

?
Anyway sorry, but I don't understand what you mean

[yzfwsf]

Code: Select all

.---------.---------.---------.
| x  x  x | x  x  x | x  x  x |
| x  x  x | x  x  x | x  x  x |
| x  x  x | x  x  x | x  x  x |
:---------+---------+---------:
| 1  1  1 | x  x  x | x  1  x |
| 1  x  x | x  x  x | x  x  x |
| 1  x  x | x  x  x | x  x  x |
:---------+---------+---------:
| x  x  x | x  x  x | x  x  x |
| x  x  x | x  x  x | x  x  x |
| 1  x  x | x  x  x | x  x  x |
'---------'---------'---------'

1r9c1 = r456c1 - r4c123 = r4c8
Your error in the red part.The first half (1r9c1 = r456c1) shows that when r9c1<>1, one of the three cells of r456c1 is 1, but we cannot confirm which cell it is, it may be r4c1, so r456c1 - r4c123 does not hold.That is to say, it is equivalent to you using r4c1=1 ==> r4c1<>1, which obviously contradicts itself.

[eleven]

Hi Mino,

i fear, that your problem is related to what i said in my first answer:
"2) Yes, a strong link also works as a weak link in an alternating chain."

But this is only true for non-grouped links, as i stated here.
Between groups with a common cell a strong link is NOT a weak link too.

Therefore in chains with grouped strong links you have to verify, that a strong link is also weak, when a weak link is requested (in all of these chains consecutive links have to be alternating strong and weak).

About strong link, why OR and not XOR?

For a strong link it suffices, that at least one side must be true (in other words, if one side is false, the other must be true), to be able to prove the eliminations, which a chain gives by it's definition.

[Mino21]

Thanks to all of you for the answers, but at this point I think the problem is my logical approach to x-cycles. it is true that I read something on SudokuWiki, but through the reasoning I tried to give myself an explanation, on which I then based the implementation of x-cycles in C++.
I try to explain what I thought:

Hidden Text: Show

a) only two candidates in an unit imply a strong link and hence the following two logical implications:

Code: Select all

 A => !B
!A =>  B

more than two candidates in a unit imply a weak link and hence the only following logical implication:

Code: Select all

 A => !B

b) a valid loop must have the following characteristics:
- at least 4 nodes;
- at least a weak link;
- at most an even subsequence of consecutive strong links or a subsequence of two consecutive weak links;
- (any number of odd subsequences of consecutive strong links).

c) loop rules (green=true and red=false; arrows indicate the starting point and the direction of the logical inferences):





d) implemented recursive algorithm about x-cycles (not grouped):
- I always start from a strong link, of which a candidate will be the arrival node that closes the loop, while I pass the other to the recursive function that, node by node, tries to build a loop;
- at each recursive call, I first use the information on the part of the loop constructed so far to deduce if the next link can be weak or must necessarily be strong;
- then I derive the type of connection (weak or strong) that I would have in the other units to which the previous node belongs, and check that it is compatible with the result illustrated in the previous point;
- if it is compatible I consider the various candidates in that unit one at a time, and if the candidate considered is not already a node I add it to the cycle;
- at this point if the loop isn't closed I go on with other recursive calls.

Is there something wrong with my logical setting?
As you can see, the whole "strong links working as weak links" issue not only never helped me, but I really didn't know about it. Does not seem to me something indispensable, or am I wrong?

Anyway code I wrote works fine with standard x-cycles, but upgrading to grouped-x-cycles is not trivial and, as already mentioned, the main problem is how to model cases like this:

Code: Select all

     c1  c2  c3 
   +---+---+---+
r1 | x | x | x |
r2 |   | x |   |
r3 |   | x |   |
   +---+---+---+

Specifically why is this wrong?

ignoring singles-nodes cases, we can only have the following 2 cases:

If we have

Code: Select all

     c1  c2  c3 
   +---+---+---+
r1 | x | x | x |
r2 |   | x |   |
r3 |   | x |   |
   +---+---+---+

r1c123 == r123c2

or

Code: Select all

     c1  c2  c3 
   +---+---+---+
r1 | x | x | x |
r2 |   | x |   |
r3 |   | x | x |
   +---+---+---+

r1c123 -- r123c2

and r1c2 is true, we have a contradiction in both the case of strong and weak link, cause the logical inference A=>!B is not respected. Or am I wrong?


As usual sorry for the bad english!

[Cenoman]

About strong link, why OR and not XOR?

I insist: A strong link is equivalent to the logical equation A OR B = TRUE
Note that A XOR B = True => A OR B = True (but the reverse is false !) Hence, A XOR B = True => strong link A = B
(and also, yes, A XOR B = True => A NAND B = True i.e. weak link A - B, but only if A XOR B = True)

Specifically why is this wrong?

Nothing wrong in your case 1, case 2
Just note that, if the blue link is a strong link, that means you are considering an x-cycle rule 2 (following Sudokuwiki presentation), which infers that the node between the two strong links, minirow r1c123 in case 1, minicolumn r123c2 in case 2, is True, other two candidates in the box being eliminated.

If we have

Code: Select all

         c1  c2  c3
       +---+---+---+
    r1 | x | x | x |
    r2 |   | x |   |
    r3 |   | x |   |
       +---+---+---+

r1c123 == r123c2
or

Code: Select all

         c1  c2  c3
       +---+---+---+
    r1 | x | x | x |
    r2 |   | x |   |
    r3 |   | x | x |
       +---+---+---+

r1c123 -- r123c2

and r1c2 is true, we have a contradiction in both the case of strong and weak link, cause the logical inference A=>!B is not respected. Or am I wrong?

You are half wrong:
- wrong for the contradiction in the case of the strong link. Xr1c123 = Xr123c2 is a valid strong link, if you consider the OR operator (and not the XOR)
- right for the contradiction in the case of the weak link. Xr1c123 - Xr123c2 is an invalid weak link, as the two groups are not disjoint (overlap cell r1c2)

The ambiguous strong link r1c123 == r123c2 can be avoided by splitting the nodes as you did in your case 1, case 2 diagrams. The results of the chains built with these will be the same, notably if your blue links are weak links, typically in Empty Rectangle patterns.

[yzfwsf]

b) a valid loop must have the following characteristics:
- at least 4 nodes;
- at least a weak link;
- at most an even subsequence of consecutive strong links or a subsequence of two consecutive weak links;
- (any number of odd subsequences of consecutive strong links).

Strong and weak links must alternate. Because a strong link is not a substitute for a weak link in all cases. If you keep doing it this way, you will make mistakes when you need to add an ALS node.
A==B means that A and B cannot be false at the same time, but can be both true。
A--B means that A and B cannot be true at the same time, but can be both false。
For group nodes, you'd better make sure that they cannot share cells.

[StrmCkr]

The above Case 1 and case 2 do not work
An ERI (empty rectangle intersection) can only act as a weak link for transition of row/col swap
As the box itself is the strong link of row is true or the col is true.

The case your looking for proof of concept is found IN a grouped 2string kite

Code: Select all

 
| X * X | \ \ \ | \ X \
|. X. |
|. X. |
_____
|. /. |
|. X. |.            - X
|. \. |


STRONG ON ROW
WEAK IN BOX
STRONG ON COL
Eliminates peer of solo cell on row and col
If star cell has a candidate then the above dosent work as it being true removes the elimination points

This is true even if you consider the internal box as a strong link.

If your using the box as an internal strong link then the next links must be weak on both row and col


strong-links-weaklinks-t34655.html

[Mino21]

Some doubts certainly remain, but at least now it all starts to make more sense to me!

I insist: A strong link is equivalent to the logical equation A OR B = TRUE
Note that A XOR B = True => A OR B = True (but the reverse is false !) Hence, A XOR B = True => strong link A = B
(and also, yes, A XOR B = True => A NAND B = True i.e. weak link A - B, but only if A XOR B = True)

I do not doubt that the logical modeling with OR (which I should deepen) is correct, simply when I reasoned about the problem I never asked myself which logical equation a strong or weak link was equivalent to, but, as previously said, I have limited to the following simple considerations:

only two candidates in an unit imply a strong link and hence the following two logical implications:

Code: Select all

 A => !B
!A =>  B

more than two candidates in a unit imply a weak link and hence the only following logical implication:

Code: Select all

 A => !B

which were sufficient to define the characteristics of a valid loop, to demonstrate the 3 loop rules and to implement a working algorithm (at least for the single-nodes).
However, while not questioning what you said, I find it quite counterintuitive to associate the strong link with the logical relationship OR, since if there are two candidates in a unit, only one of them can be true, while the other it's false.

Nothing wrong in your case 1, case 2
Just note that, if the blue link is a strong link, that means you are considering an x-cycle rule 2 (following Sudokuwiki presentation), which infers that the node between the two strong links, minirow r1c123 in case 1, minicolumn r123c2 in case 2, is True, other two candidates in the box being eliminated.

Why necessarily a loop rule 2? If after those two consecutive strong links I still have another strong link, I can potentially have a loop rule 1,2 or 3. Am I wrong?

You are half wrong:
- wrong for the contradiction in the case of the strong link. Xr1c123 = Xr123c2 is a valid strong link, if you consider the OR operator (and not the XOR)
- right for the contradiction in the case of the weak link. Xr1c123 - Xr123c2 is an invalid weak link, as the two groups are not disjoint (overlap cell r1c2)

The ambiguous strong link r1c123 == r123c2 can be avoided by splitting the nodes as you did in your case 1, case 2 diagrams. The results of the chains built with these will be the same, notably if your blue links are weak links, typically in Empty Rectangle patterns.

The adoption of the logical relationship OR or XOR obviously implies a different logical modeling, where by "logical modeling" I mean: definition of the characteristics of a valid cycle, demonstration of the 3 loop rules and implementation of an algorithm. At this point what I am wondering is if my logical setting, at least for single-nodes and group-nodes (but not for ALS-nodes (which I don't know yet), according to what @yzfwsf said) is correct and covers all possible cases (in the sense that the algorithm is able to identify all possible valid loops). Isn't it?

Strong and weak links must alternate. Because a strong link is not a substitute for a weak link in all cases. If you keep doing it this way, you will make mistakes when you need to add an ALS node.
A==B means that A and B cannot be false at the same time, but can be both true。
A--B means that A and B cannot be true at the same time, but can be both false。
For group nodes, you'd better make sure that they cannot share cells.

Thanks for the advice, I will take this into account if and when I address ALS-nodes.



@StrmCkr
sorry, but before I answer you I have to go deeper into what you wrote, and for the moment I want to resolve the matter with @Cenoman first.

[eleven]

My answer, which is my last try to make it clearer for you:

"!A => B" is logically equivalent to "A OR B", i.e. the same in different symbols.
So when you just delete "A => !B" it's correct for strong links.

As now often explained, in the sample with a full minirow and -column Xr1c123 = Xr123c2 is a strong link, and if r1c2 is true, then both sides are true.

At least one of 3 consecutive links must be weak, you never can have 3 strong links in a row, where none is a weak link too.

[Cenoman]

Also my last try...
@Mino21,
you have been told by several players in this thread, that the principle of a chain is the alternance of strong links and weak links, the reason why these chains are named AIC (Alternate Inference Chain). Only in their oldest versions, named Nice Loops and X-Cycles you may find consecutive strong or weak links, (not more than one pair, AFAIK)
The AIC version of X-Cycles is much simpler (especially for rule 2, rule 3)

So my advice to you: forget the X-Cycles, forget the consecutive strong links or weaks links (you are going nowhere with these), and switch as soon as you can to AICs. You will see that your recent learnings about strong and weak links are a sound basis for sudoku solving.
Up to a very high level of difficulty, sudoku puzzles are solved with three techniques (together with basics, of course): AICs, fishes and ALSs.

You got answers from players that are the most experimented, each with their own English, which is not always their mother language (e.g. it's not mine). Please don't try to search contradictions between them, you may find some tiny one, but it is wasted time.

[Mino21]

First of all, I still want to thank all of you for your help and for the time you have dedicated to me.

That said, it is still not clear to me IF, WHERE and WHY my logical modeling (as usual with it I mean characteristics of a valid loop, loop rules demonstration and x-cycles algorithm) is wrong.
I would not want to trivialize, but in most of the messages you have limited yourself to suggesting that I move on to AIC's (a topic that I will certainly deepen in the future) or to repeating always the usual mantra, ignoring my point of view on the problem.
Obviously I can't (and don't want to) force anyone to answer me on the merits, so if someone wants to do it, ok, otherwise no problem.

Thanks again!

[StrmCkr]

I answered the question using a x cycle (grouped 2 string kite) to dèmenstrate why an eri cannot be used consecutively as a strong into strong link

Outside of that xcycles still alternate weak - strong.
Elimination rules are constructed based on how the cells end and start..

Loop rules two types
Overlap the end and start are true for x digit then all weak links are false all Strong links are true.
Delete x from cells that see pairs of truths.

End and start dont overlap but are peers of each othet then all weak links are true and strong links are false. Delete x from cells that see pairs of truths. (start and end are ajascent think x-wing)

Basic:
End cells have common peers of start cells peers these are deleted.
There is more rules if you add muti digits like AIC then these rules are slightly modified.

My guess is your error probably occurs from the same line of thought I troubled with for a while till I coded them
that being cells linking might be strongly connected visibly but that's not what's being used!

Most of the issues arrived due to nice loops and x cycles use eureka notatio.n that includes he eliminations as part of the chain to prove the elimination cannot be true as the chain has a contradiction If it is set to true with in the cells listed. Meaning each mini row/col is treated as the link to the next instead of how aics function

Where AIC notation use the cells as a network of truth logic gates where the digit is confined to the chain proving it cannot be found else where.. Ie each gate is the represntation of a sector so that a or b is 2 different mini row/ cols in that house.

See my previous links.

Hope that helps clear the air on them.

[Mino21]

As already said, I don't know the AICs yet, but I will definitely study them in the future. I also want to point out that my goal is not solving sudokus in general, I just enjoy implementing logic problems in C/C++, and sudoku is one of them. So, even if x-cycles are now something out of date, I have started coding them and would like to finish them. To do this I created my own logical approach and honestly I still don't understand if, where and why it is wrong; you probably explained me it in your last post, but I don't think I understand it.

For example you said:

If your using the box as an internal strong link then the next links must be weak on both row and col

but if the following configuration I devised is valid



isn't the highlighted one a valid loop rule 3 (with elimination in r1c7)?

Even if you don't want to prove why my logic is wrong, can you give me an example (i mean a concrete puzzle configuration) of a loop that wouldn't be found with my setting?

[StrmCkr]

X cycles aren't out of date the underlying eureka notation is out of date.

Box 1 to box 7 is actually a weak link
(visually it can look like a strong link but that is not what is used as the LINK)

And the elemination cell r1c7 is weak linked to start (r1c123) and end (R3C9)

Like I said probably doing what I made mistakes with

Eureka notations loop rules include the elimination cell

Constructively (eureka notation is a forcing chain read left to right exclusively)

R1c7 - r1c123 = R23C2 - R8c2 = r9c13 - R9C9 = R2C9 - r1c7
On. Off. On. Off. On. Off. On. Off.

R1c7 cannot be true and false at the same time.

As an AIC.
r1c7 wouldn't be part of it simplifying the rules as this is
discontinuous
r1c123 = R123C2 - R8c2 = r9c13 - R9C9 = R2C9 => r1c7 <> x

Construcivly aics are read left to right and right to left proving that x is contained with in
That's the only difference between AIC and nice loops.

Even if you don't want to prove why my logic is wrong,

I did with the grouped 2 string kite the *, cell in that example would cause no elimination. Your rules would still trigger it.

[yzfwsf]

Assuming the number in your example is 1, the chain below is my solver output.

Code: Select all

Grouped X-Chain: 1r1c123 = r1c7 - r3c9 = r9c9 - r9c13 = r8c2 - r123c2 = 1r1c13 => r23c2,r1c7<>1