Abominable TRIAL-and-ERROR and lovely BRAIDS

Advanced methods and approaches for solving Sudoku puzzles

Postby denis_berthier » Mon Oct 27, 2008 11:44 pm



In this post, I summarise the notions necessary to define general whips and braids and I develop the consequences of the following general idea

ZT-ING or, more specifically, ZT-WHIPPING OR ZT-BRAIDING IS THE WAY OF INCLUDING BASIC PATTERNS IN WHIPS OR BRAIDS.

It is a natural, and fully supersymmetric, generalisation of the "almost-ing" principle widely used to include ALS, AALS, AAALS ..., AHS, AAHS, ...., A-Fish, AA-Fish, ..., in AICs.
Instead of almost-ing wrt to the previous right-linking candidate in the chain, it does almost-ing wrt to the target and all the previous right-linking candidates.


In the same way as my definition of a chain unifies the previously conflicting views of a chain as a sequence of candidates and as a sequence of cells (in this case of rc-, rn-, cn- or bn- cells), my definitions of a whip and a braid unifiy the research on elementary patterns with limited resolution potential and the research on more complex patterns with broad resolution potential, which have to be based on chains/whips/braids/nets.

But it should first be recalled here that all that follows is interesting only for exceptionally hard puzzles: puzzles solvable by a human can be solved by the most basic nrczt-whips.


For completeness, let me recall the main definitions.

Definition: Given a set S of candidates and an abstract elementary pattern P (e.g. a Naked-Pair or a Swordfish), we say that another set S' of candidates satisfies pattern P modulo S if, when all the candidates in S' that are nrc-linkded to some candidate in S are forgotten from S', what remains in S' satisfies pattern P.

Definition: If P is any elementary pattern, with an associated resolution rule, a candidate C is nrc-linked to P if it satisfies the conditions of the elimination rule for P.

Now, let FP be any fixed family of basic patterns.

Definition: given a target candidate z, a zt-whip(FP) [resp. a zt-braid(FP)] built on z is any sequence L1 R1 L2 R2 L3 R3 .... Ln of elements alternatively called left-linking and right-linking, where
- L1, L2 ... Ln are candidates, (as usual, it is not necessary to extend the possibilities on left-linking candidates),
- each of R1, R2, R3 ... Rn-1 is a pattern from the FP family modulo the target and the previous right-linking candidates,
- L1 is nrc-linked to the target,
- for each 1 < k <= n: Lk is nrc-linked to Rk-1 (in the above extended sense of "nrc-linked") [resp. for braids: nrc-linked to the target or to any previous right-linking candidate]; this is the first part of the chain [resp. braid] condition,
- for each 1 <= k < n, Lk is nrc-linked to at least one element of either the rc-, rn-, cn- or bn- cell containing Rk; this is the second part of the chain condition,
- there is an rc-, rn-,- cn, or bn- cell containing Ln such that there is no candidate in this cell compatible with the target and the previous right-linking candidates.
The patterns in FP are called the generating patterns of the braids zt-braid(FP).


As the families FP of generating patterns will always contain ECP+NS+HS (rules for Elementary Constraints Propagation and for Singles), these patterns will often be left implicit.

Thus, we shall write zt-braids(BI) instead of zt-braids(ECP+NS+HS+BI). These are what I've previously called the hinged-nrczt-braids or grouped-nrczt-braids.

Similarly, we shall write zt-braids(BI+SubsetRules) to mean zt-braids(ECP+NS+HS+BI+ SubsetRules). These are what I've previously called the hinged-nrczt-ALS-braids, which subsume all the nrczt-whips, all the grouped nrczt-whips and all the grouped AICs (including ALS, AALS, AAAAALS, AHS, AAAAHS, A-Fish, AAAAFish,....)


The notion of a zt-braid(FP) establishes a duality between the families FP of basic patterns and the families zt-braid(FP) of braids.


I have proven the following:

