Xsudo logic: A how to guide

Advanced methods and approaches for solving Sudoku puzzles

Xsudo logic: A how to guide

Postby sultan vinegar » Wed Sep 04, 2013 12:19 pm

Please advise of poorly written sections and concepts that are not understood. Note that I did not write Xsudo, I just tried to work out how it did stuff from the instructions.

This guide will have four sections: Basics, Triplets, Virtual Sets, Cannibalism.

Basics:

Hidden Text: Show
BASICS

Truth-Set: A collection of elements, at least one of which must be true. Truth-sets are typically one of the four native Sudoku sets; row (R), column (C), box (B), cell (N). In rare cases, one can also use virtual (V) sets, which are described in a separate section.

Link-set: A collection of elements, at most one of which must be true. Link-sets are always one of the four native Sudoku types; R,C,B,N. In theory, you could use a virtual link-set, but I have never seen it done, and I believe that xsudo does not have the facility to do it.

Logic: The collection of all truth-sets and link-sets. The only caveat is that all elements of all truth-sets must also be elements of at least one link-set. This is in contrast with the definition of cover-set in the Ultimate Fish Guide (UFG), but consistent with the definition of cover set in Hobiwan fish.

Triplet: There are two types of triplet:
A truth-set-triplet is an element that is a member of two truth-sets and one link-set.
A link-set triplet is an element that is a member of one truth-set and two link-sets.
Triplets will be described in a separate section. The basic techniques assume that there are no triplets in the logic.

Rank: In the absence of any triplets:
Rank is a number defined as the number of link-sets in the logic minus the number of truth-sets in the logic.
There is a connection between rank and the number of overlapping link-sets that guarantee the elimination of a candidate.

Theorem: For rank R logic, any candidate that is a member of 0 truth-sets and R+1 or more link-sets is guaranteed to be false, and maybe eliminated.

Proof:
For definiteness, let the number of truth-sets be “n”. There are no truth-set triplets by assumption, so there are thus at least “n” true candidates in the collection of truth-sets.
As the rank is R, the number of link-sets is “n+R”.
Assume that a candidate “x” that is a member of 0 truth-sets and R+1 or more link-sets is true.
Let’s tally up how many of our “n+R” link-sets are guaranteed to contain a true candidate. As each member of each truth-set must also be a member of exactly one link-set (no triplets remember), at least “n” link-sets contain the at least “n” true candidates from the collection of “n” truth-sets (remember, each link-set can contain at most one true candidate). In addition, “R+1” link-sets contain true candidate “x” by assumption. These “R+1” link-sets are separate to the “n” already mentioned, as there are no triplets, so no opportunity for overlap. In total, we have “n+R+1” link-sets containing a true candidate.
But we have only “n+R” link-sets, so we have a contradiction, and the assumption of true candidate “x” must be false. Hence, “x” can be eliminated.

As there are only 4 types of native link-set, there is a maximum of 4 overlapping link-sets, so the maximum rank that guarantees an elimination is rank 3. For ranks higher than 3, there will need to be at least one triplet present if an elimination is to occur.

Examples:

Rank 0:

Image

Rank 1:

Image

Rank 2:

Image

Rank 3:

Image


Triplets:

Hidden Text: Show
TRIPLETS

Truth-set Triplet (rare): 2 overlapping truth-sets and 1 overlapping link-set
Link-set Triplet (more common): 1 overlapping truth-set and 2 overlapping link-sets
Triplet State: Occupied (candidate is assumed true) / Unoccupied (candidate is assumed false)

If triplets are present, then the definition of rank is adjusted so that the connection between rank and the number of overlapping link-sets that guarantee the elimination of a candidate is maintained. In general, the rank is not constant as in the case of no triplets; the rank will be different in different regions if triplets are present.

The procedure to calculate the rank is to consider in turn each combination of triplet states. As each triplet has two possible states, for “n” triplets there are 2^n possible combinations of triplet states. For example, if there are six triplets as in the case of the exocet elimination in Fata Morgana, then there are 2^6 or 64 combinations to consider. This is a laborious calculation in general, but is often simplified by “common sense”.

