Questions about PBCS

Advanced methods and approaches for solving Sudoku puzzles

Questions about PBCS

Postby Mauriès Robert » Fri Jan 15, 2021 6:22 pm

Hi all,
The "questions to understand" are more interesting than the often useless debates wrote Denis Berthier in another thread of the forum. Also, I open this thread for all those who, like me, want to ask questions about Denis Berthier's theories developed in his book Pattern-Based Constraint Satisfaction and Logic Puzzles (PBCS).

So I start with a question that is problematic for me (manual solver) concerning the search for targets that whips (or braids) eliminate.
Questions :
A whip [n] of length n is a regular string, i.e. a regular sequence V1{L1,R1}-V2{L2,R2}...-V2{Li,Ri}...-Vn{Ln,Rn} such that (among other conditions of the definition of a whip) Vn would be empty if a candidate Z (the target) was a solution of its cell.
Is my interpretation of the precise definition given in PBCS correct?
If so, it seems to me that it is possible to construct regular sequences V1{L1,R1}-V2{L2,R2}...-V2{Li,Ri}...-Vn{Ln,Rn} of length n that are not whips because they do not highlight the candidate Z that would make Vn empty. If so, will these sequences be whips in a future state of resolution?
Robert
Mauriès Robert
 
Posts: 486
Joined: 07 November 2019
Location: France

Re: Questions about PBCS

Postby denis_berthier » Sat Jan 16, 2021 4:59 am

Mauriès Robert wrote:A whip [n] of length n is a regular string, i.e. a regular sequence V1{L1,R1}-V2{L2,R2}...-V2{Li,Ri}...-Vn{Ln,Rn} such that (among other conditions of the definition of a whip) Vn would be empty if a candidate Z (the target) was a solution of its cell.
Is my interpretation of the precise definition given in PBCS correct?

"Regular string" has a precise meaning in CS. You will never find this expression in PBCS.
In a whip, there's no Rn.
That's why, yes, if Z was True, there would be no possible value for Vn - a contradiction.


Mauriès Robert wrote:If so, it seems to me that it is possible to construct regular sequences V1{L1,R1}-V2{L2,R2}...-V2{Li,Ri}...-Vn{Ln,Rn} of length n that are not whips because they do not highlight the candidate Z that would make Vn empty. If so, will these sequences be whips in a future state of resolution?

In an y resolution state, if you take any whip V1{L1 R1}-V2{L2 R2}...-V2{Li Ri}...-Vn{Ln .}, any initial part of it: V1{L1 R1}-V2{L2 R2}...-V2{Li Ri} is a partial-whip.
The relationship between whips and partial-whips is not about being in different resolution states. It's about being a full pattern allowing an elimination or only a partially identified one - in the same RS.
denis_berthier
2010 Supporter
 
Posts: 2102
Joined: 19 June 2007
Location: Paris

Re: Questions about PBCS

Postby Mauriès Robert » Sat Jan 16, 2021 11:01 am

Hi Denis,
Thank you for your answers to my questions, but they do not answer exactly what I am trying to understand about the use of whips.
So I'm asking you a different one, expecting a yes or no from you, and if it's a no for what reason.
My question is:
Can we interpret a whip[n] of length n as a regular (*)chain V1{L1,R1}...-{Li,Ri}...-Vn{Ln,Rn} for which it is possible to find a candidate Z (compatible with
all Ri for i<n) that sees both L1 and Rn?
Cordialy
Robert

(*) In my previous comment I used the term "string", it was a translation error.
Mauriès Robert
 
Posts: 486
Joined: 07 November 2019
Location: France

Re: Questions about PBCS

Postby denis_berthier » Sat Jan 16, 2021 11:45 am

Mauriès Robert wrote:Can we interpret a whip[n] of length n as a regular (*)chain V1{L1,R1}...-{Li,Ri}...-Vn{Ln,Rn} for which it is possible to find a candidate Z (compatible with
all Ri for i<n) that sees both L1 and Rn?

No,
There need not be a Z candidate in Vn.
denis_berthier
2010 Supporter
 
Posts: 2102
Joined: 19 June 2007
Location: Paris

Re: Questions about PBCS

Postby Mauriès Robert » Sat Jan 16, 2021 1:04 pm

denis_berthier wrote:
Mauriès Robert wrote:Can we interpret a whip[n] of length n as a regular (*)chain V1{L1,R1}...-{Li,Ri}...-Vn{Ln,Rn} for which it is possible to find a candidate Z (compatible with
all Ri for i<n) that sees both L1 and Rn?

No,
There need not be a Z candidate in Vn.

