Questions about PBCS

Advanced methods and approaches for solving Sudoku puzzles

Re: Questions about PBCS

Postby denis_berthier » Mon Jan 18, 2021 5:56 pm

Yes, but I can't see any problem with this.
Your questions were initially about how to start a whip. At some point in it's extension, sure, there can be only one target - unless there are no z candidates.
denis_berthier
2010 Supporter
 
Posts: 2102
Joined: 19 June 2007
Location: Paris

Re: Questions about PBCS

Postby Mauriès Robert » Thu Jan 21, 2021 10:34 pm

Hi Denis,
I would like to ask you about another subject in your book, that of Wp-whips.
But before, could you give an example of a sudoku puzzle requiring the use of Wp-whips (p>1) and the resolution of this puzzle?
Cordialy
Robert
Mauriès Robert
 
Posts: 486
Joined: 07 November 2019
Location: France

Re: Questions about PBCS

Postby denis_berthier » Fri Jan 22, 2021 4:56 am

Mauriès Robert wrote:But before, could you give an example of a sudoku puzzle requiring the use of Wp-whips (p>1) and the resolution of this puzzle?

Any puzzle not in T&E(1) requires patterns more complex than braids. Unless some exotic pattern brings it back to T&E(1) - a statistically rare phenomenon, although it is highlighted in many examples - such patterns can only be chains. There are S-braids but even those are not as powerful as B-braids.
B-braids and the "simpler" W-whips" are a theoretical tool, very useful in refining the T&E(n) classification. But they are very complex chains with embedded chains and I don't consider them as a practical means of resolution. I haven't even programmed them in SudoRules.
However, using my BpB vs T&E(Bp) theorem, I can easily check in which BpB a puzzle is - which is IMO the only interesting thing about some puzzles.
denis_berthier
2010 Supporter
 
Posts: 2102
Joined: 19 June 2007
Location: Paris

Re: Questions about PBCS

Postby Mauriès Robert » Fri Jan 22, 2021 10:05 am

denis_berthier wrote:
Mauriès Robert wrote:But before, could you give an example of a sudoku puzzle requiring the use of Wp-whips (p>1) and the resolution of this puzzle?

Any puzzle not in T&E(1) requires patterns more complex than braids. Unless some exotic pattern brings it back to T&E(1) - a statistically rare phenomenon, although it is highlighted in many examples - such patterns can only be chains. There are S-braids but even those are not as powerful as B-braids.
B-braids and the "simpler" W-whips" are a theoretical tool, very useful in refining the T&E(n) classification. But they are very complex chains with embedded chains and I don't consider them as a practical means of resolution. I haven't even programmed them in SudoRules.
However, using my BpB vs T&E(Bp) theorem, I can easily check in which BpB a puzzle is - which is IMO the only interesting thing about some puzzles.

Too bad, I would have liked to see an example of use to verify that I understand the definition.
If I understood correctly, a Wp-whip is a main whip[n] in which a whip[p] integrated on the right allows to say that a candidate L is a candidate on the left of the main whip[n], which allows to continue the construction of the sequence.
Cordialy
Robert
Mauriès Robert
 
Posts: 486
Joined: 07 November 2019
Location: France

Re: Questions about PBCS

Postby Mauriès Robert » Sun Jan 31, 2021 5:33 pm

Hi Denis,
I'm picking up here the discussion we were having on another thread because I'm interested to know more.
denis_berthier wrote:
Mauriès Robert wrote:
denis_berthier wrote:How to obtain this in SudoRules?
1- First, load braids.
2- Second, init the puzzle: (init-sudoku-string "..42....6.6..7..3.2....61..1....46...5..9..1...71....99....37...8..4..5...37....8")
3- Third, ask for the wanted elimination: (try-to-eliminate-candidates 523); SudoRules gives:
braid[8]: r2n1{c3 c6} - r1n1{c6 c2} - r9n1{c2 c5} - c1n5{r1 r9} - r1n7{c2 c8} - r9n6{c1 c8} - c8n9{r1 r3} - b1n9{r3c3 .} ==> r2c3 ≠ 5

What would have happened if at stage 3 Sudorules had found nothing?

Nothing.
Obviously, if the elimination was not available, SudoRules wouldn't do it. Function "try-to-eliminate-candidates" doesn't do more than its name suggests; in particular, it doesn't try to eliminate any other candidate than those listed as arguments.

When you say that Sudorules seeks to eliminate only the candidates given in arguments, do you mean that it seeks to eliminate among all the candidates in the puzzle that have the same value as the candidates given in arguments or among those who see the candidates given in arguments?
Robert
Mauriès Robert
 
Posts: 486
Joined: 07 November 2019
Location: France

Re: Questions about PBCS

Postby denis_berthier » Sun Jan 31, 2021 7:14 pm

Mauriès Robert wrote:When you say that Sudorules seeks to eliminate only the candidates given in arguments, do you mean that it seeks to eliminate among all the candidates in the puzzle that have the same value as the candidates given in arguments or among those who see the candidates given in arguments?