This current section is split into six case studies, showing how to handle triplets, culminating in two “no-fish” examples.

1) Truth-set triplet easy:

In this case, the truth-set triplet behaves identical to an endo-fin from the UFG.

Image

We have 5 truth-sets, 5 link-sets and one truth-set triplet at row 3, column 3, number 2. As there is just one triplet, we have just two possibilities; triplet occupied, triplet unoccupied.

If the triplet is unoccupied, then the logic contains 5 truth-sets, 5 link-sets and no triplet (it has been set to unoccupied). So we have rank 0 logic (the fish is true).

If the triplet is occupied, then the triplet’s link-set is occupied, and so the triplet’s link-set is defined as rank 0 to maintain the connection between rank and the number of overlapping link-sets that guarantee the elimination of a candidate.

So, as in the case of an endo-fin, regardless of the triplet’s state, the triplet’s link-set is rank 0, and any candidate that is a member of 0 sets and the triplet’s link-set can be eliminated.

2) Truth-set triplet hard

In this case, the truth-set triplet does more than what an endo-fin can.

Image

We have 4 truth-sets, 4 link-sets and one truth-set triplet at row 4, column 5, number 1. As there is just one triplet, we have just two possibilities; triplet occupied, triplet unoccupied.

If we use the endo-fin approach, then we discover that the link-set in row 4 is rank 0. But the truth-set triplet can do more than an endo-fin can. I now show that the link-set in row 2 is rank 0, although it doesn’t result in any extra eliminations unfortunately. To do this, we reduce the logic. (Note that I omitted this step in the previous example, as it didn’t show anything new in that case, but here it does.)

Reducing the logic occurs in the case where the truth-set triplet is assumed occupied. We now re-draw the logic with the truth-set triplet’s two sets and one link-set removed (as they have been accounted for in the assumption that the triplet is occupied). We don’t rearrange or add in any new truth-sets or link-sets, we just look at what remains upon deletion of the triplets truth-sets and link-set.

Image

Now, when the triplet was assumed to be unoccupied, the logic was calculated to be rank 0 everywhere. So, when the triplet is assumed to be occupied, we want to match this rank for useful eliminations. The question now is: in this reduced logic, is there a sub-collection of truth-sets and link-sets (satisfying the property that every member of a truth-set is also a member of a link-set) that results in a rank 0 region? Yes! We take set 1C7, and link-set 1R2. Thus, if the triplet is occupied, then the link-set in row 2 is rank 0. Notice that the remaining two link-sets in rows 6 and 8 are rank 1, since that region has one truth-set and two link-sets.

So, regardless of the state of the triplet, the link-sets in rows 2 and 4 are rank 0.

We now turn to link-set triplets. These are similar to exo-fins in the UFG, only link-set triplets can do more than exo-fins can.

3) Link-set triplet easy

Image

We have 5 truth-sets, 7 link-sets and 1 link-set triplet in row 1, column 6, number 7. As there is just one triplet, we have just two possibilities; triplet occupied, triplet unoccupied.

If the triplet is assumed occupied, then we reduce the logic by removing the triplet's truth-set and two link-sets from the diagram. This leaves 4 truth-sets, 5 link-sets, no triplets, so rank 1 logic. As the candidate in row 9, column 9, number 7 is a member of two link-sets, it is eliminated if the triplet is occupied.

If the triplet is assumed unoccupied, then we reduce the logic by removing the candidate in row 1, column 6, number 7 from the diagram since it has been assumed false. Then, as in the case of the truth-set triplet hard, we look for a sub-collection of truth-sets and link-sets (satisfying the property that every member of a truth-set is also a member of a link-set) that results in a rank 1 or lower region (since we want to at least match the rank 1 obtained from the case where the triplet was assumed occupied).

Image

