The New Sudoku Players' Forum

[denis_berthier]

the z-chain [3]: c8n1{r9 r1} - c8n3{r1 r8} - r9c9{n3 .} ==> r9c8 ≠ 7 of the Denis resolution of this Spiral 8.3 puzzle.
If I write it like this: c8n1{r9 r1} - c8n3{r1 r89} - r9c9{n3 n7} => r9c8 ≠ 7, is this correct from Denis' point of view ?

No, this is not correct in a z-chain: there can only be one rlc for each csp-variable. Notations like r789 are reserved for real g-candidates. Here, it'd suggest it's a g-z-chain.

I ask this question because it seems to me more understandable to the user :
1) to display all the candidates of each CSP variable
2) indicate the candidate that causes the target to be eliminated. Indeed, at the start of the sequence, 3 candidates generate the partial whip [1] : c8n1{r9 r1}.

Again: z- and t- candidates are not part of the whip !!!!!!!!!!!!!!!!!!!
- If a (partial-)whip is identified during resolution, but some z- and/or t- candidate(s) disappear(s) later, it remains the exact same (partial-)whip.
- a (partial-)whip can be drawn exactly as a (partial-)bivalue-chain; once identified, the z- and t- candidates play no longer any role - a very useful property for the manual user.

From someone who doesn't even notate the llcs and csp-varaibles necessary to understand a track, these remarks are quite surprising.

[Mauriès Robert]

From someone who doesn't even notate the llcs and csp-varaibles necessary to understand a track, these remarks are quite surprising.

No, nothing surprising, I try to understand everything so I ask you questions, because for me this z-chain I would write it with an anti-track in this way P'(c8n1r9) : (-c8n1r9) =>c8n1r1->c8n3r89->r9c9n7->... => r9c8 ≠ 7.
By the way, what is rlc, llcs ... we use a lot of acronyms on this forum without ever remembering what they mean !
Robert

[denis_berthier]

From someone who doesn't even notate the llcs and csp-varaibles necessary to understand a track, these remarks are quite surprising.

No, nothing surprising, I try to understand everything so I ask you questions, because for me this z-chain I would write it with an anti-track in this way P'(c8n1r9) : (-c8n1r9) =>c8n1r1->c8n3r89->r9c9n7->... => r9c8 ≠ 7.
By the way, what is rlc, llcs ... we use a lot of acronyms on this forum without ever remembering what they mean !

I published all my chains at least 10 years before your tracks/antitracks. I didn't wait for you to define my notation and I can't see how, with all their ambiguities, your tracks/antitracks could now be a reference to understand it.
BTW, your tracks/antitracks don't make any difference between bivalue-chains, whips, g-whips, S-whips.

rlc = right-linking candidate
llc = left-linking candidate
general whip notation = whip[n]: csp1{llc1 rlc1} — csp2{llc2 rlc2} — ... — cspn(llcn .} => not Z

[Mauriès Robert]

I published all my chains at least 10 years before your tracks/antitracks. I didn't wait for you to define my notation and I can't see how, with all their ambiguities, your tracks/antitracks could now be a reference to understand it.
BTW, your tracks/antitracks don't make any difference between bivalue-chains, whips, g-whips, S-whips.

With such words you get completely lost and it is not the first time. I do not pretend to have any anteriority on your concepts, nor to tell you how you should go about it. When people ask questions, it is to understand, not to give lessons, that's what I do. As my questions seem to annoy you, I won't ask you any more, and believe me, it won't stop me from living!
Robert

[denis_berthier]

for me this z-chain I would write it with an anti-track in this way P'(c8n1r9) : (-c8n1r9) =>c8n1r1->c8n3r89->r9c9n7->... => r9c8 ≠ 7.

When people ask questions, it is to understand, not to give lessons, that's what I do.

It seems you didn't do your homework. A notation for dis^laying z- and t- candidates exists in PBCS. I let you find where.

[SpAce]

Hi Robert,

what is obvious for the creator of a concept is not necessarily obvious for the user.

Indeed.

I take an example to explain myself, with the z-chain [3]: c8n1{r9 r1} - c8n3{r1 r8} - r9c9{n3 .} ==> r9c8 ≠ 7 of the Denis resolution of this Spiral 8.3 puzzle.
If I write it like this: c8n1{r9 r1} - c8n3{r1 r89} - r9c9{n3 n7} => r9c8 ≠ 7, is this correct from Denis' point of view ?

