Set Logic Solns: Top1465#77, Easter Mons. Golden Nugget

Advanced methods and approaches for solving Sudoku puzzles

Postby denis_berthier » Thu May 22, 2008 7:21 am

Allan Barker wrote:I have always assumed this to be the case, without proof, i.e., that an elimination can open new opportunities to eliminate other candidates that could not be cleared before, or in your words, open shorter paths. Further, doesn't this imply that given a group of candidates that cause an elimination, if one or more of the candidates is removed then the remaining candidates (alone) will still cause the same elimination?

Allan, the first assertion needs no proof, as we have lots of examples. The second is much more delicate. It isn't a consequence of the first. All depends on what you mean by "cause the same elimination". If you have a fixed set of resolution rules (a resolution theory) and it doesn't have the confluence property, it might be the case that, after an elimination, some other eliminations are no longer justified by the rules. One example is BUG: an elimination allowed by BUG may become impossible if another rule is applied before it, that destroys the BUG pattern.
In case of your solver, this shouldn't happen, but this might happen at the stage of the recognizer if its set of rules doesn't have the confluence property.

Allan Barker wrote:What would be interesting is, what portion of the logic used to solve a puzzle can be classified as nrctz chains, etc.
Yes.
Or one could also consider the maximum rank necessary to solve a puzzle as a new (rough) rating and ask:
- what % of the minimal puzzles can be solved at ranks 1, 2, 3,...?
- are you sure you ever need rank 3 (for this example or for any puzzle)?
- how does the rank correlate with other ratings?
- is there any relation between rank and nrczt-solvability?
Could your solver produce such a rating (discarding the recognizer if necessary), e.g. for gsf's list?

You may consider I'm giving too much importance to rank, but, in my approach, introducing rules for (something analogous to your) rank 2 would add much complexity.

Allan Barker wrote:I was surprised I could "cut and paste" your first order logic into a second order form.
As second order logic is an extension of first order, I'm not really surprised.

Allan Barker wrote:I'm beginning to think that first order and second order logic are less different that I had imagined.
I don't know how different you imagined they were. The basic rules are the same. The "only" difference is that you have quantifiers on subsets.
But this changes a lot of things:
- from a theoretical POV, you get almost the full power of set theory - which is generally considered too much by logicians,
- from a practical POV, you reach another scale of complexity.
For problems on a finite domain, such as Sudoku, the theoretical difference can be discarded, but not the complexity problems.

Considering that Sudoku(n) is NP-complete, you may be interested by the following:
Wikipedia http://en.wikipedia.org/wiki/Fagin_theorem wrote:Fagin's theorem is a result in descriptive complexity theory which states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP. It is remarkable since it is a characterization of the class NP which does not invoke a model of computation such as a Turing machine.

More generally:
Wikipedia http://en.wikipedia.org/wiki/Descriptive_complexity wrote:Descriptive complexity is a branch of finite model theory, a subfield of computational complexity theory and mathematical logic, which seeks to characterize complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the class of languages expressible by statements of second-order logic. This connection between complexity and logic allows results to be transferred easily from one area to the other, facilitating new proof methods and providing additional evidence that the main complexity classes are somehow "natural" and not tied to the specific abstract machines used to define them.
Specifically, each logical system produces a set of queries expressible in it. The queries correspond to the computational problems of traditional complexity theory.
The first main result of descriptive complexity was Fagin's theorem, shown by Ronald Fagin in 1974,[1] which established that NP is precisely the set of languages expressible by sentences of existential second-order logic; that is, second order logic excluding universal quantification over relations, functions, and subsets.
Many other classes were later characterized in such a manner, most of them by Neil Immerman:
First-order logic defines the class FO, corresponding to AC0, the languages recognized by polynomial-size circuits of bounded depth, which equals the languages recognized by a concurrent random access machine in constant time.
First-order logic with a commutative, transitive closure operator added yields SL, which equals L, problems solvable in logarithmic space.
First-order logic with a transitive closure operator yields NL, the problems solvable in nondeterministic logarithmic space.
In the presence of linear order, first-order logic with a least fixed point operator gives P, the problems solvable in deterministic polynomial time.
Existential second-order logic yields NP, as mentioned above.
Universal second-order logic (excluding existential second-order quantification) yields co-NP.
Second-order logic corresponds to PH.
Second-order logic with a transitive closure (commutative or not) yields PSPACE, the problems solvable in polynomial space.
Second-order logic with a least fixed point operator gives EXPTIME, the problems solvable in exponential time.


