Sunday puzzle (multi steps)

Post puzzles for others to solve here.

Re: Sunday puzzle (multi steps)

Postby mith » Wed Mar 17, 2021 4:45 pm

For the rest of your paragraph, it is based on the view of a chain as a chain of inferences, which a whip is not.


Verification of llc=>rlc at each stage requires some "work" from the reader, namely checking that each candidate not named in the CSP-Variable but still present in the PM is a z or t one.


The rest of my paragraph is simply restating what you yourself have said here. If there is any candidate which is present in the PM but not named or z- or t-, then it is not a complete whip (though it may be a partial whip) - verification will fail.

Further, your "llc=>rlc" here is an inference. It's the equivalent of "If not llc, then rlc", which is true if the other conditions are met (namely that any other candidate for that CSP-Variable is a z- or t- candidate). For that matter, "direct binary contradictions" are inferences, equivalent to "If X, then not Y". You can say the whip is the continuous chain of links absent the inferences, but that's a distinction without a difference to me. At best, the inferences are just hidden in either the general whip elimination theorem or the particular form of the theorem given by the statement of the whip.

Verification of continuity should be trivial for the reader, given the presence of all the candidates necessary to check it. Contrary to what you say, continuity is an essential condition for the manual solver.


Verification of continuity is trivial given the presence of the llcs, yes. Without the llcs, verification is precisely the same amount of "work" as verification that the other candidates are z- or t- candidates. The llcs are linked to the previous (in the case of whips) or a previous (in the case of braids) rlc or Z; z- candidates and t-candidates are linked to a previous rlc or Z. If the latter is "obvious", so is the former. If you gave me a whip without notating the llcs, I would have no more trouble following it than I currently do - you have given me all the information needed in stating that it is a whip and in specifying the CSP-Variables and rlcs, I just have to do the work to verify the links between each candidate present and Z or a previous rlc. (And the same is true of braids; in the case of whips, I simply have the additional information that at least one candidate for each CSP-Variable is linked to the previous rlc.)