Denis already explained why it's not, but let me add my take on it. First, I completely understand why you would like to write it like that. Originally that would have been natural for me, too, and I had a hard time understanding Denis' chains with obvious group nodes written as single candidates. I also thought that, even if he chose to write them like that, it wouldn't hurt to write them as groups to make them more intuitive for myself. I was wrong.

There's a good reason why that rlc must not be written as a group. As Denis said, it would make it look like a g-z-chain -- a more complex (though officially undefined) type in Denis' hierarchy -- and it's not. Instead, the 3r9c8 is a z-candidate so it can't be part of the rlc. One clear benefit of Denis' system is that it gives an unambiguous idea of (some parts of) the complexity of a chain, and that must not be ruined by ad hoc changes to the syntax even if they seem intuitive.

If a chain has the g- or S-prefix it really means that it can't be written without a group or a subset node (as an rlc), at least with that chain type, which makes it inherently more complex than the basic variant of the same. For you it also means that building the corresponding track would need those basic techniques and not just singles. On the other hand, any chain/whip/braid without such prefixes unfolds with singles only, and Denis' notation corresponds with that. Thus, if you write a group node in a basic z-chain, that correspondence no longer works, because it incorrectly implies that more than singles are needed.

I ask this question because it seems to me more understandable to the user :
1) to display all the candidates of each CSP variable

I completely understand as that's also been my main criticism of Denis' notation. However, I've slowly learned to accept the philosophy behind Denis' choice of abstracting the zt-candidates away. Even so, it's not intuitive or easy to follow without actually running the logic in the grid -- but yours is much harder because it doesn't even have llcs!

That said, I agree that there should be a readable way to optionally add the missing z- and t-candidates to the notation, because it would immensely help learning the idea. The natural place for them would be between the llc and the rlc (instead of to the right as I've seen somewhere). For example:

z-chain[3]: c8n1{r9 r1} - c8n3{r1 r9z r8} - r9c9{n3 n7} ==> r9c8 ≠ 7

for me this z-chain I would write it with an anti-track in this way P'(c8n1r9) : (-c8n1r9) =>c8n1r1->c8n3r89->r9c9n7->... => r9c8 ≠ 7.

Despite a bit of practice I still can't read Denis' coordinates fluently (and probably never will (*)), so I must translate that:

P'(1r9c8) : -1r9c8 -> 1r1c8 -> 3r89c8 -> 7r9c9 => -7r9c8

I agree that with that anti-track you do need the group node. The same with the corresponding AIC:

Grouped M3-Wing: (1)r9c8 = (1-3)r1c8 = r89c8 - (3=7)r9c9 => -7 r9c8

However, note that neither depicts the z-chain (or z-whip) directly. For that you need to use a track or a contradiction memory chain:

P(7r9c8) : ((7r9c8 -> 1r1c8) -> 3r8c8) -> contradiction (r9c9 empty) => -7r9c8

(7*-1)r9c8 = r1c8 - (3)r1*9c8 = r8c8 - (3|*7=!)r9c9 => -7 r9c8

Wouldn't you agree that there's no need to use the group node in either case? If so, then you should understand why it's not correct in the z-chain either.

2) indicate the candidate that causes the target to be eliminated. Indeed, at the start of the sequence, 3 candidates generate the partial whip [1] : c8n1{r9 r1}.

I don't understand this part. The csp-variable c8n1 only has two candidates.

If the whips had been written the way I just did, it would certainly have taken me less time to understand them better!

It may seem so (it certainly did for me originally), but you would have learned them incorrectly. There are ways to make them easier to learn but not this.

--
(*) As I said a long time ago, Denis' csp-variables would be a whole lot easier to read for me (and probably many others) if they were written in the natural nrc-order (instead of rcn), as they originally were:

z-chain[3]: n1c8{r9 r1} - n3c8{r1 r8} - r9c9{n3 n7} ==> r9c8 ≠ 7

That small change is still very much on my wish list. This might be even quicker to read, but it would split some of the csp-variables, so I'm sure Denis wouldn't even consider it:

z-chain[3]: n1{r9 r1}c8 - n3{r1 r8}c8 - {n3 n7}r9c9 ==> r9c8 ≠ 7

[SpAce]

Hi Denis,

z-chains can be seen:
- either as whips with no t-candidate (z-whips); in this view, the notation with a final dot makes sense;
- or as extended bivalue-chains with additional z-candidates in (some of) their csp-variables; in this view, the notation with a final rlc makes sense.

I have no objection if someone adds a final rlc to their implementation of z-chains.

Excellent. I think we're on the same page here.