As we usually consider only the case n=9, it isn't very clear how this relates to the type of rules (first order as in SudoRules or existential second order as in your solver) needed to solve all the puzzles. But as the rules we use are valid for any n...

My approach was different: anticipating the complexity problems and motivated by human solvability, instead of trying to solve all the puzzles with rules of unbounded complexity, I tried to solve as many puzzles as possible with first order rules. For n=9, the answer is 99,99% of the minimal puzzles can be solved with nrczt-chains. How would this percentage evolve with n is an open question. I don't think I'll ever provide any answer, because:
- I've no random generator for 16x16 puzzles (or worse for 25x25, 36x36,...),
- I'm not sure SudoRules would have reasonable computation times and memory requirements for such puzzles,
- there is no obvious theoretical approach of such questions.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby StrmCkr » Sat May 24, 2008 2:57 am

What list? If you're referring to the top1465, that's an old list ... and there's no obligation by anyone to keep it current.

AFAIK the most recent comprehensive list of "toughies" is gsf's "q1-taxonomy". Your puzzle is there


i was refering to champanes list of hardest puzzle as it has Metcalfs on it but not mine... just pointing it out since he mentioned links to his list.

yes i know it has a sk loop - or a virus pattern as u refer it as. i commented on the thread in gneral puzzles with where im at on it.

yes the puzzle is also listed on the hardest thread shortly after metcalf posted his discovery i posted the cusin... havent seen to much on solving untill recently. but this is about #77 and this is my last post regardign off topic stuff.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 647
Joined: 05 September 2006

Postby Allan Barker » Sun May 25, 2008 1:26 pm

Denis,
the part about NP and complexity is particulary good since as I'm always keen to understand the theory side better. I clearly understand the practical side of complexity from the hole in the wall next to my computer in the shape of my head. But the challenge is also the fun of it. The rationale for first order logic is also clear.

Or one could also consider the maximum rank necessary to solve a puzzle as a new (rough) rating and ask:
- what % of the minimal puzzles can be solved at ranks 1, 2, 3,...?
- are you sure you ever need rank 3 (for this example or for any puzzle)?
- how does the rank correlate with other ratings?
- is there any relation between rank and nrczt-solvability?
Could your solver produce such a rating (discarding the recognizer if necessary), e.g. for gsf's list?


As far as rank goes, it should be an important parameter however, it is interdependent with other things such as length or logical permutations. Just below, I will post a logical solution to EM in which one of the difficult eliminations uses rank 6 logic! although the size of the cluster was relatively small. When I get more time I hope to look into the rating question. I think I might be able to compute the minimum number of logical permutations required to reach a solution The first thing I will try will be gsf's list.

Allan Barker wrote:
........... Further, doesn't this imply that given a group of candidates that cause an elimination, if one or more of the candidates is removed then the remaining candidates (alone) will still cause the same elimination?

Denis wrote:
All depends on what you mean by "cause the same elimination". .......... In case of your solver, this shouldn't happen, but this might happen at the stage of the recognizer if its set of rules doesn't have the confluence property.


Now it seems I did prove this assertion, somewhat indirectly, at least for working with sets. The argument is based on how permutations combine. It is is not possible for outside candidates (relative to a group of candidates) to remove 'good' permutations from inside the group, which intern are responsible for the internal eliminations. Good permutations means permutations related to those candidates that will eventually form the solution.

I no longer use the recognizer as it was originally meant for software that might be distributed to help bridge the gap between the second order world and the first order world. It still works though and could be used as discussed for statistics.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby Allan Barker » Sun May 25, 2008 2:05 pm