Only the candidates given as arguments.
denis_berthier
2010 Supporter
 
Posts: 2102
Joined: 19 June 2007
Location: Paris

Re: Questions about PBCS

Postby Mauriès Robert » Sun Jan 31, 2021 7:24 pm

denis_berthier wrote:
Mauriès Robert wrote:When you say that Sudorules seeks to eliminate only the candidates given in arguments, do you mean that it seeks to eliminate among all the candidates in the puzzle that have the same value as the candidates given in arguments or among those who see the candidates given in arguments?

Only the candidates given as arguments.

I don't understand your answer. Do you mean to say that in the above example, the candidates given as arguments are those of r2c3, so that sudorules is looking for a braid that eliminates one of these candidates?
Robert
Mauriès Robert
 
Posts: 486
Joined: 07 November 2019
Location: France

Re: Questions about PBCS

Postby denis_berthier » Sun Jan 31, 2021 7:30 pm

Mauriès Robert wrote:
denis_berthier wrote:
Mauriès Robert wrote:When you say that Sudorules seeks to eliminate only the candidates given in arguments, do you mean that it seeks to eliminate among all the candidates in the puzzle that have the same value as the candidates given in arguments or among those who see the candidates given in arguments?

Only the candidates given as arguments.

I don't understand your answer. Do you mean to say that in the above example, the candidates given as arguments are those of r2c3, so that sudorules is looking for a braid that eliminates one of these candidates?

In the example, the only candidate given as argument to function "try-to-elimintae-candidates" was n5r2c3. It's the only one that SudoRules tries to eliminate.
If you want to try all the candidates for cell r2c3, you have to list them all explicitly.
denis_berthier
2010 Supporter
 
Posts: 2102
Joined: 19 June 2007
Location: Paris

Re: Questions about PBCS

Postby Mauriès Robert » Mon Feb 01, 2021 7:28 am

denis_berthier wrote:I don't understand your answer. Do you mean to say that in the above example, the candidates given as arguments are those of r2c3, so that sudorules is looking for a braid that eliminates one of these candidates?

In the example, the only candidate given as argument to function "try-to-elimintae-candidates" was n5r2c3. It's the only one that SudoRules tries to eliminate.
If you want to try all the candidates for cell r2c3, you have to list them all explicitly.[/quote]
Ok, thank you for that answer.
I can compare the Sudorules procedure to what I do with the anti-tracks, namely:
1) I choose a candidate A from a pair of candidates (only two candidates in a CSP variable) and I construct the anti-track P'(E1) with E1=A. The candidate to be eliminated is necessarily among the candidates Zi who see E1 without being candidate of P'(E1).
2) If P'(E1) is successful, the target is eliminated.
3) If P'(E1) does not succeed, i.e. it does not contain a candidate who sees one of the Zi, then,
3a) I abandon this anti-track to resume it possibly in a later state of resolution and I use another candidate A (back to 1).
3b) I choose a set E2={A,Zi1} composed of A and one Zi1 of the Zi, in order to construct the anti-track P'(E2) which becomes an extension of P'(E1). The target is then one of the Zi that see both E1 and Zi1, and I repeat procedure 2,3,a,b with E2.
With this procedure, I progressively eliminate the Zi that cannot be the target of the anti-track.
Note that in this procedure I do not try to prove the existence of a contradiction in the sequence of construction of the anti-track, a construction which stops with 2) or 3a). But if a contradiction appears before the end of the procedure, all the Zi that see the last Ej used would be eliminated at once.
Robert
Mauriès Robert
 
Posts: 486
Joined: 07 November 2019
Location: France

Re: Questions about PBCS

Postby denis_berthier » Mon Feb 01, 2021 7:36 am

"try-to-eliminate-candidates" is not the normal SudoRules way of working. It's only a goodie I added recently.

The normal way of solving a puzzle in SudoRules is the simplest-first strategy.
denis_berthier
2010 Supporter
 
Posts: 2102
Joined: 19 June 2007
Location: Paris

Re: Questions about PBCS

Postby Mauriès Robert » Mon Feb 01, 2021 8:43 am

denis_berthier wrote:"try-to-eliminate-candidates" is not the normal SudoRules way of working. It's only a goodie I added recently.

The normal way of solving a puzzle in SudoRules is the simplest-first strategy.

Thank you for this clarification.
As you know, by hand, the simplest-first strategy is practically impossible, hence the procedure I described earlier.
I would like to take this opportunity to make a remark.
All the puzzles solved with whips that I have studied (by hand it is necessarily a small quantity), I have been able to solve them with anti-tracks according to the procedure described above. That is to say that for each whip studied, there is a set E such that the target Z of the whip is also the target Z of the anti-track P'(E) in the sense that Z sees both E and a candidate of P'(E).
Robert
Mauriès Robert
 
Posts: 486
Joined: 07 November 2019
Location: France

Re: Questions about PBCS

Postby denis_berthier » Mon Feb 01, 2021 9:13 am