We have 3 truth-sets; 1N6, 1B3, 5C9, and 3 link-sets; 1R1, 3N9, 9N9 that form a rank 0 sub-region. So, all up: if the triplet is assumed occupied, then link-set 9N9 is rank 1. If the triplet is unoccupied, then link-set 9N9 is rank 0. The worst case is rank 1, and candidate 7 in row 9, column 9 is eliminated by (reduced) rank 1 logic.

As a rule, this case is easy as the triplet’s truth-set was a bivalue (a bilocation would be just as easy), and so when the triplet is assumed false, the other element in the triplet’s truth-set must be true. In addition, we get a nice simple chain of inferences to show that if the triplet is unoccupied, then row 9, column 9, number 7 is false. So, regardless of the state of the triplet, row 9, column 9, number 7 is false.

4) Link-set triplet hard

Image

In this case, we apply the same procedure as for the previous link-set triplet case, but this current case is considered hard because we do not get the bivalue/bilocation and chain short-cut that occurred in the previous case.

We have 4 truth-sets, 6 link-sets and a link-set triplet at row 5, column 4, number 6. If the triplet is occupied, then we remove one truth-set and two link-sets from the logic, leaving 3 truth-sets, 4 link-sets and no triplets, so all link-sets are rank 1 if the triplet is occupied. The candidate at row 6, column 9, number 6 is thus eliminated if the triplet is occupied, by rank 1 logic. If the triplet is unoccupied, we remove the candidate at row 5, column 5, number 6 from the logic. We then look at the remaining logic to see if any rank 1 or lower regions exist (so as to at least match the rank 1 elimination from the case where the triplet was occupied). The logic now looks like:

Image

The sub-collection consisting of two truth-sets (6R2, 6B5) and three link-sets (6C5, 6C9, 6R6) is a rank 1 sub-region. So, again, the candidate at row 6, column 9, number 6 is eliminated by rank 1 logic. All up, regardless of the state of the triplet, the candidate at row 6, column 9, number 6 is eliminated by rank 1 logic.

The final two cases have multiple triplets. These two cases are currently under discussion in the no-fish thread, as they are template eliminations with no (classical) fish explanation. These eliminations are explainable with Xsudo logic however.

5) No-fish #1

Image

We have 6 truth-sets, 8 link-sets, 1 truth-set triplet (R9C1) and 2 link-set triplets (R8C3, R9C3). As there are 3 triplets, there are 2^3 or 8 possible triplet states. However, with common sense, we won’t have to check all 8 states, as all triplets share a box, so at most one of them is true.

Case I: The truth-set triplet is occupied, and the two link-set triplets are unoccupied.

This case is easy. Since the truth-set triplet is occupied, the truth-set triplet’s link-set is occupied, hence the link-set in row 9 is rank 0.

Case II: The link-set triplet at R8C3 is occupied, and the two others are unoccupied.

This case is also straight-forward. The occupied triplet’s two link-sets are rank 0. There are 5 truth-sets and 6 link-sets remaining. So each of the remaining link-sets is rank 1. Of interest to us is that the link-set in row 9 is rank 1.

Case III: The link-set triplet at R9C3 is occupied, and the two others are unoccupied.

This case is similar to case II. The occupied triplet’s two link-sets are rank 0. There are 5 truth-sets and 6 link-sets remaining. So each of the remaining link-sets is rank 1. Of interest to us is that the link-set in row 9 is rank 0.

Case IV: All triplets are unoccupied.

In this final case, we reduce the logic following the usual procedure. The logic is redrawn with all triplets unoccupied:

Image

We look for a rank 1 or lower sub-region to at least match our worst case so far which is rank 1. Consider the sub-region with one truth-set (9B7) and one link-set (9R9). This is a rank 0 sub-region, which is good enough for us today.

All up, regardless of the triplets’ state, the worst case rank for the link-set in row 9 is rank 1, so the candidate at row 9, column 8, number 9 is eliminated by (reduced) rank 1 logic.

6) No-fish #2

Image

We have 5 truth-sets, 7 link-sets, 1 truth-set triplet (R2C6) and 2 link-set triplets (R2C1, R2C5). As there are 3 triplets, there are 2^3 or 8 possible triplet states. However, with common sense, we won’t have to check all 8 states, as all triplets share a row, so at most one of them is true.

