The New Sudoku Players' Forum

[Mauriès Robert]

Hi Denis,

The problem is probably you haven't yet understood that the start of a chain is not a target, but a partial-whip[1] pattern - which is not more complex than intersections - and that the continuity condition plays a major role in simplifying the extensions.

and

I already told you to read the Basic User Manual for a graphical description of whips, partial-whips and t-whips.

So I got your "Basic User Manual" which I didn't know, and indeed the whips and partial whips are explained very clearly in it in addition to the very theoretical definitions in your book.
However, this does not enlighten me on "how is Z chosen without trying"?
An example to make me understand, with the 999b puzzle of mith, after the RS1 state of your resolution and after the t-whip [6] :

puzzle RS1: Show

A partial whip can be defined with the CSP variable V1=1b3 for 3 potential targets, Z1=1r1c3, Z2=1r1c4 and Z3=1r1c5. For the 3 Zi the extension with V2=1c6 is possible, as well as the extension with V3=1r6, only Z1 will lead to a result but this is seen after the partial t-whip [2] has been built. There is therefore "a priori" the problem of the choice of the target, therefore of the test for see.
If on this example of t-whip [3], this choice of Zi is "visually" easy, it becomes much more critical with longer t-whips. Hence my question: how to choose the target without testing?
Cordialy
Robert

[denis_berthier]

how to choose the target without testing?t

Every player will have his own strategy for choosing what to try first. Some will try candidates in bivalue-cells; some will try candidates that seems promising to them. There's no general rule.

[Mauriès Robert]

how to choose the target without testing?t

Every player will have his own strategy for choosing what to try first. Some will try candidates in bivalue-cells; some will try candidates that seems promising to them. There's no general rule.

Yes, I thought so, but how does Sudorules do it? Even if I understand the strategy of "simplest first", there is a moment when Sudorules is also confronted with the problem of choice, that is to say the problem of trying things out.
Robert

[denis_berthier]

how to choose the target without testing?t

Every player will have his own strategy for choosing what to try first. Some will try candidates in bivalue-cells; some will try candidates that seems promising to them. There's no general rule.

Yes, I thought so, but how does Sudorules do it? Even if I understand the strategy of "simplest first", there is a moment when Sudorules is also confronted with the problem of choice, that is to say the problem of trying things out.

SudoRules doesn't have any problem of choice: simplest-first strategy means it applies the first rule it finds among the simplest ones applicable (which, for all practical purposes, means it chooses randomly among the simplest rules applicable).
And this has no impact on the solution, for resolution theories (i.e. sets of rules) that have the confluence property (or almost have it).

[SpAce]

Hi Denis,

Thanks for the clarifications. Unfortunately I still don't have much time to think them through, so a minimal response at this time.

Logically, there'd be no difference between Naked or Hidden Singles.

That's true in the 3D point of view because any single can be viewed as either type depending on the chosen space. Thus the nakedness or hiddenness of a single is not a significant difference per se. Yet a naked single in the rc-space is not the same as a naked single in any other space, because there are no box-boundaries in the n-axis. It makes no practical difference with actual singles because they intersect with all the other constraints around them, but it does make a huge difference with almost-singles.

An almost-naked-single (2+ candidates in an rc-cell) can't intersect with anything as a unit so it can't be a whip[1]. Only (almost-)almost-hidden-singles are capable of that in the rc-space, because up to three candidates in a row, column, or box can be fully contained within a box boundary. That difference obviously remains if we switch spaces -- it just looks different because one half of the box boundaries are within the cells in the nr- and nc-spaces.

Singles are not included in the definition of whips. The definition requires a precise pattern.

Why aren't they included, and what in the definition excludes them? For example:

whip[1]: c7n6{r5 .} ==> r6c9 ≠ 6

That implies a claiming in box 6, due to 2-3 locked 6s in r456c7. However, I don't see why it couldn't mean a hidden single in r5c7 just as well. If that whip[1] is written as a 1-fish, there's no way to tell:

(6)c7\b6 => -6 r6c9 (or using my version of set logic notation: {6C7 \ 6b6} => -6 r6c9)

That Cyclopsfish would be true whether there's 1, 2, or 3 candidates of 6 in c7, as long as they're all in rows 4-6 (i.e. in box 6). I would expect the whip[1] to work the same way, but looks like it only works for cases 2 and 3. Why? (A side question: why is it a whip[1] instead of a z-chain[1]?)