T&E(FP) vs zt-braid(FP) theorem: for any family of patterns FP with associated resolution rules, any elimination that can be done by T&E(FP) can be done by a zt-braid(FP)


The T&E(FP) vs zt-braid(FP) theorem provides an easy means of testing whether a puzzle can be solved by zt-braid(FP).

This theorem can even provide a zt-braid(FP) solution for a puzzle, built from the trace of the T&E(FP) procedure. Notice however that this solution will differ from one obtained by directly looking for patterns in four respects:
- the zt-braids thus obtained will have lots of useless branches,
- even if the zt-braids thus obtained are manually pruned of their useless branches, they won't be the shortest ones possible,
- no simpler patterns, such as whips or 2D-chains ..., will be obtained,
- more generally, contrary to what is done for the rules in SudoRules, this procedure doesn't provide any means of putting priorities on the patterns obtained.



We are now naturally led to the question:

What is the "simplest" family FP of elementary patterns such that all the puzzles are solvable by zt-braid(FP)?

I've already mentioned that one can take FP = nrczt-braids and that all the known puzzles can be solved by zt-braids(nrczt-braids), but FP = nrczt-braids is too complex to be an interesting generating family.
The following results suggest that one can find a family FP of basic patterns much simpler than nrczt-braids such that all the known puzzles can be solved by zt-braids(FP).
Of course, the same question can be asked for whips:

What is the "simplest" family FP of elementary patterns such that all the puzzles are solvable by zt-whip(FP)?

In a sense, the question about whips is more interesting, because whips are chains (no branching) whereas braids are nets (even though relatively mild ones), but it is much more difficult to deal with it.



In a previous post, I had given results for the gsf collection of extreme puzzles. Here are more detailed results for the same braids.

Code: Select all
Nb of puzzles solved by the different types of braids:

FP family............ECP+NS+HS.........ECP+NS+HS+BI..............BI+SubsetRules
Braids used..........nrczt-braids......hinged-zt-braids..........hinged-zt-LS-braids
Other name(s)..........................grouped-nrczt-braids......zt-braids(BI+SubsetRules)
.......................................zt-braids(BI)
1-500................0.................187.......................443
501-1000.............0.................178.......................460
1001-1500............0.................163.......................486
1501-2000............0.................168.......................490
2001-2500............0.................135.......................474
2501-3000............0.................116.......................479
3001-3500............1.................120.......................473
3501-4000............0.................113.......................472
4001-4500............1.................104.......................448
4501-5000............0.................231.......................482
5001-5500............47................348.......................500
5501-6000............434...............490.......................500
6001-6500............487...............500.......................500
6501-7000............494...............500.......................500
7001-7500............500...............500.......................500
7501-8000............500...............500.......................500
8001-8152............152...............152.......................152
Total................2616..............4505......................7859
Rest.................5536..............3647......................293



As zt-braids(BI+SubsetRules) subsume all the grouped whips and AICs, this will be the starting point for my further analyses of larger families of generating patterns.
Last edited by denis_berthier on Mon Dec 08, 2008 5:50 pm, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Tue Oct 28, 2008 4:48 am


Adding finned fish and x2y2-belts in the zt-braids(BI+SubsetRules).

I've been wondering about adding x2y2-belts in the family of generating patterns of zt-braids.
x2y2-belts have been defined here: http://forum.enjoysudoku.com/viewtopic.php?t=5894
They are my interpretation of Steve's pattern (also known as SK-loop).
When x2y2-belts are added to the above family of generating patterns, we get a new type of braid: zt-braid(BI+SubsetRules+x2y2-belts)

However, there are patterns simpler than x2y2-belts that should be introduced before them as generating patterns. I therefore introduced finned fish.


Code: Select all
Nb of puzzles solved by the different types of braids:

