more on whips, braids, T&E...

Advanced methods and approaches for solving Sudoku puzzles

Re: About subsumption

Postby pjb » Sat Oct 08, 2011 5:29 am

denis_berthier wrote:I've shown long ago that most cases of Naked, Hidden or Super-Hidden (Fish) subset patterns are subsumed by whips. But there are very rare cases when this is not the case, in particular for complete quads (i.e. quads that contain the 4 candidates in each of their 4 cells). The following is an interesting such example.
The puzzle comes from the Jellyfish collection, it is #017#Mauricio-002#8#1, with SER = 8:
.............1.....123.456...........23...78..47.6.12...........318.764..58...23.

[/code]


This is one of those interesting puzzles that can be solved surprisingly easily using a technique not mentioned in this thread so far - ie - pattern overlay method. With my solver (philsfolly), it detects a naked quad in box5, then a sashimi swordfish followed by a finned swordfish. Then the next tenique in my hierarchy is POM, and it finds no fewer than 20 9's for deletion, after which it is solved with singles.

pjb
pjb
2014 Supporter
 
Posts: 1722
Joined: 11 September 2011
Location: Sydney, Australia

Re: About subsumption

Postby denis_berthier » Sat Oct 08, 2011 6:59 am

pjb wrote: ...pjb


I can't see the point of repeating what you said a few posts above, which Pat and I already answered.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Rating, again

Postby denis_berthier » Sat Oct 15, 2011 5:24 am





Rating, again



Rating puzzles has always been a hard problem, much harder than solving them.


The W and B ratings
Long ago, I have introduced the W and B ratings (at that time, I used more complex names: pure nrczt-whip and pure nrczt-braid ratings) based on the length of whips or braids necessary to solve a puzzle.

The B rating satisfies the minimum properties one may expect of a consistent rating:
- it is defined in a purely logical way, independent of any implementation;
- it is based on an increasing sequence of resolution theories that have the confluence property;
- using the "simplest first" strategy, it can therefore be computed with only one resolution path;
- it is invariant under all the Sudoku symmetries and super-symmetries;
- it does not make any difference between the four 2D spaces (said otherwise, it makes no difference between contradiction links along numbers, rows, columns or blocks).

Moreover:
- the W rating is finite for almost all the minimal puzzles (tested on 10,000,000 randomly generated ones);
- the W rating associated with the simplest first strategy, when finite, provides a good approximation of the B rating;
- due to the almost subsumption theorems of (Naked, Hidden and Super-Hidden) Subsets by whips of same length, the W rating is almost always equal to the S rating (based on Subsets) when S is finite.

The braid and Subsets techniques can be used in conjunction; they lead to define the S+B rating (which I formally called the nrczt-braid rating). The S+B rating has all the good properties of the B rating listed above. For almost all the puzzles, one has B = S+B: adding Subsets in the landscape does not change much. Ina ll this, braids can be replaced by whips, still with little change in the resulting ratings.


It is essential to notice that this is enough to rate all the puzzles a normal player can solve by hand - and much beyond.
As it deals with puzzles no one is likely to solve by hand, the rest of this post can only be interesting from a more theoretical point of view.

Straightforward extensions of these ratings are the gB and gW ratings, based on g-braids and g-whips [which I formally called braids(BI) and whips(BI)]. They satisfy all the good properties of ratings listed above.



The SpB and BpB ratings

Now considering exceptionally hard puzzles, more complex solving techniques are needed.
Long ago also, using a more complex terminology than now, I have presented in this forum other rating(s) based on various families of braids with embedded patterns.

First step beyond braids or g-braids:
For any p > 1, Sp-braids are defined as generalized g-braids accepting inner Subsets of maximum length p as their right-linking objects, while the left-linking objects always remain mere candidates. S-braids accept inner Subsets of a priori unrestricted length (but the length of inner Subsets is of course smaller than the total length of the braid in which they are embedded).
For any p >1, one can define the SpB rating, associated with Sp-braids in the same way as the B rating is associated with ordinary braids. And one one can define the SB rating, associated with S-braids with inner Subsets of a priori unrestricted length.