Case I: The link-set triplet at R2C1 is occupied, and the other two triplets are unoccupied.

The occupied triplet’s two link-sets are rank 0. There are 4 truth-sets and 5 link-sets remaining. So each of the remaining link-sets is rank 1. Of interest to us is that the link-set in row 9 is rank 1.

Case II: The link-set triplet at R2C5 is occupied, and the other two triplets are unoccupied.

The occupied triplet’s two link-sets are rank 0. There are 4 truth-sets and 5 link-sets remaining. So each of the remaining link-sets is rank 1. Of interest to us is that the link-set in row 9 is rank 1.

Case III: The truth-set triplet is occupied, and the other two triplets are unoccupied.

We re-draw the logic after setting the triplet’s to the assumed states.

Image

We look for a sub-region that is rank 1 or lower, to at least match the worst case so far which is rank 1. The region with one truth-set (9C1) and 1 link-set (9R9) is rank 0.

Case IV: All triplets are unoccupied:

We re-draw the logic after setting the triplet’s to the assumed states.

Image

We look for a sub-region that is rank 1 or lower, to at least match the worst case so far which is rank 1. The region with one set (9C1) and 1 link-set (9R9) is rank 0.

All up, regardless of the triplets’ state, the worst case rank for the link-set in row 9 is rank 1, so the candidate at row 9, column 5, number 7 is eliminated by (reduced) rank 1 logic.


Virtual Sets:

Hidden Text: Show
Xsudo allows the user to specify one virtual truth-set. This is useful for two solving techniques: Guardians and AURs. We now look at two examples of Virtual X-wings.

Example 1: Guardians

Image

The virtual truth-set (black) consists of two elements; row 2, column 2, number 7 and row 9, column 6, number 7. At least one of these elements must be true to prevent the illegal conjugate loop of length 5 for the digits 7 in cells 4N2,4N4,7N4,8N5 and 8N2. The remaining logic works the same; 2 truth-sets, 2 link-sets, no triplets, so rank 0 logic.

Example 2: AURs (Assumes puzzle has at most one solution)

Use of this technique is an individual’s personal preference; some are comfortable with it, others are not. For those who are happy to use it, here’s how Xsudo does it.

Image

The virtual truth-set (black) consists of two elements; row 4, column 1, number 3 and row 8, column 2, number 3. If the puzzle is assumed to have at most one solution, then at least one of these elements must be true to prevent the deadly pattern in cells 4N1, 4N2, 8N1, 8N2. The remaining logic works the same; 2 truth-sets, 2 link-sets, no triplets, so rank 0 logic.


Cannibalism:

Hidden Text: Show
Cannibalism can almost always be explained by using simpler non-cannibalistic logic. It occurs when the assumption of a link-set triplet being occupied results in a negative rank sub-region in the puzzle. The link-set triplet must thus be unoccupied, so a truth-set digit is eliminated (cannibalised).

Example 1: Mutant Swordfish

Image

We have 3 truth-sets, 3 link-sets and 1 link-set triplet at row 1, column 4, number 5. Consider the case where the link-set triplet is occupied. So, we remove the triplet’s truth-set and two link-sets from the logic:

Image

We are left with a rank -1 sub-region; two truth-sets and one link-set. This has no solution, so the assumption that the triplet was occupied is false, and the candidate may be eliminated (cannibalised).

In this example, what really happened was that we missed the (simpler) empty rectangle:

Image

Two truth-sets, three link-sets, no triplets, so nice simple rank 1 logic.

Example 2:

What a way to finish the guide with arguably the most beautiful piece of logic in all of Sudoku found to date: Champagne’s “Double JExocet”.

Image

We can account for all the eliminations in three steps:

Image
Image
Image

Note that I had to use the complementary finned fish interpretation in the first step, but resorted to the standard interpretation in steps 2 and 3.