FP family............ECP+NS+HS.........+BI.......................+SubsetRules................+finned-fish................+x2y2-belts
1-500................0.................187.......................443.........................466.........................489
501-1000.............0.................178.......................460.........................480.........................497
1001-1500............0.................163.......................486.........................494.........................500
1501-2000............0.................168.......................490.........................496.........................499
2001-2500............0.................135.......................474.........................489.........................497
2501-3000............0.................116.......................479.........................493.........................499
3001-3500............1.................120.......................473.........................486.........................498
3501-4000............0.................113.......................472.........................493.........................499
4001-4500............1.................104.......................448.........................471.........................497
4501-5000............0.................231.......................482.........................494.........................499
5001-5500............47................348.......................500.........................500.........................500
5501-6000............434...............490.......................500.........................500.........................500
6001-6500............487...............500.......................500.........................500.........................500
6501-7000............494...............500.......................500.........................500.........................500
7001-7500............500...............500.......................500.........................500.........................500
7501-8000............500...............500.......................500.........................500.........................500
8001-8152............152...............152.......................152.........................152.........................152
Total................2616..............4505......................7859........................8014........................8126
Rest.................5536..............3647......................293.........................136.........................26



These results are an indication of what a generating family of patterns may be and what the resolution potential of the corresponding braids is; it is not proposed as the final answer to the questions in the previous post.
What's noticeable here again is that, for any FP family, the number of puzzles unsolved is almost constant in a broad range of the Q1 rating.
Last edited by denis_berthier on Mon Dec 08, 2008 6:04 pm, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Wed Nov 05, 2008 9:53 pm

Deleted: superseded by modifications in the previous post.
Last edited by denis_berthier on Mon Dec 08, 2008 6:07 pm, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Mon Nov 10, 2008 12:35 am

Deleted: superseded by modifications in the previous post.
Last edited by denis_berthier on Mon Dec 08, 2008 6:08 pm, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Wed Nov 12, 2008 11:05 pm

Deleted: superseded by modifications in the previous post.
Last edited by denis_berthier on Mon Dec 08, 2008 6:08 pm, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby DonM » Thu Nov 13, 2008 6:51 am

denis_berthier wrote:[b]One way these results shouldn't be interpreted is as any form of support on my part for nets. I've always said I didn't like nets, but there's no formal logic reason for this, it is just a personal opinion. And it seems that some form of nets is necessary if one wants to solve the hardest puzzles. Of course again, I doubt any normal player wants to solve the hardest puzzles.


Approximately, what difficulty, say ER, level are you considering the hardest puzzles? (Serious question of interest.:) )
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby denis_berthier » Thu Nov 13, 2008 7:17 am

DonM wrote:Approximately, what difficulty, say ER, level are you considering the hardest puzzles?

I'm not a specialist of the hardest puzzles. The hardest ER I know is 11.6. But I think ER is not very meaningful at such levels.
AFAIK, no such puzzle has ever been been solved manually.

The hardest puzzles that are solved manually by excellent players I know are at ER 9.3 or 9.4.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby re'born » Thu Nov 13, 2008 9:27 am

denis_berthier wrote:
DonM wrote:Approximately, what difficulty, say ER, level are you considering the hardest puzzles?

I'm not a specialist of the hardest puzzles. The hardest ER I know is 11.6. But I think ER is not very meaningful at such levels.
AFAIK, no such puzzle has ever been been solved manually.

The hardest puzzles that are solved manually by excellent players I know are at ER 9.3 or 9.4.


Presumably this is, at least, modulo the occasional 10 or 11+ solved using Gurth's symmetry techniques. Even I can do those by hand.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby denis_berthier » Thu Nov 13, 2008 8:55 pm

re'born wrote:
denis_berthier wrote:
DonM wrote:Approximately, what difficulty, say ER, level are you considering the hardest puzzles?

I'm not a specialist of the hardest puzzles. The hardest ER I know is 11.6. But I think ER is not very meaningful at such levels.
AFAIK, no such puzzle has ever been been solved manually.

The hardest puzzles that are solved manually by excellent players I know are at ER 9.3 or 9.4.