Second step beyond braids or g-braids:
Similarly, for any p > 1, Bp-braids are defined as generalized braids accepting inner braids of maximum length p as their right-linking objects, while the left-linking objects always remain mere candidates. And B-braids accept inner braids of a priori unrestricted length (but the length of inner braids is of course smaller than the total length of the braid in which they are embedded).
For any p >1, one can define the BpB rating, associated with Bp-braids in the same way as the B rating is associated with ordinary braids. And one one can define the BB rating, associated with B-braids with inner braids of a priori unrestricted length.

All these ratings also satisfy all the good properties listed above.

In the same way as braids or whips are much more powerful than Subsets, Bp-braids are much more powerful than Sp-braids.




New results

I introduced all these more complex braids with inner patterns on this forum in 2008 ("abominable T&E and lovely braids" thread), where I also gave some idea of the scope of Sp-braids, using gsf's 8152 list. All this has also been available on my website for a long time, in a more synthetic form (http://www.carva.org/denis.berthier/HLS).

What's new since the time I introduced all this fauna ?

- I have studied these patterns more formally and in much more detail in the third part of my new book (Constraint Resolution Theories, or CRT, announced a few posts above); unless you want formal definitions and proofs, reading it is not necessary for understanding these patterns and the main results proven in it (the confluence property of the associated resolution theories and the "T&E(T) vs T-braids" correspondence theorem);

- as my old conjecture that all the puzzles can be solved with at most 2 levels of Trial-and-Error [T&E(2)] has survived the recent new series of 11+ puzzles, and due to the "T&E(2) vs B-braids" correspondence theorem proven in CRT, all the known puzzles can be solved either by Singles, or by ordinary braids or by B-braids; moreover, the necessity of B-braids appears only for extremely rare cases (fewer than 1 in 10,000,000);