So that begs the question, can all Cannibal eliminations be reproduced with non-cannibalistic equivalents???
Last edited by sultan vinegar on Thu Dec 19, 2013 11:35 am, edited 5 times in total.
sultan vinegar
 
Posts: 81
Joined: 27 August 2013

Re: Xsudo logic: A how to guide

Postby Sudtyro2 » Wed Sep 04, 2013 8:29 pm

sultan vinegar wrote:Please advise of poorly written sections and concepts that are not understood. Note that I did not write Xsudo, I just tried to work out how it did stuff from the instructions. This guide will have four sections: Basics, Triplets, Virtual Sets, Cannibalism.

Seems like a good start to the How-To Guide :!:
Could you also include in the Triplets section an explanation about the five linkset triplets in Allan's 8s grid? You recently discussed that grid in the arcilla topic, but I could never understand how Allan picked only two triplets out of the five available to do the analysis. IOW, why not maybe go for three triplets and an effective rank of 0? Details would be most welcome!
Sudtyro2
 
Posts: 444
Joined: 15 April 2013

Re: Xsudo logic: A how to guide

Postby daj95376 » Thu Sep 05, 2013 2:18 am

Thank You for your NoFish example #1 under Triplets. It would seem that more is needed than the sets and link-sets to explain Xsudo's conclusion for r9c8<>9. This indicates that Xsudo's conclusion is beyond the logic of a Fish using these sets(base) and link-sets(cover).

BTW: you are missing an "^" in the following statement from the example: "... there are 23 or 8 possible triplet states."


Danny A. Jones
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Xsudo logic: A how to guide

Postby sultan vinegar » Fri Sep 06, 2013 2:53 am

I have added the first draft in the sections: Virtual Sets, Cannibalism. I've also made some minor changes in the first two sections in response to some good feedback. There will be more alterations in the future.

Could you also include in the Triplets section an explanation about the five linkset triplets in Allan's 8s grid?


Code: Select all
 
.  .  . | .  .  . | .  .  .
8  8  . | .  .  . | .  A  .
.  .  8 | .  .  . | .  .  8
--------+---------+---------
.  .  8 | .  8  . | .  8  .
8  .  . | 8  .  . | .  8  .
.  8  8 | .  8  . | 8  .  .
--------+---------+---------
8  .  8 | .  8  . | 8  8  8
.  8  . | .  8  . | .  8  T
8  B  . | 8  .  . | 8  .  .


The five link-set triplets are in cells 2N8, 5N8, 8N2, 9N1 and 9N2. Five triplets means 2^5 or 32 combinations to check! Note that as three triplets share a box, and another two share a column, that this reduces to 14 possible cases. Considering only two triplets was just a short-cut, to explain it in the easiest way. So the quick answer to your question is that you do need to consider all 5 triplets. I just used a convenient short-cut that is obvious in hind-sight. Observe that if triplet A at cell 2N8 is assumed unoccupied, that the whole thing falls over straight away due to the bi-location in box 3, regardless of any other triplet state. You can verify that the other cases all work too.

As for your question of trying to reduce the rank further, well, when you check all the cases, it doesn't happen, so I didn't mention it.

There is still a misconception out there that there is some simple magic rule that will allow human solvers to reduce logic with multiple triplets really easily just by looking at it! There's not. Xsudo crunches all the cases for every link-set for every combination of triplet states. Humans are used to simple fish with one-fin, and are happy to consider the two cases. Xsudo just takes it further. It considers the different combinations of triplet states as these are the only way to alter the rank. If you consider the two cases for a standard candidate that is a member of one set and one link-set, then regardless of whether it is occupied or not, the rank stays the same, and you haven't got anywhere!

The main difference between Xsudo logic and Ultimate Fish Guide (UFG) logic is this:

UFG: Fin false implies fish true. Fin true implies direct line of sight eliminations. Intersect the two cases for common eliminations.

Xsudo: All of the above, plus it looks for smaller fish in the remaining logic. This way, you don't need to propagate a big error net, you can tell from the "sub-fish" if you are going to be a link-set short.
sultan vinegar
 