Presumably this is, at least, modulo the occasional 10 or 11+ solved using Gurth's symmetry techniques. Even I can do those by hand.


Right, but this will be true of any technique: if specific patterns (based on some form of symmetry or other) are present in a puzzle and allow specific eliminations, the difficulty of the puzzle measured by a rating that doesn't take the corresponding specific rules into account looses much of its meaning.
I'm not proficient in Gurth's techniques, but rules based on specific symmetries may be an interesting topic as an exercice of rule writing (AI teacher speaking). Do you have references?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby 999_Springs » Sat Nov 15, 2008 11:35 am

denis_berthier wrote:The hardest puzzles that are solved manually by excellent players I know are at ER 9.3 or 9.4.

I'm quite surprised - is the mid-9s really the cap on manual solving? I wouldn't consider myself a particularly excellent player, but two and a half years ago I found a neat solution to a puzzle which I recently learnt was #2 from the top1465 (ER=9.5) and I posted it here (5th post on the page).
Hidden Text: Show
Once upon a time I was a teenager who was active on here 2007-2011
999_Springs
 
Posts: 367
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Postby DonM » Sat Nov 15, 2008 1:30 pm

999_Springs wrote:
denis_berthier wrote:The hardest puzzles that are solved manually by excellent players I know are at ER 9.3 or 9.4.

I'm quite surprised - is the mid-9s really the cap on manual solving? I wouldn't consider myself a particularly excellent player, but two and a half years ago I found a neat solution to a puzzle which I recently learnt was #2 from the top1465 (ER=9.5) and I posted it here (5th post on the page).


SE is not perfect and it is possible that this an aberration because ordinarily any puzzle roundabout ER= above 8.6-9.0 can't be solved without a net. The 2nd possibility to be perfectly honest is that your solution has an error mainly because the two critical chains do not have complete notation which means that the eliminations can't be easily verified. I say this with the greatest of humility because I have submitted more than one solution for puzzles at ER >= 8.3 that I thought was the best of the bunch only to be informed that I had made an error- and that was after having checked it several times.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby denis_berthier » Sat Nov 15, 2008 8:46 pm

999_Springs wrote:
denis_berthier wrote:The hardest puzzles that are solved manually by excellent players I know are at ER 9.3 or 9.4.

I'm quite surprised - is the mid-9s really the cap on manual solving? I wouldn't consider myself a particularly excellent player, but two and a half years ago I found a neat solution to a puzzle which I recently learnt was #2 from the top1465 (ER=9.5) and I posted it here (5th post on the page).

I've just checked: top1465 #2, SER 9.5, can't be solved with mere nrczt-whips but it can be solved with zt-braids(ECP+NS+HS+BI) i.e. hinged-nrczt-braids.

Could you be more explicit on the following two chains in your solution and what they eliminate?
Code: Select all
r5c2-7(-r5c4)-r5c789=7=hidden pair r46c7-7-r2c7=7=hidden pair r2c89=5=r2c5-5-r4c5-9-r5c4-4-r5c7-1-r5c8, no value for r5c9
hidden pair in c2
r8c2=8
3 is locked in c3b7
r2c7-7(-r7c7)-naked triple r456c7-1-r7c7-2(-r7c5)-r7c1-1(-r4c1)-r7c5-5-r4c5-9(-r5c4)-r4c1-8-r4c7-1-r5c7-4-r5c4-7, no place for 7 in b6

They look like some zt-whip with Pair and Triplet components. Could you try to re-write them as such?

As for the highest SER accessible to human solvers, the good news of this thread is that, if you accept nets (which are anyway necessary for extreme puzzles), then you can't refuse braids (which are the mildest kind of nets one can imagine - there is still some linear structure) and you can hardly refuse Trial and Error (with no recursion and no guessing). As a result, using T&E in combination with relatively simple patterns, you can solve all the puzzles.

