The New Sudoku Players' Forum

[bennys]

To Jeff and Rubylips
No doubt that both of you are right.
After I recognized that chain I could represent it in your ways but I wanted to put it the way I found it.
Currently I try to look at a subset of unit of what I called Almost Locked
and others including Rubylips call Almost Disjoint Subset
and try to find one placement that will "kill" two candidates.

[Hanyou Hottie]

I think all you people are trying too hard. Which isn't to say that discovering new techniques is bad, just that sometimes much simpler (and easier to use) techniques will work just fine.

It looks like Ruud's solver found the most straightforward answer, except that no other techniques besides coloring need to be done. Also, you can choose to do either the 6s or the 8s first with the same result: r4c4 is 8 and r3c5 is 6. After that you're left with only singles.

Allow me to illustrate how complete simple coloring can be used instead of attempting to find such patterns as turbot fishes:


From this image it should be pretty obvious (if you are familiar with coloring) that r1c4 can not be 6, which of course leaves c3c5 as the only place for 6 in that box. In my opinion, noticing a couple of conjugate pairs that intersect is a lot easier than trying to pick out a fishy cycle (or turbot fish) in a puzzle. Also note that complete simple coloring (as defined by Lummox JR) is a super set of fishy cycles and turbot fishes (I suppose if you want proof, you can go ask him :). Because of this I haven't even bothered with trying to learn about such techniques, since they can be hard to spot even if you are familiar with them.

This is all just my opinion really. I just want to let people (especially new players) know about complete simple coloring and it's uses. It seems like many people on this forum use fishy cycles, etc., and I can't comprehend why one would prefer them over some basic coloring.

[emm]

I like this idea - though it looks like complicated colouring to me. Would you, or someone, please explain how it works here?

[MCC]

I'm not sure if this is what you want em.

Hanyou has coloured all the cells with a 6 in them.

If r1c4=6=>r1c9<>6=>r9c9=6=>(r9c6<>6 and r7c7<>6)=>r7c4=6
r1c4=6 and r7c4=6 contradiction two 6's in c4.
Therefore r1c4<>6.

[emm]

Thanks MCC – perfect! I was blinkered, looking for conjugate pairs. Thanks HH too.

[rubylips]

It seems like many people on this forum use fishy cycles, etc., and I can't comprehend why one would prefer them over some basic coloring.

Aren't they the same thing? (Though I don't have a formal proof to hand). Of course, as you say, people should be free to use whichever form of the technique they prefer.

[Nick70]

In my opinion, noticing a couple of conjugate pairs that intersect is a lot easier than trying to pick out a fishy cycle (or turbot fish) in a puzzle.

Actually, the pattern you highlighted is exactly a turbot.

When looking for a turbot in that example, I would have looked for the "fin" first--that is, the diagonal line; in this case, the two cells in box 9. Then I would have tried drawing the sides from there, to meet another cell (in this case, either row 9/col 7 or row 7/col 9), checking if the turbot could be completed, finding that it would close on R1C4.

So it's just a way to look for a visual pattern which is easy to identify.

[Hanyou Hottie]

Yes, I believe it is true that fishy cycles and using coloring to its full extent will get you the same result. I just brought up the topic because, at least for me, seeing conjugate pairs is easier than looking for fish patterns that bend around corners and such. I realize that what I highlighted was indeed a turbot, I was just showing how to use colors in that situation to get the same result. I can try to explain how coloring was used here, as well as provide the logic behind it, if anyone's interested, so you can make the decision yourself as to which technique you prefer.

Using coloring of any type doesn't involve implicating chains, like MCC has created. Coloring simply states that, for a given conjugate pair (only two cells with a candidate in a group), one cell has to be true, and one has to be false. It doesn't make any guesses as to which one is true and which is false, it just establishes a logical Not relationship.

Referring to my previous post now, yes, all the sixes have been highlighted, and I colored two conjugate pairs to show the logical Not relationship. For the pair in row 7, either the purple cell or the amber cell has to be true, and for the pair in column 9, either green or blue has to be true. The important connection to see here is the fact that the amber cell and the blue cell (two cells from separate conjugate pairs) happen to share a common group, box 9. This allows us to form an additional relationship, which is that amber and blue are mutually exclusive, meaning they both can't be true at the same time. This isn't the same as a logical not relationship, however, as they both could be false. So now we have three possibilities:
Amber is true, blue is false. Therefore purple is false, and green is true.
Amber is false, blue is true. Therefore purple is true, and green is false.
Amber if false, blue is false. Therefore purple is true, and green is true.
It is not possible for amber to be true and blue to be true at the same time, so it is therefore also not possible for purple to be false and green to be false at the same time.