Posts: 81
Joined: 27 August 2013

Re: Xsudo logic: A how to guide

Postby Sudtyro2 » Fri Sep 06, 2013 11:04 am

sultan vinegar wrote:... you do need to consider all 5 triplets. I just used a convenient short-cut that is obvious in hind-sight.

Yes, 20/20 hindsight always helps! :) Thanks for the detailed explanation...that clears up a lot of issues for me!
Sudtyro2
 
Posts: 444
Joined: 15 April 2013

Re: Xsudo logic: A how to guide

Postby ronk » Fri Sep 06, 2013 3:30 pm

sultan vinegar wrote:
Could you also include in the Triplets section an explanation about the five linkset triplets in Allan's 8s grid?
h
Code: Select all
 
.  .  . | .  .  . | .  .  .
8  8  . | .  .  . | .  A  .
.  .  8 | .  .  . | .  .  8h
--------+---------+---------
.  .  8 | .  8  . | .  8  .
8  .  . | 8  .  . | .  8  .
.  8  8 | .  8  . | 8  .  .
--------+---------+---------
8  .  8 | .  8  . | 8  8  8
.  8  . | .  8  . | .  8  T
8  B  . | 8  .  . | 8  .  .

The five link-set triplets are in cells 2N8, 5N8, 8N2, 9N1 and 9N2.

What logic (sets & linksets) yields those triplets? If posted earlier, what is the link to that post?

[edit: I did find this. If it's the correct prior reference, I don't see how 2N8 is a linkset-triplet.]
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Xsudo logic: A how to guide

Postby Sudtyro2 » Fri Sep 06, 2013 11:33 pm

[Edit to place post content in hidden text. Same info (and more) is covered in the post that follows.]
Hidden Text: Show
ronk wrote:
sultan vinegar wrote:
Could you also include in the Triplets section an explanation about the five linkset triplets in Allan's 8s grid?

Code: Select all
 
.  .  . | .  .  . | .  .  .
8  8  . | .  .  . | .  A  .
.  .  8 | .  .  . | .  .  8h
--------+---------+---------
.  .  8 | .  8  . | .  8  .
8  .  . | 8  .  . | .  8  .
.  8  8 | .  8  . | 8  .  .
--------+---------+---------
8  .  8 | .  8  . | 8  8  8
.  8  . | .  8  . | .  8  T
8  B  . | 8  .  . | 8  .  .

The five link-set triplets are in cells 2N8, 5N8, 8N2, 9N1 and 9N2.
... I don't see how 2N8 is a linkset-triplet.

In my old notes Allan's original 5-Fish was c124b36\r25689c89b7, of raw rank 3. The five linkset triplets were:
r2c8, r9c2, r5c8, r8c2, and r9c1. I saved an image of the grid showing all sets and linksets...can upload, maybe, (with how-to-upload instructions :oops:)

r2c8 is an intersection of the r2 and c8 linksets (covers).
Last edited by Sudtyro2 on Tue Sep 10, 2013 10:40 am, edited 1 time in total.
Sudtyro2
 
Posts: 444
Joined: 15 April 2013

Re: Xsudo logic: A how to guide

Postby sultan vinegar » Fri Sep 06, 2013 11:39 pm

Quick answer is Truths: C124B36, Links: r25689c89b7. See http://forum.enjoysudoku.com/a-new-view-of-fish-naked-or-hidden-t5017-60.html#p229706.

The analysis is probably not as rigorous as it could be. Sorry for the confusion. It's not surprising that it occurred given that I posted different analyses of the same grid in different topics!

Edit: Got beaten to it!
sultan vinegar
 
Posts: 81
Joined: 27 August 2013

Re: Xsudo logic: A how to guide

Postby Sudtyro2 » Mon Dec 30, 2013 9:48 pm