Talking of implementation, in SudoRules, it would require some minor changes of the implementation of z-chains, implying additional computation and memory: currently, once the final csp and llc are determined, the test is only that all the other candidates for this csp are linked to the target; there's no need to pre-select one of these candidates as the last rlc. Said otherwise, the whip view allows more optimisation.

I get it. I just think it would be natural to call them z-whips when that pov is used, but I can live with z-chains now that I know.

There's no g-candidate in the non-g chains, not even at the end. The reasons are simple: 1) logically wise, they are defined independently of the notion of a g-candidate and 2) implementation wise, they are coded without requiring any implementation of g-candidates.

I understand. My suggestion implied changing the label as well to reflect that it's a g-variant. However, while I was writing my response to Robert I realized why it wouldn't be a good idea even that way. Since the g-complication is not actually needed it's not a real g-variant, and it wouldn't make sense to imply otherwise by using the g-label and -notation.

In other CSPs, g-candidates can be quite complex (see e.g. my whole theory of g-candidates in Kakuro). In Slitherlink, I haven't even implemented them.

Ok. It would be interesting and educational to look at examples of some of the other games you've implemented, and see how the same rules are applied there. I did look at some of the *-Queens examples in the PBCS, and they were very illustrative of the whip[1] concept.

I have defined g-bivalue-chains but I rarely use them. I could have defined g-z-chains, but I didn't because at this point it doesn't make much sense to introduce so many special cases of g-whips.

Ok. But in principle those concepts exist in your framework, as I expected? That's what I wanted to know.

[Mauriès Robert]

Hi SpAce,
Thank you for your detailed comment. I make a global answer by going back to the example I used.
I know very well that the z-chain [3]: c8n1{r9 r1} - c8n3{r1 r8} - r9c9{n3 .} ==> r9c8 ≠ 7 should read in the following order :
n7r9c8=>-c8n1r9=>c8n1r1=>- c8n3r1=>c8n3r8=>- r9c9n3 so r9c9 is empty, and therefore 3r9c8 is not shown
We have the same reading direction as for track P(7r9c8) without 3r9c8 and with the same conclusion.
This is not my concern and I respect Denis Berthier's writing convention.
What I note is that at the base of everything it is first necessary to identify the Z target from which one starts to build the chain. And my question is always the same, which remains without a real answer: "how do you identify a target without testing it?".
This is why I point out that to build the first link of the chain which is a partial whip we have several possible choices Z1=3r9c8, Z2=7r9c8 etc... with all the candidates of r9c8 different from 1, and that if we proceed as I write it in a form "equivalent" to an anti-track we do not choose the target we find it.
If for a chain [3] one can easily visualize the pattern that rests on a target, this is impossible for a long chain and consequently the trials are inevitable, as they are when one invalidates a long track.
Cordialy
Robert

[SpAce]

Hi Robert,

What I note is that at the base of everything it is first necessary to identify the Z target from which one starts to build the chain. And my question is always the same, which remains without a real answer: "how do you identify a target without testing it?".

I can't answer for Denis because I don't know how he does it. Let's figure out instead how I might do it...

Part 1. Non-z-patterns.

First of all, the problem only exists with patterns that have z-candidates, i.e. z-chains and zt-whips/braids. With pure t-patterns (and obviously biv-chains) there's no problem, because the chain can be started and built freely without knowing anything about the eventual target. However, for that to make sense they should be written with an actual end-point instead of a dot at the end.