Of course, one can refuse nets for puzzles that can be solved without them (and I am personally on this side). Looking for whips based on different families of basic patterns is then the most powerful technique as of today. But we have no idea of how powerful exactly (probably much beyond SER 10).
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Sat Nov 15, 2008 8:48 pm

DonM wrote:ordinarily any puzzle roundabout ER= above 8.6-9.0 can't be solved without a net.

Puzzles upto SER 9.3 can be solved with nrczt-whips - no net is necessary.
And, if you put more complex components in the whips, then you can go much beyond SER 9.3.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby Allan Barker » Sat Nov 15, 2008 10:37 pm

I think I understand Denis's view that 9.5 seems to be some kind of barrier. There is an immense change of difficulty between about 9.5 and 11.5 as if SE compresses the top of the scale above 9.5. If the scale went from 1 to 30, with 10 to 30 covering the existing 9.5 to 11.5 range, maybe the scale would look more linear.

denis_berthier wrote:I've just checked: top1465 #2, SER 9.5, can't be solved with mere nrczt-whips but it can be solved with zt-braids(ECP+NS+HS+BI) i.e. hinged-nrczt-braids.

I took a look at the same and found a short, non-symetrical rank=0 SK-like loop that blasts the puzzle to singles.
I posed it here in the Monster Loop thread, top1465 #2 loop solution.
.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby ttt » Sat Nov 15, 2008 11:04 pm

Hi All,
For #2 of top 1465, based on 999-Springs, I present as below (using Eureka! – AIC notation):
Code: Select all
 *-----------*
 |7.8|...|3..|
 |...|2.1|...|
 |5..|...|...|
 |---+---+---|
 |.4.|...|.26|
 |3..|.8.|...|
 |...|1..|.9.|
 |---+---+---|
 |.9.|6..|..4|
 |...|.7.|5..|
 |...|...|...|
 *-----------*
After SSTS
 *--------------------------------------------------------------------------------------*
 | 7        126      8        | 459      4569     4569     | 3        1456     1259     |
 | 469      36       3469     | 2        34569    1        | 4679     45678    5789     |
 | 5        1236     123469   | 78       3469     78       | 12469    146      129      |
 |----------------------------+----------------------------+----------------------------|
 | 189      4        1579     | 3579     59       3579     | 178      2        6        |
 | 3        1267     12679    | 479      8        24679    | 147      1457     157      |
 | 268      25678    2567     | 1        2456     24567    | 478      9        3        |
 |----------------------------+----------------------------+----------------------------|
 | 128      9        12357    | 6        125      2358     | 127      1378     4        |
 | 12468    12368    12346    | 3489     7        23489    | 5        1368     1289     |
 | 12468    1235678  1234567  | 34589    12459    234589   | 12679    13678    12789    |
 *--------------------------------------------------------------------------------------*

Move 1: present as Kraken cell => r5c236<>7
Code: Select all
(7)r5c4
 ||
(4)r5c4-(4=ht157)r5c789
 ||
(9)r5c4-(9=5)r4c5-(5)r2c5=(hp58-7)r2c89=(7)r2c7-(7)r456c7=(7)r5c89

Move 2:
Code: Select all
(5)r2c5=(hp58-7)r2c89=(7)r2c7-(7=hp12)r7c17-(12=5)r7c5

=> loop => r1469c5<>5, r456c7<>7, SSTS to the end

Edit:
Other way for thinking on Move 1, look 5’s & 7’s and bilocation 8’s at row 2 => at least one of r2c5=5 & r2c7=7 must be true
Code: Select all
(quad1457=9)r5c4789-(9=5)r4c5-(5)r2c5=(hp58-7)r2c89=(7)r2c7-(7)r456c7=(7)r5c89 => r5c236<>7


BTW, I think that is not much puzzles with ER9.5 like this...:D

ttt
ttt
 
Posts: 185
Joined: 20 October 2006
Location: vietnam

PreviousNext

Return to Advanced solving techniques