One old issue I still seem to struggle with regards linkset triplet logic as applied to Allan's 8s grid...
sultan vinegar wrote:
Code: Select all
        .  .  . | .  .  . | .  .  .
        8  8  . | .  .  . | .  A  .
        .  .  8 | .  .  . | .  .  8
        --------+---------+---------
        .  .  8 | .  8  . | .  8  .
        8  .  . | 8  .  . | .  8  .
        .  8  8 | .  8  . | 8  .  .
        --------+---------+---------
        8  .  8 | .  8  . | 8  8  8
        .  8  . | .  8  . | .  8  T
        8  B  . | 8  .  . | 8  .  .

Truths: C124B36
Links: r25689c89b7
Rank: 3

We have 5 link triplets, but only two are required for the analysis, one at A (r2c8), the other at B (r9c2). T is the target for elimination.

Case I: Triplets A and B are both true. Then we have 3 truths and 4 links remaining, so the rank is 1, and T is eliminated as it is in 0 truth sets and 2 link sets.

Case II: Triplet A is false (B plays no part). Then, as for Allan's instructions, we cut the logic on the triplet's minor branch, and look for a subcover in the remaining logic. When we do this, a subcover of 1 truth in b3, and 1 link in column 9 ensues (Franken cyclops fish if you like), thus column 9 is a rank 0 sub-region and T is eliminated.

Case III: Triplet A is true, and triplet B is false. Again, cut the logic on the minor branch of the triplet, and look for a subcover in the remaining logic. Note that the remaining logic does not include r2c2 nor r45c8 due to A being assumed true. When we do this, a subcover of 2 truths in c2b6, and 2 links in r68 ensues (Franken X-wing if you like), thus rows 6,8 are a rank 0 sub-region and T is eliminated.

When you intersect the three cases, the worst rank for T is rank 1, and so T is eliminated under rank 1 logic.

In Case I, the thing that worries me is that triplets A and B cannot both be true (as templates or a short network diagram will quickly show). So this case seems to be based on a false premise.
Code: Select all
 A-r2c1
    ||
   r5c1-r5c4=r9c4-B
    ||
  r79c1-B


Realizing that, Case III then implies that if triplet A is set true (thus forcing B to be false), then somehow we can eliminate T. But, conventional wisdom says that setting any one linkset triplet true can only reduce the puzzle's raw rank by 1 (as was applied in Case I, twice).

Help?
Sudtyro2
 
Posts: 444
Joined: 15 April 2013

Re: Xsudo logic: A how to guide

Postby sultan vinegar » Tue Dec 31, 2013 11:48 am

Ultimately, if the puzzle has a single solution, then there is only ever one true case. The argument for case I proves that IF case I is true, then T is eliminated. If case I is known a priori to be not true, then there is no need to prove it (again).

As for the conventional wisdom part, how does a standard JE3 with 11 truth sets, 14 link sets (raw rank 3) and exactly 2 true link-set triplets reduce the rank to 0 in the target cell link sets? The "each link-set triplet reduces the rank by exactly one" conjecture is not true in general.

A tip when doing these reduced rank calculations is that "near enough is good enough". You don't need to calculate everything exactly. Link-set triplets can reduce the rank in certain regions; truth-set triplets can increase the rank in certain regions. So if there are no truth-set triplets (as in this example), and you've reduced the rank by enough in a certain region to guarantee an elimination, then there is no need to finish the calculation exactly.
sultan vinegar
 
Posts: 81
Joined: 27 August 2013

Re: Xsudo logic: A how to guide

Postby Sudtyro2 » Wed Jan 01, 2014 5:28 pm

Thanks, SV, for the quick response and explanations. I'll now have to admit frankly that I will probably never fully understand the concepts of cutting the logic, minor branches, subcovers, reduced-rank sub-regions, etc.

In light of that, I'd like to propose a simplified approach to handling linkset-triplet logic that is more easily adapted for use by the manual solver. This idea has also been suggested by aran, ronk, et al. Your feedback would then be most helpful before proceeding any further along this line of thought.