Mauriès Robert wrote:All the puzzles solved with whips that I have studied (by hand it is necessarily a small quantity), I have been able to solve them with anti-tracks according to the procedure described above. That is to say that for each whip studied, there is a set E such that the target Z of the whip is also the target Z of the anti-track P'(E) in the sense that Z sees both E and a candidate of P'(E).


As whips are a particular case of braids and anti-tracks are obviously only a degraded version of braids or an improved version of T&E, I can't see anything unexpected here.
denis_berthier
2010 Supporter
 
Posts: 2102
Joined: 19 June 2007
Location: Paris

Re: Questions about PBCS

Postby Mauriès Robert » Mon Feb 01, 2021 10:37 am

denis_berthier wrote:
Mauriès Robert wrote:All the puzzles solved with whips that I have studied (by hand it is necessarily a small quantity), I have been able to solve them with anti-tracks according to the procedure described above. That is to say that for each whip studied, there is a set E such that the target Z of the whip is also the target Z of the anti-track P'(E) in the sense that Z sees both E and a candidate of P'(E).


As whips are a particular case of braids and anti-tracks are obviously only a degraded version of braids or an improved version of T&E, I can't see anything unexpected here.

I disagree with your interpretation of the anti-tracks as I use them. They are not degraded versions of the braids, they just do the same elimination work. Among other differences, a braid highlights a contradiction, but the anti-track does not. Nor are they T&E whose principle is to try a candidate that one eliminates if the sequence leads to contradiction.
Robert
Mauriès Robert
 
Posts: 486
Joined: 07 November 2019
Location: France

Re: Questions about PBCS

Postby denis_berthier » Mon Feb 01, 2021 11:20 am

Mauriès Robert wrote:
denis_berthier wrote:
Mauriès Robert wrote:All the puzzles solved with whips that I have studied (by hand it is necessarily a small quantity), I have been able to solve them with anti-tracks according to the procedure described above. That is to say that for each whip studied, there is a set E such that the target Z of the whip is also the target Z of the anti-track P'(E) in the sense that Z sees both E and a candidate of P'(E).


As whips are a particular case of braids and anti-tracks are obviously only a degraded version of braids or an improved version of T&E, I can't see anything unexpected here.

I disagree with your interpretation of the anti-tracks as I use them. They are not degraded versions of the braids, they just do the same elimination work. Among other differences, a braid highlights a contradiction, but the anti-track does not. Nor are they T&E whose principle is to try a candidate that one eliminates if the sequence leads to contradiction.

You can disagree as much as you want. Facts remain facts.
The way you use anti-tracks has nothing to do with their definition. And the way I use braids/whips in SudoRules (simplest-first strategy) has nothing to do with their definition. I always said that the simplest-first strategy is for SudoRules and human solvers could use them in different ways.
denis_berthier
2010 Supporter
 
Posts: 2102
Joined: 19 June 2007
Location: Paris

Re: Questions about PBCS

Postby denis_berthier » Tue Feb 02, 2021 5:42 am

Mauriès Robert wrote:...what I do with the anti-tracks, namely:
1) I choose a candidate A from a pair of candidates (only two candidates in a CSP variable) and I construct the anti-track P'(E1) with E1=A. The candidate to be eliminated is necessarily among the candidates Zi who see E1 without being candidate of P'(E1).
2) If P'(E1) is successful, the target is eliminated.
3) If P'(E1) does not succeed, i.e. it does not contain a candidate who sees one of the Zi, then,
3a) I abandon this anti-track to resume it possibly in a later state of resolution and I use another candidate A (back to 1).
3b) I choose a set E2={A,Zi1} composed of A and one Zi1 of the Zi, in order to construct the anti-track P'(E2) which becomes an extension of P'(E1). The target is then one of the Zi that see both E1 and Zi1, and I repeat procedure 2,3,a,b with E2.
With this procedure, I progressively eliminate the Zi that cannot be the target of the anti-track.
Note that in this procedure I do not try to prove the existence of a contradiction in the sequence of construction of the anti-track, a construction which stops with 2) or 3a). But if a contradiction appears before the end of the procedure, all the Zi that see the last Ej used would be eliminated at once.

I translate this into:
Code: Select all
1) choose a candidate A from a bivalue cell.
2) if T&E(BRT or S, 1, A) finds an error, then eliminate A
3) otherwise:
3a) either give up and goto 1)
3b) or go one level of T&E deeper, possibly iterating (which includes possibly going still deeper in T&E).

No criterion is given for choosing between 3a and 3b.
No criterion is given for choosing between the Zi's.


Mauriès Robert wrote:All the puzzles solved with whips that I have studied (by hand it is necessarily a small quantity), I have been able to solve them with anti-tracks according to the procedure described above. That is to say that for each whip studied, there is a set E such that the target Z of the whip is also the target Z of the anti-track P'(E) in the sense that Z sees both E and a candidate of P'(E).

I'm curious to see what this procedure gives with puzzle "fish-on-wave 9.3". In particular, how deep in T&E you'll have to go to fully solve the puzzle.
denis_berthier
2010 Supporter
 
Posts: 2102
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Advanced solving techniques