So, in all three possible cases, either green is true, purple is true, or both are true. Since r1c4 shares a group with green (same row) and purple (same column), and one of those colors has to be true, r1c4 must therefore be false.

Notice again how there was no starting assumption that r1c4 was true, as is the case with forcing chains. Forcing chains uses a logical method called proof by contradiction, where you first assume that the thing you're trying to prove false is instead true, and then showing that by doing so, a contradiction appears somewhere down the line, implying that the initial assumption of truth was wrong. Coloring, on the other hand, uses one of the most basic methods of logic, known as truth tables. Making a truth table involves writing down all the possible states of a few propositions (in this case the propositions are whether a cell is true or not), and then relating the propositions to each other with logical operations. Here's an example of the truth table for a conjugate pair:

The “+” symbol here is used as the exclusive-or (XOR) operator. Notice that the truth table only shows an outcome of true when either B or G is true, but not when both are true, and not when neither is true, which is exactly how a conjugate pair in sudoku works (One member of a conjugate pair must be the actual number, and the other can not be the number. It's not possible for both cells to be the number, and it's not possible for both cells to not be the number.).

Now, to get results from a truth table, we have to create logical arguments know as tautologies or contradictions. A tautology is simply a truth table in which all the possible outcomes end up being true. A contradiction is the opposite. It's a truth table in which all states of the propositions result in all outcomes being false. Here's a simple truth table that demonstrates a contradiction:

Here “&” is the AND operator, and “~” is negation, or the NOT operator. This demonstrates that no matter what state proposition P is in, the outcome of our logical relationship is false. This allows to reach a conclusion without knowing the state of P: we know the outcome is always false, so the state of P is irrelevant. An analogous situation can be shown in terms of algebra, if you're more familiar with that topic (if not, disregard what follows). Take the simple function F(x)=x*0. Here it should be obvious that the state of x is quite irrelevant; the outcome of the function will always be 0. If this function were involved in a larger algebraic problem, we could substitute the value of 0 in for any instance of F(x), thus reducing the complexity of the problem by eliminating a variable.

Now back to how this affects sudoku in the coloring example I highlighted. Our logical argument here is that “there is a 6 in one of the groups (row, column, or box) of r1c4” (but not r1c4 itself, obviously). If we can show that this argument is true for all possible states of the colors on the board (which are our propositions), this will make a tautology, letting us ignore our propositions. Above I showed that this is indeed the case; no matter the state of the propositions green and amber, either blue, purple, or both will be true, which results in our argument being true all the time, i.e., a tautology. Since our argument has been shown to be a tautology, we can look at the rules of sudoku and see that there can only be one copy of a number in a group, and then remove candidate 6 from r1c4. This gives us a hidden single on r3c5, the correct position of 6.

To wrap this all up, I'll give you a simple pattern to look for, rather than trying to work through all that logic every time. Say you have cells A and B in a conjugate pair, and cells C and D in a separate conjugate pair. If A and C happen to share a common group, the intersection of B and D is then false. Like so:

Or here, where nines are highlighted:

[Jeff]

This is a classic turbot fish. Angus call this multi-colouring in his solver. To me, it's just another single value combination chain of length 5. If you haven't read about turbot fish before, then it is an excellent observation indeed.

[masb]

It looks to me as if this is solved quite easily with just the XY-Wing shown in Ruud's solver output. My solver, Numbler (available via http://www.axcis.com.au/bb/viewtopic.php?t=25) comes up with:

Code: Select all

Box Column @ 3> r9c9x2
Row Box @ 2> r3c5x1
XYWing @ r9c9 r2c9 r9c6> r2c5x2 r2c6=1 r1c9x2
Single r2c5=8
Single r2c9=2 r3c5=6
Single r1c4=2
Single r7c4=6
Single r4c4=8 r7c7=2 r9c6=2
Single r4c2=6 r6c6=6
Single r6c8=8
Single r3c8=1 r5c7=6
Single r1c8=6 r3c2=8 r9c7=8
Single r1c3=1 r1c9=8 r5c2=1 r9c9=6
Single r5c5=2 r6c3=2
Single r5c3=8 r6c5=1

So just straightforward singles after the XY-Wing. No Swordfish or colouring required. You can see this visually on the Numbler screen.

In the solution above, the values between the "@" and ">" are references to cells or boxs and "=" means set the cell to the value and "x" means remove the pencil candidate.