I'll borrow from your head post the Triplet section's example “4) Linkset-triplet hard,” with the abbreviated grid shown below:

 
Code: Select all
        .  .  . | .  .  . | .  .  .
        .  .  . | .  6  . | .  .  6
        .  .  . | .  .  . | .  .  .
        --------+---------+---------
        .  .  . | .  6  . | .  .  .
        .  6  . | A  .  . | .  .  .
        .  6  . | .  .  6 | .  .  T
        --------+---------+---------
        .  .  . | .  .  . | .  .  .
        6  .  . | 6  6  . | .  .  .
        .  6  . | .  .  . | .  .  .

Truths: r28c2b5
Links: r56c459b7
Rank: 2

Linkset triplet at r5c4 is marked as A. Elimination cell at r6c9 is marked as T. The simplified solution is summed up as follows.

If A is true (occupied) then the global rank is reduced from 2 to 1, and T is therefore eliminated at the intersection of links r6 and c9.

If A is false (unoccupied) then look for chain(s)/network(s) from A that yield the same reduced-rank elimination. If found, the elimination is confirmed.

For this grid one can use a [b5]SIS to account for both parities. The SIS contains exactly one truth:
Code: Select all
r5c4 => rank=1  => r6c9<>6
 ||
r6c6            => r6c9<>6
 ||           
r4c5-r2c5=r2c9  => r6c9<>6

Elimination confirmed.

This same procedure can be applied to the case of multiple linkset triplets, such as in Allan's 8s grid discussed previously, but I will await your comments before proceeding.
Sudtyro2
 
Posts: 444
Joined: 15 April 2013

Re: Xsudo logic: A how to guide

Postby sultan vinegar » Thu Jan 02, 2014 2:28 am

Sudtyro2 wrote:Thanks, SV, for the quick response and explanations. I'll now have to admit frankly that I will probably never fully understand the concepts of cutting the logic, minor branches, subcovers, reduced-rank sub-regions, etc.


I think that you do understand those topics; you just call them different things. It's all summed up in your sentence:

Sudtyro2 wrote:If A is false (unoccupied) then look for chain(s)/network(s) from A that yield the same reduced-rank elimination. If found, the elimination is confirmed.


The translation is as follows:

"Cutting the logic" <==> "look for chain(s)/network(s) from A"
"minor branch" <==> "from A"
"subcovers" <==> "that yield the same reduced-rank elimination"
"reduced rank sub-regions" <==> "If found, the elimination is confirmed"

Once you get through all the fancy words, all it comes down to is controlled guessing. With no triplets, fish can be understood elegantly by counting. When there are triplets, all that goes out the window, so you resort to primitive guessing to force a verity. If the triplet is true, does a smaller fish ensue? If the triplet is false, does a smaller fish ensue? Intersect both cases for common eliminations. In the first case, it is not normally necessary to find the fish explicitly; a counting argument can suffice. It is in the second case that you definitely need to find the smaller fish explicitly. I conjecture that for fish with a single triplet, that it is possible to write them as chains, with some elements of the chain possibly being smaller fish. E.g. for your 6's grid:

Code: Select all
        .  .  . | .  .  . | .  .  .
        .  .  . | .  6  . | .  .  6
        .  .  . | .  .  . | .  .  .
        --------+---------+---------
        .  .  . | .  6  . | .  .  .
        .  G  . | A  .  . | .  .  .
        .  6  . | .  .  6 | .  .  T
        --------+---------+---------
        .  .  . | .  .  . | .  .  .
        6  .  . | G  6  . | .  .  .
        .  6  . | .  .  . | .  .  .


{r2c9 == r2c5 -- r4c5 == r6c6} == A -- G == {r2c9 == r2c5-- r8c5 == r8c1 -- r9c2 == r6c2} -- T -- loop

So in this case, the smaller fish end up being X-chains themselves. Note that the "-- G == {r2c9 == r2c5-- r8c5 == r8c1 -- r9c2 == r6c2}" section is not explicitly necessary; your counting argument "A true => rank =1" suffices without finding the smaller fish explicitly.
sultan vinegar
 
Posts: 81
Joined: 27 August 2013


Return to Advanced solving techniques