- as a result, the BB rating of a puzzle P (i.e. the minimal length of the B-braids necessary to solve P) is universal, in the sense of being finite for all the puzzles (at least for all the known ones, but I conjecture it's true for all), in addition to having the same good properties as the B rating;

- I now have detailed classification results for gsf's 8152 list for Bp-braids (instead of only Sp-braids previously).




Open question

One question that remains open is the minimal value of p such that all the (known) puzzles can be solved with Bp-braids (possibly with a BpB rating larger than their BB rating). Until now, I have examples that need p≥6. But, for such cases, computation times are long (I have never had time to optimise this program, independent of SudoRules) and I can't yet try many puzzles.

Whips and braids have the essential property of being non-anticipative (or, equivalently, non-look-ahead).
As inner braids can be considered as a form of look-ahead, knowing this minimum value of p would provide an upper bound for the degree of look-ahead necessary to solve any puzzle.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Rating, again

Postby denis_berthier » Thu Nov 17, 2011 1:11 pm

denis_berthier wrote: One question that remains open is the minimal value of p such that all the (known) puzzles can be solved with Bp-braids (possibly with a BpB rating larger than their BB rating). Until now, I have examples that need p≥6.

I now have an example with p = 7.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Bi-whips/bi-braids; W*-whips/B*-braids

Postby denis_berthier » Fri Nov 18, 2011 6:56 am



Bi-whips/bi-braids; W*-whips/B*-braids


Perhaps the structure of W-whips and B-braids, with their inner whips or braids, remains a little mysterious. The definitions below introduce patterns that still have inner whips or braids, but that are structurally simpler.

Let me first recall that candidates and 2D cells (i.e. rc, rn, cn and bn cells) are the basic concepts in the definition of whips/braids.


Definition of bi-whips and bi-braids

Definition: given two different candidates Z1 and Z2 in a resolution state RS, for any n>=1, a bi-whip[n] based on Z1 and Z2 is a sequence of candidates (L1, R1, ..., Ln-1, Rn-1, Ln) (as in the whips case, there's no Rn), such that:
- in the sequence (L1, R1, ..., Ln-1, Rn-1, Ln), any two consecutive elements are different;
- Z1 and Z2 do not belong to (L1, R1, L2, R2, ... Ln);
- L1 is linked to Z1 or Z2;
- right-to-left continuity: for any 1 < k <= n, Lk is linked to Rk-1;
- strong left-to-right continuity: for any 1 <= k < n, Lk and Rk are candidates for the same 2D cell Vk;
- Ln is a candidate for 2D cell Vn;
- Z1 and Z2 are not candidates for Vn;
- for any 1 <= k < n: Rk is the only candidate for 2D cell Vk compatible with Z1, Z2 and all the previous Ri (i<k);
- Vn has no candidate compatible with Z1, Z2 and all the previous Ri (i<n); (but Vm has more than one candidate - my usual non-degeneracy condition for the global structure being defined);
- (L1, R1, ..., Ln-1, Rn-1,... Ln) is not a whip[n] based on Z1;
- (L1, R1, ..., Ln-1, Rn-1,... Ln) is not a whip[n] based on Z2;

Definition: a bi-braid[n] is a list as above, with the right-to-left continuity condition and the last two conditions replaced by:
- for any 1<k<=n, Lk is linked to Z1 or Z2 or a previous Ri;
- (L1, R1, ..., Ln-1, Rn-1, Ln) is not a braid[n] based on Z1;
- (L1, R1, ..., Ln-1, Rn-1, Ln) is not a braid[n] based on Z2;

Definition: given two different candidates Z1 and Z2 in a resolution state RS, Z1 and Z2 are said bi-whip[n] incompatible (respectively bi-braid[n] incompatible) in RS if there exists in RS some bi-whip[n] (resp. some bi-braid[n]) based on Z1 and Z2.
Z1 and Z2 are said bi-whip (respectively bi-braid) incompatible in RS if there is some n such that, in RS, they are bi-whip[n] (resp. bi-braid[n]) incompatible.

Remark: for any 1 <= n <= infinite, bi-whip[n] and bi-braid[n] incompatibility between Z1 and Z2 are restricted constructive forms of the abstract logical nand2 predicate defined by: nand2(Z1, Z2) = not (Z1 and Z2).
By convention one could define bi-whip[0] incompatibility between Z1 and Z2 as "linked".


Definition of W*-whips and B*-braids

Definition: given a candidate Z in any resolution state RS, a W*-whip based on Z is a sequence of candidates (L1, R1, ... , Ln-1, Rn-1, Ln) that satisfies the following conditions:
- in the sequence (L1, R1, ..., Ln-1, Rn-1, Ln), any two consecutive elements are different;
- Z does not belong to (L1, R1, L2, R2, ... Ln);
- L1 is linked to Z;
- extended right-to-left continuity: for any 1 < k <= m, Lk is linked to Rk-1 or Lk and Rk-1 are bi-whip incompatible in RS;
- strong left-to-right continuity: for any 1 <= k < n, Lk and Rk are candidates for the same 2D cell Vk;
- Ln is a candidate for 2D cell Vn;
- Z is not a candidate for Vn;
- for any 1<=k<n: Rk is the only candidate for 2D cell Vk compatible and not bi-whip incompatible in RS with Z and with all the previous right-linking candidates Ri;
- Vn has no candidate compatible and not bi-whip incompatible in RS with the target Z and with all the previous right-linking candidates (but Vn has more than one candidate - my usual non-degeneracy condition of the global structure being defined).

Definition: a B*-braid based on Z is a sequence as above, with "bi-whip compatible" replaced by,"bi-braid compatible" and with the extended right-to-left continuity condition replaced by:
- for any 1 <= k <= m, Lk is linked to Z1 or Z2 or a previous Ri or Lk is bi-whip incompatible in RS with Z1, Z2 or a previous Ri.

The intuitive meaning is that, in W*-whips [resp. B*-braids], bi-whip [resp. bi-braid] contradictions can be used wherever direct links are used in ordinary whips/braids.


Remarks:
1) W*-whips [respectively B*-braids] are based on indirect pairwise contradictions whereas ordinary whips [resp. braids] are based on direct contradictions;
2) but the ways a contradiction may be found are constructive and similar in both cases;
3) W*-whips and B*-braids are structurally much simpler than W-whips and B-braids.