This message left intentionally blank.:(
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby Allan Barker » Sun May 25, 2008 2:34 pm

Complete Logical Solution to Easter Monster

The complete logical solution to Easter Monster can be found on my website,
http://sudokuone.com/sweb/extra/easter/a_em.htm. I have placed a few example eliminations here that focus on smaller eliminations with interesting logic rather than the large, very difficult ones. However, two difficult moves are included near the bottom particulary Elimination 8, which has a rank of 6. For comparison, chains are rank 1 and AALS are rank 2.

The solution, like that to Top1465 #77, is based on freeform logic that allows eliminations to assume any logical form. The logic should therefore have a more natural form than logic produced by other techniques. Freeform logic never requires more than about 60 nodes for the most difficult eliminations.

General set logic theory provides relatively simple explanations for these eliminations. In fact, the most difficult eliminations rely more heavily on the two main principles of general set logic, 1) the containment of eliminatees in multiple sets and 2) the use of triplet links to "concentrate" the logic.
.
Notation. The notation is the same except some cases use a list of covering linksets instead of overlap linksets, particularly for rank 0, fish-like logic. An embedded (STS..) refers to triplets where T means linkset Triplet and S means Set triplet. A description of how Sudoku set logic rules are applied can found under "A Quick Guide to Sudoku Set Logic" in the second post of this thread or on this website page: Quick Guide to Sudoku Set Logic


Elimination 1, rank 0 super-fish catches 13.

These early elimination(s) to Easter Monster have been reported previously, most notably
Steve K's EM Attack. The highly symmetric solution can take many forms, most of which use 16 sets and 16 linksets to make a ring like rank 0 super-fish that eliminates 13 candidates. Shown here are two eliminations with different symmetry, the least symmetrical first.

Rank 0, S[r2(12) n1(28) n3(28) n7(28) n8(1379) n9(28) b2(67)], L[r1(67) r8(45) c2(48) c8(39) n2(56) b12 b31 b7(16) b9(27)] => r1c3<>7, r2c5<>3, r2c5<>8, r2c6<>8, r3c1<>2, r5c2<>4, r5c2<>8, r5c8<>3, r5c8<>9, r7c3<>1, r8c4<>5, r8c5<>4, r9c1<>6

which is of the form S[set group]+L[linkset group] => <eliminations>

Note: The yellow in box 7 indicates a highlighted elimination set, which can be seen in the 3D image by clicking the reference below.

Image
View 3D image

A more symmetrical solution that eliminates the same candidates using only cell sets in the corner boxes is shown below.

Rank 0, S[n1(28) n2(1379) n3(28) n7(28) n8(1379) n9(28)], L[r2(38) r8(45) c2(48) c8(39) b1(27) b3(16) b7(16) b9(27)] => r1c3<>7, r2c5<>3, r2c5<>8, r2c6<>8, r3c1<>2, r5c2<>4, r5c2<>8, r5c8<>3, r5c8<>9, r7c3<>1, r8c4<>5, r8c5<>4, r9c1<>6

Image
View 3D image

Steve K's Original Solution:

Image
[

Eliminations 2 to 4, rank 0 symmetric Naked Triples.

Eliminations 2 and 4 are row and column naked triples symmetrically arranged in a '+' pattern centered in the middle of the grid. They fill the gaps in the structure of elimination 1. Together they remove another 15 candidates and produce the first assignment, which removes 6 more candidates.

Elimination 1: Rank 0, S[n5(248)] + L[r5(126)] =>
r5c1<>2, r5c1<>6, r5c3<>1, r5c6<>1, r5c6<>2, r5c6<>6, r5c7<>1, r5c7<>2, r5c9<>6
Elimination 3. Rank 0, S[n56](single) => r5c6=4, r4c5<>4, r5c1<>4, r5c3<>4, r7c6<>4, r9c6<>4.
Elimination 4. Rank 0, S3=[n(248)5] + L[c5(126)] => r1c5<>6, r3c5<>1, r3c5<>2, r7c5<>1, r7c5<>2, r9c5<>6.


Elimination 23, a triplet jellyfish.

Image

This structure would be a rank 0 jellyfish with 4 sets and 4 linksets except that box 5 overlaps column set 5. This forms a set triplet that raises the effective rank of the structure to 1 except in the direction of the triplet's linkset, row 4. Therefore, rows 2 and 4 can cause eliminations while rows 6 and 8 cannot. The 3D diagram highlights the rank 0 region in black. The set structure is:

Rank 0, [c(357)1 b51] + [r(2468)1](S) => r4c8<>1

Image


Elimination 10, rank 2, triplet Kraken fish.

Image

Elimination 10 has 4 sets connected by 6 linksets and is therefore rank 2, which requires 3 overlapping linksets to however, there is no place where this happens. According to set logic rules, the minor side of triplet A has a rank that is lower by 1 this rank = 1. Column 9 and row 6 can therefore overlap and remove candidate r6c9n6. The region of lower rank caused by triplet A is highlighted in crimson (or yellow for column 9). The logic is then:

Rank 2, [r(28)6 c26 b56](T)r56*c96 => r6c9<>6

Image


Elimination 26, simple logic.

Image

Elimination 26 is a medium size rank 2 cluster but its logic is simple. It needs 3 overlapping linksets to make elimination but has only two. The only triplet A lowers the rank along the path with cell set n83 thereby allowing overlapping linksets r85 and n87 to eliminate candidate r8c7n5. According to set logic, it is not necessary to address all of the complexity in the logic to eliminate the candidate.

Rank 2, [r(46)1 r34 c2(12) c72 n83 b94](T)r85*n87 => r8c7 <> 5

Image


Elimination 32, a rank 0 path in a rank 1 group.

Image

Elimination 32 is a rank 1 multiple-loop with both set and linkset triplets. Although it has 7 sets, only 6 true nodes are guaranteed if set triplet S is occupied and the effective rank for the structure would be 2. However, set triplet S points in the direction of row 51 and lowers the rank along that path. Linkset triplet T points in the opposite direction along the same path lowering the effective rank further to rank 0. Linksets along this path can therefore eliminate candidates including the one at r5c9n5. This illustrates the additive nature of triplets. The rank 0 sets are highlighted in black. The elimination is thus:

Errata:[has 8 sets, only 7 true nodes] -> [has 7 sets, only 6 true nodes]

S7=[r35 r51 c35 c82 n7(26) b71](ST)n58 => r5c8<>6
Image


Elimination 8, rank 6 logic!

Last but surely not least is elimination 8, which has the incredible rank of 6, which implies that 7 overlapping linksets are required to eliminate a candidate. The logic is small relative to other difficult eliminations and uses only 15 sets plus required linksets.

Image

As shown in the logic diagrams, candidate r2c5n2 sits at the intersection of 4 link sets however, this is not enough to eliminate the candidate. The three linkset triplets marked as A, B, and C all point in the direction of the candidate and thus lower the effective rank in the region of the candidate. Such effects are usually additive. Set triplets, most obviously X and Y, are also oriented correctly in the direction of the candidate. A proper analysis of multiple triplets is not difficult but the final proof is that the candidate is eliminated.

S15=[r21 r34 r4(247) c(58)1 c(168)2 n8(39) b1(25) b62], L21=[r(48)1 r(267)2 r85 c3(45) c72 c9(47) n25 n3(12) n4(1358) n58 b22 b31] => r2c5<>2

Image


Elimination 14, the bigger the better, 51 set logic cluster.

View 2D image
View 3D image

Elimination 14 is the largest set cluster found while solving Easter Monster. It is a 51 set, rank 5 structure with many triplets. The 51 sets contain 61 candidates. The set notation for the structure is:

Rank 5, [r(27)2 r(148)4 r35 r19 c8(39) n(379)2 n83 n(27)5 n96 b15 b2(28) b3(16) b74 b97] + [r2(16) r38 r7(34) r9(67) c14 c28 c3(45) c58 c6(258) c74 n31 n34 n15 n17 n(1379)8 n89 b1(24) b71] => r3c1<>4.
Last edited by Allan Barker on Tue May 27, 2008 10:26 pm, edited 5 times in total.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby ronk » Sun May 25, 2008 3:46 pm

Allan Barker wrote:
Elimination 32, a rank 0 path in a rank 1 group.

Image

Elimination 32 is a rank 1 multiple-loop with both set and linkset triplets. Although it has 8 sets, only 7 true nodes are guaranteed if set triplet S is occupied and the effective rank for the structure would be 2. However, set triplet S points in the direction of row 51 and lowers the rank along that path. Linkset triplet T points in the opposite direction along the same path lowering the effective rank further to rank 0. Linksets along this path can therefore eliminate candidates including the one at r5c9n5. This illustrates the additive nature of triplets. The rank 0 sets are highlighted in black. The elimination is thus:

S8=[r35 r51 r72 c35 c82 n7(26) b71](ST)n58 => r5c8<>6

2r7c8 appears to be a "set triple" and yet it received no mention. Why?

No digit of r7c6 is covered twice, so how can there be a "linkset triple?"

Moreover, 2r7c6 seems to be a set triple -- rather than a linkset triple -- because it's a member of both cellset r7c6 and rowset 2r7.

There's a lot I don't understand about the "ranks", but these three points seem to be more basic than that. What am I missing?

[edit: Allan Barker changed url of "original" incorrect image]
Last edited by ronk on Sun May 25, 2008 11:50 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Allan Barker » Mon May 26, 2008 3:15 am

Ronk wrote: 2r7c8 appears to be a "set triple" and yet it received no mention. Why?
No digit of r7c6 is covered twice, so how can there be a "linkset triple?"
Moreover, 2r7c6 seems to be a set triple -- rather than a linkset triple -- because it's a member of both cellset r7c6 and rowset 2r7.
There's a lot I don't understand about the "ranks", these three points seem to be more basic than that. What am I missing?

Nothing, you have caught an error. I uploaded an old version of elimination 31, probably from worrying too much about background colors, etc. The only difference is row set r72, which is shown as a (strong) set in the old version and as a linkset in the new version.

Although both are 'logically' correct, viewing the old version and reading my description of the new version will surly be confusing. Besides, as you point out, 2r7c8 is not covered by a linkset and thus wrong wrt set theory as described. This is not logically incorrect because it is equivalent to an X-wing where one of the two linksets might be a strong set. However, to be true to set theory, the set should be drawn as a linkset *or* the nodes connecting the strong sets should be covered with additional linksets (i.e., box or cell sets). The analyzer does all this automatically.

I have replaced the files, which sit on my website, which also corrects the image in your reply. It might be good to preserve the error because it is informative. You can do this by editing your reply, look for the .jpg filename, and add 2 x's like [filexx.jpg].

Re, rank. Rank is a rather arbitrary word however, everything about rank up until triplets is an extension of fish like arguments, albeit a big one. A swordfish has 3 sets and 3 linksets. The three sets mean that 3 of the candidates in the swordfish must be real (be there) and they must be somewhere in the linksets. The linksets therefore have no spare capacity to accommodate other candidates, thus rank 0 means full. A finned swordfish has 4 linksets so it has one 'hole' left, rank 1. However, no candidate can be where two linksets overlap, the candidates from the sets must occupy at least one of the linksets.

Then triple points are all about what happens when a candidate, or a hole, occupies a three-way triplet.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby ronk » Tue May 27, 2008 1:08 pm

Allan Barker wrote:Complete Logical Solution to Easter Monster

The complete logical solution to Easter Monster can be found on my website, http://sudokuone.com/extra/easter/a_em.htm.

At this moment, this link is broken.

Allan Barker wrote:Elimination 1, rank 0 super-fish catches 13.

These early elimination(s) to Easter Monster have been reported previously, most notably
Steve K's EM Attack. The highly symmetric solution can take many forms, most of which use 16 sets and 16 linksets to make a ring like rank 0 super-fish that eliminates 13 candidates. Shown here are two eliminations with different symmetry, the least symmetrical first.

Steve Kurzhal's original K-loop step -- also symmetrical -- used paired strong links in r2, c8, r8 and c2, specifically the sets 1r2, 6r2, 2r2, and 7r2 plus the same for c8, r8 and c2. It would be nice if you included a 2D illustration of this form as well.

Allan Barker wrote:A more symmetrical solution that eliminates the same candidates using only cell sets in the corner boxes is shown below.

Rank 0, S[n1(28) n2(1379) n3(28) n7(28) n8(1379) n9(28)], L[r2(38) r8(45) c2(48) c8(39) b1(27) b3(16) b7(16) b9(27)] => r1c3<>7, r2c5<>3, r2c5<>8, r2c6<>8, r3c1<>2, r5c2<>4, r5c2<>8, r5c8<>3, r5c8<>9, r7c3<>1, r8c4<>5, r8c5<>4, r9c1<>6

Image

Should box 7 really be colored tan?

While linksets 2b1 and 6b7 are there, they aren't drawn thru eliminations 2r3c1 and 6r9c1, respectively.

Linksets 3c8 and 9c8 overlap (for the most part), so unless you already know they're there ... you probably won't know they're there.:) Ditto for linksets 4r8 and 5r8. (Well, in this case two different eliminations in each overlap are a big tipoff.) Unfortunately, there's probably little that can be done on a 2D image.

I'm gradually working my way up to the more complex illustrations.:)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Allan Barker » Wed May 28, 2008 3:13 am

Ronk,

OK, I have fixed everything, .. a few times.

Should box 7 really be colored tan?


Box 7 is tan because box set 6b7 is highlighted as an example elimination zone in the 3D image, to which I only posted a clickable reference.

While linksets 2b1 and 6b7 are there, they aren't drawn thru eliminations 2r3c1 and 6r9c1, respectively
.

The linkset links are part of the eliminator (eliminatiing structure), which does not include eliminated candidates (usually). I consider elimination "zones" seperately. The tan highlight was one such example zone.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby ronk » Wed May 28, 2008 1:20 pm

Allan Barker wrote:OK, I have fixed everything, .. a few times.

Thanks, I see your Easter Monster (EM) website link now working and the addition of Steve Kurzhal's original solution step (to this thread, not your website).

Allan Barker wrote:
Ronk wrote:
While linksets 2b1 and 6b7 are there, they aren't drawn thru eliminations 2r3c1 and 6r9c1, respectively.

The linkset links are part of the eliminator (eliminatiing structure), which does not include eliminated candidates (usually). I consider elimination "zones" seperately. The tan highlight was one such example zone.

OK. I'll view any linkset restricted to a box as "zonal" -- and without the need to be drawn thru its eliminations.

[edit: added the following]

Allan Barker wrote:Elimination 23, a triplet jellyfish.

[edit: image not quoted]

This structure would be a rank 0 jellyfish with 4 sets and 4 linksets except that box 5 overlaps column set 5. This forms a set triplet that raises the effective rank of the structure to 1 except in the direction of the triplet's linkset, row 4. Therefore, rows 2 and 4 can cause eliminations while rows 6 and 8 cannot.

I don't believe row 2 can cause eliminations.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Allan Barker » Thu May 29, 2008 2:37 am

[quote]..... of Steve Kurzhal's original solution step [quote/]
There is also a full description of Steve's SK loop at Steve's Easter Monster Solution, also sighted somewhere in my original thread on Sudoku Set Logic.

Row 2 of elimination 23
I don't believe row 2 can cause eliminations.

Row 2 of elimination 23 can eliminate candidates. I include another image where I highlight all elimination zones (transparent cubes) and 'add' a candidate to row 2, which is eliminated. Rank 0 sets are highlighted black. The results are from a second order logic analyzer that works for any logic form. The ultimate 'proof' is that no arrangement of candidates leaves row 2 unoccupied, which is easy to test. I included elimination 23 because I was surprised at such a simple example. According to set logic rules, the rank 0 zone continues until the branch rejoins the rest of the logic.

Image

Image

Another simple example, grouped turbot chain

A similar and more familiar example is this Grouped Turbot Chain from Sudopedia.

Image

According to the set logic rules, this overlap of row 5 and column 2 makes the structure rank 1 and makes the region on the linkset side of the overlap rank 0. The box linkset set immediately rejoins the rest of the logic so it is the only rank 0 linkset. The eliminations in rows 4 and 6 on the left are not related to candidates on the right in the same rows. The conventional arguments for these eliminations that I have seen are not pleasing(?).
The full discussion for the GTC is at: Grouped Turbot Chain

I will start on a brief guideline for images but in the mean time:

Quick Image Guide

Broad lines are the links for either sets or link sets.
Colors: red=ROW, green=COLUMN, blue=CELL, brown(tan)=BOX.
Sets: (strong links) are solid colors.
Linksets: (weak links) are light or transparent colors.
Linksets: can also be solid white (all types) in 3D rendered mode.
Singles or linksets connected to 1 node are short stubs extending in 2 directions.
Sets and linksets only connect candidates in the logic structure, unless noted.
Candidates are medium gray (3D) or numbered circles (2D), orange=eliminated, green= assigned, deep red=eliminated from within the structure. Candidates are highlighted white when viewing candidate permutations.
Optional highlights (comments usually included)
1. Set zones: highlight an entire set or linkset.
2. Elimination zones: highlight individual candidate elimination zones with squares (or cubes in 3D) yellow or pale blue.
2D grids are 2D projections of a 3D drawings, a tan box highlight in 2D could be 1, 2, or more highlighted box sets in 3D.
Sets and linksets will sometimes overlap in 2D, box linksets are slightly larger than other linksets to help show overlap. (I continue to work on this, but so far, I only get spaghetti).
Some other highlights:
1. Rank 0 (I use the work saturated) linksets are sometimes highlighted black.
2. End nodes, or groups of end-nodes shows as transparent purple zones.
3. Other optional highlights, as described.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby ronk » Thu May 29, 2008 1:09 pm

Allan Barker wrote:Row 2 of elimination 23
I don't believe row 2 can cause eliminations.

Row 2 of elimination 23 can eliminate candidates. I include another image where I highlight all elimination zones (transparent cubes) and 'add' a candidate to row 2, which is eliminated. Rank 0 sets are highlighted black.

I understand what you're saying, but I have a problem with "set theory" eliminations that effectively use internal strong links with triplets, in this case, r4c5 -1- r4c7 =1= r2c7. (Perusal of the more complex EM eliminations, however, leads me to believe such usage is commonplace.)

From another point of view, your r2 eliminations are valid only because some vertices of the c357b5\r2468 jellyfish are unpopulated. IOW it doesn't apply to the generalized cccb\rrrr jellyfish pattern.

Allan Barker wrote:A similar and more familiar example is this Grouped Turbot Chain from Sudopedia.

Image

According to the set logic rules, this overlap of row 5 and column 2 makes the structure rank 1 and makes the region on the linkset side of the overlap rank 0. The box linkset set immediately rejoins the rest of the logic so it is the only rank 0 linkset. The eliminations in rows 4 and 6 on the left are not related to candidates on the right in the same rows.

"Immediately rejoins the rest of the logic" is a bit vague. I'm interpreting it to effectively mean the set triplet does not see a strong link. Would you please clarify the phrase?

Allan Barker wrote:The conventional arguments for these eliminations that I have seen are not pleasing(?).

Have you ever scanned my fish exemplars in The Ultimate Fish Guide thread?

Allan Barker wrote:Quick Image Guide

...

Thanks, but what I really need clarification on is "points" ... as in "points in the direction of" and "points in the opposite direction of" that I've seen used elsewhere.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ronk » Fri May 30, 2008 2:05 pm

Allan Barker wrote:Elimination 26, simple logic.

Image

Elimination 26 is a medium size rank 2 cluster but its logic is simple. It needs 3 overlapping linksets to make elimination but has only two. The only triplet A lowers the rank along the path with cell set n83 thereby allowing overlapping linksets r85 and n87 to eliminate candidate r8c7n5. According to set logic, it is not necessary to address all of the complexity in the logic to eliminate the candidate.

Rank 2, [r(46)1 r34 c2(12) c72 n83 b94](T)r85*n87 => r8c7 <> 5

I've counted and recounted and counted yet again, and keep coming up with 8 sets and 9 linksets, which would make this example rank 1. This would yield an elimination at the linkset triple, r5c2<>1.

You state it's rank 2, and the difference must have something to do with the double border at r8c7, as if two linksets for cell r8c7 were required. I can see no logical need for that "double cover." Please clarify.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Allan Barker » Fri May 30, 2008 4:40 pm

Hi Ronk, This is a reply to your next to last message, as I see the new one. It's late here and I will take a look at that tomorrow.

I understand what you're saying, but I have a problem with "set theory" eliminations that effectively use internal strong links with triplets, in this case, r4c5 -x- r4c7 =x= r2c7. (Perusal of the more complex EM eliminations, however, leads me to believe such usage is commonplace.) ........ From another point of view, your r2 eliminations are valid only because some vertices of the c357b5\r2468 jellyfish are unpopulated. IOW it doesn't apply to the generalized cccb\rrrr jellyfish pattern.

Triplets with two strong links are common only in more complex logic. This example is only one of this size I've ever seen where the only solution (I can find) requires the set triplet. Overlapping linksets are of course more common.

(Perusal of the more complex EM eliminations, however, leads me to believe such usage is commonplace.)


This is correct however, I would use "occurrence" in place of "usage". The reason being that the solver I used looks for literally everything and this is what it finds when looking for the easiest or simplest solutions. The solver has no way to impress or use any particular logic form, except that it is made of sets.


Have you ever scanned my fish exemplars in The Ultimate Fish Guide thread?

I have often seen it referenced but never took a look until now and must say that is a very impressive piece of work. As mentioned, the grouped turbot chain example I gave was from Sudopedia.

"Immediately rejoins the rest of the logic" is a bit vague. I'm interpreting it to effectively mean the set triplet does not see a strong link. Would you please clarify the phrase? ...... Thanks, but what I really need clarification on is "points" ... as in "points in the direction of" and "points in the opposite direction of" that I've seen used elsewhere.


I am writing up a section to clarify this and other points, which I will put it in the other thread on set logic by Monday. In the mean time I hope this answers most of the questions.

1. Both sets and linksets can overlap to form triplets that can lead to areas of different rank. For the sake of discussion, it is convenient to describe a triplet as pointing in the direction of its minor set, or odd set out. A triplet with two linksets points in the direction of the set and a triplet with two sets points in the direction of the linkset. The logic in the pointing direction is called the minor branch or upper branch.

2. Both sets and linksets can form triple points that create regions of different rank however, inside each region rank again works like a global property. For logic with one set-triplet where the overall rank is R, the local ranks are: R for the linkset containing the overlap node and all other linksets in the region directly connected to it.
R + 1 for all other linksets.

3. Defining regions, taking a set-triplet as an example. A set triplet defines the boundary between two regions, one of which contains the linkset branch and the other contains the two set branches. If the logic on the linkset side never rejoins the rest of the logic then the rank will be lower everywhere along the branch. If the linkset branch eventually reconnects with the rest of the logic then another boundary is needed to define the region. In general, the low rank branch will continue until the first bifurcation that has two separate return paths to the two sets. This statement is not always easy to prove in complex logic, but extensive testing and simulation has never shown any exception. Monday I will post a series of logic that demonstrates the principle.

Applied to the grouped turbot chain example, the rank 0 zone starts at the box linkset where it connects to the row and column set via the triplet. The box linkset then reconnects to both the row and the column sets forming the return paths. Thus the box set is the only set that is rank 0.

Edit:Grammer.
Last edited by Allan Barker on Sat May 31, 2008 1:06 am, edited 1 time in total.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

It is 9 or 10 linkset?

Postby Allan Barker » Fri May 30, 2008 5:17 pm

Ronk wrote:
I've counted and recounted and counted yet again, and keep coming up with 8 sets and 9 linksets, which would make this example rank 1. This would yield an elimination at the linkset triple, r5c2<>1.

You state it's rank 2, and the difference must have something to do with the double border at r8c7, as if two linksets for cell r8c7 were required. I can see no logical need for that "double cover." Please clarify.


Your reasoning is correct, if there were 9 linksets it would make the logic rank1 and not rank2 and thereby additionally eliminate r5c2<>1.

However, I count 4 light blue cell linksets, 3 light tan box linksets, 1 green column linkset, and two light red row linksets, one in row 6 and the tiny "end" linkset in row 8. Thats 10. At first I thought you might have missed the small one in row 8, but I see that's not the case. Maybe also try recounting in the 3D image.

The thin dark gray line traveling all the way across row 8 and the thin gray square box surronding the cell linkset in r8c7 is a cursor I often turn on to show which sets are causing an elimination.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

PreviousNext

Return to Advanced solving techniques