(To clarify something I said earlier so there's no confusion: "In the cases where there is both a left-linking candidate and a t-candidate, losing the t-candidate leaves the whip unchanged (since we still have the llc), while losing the llc leaves us with slightly different whip using the t-candidate". This should say "t-candidate which is also linked to the previous rlc; if the t-candidate links to a different rlc, losing the llc would instead become a shorter whip or a braid, depending on what the rest of the whip looked like. Personally, I would consider drawing a distinction between these types of t-candidate - maybe l-candidate for this sort of candidate which is interchangable with the llc - in addition to or instead of the distinction between z-candidates and t-candidates, if such distinctions are necessary at all.)

Beware of approximative language.


Quoting from BUM, emphasis mine:

"A chain is defined as a continuous sequence of candidates, where continuity means that each candidate is linked to the previous one."

"Finally, braids and g-braids allow another type of extension, where the continuity condition is relaxed: in Figure 1.3, imagine that, instead of being linked to the pending candidate R1 for the previous CSP-Variable V1, “left linking candidates” C2,1 and C2,2 for V2 were linked to Z; or that, instead of being linked to the pending candidate R2 for the previous CSP-Variable V2, “left linking candidates” C3,1 and C3,2 for V3 were linked to Z or to a more distant pending candidate, e.g. R1."

It seems to me that braids are relaxing continuity itself, according to the definition you have provided here. Maybe the distinction between "continuity" and "continuity condition" you are making is more rigorously defined elsewhere, but it sure seems blurred here.
mith
 
Posts: 950
Joined: 14 July 2020

Re: Sunday puzzle (multi steps)

Postby denis_berthier » Wed Mar 17, 2021 5:19 pm

I think this summarises all your problems in understanding whips:
mith wrote:"direct binary contradictions" are inferences,

As long as you keep thinking in terms of inferences, you fail to understand the essential points of my approach.
I've been very clear that verifying the whip conditions doesn't involve any inference, direct or not. It involves checking the existence of structural links. Re-read my previous answer.


mith wrote:
Verification of continuity should be trivial for the reader, given the presence of all the candidates necessary to check it. Contrary to what you say, continuity is an essential condition for the manual solver.

Verification of continuity is trivial given the presence of the llcs, yes.

Nothing to add. The presence of the llcs is therefore useful.
For the rest of the paragraph, I've already answered. Read my answer.


mith wrote:
Beware of approximative language.

Quoting from BUM, emphasis mine:
"A chain is defined as a continuous sequence of candidates, where continuity means that each candidate is linked to the previous one."

"Finally, braids and g-braids allow another type of extension, where the continuity condition is relaxed: in Figure 1.3, imagine that, instead of being linked to the pending candidate R1 for the previous CSP-Variable V1, “left linking candidates” C2,1 and C2,2 for V2 were linked to Z; or that, instead of being linked to the pending candidate R2 for the previous CSP-Variable V2, “left linking candidates” C3,1 and C3,2 for V3 were linked to Z or to a more distant pending candidate, e.g. R1."

It seems to me that braids are relaxing continuity itself, according to the definition you have provided here. Maybe the distinction between "continuity" and "continuity condition" you are making is more rigorously defined elsewhere, but it sure seems blurred here.

You're providing the correct citation to show exactly the opposite of what you're suggesting.
If you read it as it is written, it shows the definition of continuity is not changed in braids. The "continuity condition is relaxed" implies there is no longer a single continuous line in a braid.
denis_berthier
2010 Supporter
 
Posts: 3970
Joined: 19 June 2007
Location: Paris

Re: Sunday puzzle (multi steps)

Postby mith » Wed Mar 17, 2021 6:28 pm

denis_berthier wrote:I've been very clear that verifying the whip conditions doesn't involve any inference, direct or not.


You've been very clear in repeating that assertion, yes.

The whip is verified if the conditions (all llc=>rlc are valid, all rlc->llc are valid) are met. The conditions are met. Therefore, the whip is verified.
llc=>rlc is verified if the conditions (all remaining candidates in this CSP-Variable are linked to Z or a previous rlc) are met. The conditions are met. Therefore, llc=>rlc is verified.
7r4c1 and 7r6c2 are linked if they cannot both be true. A digit cannot be true in two cells if those cells are in the same house. r4c1 and r6c2 are in the same house. Therefore, 7r4c1 and 7r6c2 are linked.

These are all inferences. At least for the examples I have seen, any whip is logically equivalent to some (possibly branching) chain of inferences. Maybe there is some value in ignoring that equivalence (which we aren't seeing), or maybe they really aren't always logically equivalence and you have an example of some such whip (in sudoku or otherwise); if the latter, I would be interested to see such a thing.

The "continuity condition is relaxed" implies there is no longer a single continuous line in a braid.


If there is no single continuous line, there is no longer a "continuous sequence of candidates" such that each candidate is linked to the previous one. There is instead of a branching tree of candidates such that each candidate is linked to a previous one. If what you mean is that in both cases there is a connected graph, fair enough; that's not what your definition of chain/continuous sequence/continuity states. "continuous sequence... linked to the previous one" and "instead of being linked to the pending candidate... for the previous CSP-Variable" are at odds as written.

Pedantics aside, this is completely irrelevant to the question of why you have defined continuity on a sequence of candidates vs. a sequence of CSP-Variables vs. a mix. If the only answer is "because it works", fair enough. If the answer is "because it's the only way it works", that's what I would be interested in understanding.
mith
 
Posts: 950
Joined: 14 July 2020

Re: Sunday puzzle (multi steps)

Postby denis_berthier » Wed Mar 17, 2021 6:59 pm

mith wrote:7r4c1 and 7r6c2 are linked if they cannot both be true. A digit cannot be true in two cells if those cells are in the same house. r4c1 and r6c2 are in the same house. Therefore, 7r4c1 and 7r6c2 are linked.
These are all inferences.

Totally irrelevant. n7r4c1 and n7r6c2 are linked in any Sudoku puzzle, because of the definition of a link in the Sudoku CSP. This doesn't require any kind of reasoning. It belongs to the general expression of Sudoku in terms of a binary CSP, i.e. to the structural background of any Sudoku puzzle. This is explained in full detail in [PBCS].

mith wrote: At least for the examples I have seen, any whip is logically equivalent to some (possibly branching) chain of inferences. Maybe there is some value in ignoring that equivalence (which we aren't seeing), or maybe they really aren't always logically equivalence and you have an example of some such whip (in sudoku or otherwise); if the latter, I would be interested to see such a thing.

There can't be any equivalence between two entities of different natures. What I've already said is: a whip is the support for inferences with no OR branching.

mith wrote:
The "continuity condition is relaxed" implies there is no longer a single continuous line in a braid.

If there is no single continuous line, there is no longer a "continuous sequence of candidates" such that each candidate is linked to the previous one. There is instead of a branching tree of candidates such that each candidate is linked to a previous one.

Yes. But the word "branching" is useless. A tree has branching.

mith wrote:If what you mean is that in both cases there is a connected graph,

No. A connected graph is an excessively general structure for describing a braid.
A braid is NOT a chain. It is a sequence of candidates such as...


mith wrote:[Pedantics aside, this is completely irrelevant to the question of why you have defined continuity on a sequence of candidates vs. a sequence of CSP-Variables vs. a mix. If the only answer is "because it works", fair enough. If the answer is "because it's the only way it works", that's what I would be interested in understanding.

The "why" you asked and I answered in terms of "it works" was about my various chains.
For the basic concept of continuity, the answer is much more direct. Links are defined between candidates (indeed, between labels). Continuity is defined in terms of links. So, yes, as far as continuity is concerned, this is the only way it can rationally be defined.
denis_berthier
2010 Supporter
 
Posts: 3970
Joined: 19 June 2007
Location: Paris

Re: Sunday puzzle (multi steps)

Postby AnotherLife » Sat Mar 20, 2021 12:00 pm

creint wrote:
AnotherLife wrote:1. Does the above whip remind you of a single continuous line?
2. Is it easy to construct such a whip by yourself without help from computer programmes?
3. Do the corresponding branches of the whip differ very much from the links of my forcing net (I give this link for the third time: https://disk.yandex.ru/i/rBJo3ttnB5sQeg )?


1,3 no, in my opinion both are forcing nets.
2 no, not for me.

mith wrote:At least for the examples I have seen, any whip is logically equivalent to some (possibly branching) chain of inferences.

I will try to show that any whip can be associated with a forcing net, that is, a series of AICs starting from the target Z and maybe branching at the right-linking candidates of the whip. Moreover, this forcing net is needed to prove that Z is eliminated by the whip. Actually, I meant this from the very start but I was insulted for having a different point of view on whips. As I said before, I am not going to discuss anything with monsieur Berthier until he apologizes to me. Now I am addressing those who are ready to listen to me and respect me.

Let us consider a sequence of variables V1,…,Vn where each Vi can take one value of a finite number (not less than two) of possible values. Suppose that all the candidates of V1 except for R1 are weakly linked to the target Z, and for each Vi, i=2,…,n-1, there exist its candidates Li (left-linking candidate, llc) and Ri (right-linking candidate, rlc) such as Li is weakly linked to R(i-1), and there exist a candidate Ln for Vn such as Ln is weakly linked to R(n-1), the other candidates of Vi, i=2,...,n, being weakly linked either to Z (Z-candidates) or to an Rk, k<i (t-candidates). The sequence V1,…,Vn is continuous in the sense that each Vi, i=2,…,n, is somehow linked to the previous one, but if we take account of all the links between Vi’s and Z, we can hardly consider the whole structure as a continuous line. Rather, it reminds of a net.

Now let us construct this forcing net and prove that this structure actually eliminates Z. Suppose that Z is present. Firstly, let us take one possible value of V1 different from R1 and call it L1, the other candidates of V1 being Z-candidates. Now we have a bunch of AICs of length one starting from Z and ending in one of these Z-candidates. We also have an AIC of length two starting from Z and ending in R1, and this can be written as follows: Z-L1=R1 (we have a strong link because all the Z-candidates have already been eliminated). Let us take some i, 1<=i<n, and suppose that for each Rk, k<=i, we have already constructed an AIC starting from Z and ending in Rk. Now let us consider the possible values of V(i+1). We have a bunch of AICs of length one starting from Z and ending in one of the Z-candidates of V(i+1). For each t-candidate of V(i+1) there exists an Rk, k<i+1, such as Rk is weakly linked to this candidate, and we can continue the earlier constructed AIC to this t-candidate. As L(i+1) is weakly linked to Ri, we can continue the earlier constructed AIC from Ri to L(i+1). If i+1<n then we can continue this AIC further to R(i+1) due to the strong link between L(i+1) and R(i+1). Continuing this process, we will eventually come to the last variable Vn, and all of its candidates will be ends of some AICs starting from Z, in other words, there is no candidate for Vn, so we have a contradiction. This means that Z cannot be present.

The longest AIC of all the ones constructed above will be of length 2n-1, and it can be written as Z-L1=R1-L2=R2-…-L(n-1)=R(n-1)-Ln. Actually, that was the only AIC depicted by monsieur Berthier in his image. I think that he deliberately omitted some important details in order to persuade his audience that his construction is simpler than it really is. I have slightly changed my graphical representation of the whip discussed above to show all the AICs: https://disk.yandex.ru/i/EeLyjDjp2h4Eng
Bogdan
AnotherLife
 
Posts: 192
Joined: 07 January 2021
Location: Moscow, Russia

Re: Sunday puzzle (multi steps)

Postby denis_berthier » Sat Mar 20, 2021 3:54 pm

AnotherName,
If you want to be respected, start by respecting the others. And first by not systematically distorting all that they say.

Why don't you include your images as everybody else instead of forcing people who want to see them to connect to a website that records cookies on our machines without asking permission?
denis_berthier
2010 Supporter
 
Posts: 3970
Joined: 19 June 2007
Location: Paris

Re: Sunday puzzle (multi steps)

Postby eleven » Sat Mar 20, 2021 9:56 pm

Back to the original puzzle, a 1.5 stepper:
Code: Select all
 *-------------------------------------------------------------------*
 |  3      9     8      |  2      14      5     |  7     14    6     |
 |  6      25    15     |a 149    3       7     |  8     124   59    |
 |  4      257   157    |a 19     6       8     |  159   123   359   |
 |----------------------+-----------------------+--------------------|
 | #78     3     4      | #78     5       9     |  2     6     1     |
 |  5      178   6      |a*78-14  12478   124   |  3     9     78    |
 |  9      178   2      |  3      1-78    6     |  4     5     78    |
 |----------------------+-----------------------+--------------------|
 |  17     6     3579   |  1457   1479    134   |  159   8     2     |
 | *128   a58    359    |b#158   *1289    123   |  6     7     4     |
 | #1278   4     579    |  6     #12789   12    |  159   13    359   |
 *-------------------------------------------------------------------*

To avoid the broken wing for 8 in r4c14,r8c4,r9c15 : 8r8c15 = 8r5c4
78r45c4 = 149r235c4 - (1=58)r8c24 - 8r8c15 == 87r54c4 => -14r5c4 [bte] (& 1r6c5 [ste])
eleven
 
Posts: 3094
Joined: 10 February 2008

Re: Sunday puzzle (multi steps)

Postby jco » Sun Mar 21, 2021 12:30 am

Hello,

eleven wrote:Back to the original puzzle, a 1.5 stepper:
Code: Select all
 *-------------------------------------------------------------------*
 |  3      9     8      |  2      14      5     |  7     14    6     |
 |  6      25    15     |a 149    3       7     |  8     124   59    |
 |  4      257   157    |a 19     6       8     |  159   123   359   |
 |----------------------+-----------------------+--------------------|
 | #78     3     4      | #78     5       9     |  2     6     1     |
 |  5      178   6      |a*78-14  12478   124   |  3     9     78    |
 |  9      178   2      |  3      1-78    6     |  4     5     78    |
 |----------------------+-----------------------+--------------------|
 |  17     6     3579   |  1457   1479    134   |  159   8     2     |
 | *128   a58    359    |b#158   *1289    123   |  6     7     4     |
 | #1278   4     579    |  6     #12789   12    |  159   13    359   |
 *-------------------------------------------------------------------*

To avoid the broken wing for 8 in r4c14,r8c4,r9c15 : 8r8c15 = 8r5c4
78r45c4 = 149r235c4 - (1=58)r8c24 - 8r8c15 == 87r54c4 => -14r5c4 [bte] (& 1r6c5 [ste])


Beautiful, elegant solution! applause!

Regards,
jco
JCO
jco
 
Posts: 709
Joined: 09 June 2020

Re: Sunday puzzle (multi steps)

Postby AnotherLife » Fri Apr 02, 2021 12:33 pm

denis_berthier wrote:AnotherName,
If you want to be respected, start by respecting the others.

You know my name. I am Bogdan Grigorenko.
Bogdan
AnotherLife
 
Posts: 192
Joined: 07 January 2021
Location: Moscow, Russia

Previous

Return to Puzzles