[denis_berthier]

Hi SpAce,
As there's no almost-anything in my approach, all that you say about it is irrelevant.

Singles are not included in the definition of whips. The definition requires a precise pattern.

Why aren't they included, and what in the definition excludes them?

In the definition, whips have lengths ≥ 1. So, there must be a target z and at leat one csp-variable csp1, with a llc1, and the other conditions trivially imply that csp1 cannot be a csp-variable for z.
Why don't I define whips of length 0? Because it's useless!

[SpAce]

As there's no almost-anything in my approach, all that you say about it is irrelevant.

I'm just translating your terminology into something more people here would understand. You must have noticed that many of us use "almost" quite a bit.

In the definition, whips have lengths ≥ 1.

Check. length = 1

So, there must be a target z

Check. z = n6r6c9

and at leat one csp-variable csp1

Check. csp1 = c7n6

with a llc1

Check. llc1 = n6r5c7

and the other conditions trivially imply that csp1 cannot be a csp-variable for z.

Check. c7n6 is not a csp-variable for n6r6c9

--
As far as I see, none of your listed conditions are violated even if n6r5c7 is a single in c7. What am I missing?

Why don't I define whips of length 0? Because it's useless!

For the same reason I'm not talking about whips of length 0.

[denis_berthier]

As far as I see, none of your listed conditions are violated even if n6r5c7 is a single in c7. What am I missing?

I didn't check the details. But even if they are correct, what does it prove? That one can use a hypersonic missile to kill a fly?
What you're probably missing is the simplest-first strategy.

[SpAce]

As far as I see, none of your listed conditions are violated even if n6r5c7 is a single in c7. What am I missing?

I didn't check the details.

I guess I have to answer my own question, then I wasn't necessarily missing anything, but the Basic User Manual was. It doesn't state the complete rule for whips[1], allowing a wider interpretation:

The whip[1] rule: if a candidate Z is linked to all the remaining candidates for a CSP-Variable V1 (which implies that Z is not a candidate for V1), then Z can be deleted.

By that definition alone, eliminations by singles could be considered whips[1]. However, the PBCS has this extra condition:

Vn has no candidate compatible with Z and with all the previous right-linking candidates (but Vn has more than one candidate – this is a non-degeneracy condition).

That does exclude singles because in those cases Vn (=V1) has only one candidate. So, we can agree that your official definition of whips doesn't include singles, but it's only because of that extra rule preventing "degenerate" patterns.

But even if they are correct, what does it prove? That one can use a hypersonic missile to kill a fly?

No. For one, it's about reading definitions as they're written and seeing what they actually include and exclude. The whip[1] definition in the BUM is not accurate because it would include singles, contradicting the PBCS. You may think it should be obvious anyway, but it isn't. Whips would work just as well if singles were included, but I guess it would be inconsistent with your generally non-polymorphic type hierarchy.

What you're probably missing is the simplest-first strategy.

It shouldn't have anything to do with this. Coupling pattern definitions with a specific strategy is a violation of the SoC principle. Furthermore, having singles included in whips[1] wouldn't preclude from using the simplest-first (or any) strategy in any way. It would just require a slightly more fine-grained and polymorphic type hierarchy, which would actually improve the simplest-first strategy among other things.

--
All of that said, I'm not advocating such drastic changes at all. I just wanted to explain where my POV came from. I don't have a problem with the PBCS definition of whips. The problem was the incomplete one in the BUM.

[SpAce]

Hi again Denis,

Now that we agree that singles are not whips (or any chains in your system), I still have this open question about the real whips[1]:

A side question: why is it a whip[1] instead of a z-chain[1]?

I'll get back to that question below, but first something about z-chains since they're related. I hope you understand that I'm definitely not trying to irritate you in any way, even though I'm revisiting the risky labeling/notation topic. I'm really glad we can finally have civilized conversations, and I'd like to keep it that way. I'm genuinely trying to understand the naming logic of your chains, so humor me.

Some time ago I asked why z-chains weren't called z-whips despite the whippy notation (ending with a dot), or alternately why they weren't written with a chainy notation (having both end-points). That discussion didn't end well, and instead of an answer I got a ban. So, I stopped worrying about it (just like about the funny banning policies) and accepted it as a fact of life. However, now that I looked for the whip definition I happened to notice this:

In particular, a z-chain with a global loop would merely be a z-whip.

What? Now I'm really baffled. So, there are actual z-whips and they're different from z-chains? Where is their definition? Only z-chains seem to be defined in the PBCS, but that definition surprised me as well:

Definition: in a resolution state RS, given a candidate Z (which will be the target), a z-chain of length n (n ≥ 1) built on Z is a regular chain (L1, R1, L2, R2, .... Ln, Rn) associated with a sequence (V1, ... Vn) of CSP variables, such that:
– Z does not belong to {L1, R1, L2, R2, .... Ln, Rn};
– L1 is linked to Z;
– for any 1 ≤ k < n, Rk is the only candidate for Vk compatible with Z, apart possibly for Lk;
– Z is not a label for Vn;
– Ln is the only candidate for Vn possibly compatible with Z (but Vn has more than one candidate – this is a non-degeneracy condition); in particular Rn is linked to Z.

Now that looks exactly like I would imagine a z-chain should -- with an actual Rn instead of a dot. That would put it in the same category with biv-chains, both having actual end-points that are linked to the target, and both being reversible (even by your tighter definition). Those labels and notations would be in sync.

Why don't the current z-chains look like that? Why do they have a dot at the end, which makes them look like whips instead of chains? Did the z-whips actually look like the z-chains do now?