One could also imagine a resolution technique starting by pre-computing all the bi-whip or bi-braid incompatibility relationships and then using them in the same way as ordinary links are used in ordinary whips and braids.
Unfortunately, as these relations are not structural, they would have to be updated, with probably new instances created every time a candidate is deleted.
Moreover, these new definitions do not allow to define ratings compatible with the previously defined ones: they reduce to the same complexity (zero) all the bi-whip[d] or bi-braid[d] pairwise contradictions, for all d.
Finally, using these indirect contradictions as if they were standard links would be equivalent to having a hidden level of T&E.
Last edited by denis_berthier on Sat Jul 28, 2012 3:26 am, edited 3 times in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Bi-whips/bi-braids; another view of W-whips/B-braids

Postby ronk » Sat Nov 19, 2011 5:05 pm

denis_berthier wrote:Definition of bi-whips and bi-braids

Definition: given two different candidates Z1 and Z2 in a resolution state RS, for any n>=1, a bi-whip[n] based on Z1 and Z2 is a sequence of candidates (L1, R1, …, Ln-1, Rn-1, Ln) (as in the whips case, there's no Rn), such that:
  • ...
Definition: a bi-braid[n] is a list as above, with the right-to-left continuity condition and the last two conditions replaced by:
  • ...

denis, most of us get little out of word definitions without illustrations. Therefore, I hope you're planning to post a few examples in the not-too-distant future.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Bi-whips/bi-braids; another view of W-whips/B-braids

Postby denis_berthier » Sun Nov 20, 2011 5:40 am

ronk wrote:I hope you're planning to post a few examples in the not-too-distant future.


bi-whip contradictions:
The simplest example of a bi-whip contradiction between Z1 and Z2 is a chain Z1 - {x y} - Z2, where Z1 is nrc-linked to x, Z2 to y and the 2D cell {x y} is bivalue / bilocal.
Another family of examples is obtained from a partial whip, between its target and any of its left-linking candidates. But the interesting cases are when one has to use the two targets to go on in the chain, as in the following case.

Another simple example is the pattern Z1 - {x t1 t2 y} - Z2, where Z1 is nrc-linked to x and t1, Z2 to y and t2 and the medium 2D cell has exactly the 4 candidates displayed.
Example: x t1 t2 y in the same row r; x t1 Z1 in the same block; y t2 Z2 in the same block (all being candidates for the same number n and no candidate n in the 3rd block intersecting row r).

Code: Select all
x t1              t2 y
Z1                  Z2


You can reverse the roles of blocks and rows.
You can easily imagine longer intermediate chains with any number of z1 z2 t1 t2 candidates in the intermediate cells.
The conditions are the same as for a whip, except that there are now 2 "targets".
Instead of a contradiction on the target in a whip, here the conclusion is a contradiction between the two targets.



As for the way these may be used within W*-whips and B*-braids, you can confine your reading to what's in bold characters in my post, which is a very simple and clear view of how these patterns generalise whips/braids.
The intuitive meaning is that, in W*-whips [resp. B*-braids], bi-whip [resp. bi-braid] contradictions can be used wherever direct links are used in ordinary whips/braids.
The simplest example of W*-whips is W1-whips = g-whips. You can see the corresponding thread for examples. Moreover, in this case, the equivalence of the two views is trivial.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: more on whips, braids, T&E...

Postby Mauricio » Fri Sep 07, 2012 12:07 am

Mauricio
 
Posts: 1174
Joined: 22 March 2006

Previous

Return to Advanced solving techniques