In fact, I don't see any reason to write or think them as contradictions. As far as I see, any t-whip/braid could be written with an actual end point, just like z-chains and biv-chains, because the final contradiction actually depends on an unwritten z-candidate. Doesn't it? (With zt-patterns that's not necessarily true.) For example:

t-whip[3]: r5c7{n6 n8} - r4n8{c8 c1} - c1n2{r4 .} ==> r5c1 ≠ 6

=>

t-chain[3]: r5c7{n6 n8} - r4n8{c8 tc7 c1} - c1n2{r4 r5} ==> r5c1 ≠ 6

Much easier to understand, imho. I'd save the dots for when they're truly unavoidable, i.e. some zt-patterns with the final contradiction depending on t-candidates only.

Btw, if t-whips/braids are written like that, they're pretty much equivalent to anti-tracks. The basic variants correspond with anti-tracks that are built with singles only, and with the g- and S-extensions they're almost the same (except for the notation). That should tell you how to find them without starting with the target and ending with a contradiction.

Part 2. z-patterns.

This is a more complex problem, but not unsolvable, I think. One could start the chain and deal with any t-candidates normally. However, when some left-linked csp-variable has more than one potential right-linking-candidate (prlc), the chain can't continue as usual. If there are only two such prlcs, one should check if (at least) one of them shares potential targets with L1. If so, that would be chosen as the potential z-candidate (pz1) and the other as the potential rlc (prlc1).

Then the chain would be continued normally using prlc1 as the right-linking-candidate, until some further rlc links to one or more of the same potential targets as L1 and pz1, or a contradiction is found, or a similar bottleneck arises. In the first case, all potential targets linked to L1, Rn, and pz1 become real targets and can be eliminated. If a contradiction is found, then any targets shared by L1 and pz1 become victims.

In the third case one should check if there are any potential targets shared by either of the two new prcls and both L1 and pz1. If so, one is chosen as pz2 and the other as prlc2. Again the chain is continued using prlc2, and so on. At any point the potential targets are limited to those that are linked to L1, all pzs, and possibly Rn.

If the first choice of the rlc/pz roles doesn't yield results, one could backtrack and try them the other way with a different set of potential targets.

--
I have never tried that kind of a procedure, but it seems at least somewhat viable. Of course it has the taste of OR-branching and backtracking, but in a very limited form. If there's more than one branching point, the list of potential targets should narrow down very quickly making the following branching options trivial.

What do you think?
--

PS. Since t-patterns are way easier to find than z-patterns (at least for a manual solver), shouldn't they be before them in the simplest-first hierarchy? The latter are only simpler when started from a particular target, and they're also easier to notate as (nested) AICs. Yet finding them without a locked target is much harder because of the OR-branching.

[denis_berthier]

That said, I agree that there should be a readable way to optionally add the missing z- and t-candidates to the notation, because it would immensely help learning the idea. The natural place for them would be between the llc and the rlc (instead of to the right as I've seen somewhere). For example:
z-chain[3]: c8n1{r9 r1} - c8n3{r1 r9z r8} - r9c9{n3 n7} ==> r9c8 ≠ 7

It seems you didn't do your homework
A notation for the z- and t-candidates exists in PBCS. I let you find it by yourself. As I said before, these candidates are not part of the whip, so using this notation systematically would convey the wrong message.

[SpAce]

It seems you didn't do your homework

Then you didn't read carefully.

A notation for the z- and t-candidates exists in PBCS. I let you find it by yourself.

Oh, I've seen it. I've also said a long time ago that I consider it less readable than not having them at all. Putting the zt-candidates to the right-hand side of the rlc is one of the most unintuitive notations I've seen. Hence my suggestion to put them in the middle. I'm adamant about that, but open to anything else, though I'd prefer to keep them relatively clean and concise.

As I said before, these candidates are not part of the whip, so using this notation systematically would convey the wrong message.

That's why I said: optionally.

[denis_berthier]

A notation for the z- and t-candidates exists in PBCS. I let you find it by yourself.

Oh, I've seen it. I've also said a long time ago that I consider it less readable than not having them at all. Putting the zt-candidates to the right-hand side of the rlc is one of the most unintuitive notations I've seen. Hence my suggestion to put them in the middle.

I agree, it's clearer in the middle.
Considering the example on page 136 of PBCS2, I would now write it as follows, with vertical bars separating clearly the llc and rlc from the rest:

braid[4]: c6n4{r4 r9} – c6n6{r4 r7} – r8c4{n6 |n4#1| n5} – c5n5{r8 |r4* r5* r6* r7#3| .} ==> r4c6 ≠ 5

* still means linked to the target
#n still means linked to the nth rlc

Still keeping in mind that candidates between the vertical bars are not part of the braid and are exceptionally displayed for explanatory purposes only.

[denis_berthier]

here is a minimal spiral:

Code: Select all

+-------+-------+-------+
! . . . ! 1 2 3 ! 4 . . !
! . . 4 ! . . . ! . 5 . !
! . 6 . ! . 4 7 ! . . 8 !
+-------+-------+-------+
! . 4 . ! 9 . . ! 8 . 7 !
! . 9 . ! . . . ! 5 . 3 !
! . . 7 ! . . 4 ! . . 9 !
+-------+-------+-------+
! . . . ! 2 7 . ! . 8 . !
! . 5 . ! . . . ! 9 . . !
! . . 6 ! 3 9 5 ! . . . !
+-------+-------+-------+

Minimal ; SER=8.4
JPF

It has a solution in W4, interesting for beginners in whips and other chains:

Hidden Text: Show

***********************************************************************************************
*** SudoRules 20.1.s based on CSP-Rules 2.1.s, config = W+SFin
*** Using CLIPS 6.32-r779
***********************************************************************************************
singles ==> r3c4 = 5, r1c9 = 6, r8c4 = 4, r7c9 = 5, r9c9 = 4, r7c1 = 4, r7c3 = 9, r5c8 = 4, r5c4 = 7, r2c6 = 9
153 candidates, 801 csp-links and 801 links. Density = 6.89%
whip[1]: r9n8{c2 .} ==> r8c3 ≠ 8, r8c1 ≠ 8
whip[1]: r1n8{c3 .} ==> r2c2 ≠ 8, r2c1 ≠ 8
hidden-pairs-in-a-block: b9{r7c7 r8c8}{n3 n6} ==> r8c8 ≠ 7, r8c8 ≠ 2, r8c8 ≠ 1, r7c7 ≠ 1
hidden-single-in-a-row ==> r8c1 = 7
hidden-pairs-in-a-column: c5{n3 n5}{r4 r6} ==> r6c5 ≠ 8, r6c5 ≠ 6, r6c5 ≠ 1, r4c5 ≠ 6, r4c5 ≠ 1
z-chain[3]: b6n2{r6c8 r6c7} - c2n2{r6 r2} - c9n2{r2 .} ==> r9c8 ≠ 2
biv-chain[3]: c9n1{r2 r8} - r9c8{n1 n7} - b3n7{r1c8 r2c7} ==> r2c7 ≠ 1
biv-chain[4]: r6c4{n8 n6} - c7n6{r6 r7} - r7c6{n6 n1} - c5n1{r8 r5} ==> r5c5 ≠ 8
biv-chain[4]: r7c6{n1 n6} - c7n6{r7 r6} - r6c4{n6 n8} - c6n8{r5 r8} ==> r8c6 ≠ 1
z-chain[4]: r6n5{c1 c5} - r6n3{c5 c2} - r7n3{c2 c7} - c7n6{r7 .} ==> r6c1 ≠ 6
t-whip[4]: r2c9{n1 n2} - r8n2{c9 c3} - r3n2{c3 c1} - r3n9{c1 .} ==> r3c8 ≠ 1
whip[4]: r2c9{n1 n2} - r2c1{n2 n3} - r3c3{n3 n2} - r8n2{c3 .} ==> r2c2 ≠ 1
z-chain[2]: r2n1{c1 c9} - b9n1{r8c9 .} ==> r9c1 ≠ 1
z-chain[4]: c7n6{r6 r7} - r7c6{n6 n1} - c2n1{r7 r9} - c8n1{r9 .} ==> r6c7 ≠ 1
whip[1]: b6n1{r6c8 .} ==> r9c8 ≠ 1
singles ==> r9c8 = 7, r1c8 = 9, r3c1 = 9, r2c7 = 7, r1c2 = 7, r3c3 ≠ 3
finned-x-wing-in-rows: n2{r8 r2}{c9 c3} ==> r3c3 ≠ 2
stte

[SpAce]

It has a solution in W4, interesting for beginners in whips and other chains

Yes, that's a nice example, having specimens of all four of the basic types of chains/whips: biv, z, t, and zt. All found in the same length[4], too, which makes comparisons easier.

[SpAce]

I agree, it's clearer in the middle.

Great!

Considering the example on page 136 of PBCS2, I would now write it as follows, with vertical bars separating clearly the llc and rlc from the rest:

braid[4]: c6n4{r4 r9} – c6n6{r4 r7} – r8c4{n6 |n4#1| n5} – c5n5{r8 |r4* r5* r6* r7#3| .} ==> r4c6 ≠ 5

Much better! I was going to suggest surrounding the zts with [] but || works too. The latter is a bit loaded, however, because it's used as OR in most other notations. I might even consider using no barriers at all, because the location and the markers are enough to identify the role of each candidate without any ambiguity.

* still means linked to the target
#n still means linked to the nth rlc

No problem with that. I was going to suggest z and t instead of * and # just to avoid wondering which is which, because things like that are easy to forget when they're rarely used. However, if the # is always postfixed with n it must clearly be a t-candidate, so there's no ambiguity even with the symbols.

Btw, I would definitely favor a convention of listing the t-candidates first and then the z-candidates to put both closer to their linked partners. In a way the t-candidates are extra left-linking-candidates and the z-candidates are extra right-linking-candidates, so it would be logical to list them in that order. (They're in that order and on different sides of the '=' in AIC-like memory-chains as well.)