I asked those same questions last time (except for the last one because I didn't know z-whips even existed), with known results. Now it looks to me that they were even more legitimate questions than I thought, since at some point in time (at least when that edition of the PBCS was published) you apparently have fully agreed with my vision of the proper combinations of labeling and notation. Back then z-chains looked like chains (based on that definition), and I would imagine that the (undefined) z-whips looked like whips.

What happened? When did you start writing z-chains with the z-whip notation and why?

I can easily see that both z-chains and z-whips would be redundant, and it's better to keep just z-chains. What I don't understand is why you notate them like whips, especially now that I've seen that it's not how the PBCS defines them.

--
Back to my question at the top. Based on the newly discovered fact that z-whips have actually existed, and probably in the same form as the current z-chains, I might rather ask: why is it a whip[1] instead of a z-whip[1]? (I've understood that mere 'whip' is a synonym for 'zt-whip' instead of a generic label for all kinds of whips, but I could be wrong.)

Obviously whip[1] can't have any t-candidates, so it can't be either a zt-whip or a t-whip, which leaves only z-whip. Furthermore, since presumably all z-whips can be written as z-chains (by replacing the dot with Rn), it should mean that all whips[1] are actually z-chains[1] or even biv-chains[1]. Right? If you agree with that, then why do you insist on using a more complicated chain type unnecessarily?

[denis_berthier]

Vn has no candidate compatible with Z and with all the previous right-linking candidates (but Vn has more than one candidate – this is a non-degeneracy condition).

That does exclude singles because in those cases Vn (=V1) has only one candidate. So, we can agree that your official definition of whips doesn't include singles, but it's only because of that extra rule preventing "degenerate" patterns.

It's not an '"additional rule". It's part of the definition of whips.
It is clearly stated in the BUM that the graphical representations are mainly intuitive/introductory and that the full definitions are given in PBCS. Not everything can be represented graphically.
And, yes, all my definitions are intended to prevent degenerated patterns, e.g. a Pair will never be identified as a degenerated Quad. This is a necessary condition for being able to unambiguously define the length/size of a pattern.

Whips would work just as well if singles were included, but I guess it would be inconsistent with your generally non-polymorphic type hierarchy.

As I said, my definitions are at the logical level and they exclude degenerated patterns. That's unrelated to polymorphism, at the implementation level.
I need not use polymorphism to implement any resolution rule in SudoRules: the logical formulæ are the program.

Coupling pattern definitions with a specific strategy is a violation of the SoC principle.

Perfect. None of my definitions depends on any way on how it is used.
Resolution rules are pure logic formulæ, written in FOL in the language of Sudoku defined in PBCS. Thanks to confluence, one can super-impose the simplest-first strategy on them; but they can be used in many different ways, unchanged.
My invocation of the simplest-first strategy here was irrelevant.

[denis_berthier]

Hi SpAce,
A whip[1] could also be called by many names: z-chain[1], z-whip[1], g-whip[1], braid[1], g-braid[1] - or intersection, pointing, claiming (which would hide its relation with the rest of the chains). It can't be called a bivalue-chain[1] because it can have more than one z-candidate.

Ever since I've discovered them, I've considered whips as the most important of all the chain patterns: they have almost the same resolution power as braids, they are structurally and computationally much simpler, they are much easier to find for a manual solver.
It was therefore natural to build a complete hierarchy around them, starting at whips[1].

z-chains are whips with no t-candidates.
Each csp-variable in a bivalue-chain has exactly two candidates and they are written even in the last csp-variable. This is a detail of notation.
For z-chains, that'd be impossible, as the last csp-variable may have more than one z-candidate.

[SpAce]

Hi Denis,

Thanks for the clarifications!

Whips would work just as well if singles were included, but I guess it would be inconsistent with your generally non-polymorphic type hierarchy.

As I said, my definitions are at the logical level and they exclude degenerated patterns. That's unrelated to polymorphism, at the implementation level.
I need not use polymorphism to implement any resolution rule in SudoRules: the logical formulæ are the program.

I understand that. I wasn't talking about programming details but logical polymorphism at the pattern level. What I mean by that is that the same pattern of candidates can be seen through many different perspectives and called by several names. For example, an X-Wing pattern can be seen as a Turbot Fish, two X-Chains, an X-Loop, two AICs, an AIC-Loop, a 2-fish, a Subset (in your system), a 2x2 Rank 0 pattern, etc. They're all somewhat different yet valid ways to see and use same object.

Your system does have some polymorphism too (e.g. whips are special cases of braids) but probably less of it, or at least I don't have a clear picture of such relationships and hierarchies.

A whip[1] could also be called by many names: z-chain[1], z-whip[1], g-whip[1], braid[1], g-braid[1] - or intersection, pointing, claiming (which would hide its relation with the rest of the chains).

Ok. That clarifies your approach. It's also an example of polymorphism. Yet I wouldn't know how exactly you see their relationships, as in what is a (more specific) subtype of what, etc. Well, pointings and claimings are obviously subtypes of intersections, and g-whips probably subtypes of g-braids, but the rest aren't so clear.

It can't be called a bivalue-chain[1] because it can have more than one z-candidate.

I only meant the special case when it has just two. (I can see now that I didn't write it clearly.)

It was therefore natural to build a complete hierarchy around them, starting at whips[1].

I understand, and I thought it was probably your intention. No problem with that.

z-chains are whips with no t-candidates.

Then what are z-whips? Are they synonyms or is there a difference?

Each csp-variable in a bivalue-chain has exactly two candidates and they are written even in the last csp-variable. This is a detail of notation.
For z-chains, that'd be impossible, as the last csp-variable may have more than one z-candidate.

Why would it make it impossible? Why can't the last csp-variable work just like the first one, only mirroring it? Pick one z-candidate as the Rn and leave the rest as z-candidates, just like one is picked as the L1 in the first csp-variable. What's wrong with that? That's how I'd prefer to write them because then it would look like a chain, being symmetric and reversible and all. No need to resort to a contradiction. (*)

Previously I thought the same could be done with all whips and braids too, but I was obviously wrong about that. With them the last csp-variable doesn't necessarily have any candidate linking to the target, thus no possible Rn. I think that's a crucial difference between z-chains and whips/braids, and it would be nice it were reflected in the notation.

(*) Added. Another possibility: since Rn is an rlc, couldn't it be a group node combining all of those z-candidates? That leads to another question: what are biv-chains and z-chains called if they include group nodes or subsets as rlcs? Does it make them g- or S-whips automatically?

[denis_berthier]

Hi SpAce,

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.

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.

(*) Added. Another possibility: since Rn is an rlc, couldn't it be a group node combining all of those z-candidates? That leads to another question: what are biv-chains and z-chains called if they include group nodes or subsets as rlcs? Does it make them g- or S-whips automatically?

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.
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.

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.

[Mauriès Robert]

Hi Denis and SpAce,
I read with interest your exchanges and I understand SpAce's questions, which for some are mine as well, which proves that what is obvious for the creator of a concept is not necessarily obvious for the user.
So I add my grain of salt while waiting for an answer that will enlighten me a bit more on the whip concept.
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 ?
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}.
If the whips had been written the way I just did, it would certainly have taken me less time to understand them better!
Cordialy
Robert