Ah yes, in another subject I have already asked you the question of whether Vn always has a z-candidate. I had forgotten that ! :(
So if I summarize my questions, we can interpret a whip[n] of length n as a regular chain V1{L1,R1]...-Vi{Li,Ri}...-Vn{Ln} for which it is possible to find a candidate Z (compatible with
all Ri for i<n) which sees L1 and would make Vn empty if Z was solution. Yes or no, if not why?
Cordialy
Robert
Last edited by Mauriès Robert on Sat Jan 16, 2021 3:42 pm, edited 2 times in total.
Mauriès Robert
 
Posts: 486
Joined: 07 November 2019
Location: France

Re: Questions about PBCS

Postby denis_berthier » Sat Jan 16, 2021 2:20 pm

Did you read my answer?
There's no Rn.
denis_berthier
2010 Supporter
 
Posts: 2102
Joined: 19 June 2007
Location: Paris

Re: Questions about PBCS

Postby Mauriès Robert » Sat Jan 16, 2021 3:41 pm

denis_berthier wrote:Did you read my answer?
There's no Rn.

Yes, I omitted to remove Rn in the sequence, I corrected it. So my interpretation is good after this correction?
Having said that, I don't understand some whips in your book. For example the whip [3] in the last line of page 232 (paragraph 8.8.3.2). In this case, I can consider the regular chain r6c4{n9 n5}-r5c5{n5 n4}-r9c5{n4 n9} which contains R3 which is not eliminated by the structure of the sequence but by the choice of the target. Wouldn't this whip rather be a z-chain?
Robert
Mauriès Robert
 
Posts: 486
Joined: 07 November 2019
Location: France

Re: Questions about PBCS

Postby denis_berthier » Sat Jan 16, 2021 4:41 pm

Mauriès Robert wrote:
denis_berthier wrote:Did you read my answer?
There's no Rn.

Yes, I omitted to remove Rn in the sequence, I corrected it. So my interpretation is good after this correction?

It's not Vn{Ln} but Vn{Ln .} . There is a reason for having a dot.
No.

Mauriès Robert wrote: I don't understand some whips in your book. For example the whip [3] in the last line of page 232 (paragraph 8.8.3.2). In this case, I can consider the regular chain r6c4{n9 n5}-r5c5{n5 n4}-r9c5{n4 n9} which contains R3 which is not eliminated by the structure of the sequence but by the choice of the target. Wouldn't this whip rather be a z-chain?

In this example, only whips and Subsets were active. If you activate z-chains, you get the following:
Code: Select all
biv-chain-rc[3]: r6c4{n9 n5} - r5c5{n5 n4} - r9c5{n4 n9} ==> r7c4 ≠ 9, r9c4 ≠ 9
it's not only a z-chain but a mere bivalue-chain in rc-space, i.e. an xy-chain
denis_berthier
2010 Supporter
 
Posts: 2102
Joined: 19 June 2007
Location: Paris

Re: Questions about PBCS

Postby denis_berthier » Sat Jan 16, 2021 4:42 pm

Mauriès Robert wrote:
denis_berthier wrote:Did you read my answer?
There's no Rn.

Yes, I omitted to remove Rn in the sequence, I corrected it. So my interpretation is good after this correction?
Having said that, I don't understand some whips in your book. For example the whip [3] in the last line of page 232 (paragraph 8.8.3.2). In this case, I can consider the regular chain r6c4{n9 n5}-r5c5{n5 n4}-r9c5{n4 n9} which contains R3 which is not eliminated by the structure of the sequence but by the choice of the target. Wouldn't this whip rather be a z-chain?
Robert
Mauriès Robert wrote:
denis_berthier wrote:Did you read my answer?
There's no Rn.

Yes, I omitted to remove Rn in the sequence, I corrected it. So my interpretation is good after this correction?

It's not Vn{Ln} but Vn{Ln .} . There is a reason for having a dot.
No.

Mauriès Robert wrote: I don't understand some whips in your book. For example the whip [3] in the last line of page 232 (paragraph 8.8.3.2). In this case, I can consider the regular chain r6c4{n9 n5}-r5c5{n5 n4}-r9c5{n4 n9} which contains R3 which is not eliminated by the structure of the sequence but by the choice of the target. Wouldn't this whip rather be a z-chain?

In this example, only whips and Subsets were active. If you activate z-chains, you get the following:
Code: Select all
biv-chain-rc[3]: r6c4{n9 n5} - r5c5{n5 n4} - r9c5{n4 n9} ==> r7c4 ≠ 9, r9c4 ≠ 9
it's not only a z-chain but a mere bivalue-chain in rc-space, i.e. an xy-chain, a very special case of whip - which will be found as a whip if the specific rule is not present.
denis_berthier
2010 Supporter
 
Posts: 2102
Joined: 19 June 2007
Location: Paris

Re: Questions about PBCS

Postby Mauriès Robert » Sat Jan 16, 2021 7:09 pm

denis_berthier wrote:It's not Vn{Ln} but Vn{Ln .} . There is a reason for having a dot.
No.

You write in your book that the dot inside the last curly brackets means the absence of a compatible candidate. I thought that the absence of Rn was sufficient without the need to specify this detail.
Robert
Mauriès Robert
 
Posts: 486
Joined: 07 November 2019
Location: France

Re: Questions about PBCS

Postby denis_berthier » Sun Jan 17, 2021 4:59 am

Mauriès Robert wrote:
denis_berthier wrote:It's not Vn{Ln} but Vn{Ln .} . There is a reason for having a dot.

You write in your book that the dot inside the last curly brackets means the absence of a compatible candidate. I thought that the absence of Rn was sufficient without the need to specify this detail.

Detail? Stating explicitly that there's no compatible candidate is a detail?
denis_berthier
2010 Supporter
 
Posts: 2102
Joined: 19 June 2007
Location: Paris

Re: Questions about PBCS

Postby Mauriès Robert » Sun Jan 17, 2021 9:28 am

denis_berthier wrote:
Mauriès Robert wrote:
denis_berthier wrote:It's not Vn{Ln} but Vn{Ln .} . There is a reason for having a dot.

You write in your book that the dot inside the last curly brackets means the absence of a compatible candidate. I thought that the absence of Rn was sufficient without the need to specify this detail.

Detail? Stating explicitly that there's no compatible candidate is a detail?

You misinterpret the meaning of that term in the context of my sentence, which is "I thought that the absence of Rn was sufficient without the need to specify this detail." The term detail should be taken to mean "this aspect of the notation" and not that this aspect is insignificant. It would be preferable if you could tell me whether indeed the absence of Rn necessarily implies the absence of a compatible or nonand why.
Last edited by Mauriès Robert on Sun Jan 17, 2021 2:21 pm, edited 1 time in total.
Mauriès Robert
 
Posts: 486
Joined: 07 November 2019
Location: France

Re: Questions about PBCS

Postby Mauriès Robert » Sun Jan 17, 2021 2:14 pm

Hi Denis,
I understand that an x-wing is a model, a kite, a skyscraper too etc... their definitions make no reference to the target, it is the target that is defined according to the model.
You yourself in PBCS defined the model of a biv-chain that I understand well, which also makes no reference to the target, it is the target that is defined according to the model.
For whips as you define them in PBCS, the definition refers to the target, besides you write "...a zt-whip (in short a whip) of length n (n ≥ 1) built on Z... ".
If a whip is a model like an x-wing or a biv chain, it should be possible to define it without reference to the target and define the target according to the model. Hence my question:
Can you give separately a definition of a whip that does not refer to the target, then a definition of the target of a whip?
Robert
Mauriès Robert
 
Posts: 486
Joined: 07 November 2019
Location: France

Re: Questions about PBCS

Postby denis_berthier » Mon Jan 18, 2021 5:20 am

I don't use the word "model" in this context, as the proper word is "pattern".

Who said a pattern may not refer to its target? Oddagons are not my invention; they refer to their target.
You have to live with this. Some patterns don't refer to their target in their definition, some do. Whips do.

And, again, this doesn't imply that the target is the starting point for looking for them.
denis_berthier
2010 Supporter
 
Posts: 2102
Joined: 19 June 2007
Location: Paris

Re: Questions about PBCS

Postby Mauriès Robert » Mon Jan 18, 2021 5:27 pm

Hi Denis,
denis_berthier wrote:I don't use the word "model" in this context, as the proper word is "pattern".

Who said a pattern may not refer to its target? Oddagons are not my invention; they refer to their target.
You have to live with this. Some patterns don't refer to their target in their definition, some do. Whips do.

And, again, this doesn't imply that the target is the starting point for looking for them.


Model instead of pattern, a translation problem on my part without more, I meant pattern.
Your answer means that it is not possible to define a whip without referring to its target. I take note of this.
You then say "And, again, this doesn't imply that the target is the starting point for looking for them." I agree with that, the starting point of a whip [n] is a partial whip [1] and not a target.
However, since the definition of a whip [n] refers to the target Z by saying that L1 is related to Z, as soon as the partial whip [1] is chosen, necessarily the target is one of the puzzle candidates that see L1. If a Vi (i<n) contains one of these candidates that see L1, then the target is fully identified while we are only at the partial whip[i] stage. If the starting point of a whip [n>1] is not the target, its construction is inseparable from the target it must eliminate.
Robert
Mauriès Robert
 
Posts: 486
Joined: 07 November 2019
Location: France

Next

Return to Advanced solving techniques