The New Sudoku Players' Forum

[RW]

So one needs to consider ...

• only those candidates outside the uniquenss pattern which destroy the deadly pattern, and
• of those, only the candidates which have complements, and
• of those, only one of each complementary pair (pair?) of candidates.

No. If you choose to consider candidates outside the uniqueness pattern which destroy the deadly pattern it is enough to consider only the candidates in either all rows, columns or boxes involved. In this MUG case the column alternative is more complicated (as there is more than 2 candidate values for each cell) so let's forget about that for now.

Code: Select all

 *-----------------------------------------------------------*
 | 356   4    #1356  |*689  *159  *1689  |#578   2     567   |
 | 9     578   567   | 24    245  +68    | 1     4568  3     |
 | 56    18    2     | 3    +14    7     | 9     48    56    |
 |-------------------+-------------------+-------------------|
 | 2567  9     3567  | 1     2368  4     | 23578 3568  2567  |
 | 8     12357 13567 | 269   236   39    | 2357  1356  4     |
 | 2346  123   346   | 7     2368  5     | 238   9     126   |
 |-------------------+-------------------+-------------------|
 | 47    37    8     | 5    +3479  2     | 6     13    19    |
 | 1     2357  9     | 46    467   36    | 2345  35    8     |
 | 2345  6     345   |*89   *1349 *18    | 234   7    #259   |
 *-----------------------------------------------------------*

Looking at the extra values in the two rows we have the possibilities: r1c3=1, r1c7=8 and r9c9=9. Now, if r1c3<>1 and r1c7<>8 then r1c456 is a hidden triplet 189 and if r9c9<>9 then r9c456 is a hidden triplet 189 => Nothing you can do could possibly avoid the deadly pattern anymore! Therefore one of the three mentioned cellvalues must be true.

Looking at the boxes, we also have three candidates outside the pattern: r2c6=8, r3c5=1 and r7c5=9. If r2c6<>8 and r3c5<>1 then r1c456 is a hidden triplet 189 and if r7c5<>9 then r9c456 is a hidden triplet 189 => at least one of the three cellvalues must be true. This would btw let us make the elimination

if r1c6=1 (=>r3c5<>1) => r9c6=8 (=>r2c6<>8) => r9c4=9 (=>r7c5<>9)

=> r1c6<>1

RW

[Myth Jellies]

Here's an AIC:

Code: Select all

7[r8c5]=(3&4&6)[r8c456]-(3v4v6)[r9c456]=(1&8&9)[r9c456]-(1v9)[r9c9]=
(2v5)[r9c9]-(2&5)[r8c78]=(3v4v6)[r8c78]-(3&4&6)[r8c456]=7[r8c5]

=> 7[r8c5] is True

where '&', 'v' stand for AND, OR respectively.

Nice find...No wonder I didn't see that. I don't tend to muck about with the or-ing of candidates within groups much, but maybe I should start.

OK, but what about my question about r5c4=9 being true to avoid the deadly MUG?

I hope RW's explanation helped. Any legitimate avoidance has to hit one of the 189's outside of MUG in r19 or else r19 won't have a full set of digits. Crashing the puzzle doesn't count Actually it is hard to go wrong as long as you give it a little thought. You want to focus on the houses that are forced to contain all of the digits if the MUG is true. Any of the sets ABC or D below will have to contain a 1, 8, or 9 to avoid the MUG, but you only have to consider one of them.

Code: Select all

 *------------------------------------------------------------*
 | 356   4   AB1356  |*689  *159  *1689  |AB578   2     567   |
 | 9     578   567   | 24    245 CD68    |  1     4568  3     |
 | 56    18    2     | 3   CD14    7     |  9     48    56    |
 |-------------------+-------------------+--------------------|
 | 2567  9     3567  | 1     2368  4     |  23578 3568  2567  |
 | 8     12357 13567 | 269   236   39    |  2357  1356  4     |
 | 2346  123   346   | 7     2368  5     |  238   9     126   |
 |-------------------+-------------------+--------------------|
 | 47    37    8     | 5   BD3479  2     |  6     13    19    |
 | 1     2357  9     | 46    467   36    |  2345  35    8     |
 | 2345  6     345   |*89   *1349 *18    |  234   7   AC259   |
 *------------------------------------------------------------*


There is no reason why this type of logic can't be applied to unique rectangles as well, though there may be strong links for any cases that one could easily analyze.

[ravel]

Very nice solution, MJ.

I agree with RW, that it is much more elegant than a 2 monster chains solution. On the other hand finding or reading 2 long chains might be done in shorter time than finding or going through all your shorter steps. So i have 2 different ways of "rating solutions": elegance (very subjective) and effectiveness. To make it even more complicated: not in all cases shorter chains are more elegant. I have read some chains by Carcul, RW & co that were not short (and maybe not the shortest possible), but elegant though.

Particularly concerning the effectiveness i cannot agree that eliminations by contradiction (empty cell, no place for a digit in a unit or deadly pattern) are some kind of "worse" than by "meta xy-chains", that lead to an "either this or that holds, therefore these eliminations can be made". The main reason is, that e.g. when i try to find xy-chains, often i get something like: "Either this bivalue cell is x or it is y, then this and that and - oops - contradiction". So i know that it cannot be y and it would be strange for me not to use it. Isn't it hard not to stumble on such contradictions, when studying a puzzle?

[Carcul]

Now, if a is <7>, the strong links force d to be <7> and not <3>.
If a is <3>, d cannot be <3>, because that would force <7> at b, c, which is the deadly pattern.

Consider the following grid:

Code: Select all

 . .  . | . .  . | . . .
 . .  . | . .  . | . . .
 . .  . | . .  . | . . .   
--------+--------+------
 . 37 . | . 37 . | . . .
 . 37 . | . 37 . | . . .
 . .  . | . .  . | . . .
--------+--------+------
 . 3  . | . 7  . | . . .
 . 7  . | . 3  . | . . .
 . .  . | . .  . | . . .


Why are you considering that cells r78c25 make up a deadly pattern?
I don't see anything deadly in it. For me, cells r45c25 make up a true deadly pattern. Could you explain?

Thanks. Carcul

[r.e.s.]

Why are you considering that cells r78c25 make up a deadly pattern?
I don't see anything deadly in it. For me, cells r45c25 make up a true deadly pattern. Could you explain?

You're quoting keith, but I explained it already in the post preceding his: Since there is no clue given for any of those four 3-7-3-7 cells (r78c25), a uniqueness-destroying rectangle would have entered the puzzle. (This is called an "unavoidable set" just because, if there is to be a unique solution, a puzzle-setter cannot avoid placing a clue in at least one of its cells.)

[keith]

I think Carcul is saying that the candidates

Code: Select all

37 | 37
37 | 37


are the deadly pattern. He is correct.

The solution fragment

Code: Select all

7 | 3
3 | 7


is, strictly speaking, not a deadly pattern. Some, including me, do sometimes refer to it as such.

Keith

[r.e.s.]

The solution fragment

Code: Select all

7 | 3
3 | 7


is, strictly speaking, not a deadly pattern. Some, including me, do sometimes refer to it as such.

Well, possibly you should have been more careful ; however, ISTM that the question being asked is "What's deadly about this pattern?" (since he said he saw nothing deadly about it). I hope the answer to that has now been adequately explained.

[daj95376]

I know everyone is discussing advanced techniques/issues associated with this puzzle. I'm sorry to interrupt the flow. However, this also works without very complicated chains.

Code: Select all

r3      -  56    Naked  Pair
    b3  -  4     Locked Candidate (1)
    b3  -  7     Locked Candidate (1)
    b5  -  8     Locked Candidate (1)
r7c2    =  7     [r7c2]=3 => [r9]=INVALID
r2c3    =  7     Hidden Single
r5c7    =  7     Hidden Single
r1c9    =  7     Hidden Single
r4c1    =  7     Hidden Single
r8c5    =  7     Hidden Single
r1c7    =  8     [r1c7]=5 => [r8]=INVALID
                 Naked  Singles remain

[r7c2]=3 => [r7c8]=1 => [r7c9]=9
                     => [r6c9]=1 => [r6c2]=2 => [r9c1]=2 => [r9c9]=5 => [r8c8]=3 => [r9]=INVALID

[r1c7]=5 => [r3c9]=6 => [r3c1]=5 => [r2c2]=8 => [r2c6]=6 => [r8c6]=3 => [r5c6]=9
                                             => [r2c8]=4 => [r2c4]=2 => [r5c4]=6 => [r8]=INVALID


[Myth Jellies]

Particularly concerning the effectiveness i cannot agree that eliminations by contradiction (empty cell, no place for a digit in a unit or deadly pattern) are some kind of "worse" than by "meta xy-chains", that lead to an "either this or that holds, therefore these eliminations can be made".

If you are saying that, for a difficult puzzle, brute force methods are more effective at getting to a solution than methods that are basically an extended "OR", then I agree 100%. I also agree that most brute force methods are easier to apply and can result in a simpler reduction in some cases.

The thing is, I know that any puzzle can be solved by a decent brute force method. Thus, I have merely a mild interest in seeing extremely tough puzzles cracked by one or two hefty brute force reductions; though I am blown away by some people finding these reductions and solving these puzzles without the use of pencilmarks. But what is unknown is whether or not these tough puzzles can ever be cracked by theoretical methods. That is the sudoku problem which fascinates me the most; and I suspect that it is a driving force behind the creation of many of these advanced methods. If you are happy with a brute force method that can solve any puzzle, then there really is little impetus to work at discovering and developing new methods.

...when i try to find xy-chains, often i get something like: "Either this bivalue cell is x or it is y, then this and that and - oops - contradiction". So i know that it cannot be y and it would be strange for me not to use it. Isn't it hard not to stumble on such contradictions, when studying a puzzle?

If you approach chains from an "if-then" perspective, then I can see your problem. I approach chains from an "extended or" perspective. A or B must be true. Both B and C cannot be true. C or D must be true. Now I know A or D is true--is there a deduction I can make? Continue. Using this approach, I never really stumble on any contradictions.

[Carcul]

a uniqueness-destroying rectangle would have entered the puzzle.

That is the part that I don't understand. Why can you say that?

Carcul

[Carcul]

Using this approach, I never really stumble on any contradictions.

Oh yes you do: otherwise, you would't make any deductions. Just the fact that you are saying that is by itself a contradiction.

Looking at ALS set A, note that if you exclude the 6's from the set, you end up with the primed digits remaining. Thus we have...

Do you call that "theoretical"? "Action at distance"?
No further comments your Honour...

Carcul

[ravel]

If you approach chains from an "if-then" perspective, then I can see your problem.

Maybe this is my problem. I cannot judge that because i would have to make a brain wash not to think (also) this way, when solving a sudoku.

I approach chains from an "extended or" perspective. A or B must be true. Both B and C cannot be true. C or D must be true. Now I know A or D is true--is there a deduction I can make? Continue. Using this approach, I never really stumble on any contradictions.

Suppose now you also have "both B and D cannot be true". Wouldn't you eliminate B by contradiction?

[r.e.s.]

a uniqueness-destroying rectangle would have entered the puzzle.

That is the part that I don't understand. Why can you say that?

Solved digits 3-7-3-7 in r78c25 would be a type of pattern called an "unavoidable set" in a solution grid:

For any unavoidable set in a solution grid, any unique-solution puzzle made from that grid must give at least one element of that set as a clue.

If no element of an existing unavoidable set is given as a clue (as in our hypothetical case), then the puzzle does not have a unique solution -- "a uniqueness-destroying pattern would have entered the puzzle".

[daj95376]

If you approach chains from an "if-then" perspective, then I can see your problem. I approach chains from an "extended or" perspective. A or B must be true. Both B and C cannot be true. C or D must be true. Now I know A or D is true--is there a deduction I can make? Continue. Using this approach, I never really stumble on any contradictions.

Boy, and I thought that I was the only one who could step in it. I sure would like to see your algorithm for finding Naked Pairs. Here's mine.

If I find a cell in a unit with candidates <12> ... and then I find another cell in that unit with candidates <12> ... I deduce that none of the other cells in this unit can have these candidates. Give me good ol' if-then any day. (Yes, I know this isn't exactly what you meant, but I couldn't help myself.)

Second, my set theory days are way behind me and mostly a blur. However, you seem to have left something out in your logic above. Yes, you know that either A or D is true, but what if you can't deduce anything from that. There's still the fact that either B or C is true and you may be able to deduce something from that. Oh, wait a minute, that would be a brute-force type of logic on trying AD and then trying BC. We can't have that!

If you follow a chain with the express purpose of encountering a specific condition, then you have a technique in my opinion.

If you follow a chain with the express purpose of finding a contradiction and making use of that contradiction, then it could be said that you're using brute-force.

If you find a Naked Pair in a unit and use the fact that it's a contradiction for those candidates to exist in other cells in the unit, then you decide on what you're going to call it!

Now, after all this useless rambling on my part, I wish to point out that there are a great many useful techniques that very bright people have derived for reducing the complexity of Sudoku puzzles. I do NOT in any way wish to demean their effort or results!!! However, there seems to be a plethora of puzzles where it's unlikely that anyone is going to derive a logical solution for them in the near future. (I applaud those who keep trying!!!) This leaves brute-force or walking away without a solution. You choose!

Bottom Line: Sudoku puzzles exist because there are contradictory states in the resulting candidates. The object of solving a puzzle is to successively eliminate these states until a solution can be derived.

[r.e.s.]

Using this approach, I never really stumble on any contradictions.

Oh yes you do: otherwise, you would't make any deductions.

Boy, and I thought that I was the only one who could step in it.
...
Bottom Line: Sudoku puzzles exist because there are contradictory states in the resulting candidates. The object of solving a puzzle is to successively eliminate these states until a solution can be derived.

Here's my two cents worth ...

A contradiction (in classical logic) is a conjunction of the form (A AND ~A), and it is not *necessary* for such a proposition to appear in a valid Alternating Inference Chain (AIC) deduction.

To take a simple example, say we have an AIC of form x--a==b--x. (Writing '--' instead of '-' for better readability.)

Code: Select all

The definition of x--a is the proposition (~x OR ~a), also denoted (x => ~a).

The definition of a==b is the proposition (a OR b), also denoted (~a => b).

The definition of b--x is the proposition (~b OR ~x), also denoted (b => ~x).

The definition of x--a==b--x is the proposition (x--a) AND (a==b) AND (b--x),
also denoted (x => ~a) AND (~a => b) AND (b => ~x)  (or just x => ~a => b => ~x).

By the rules of classical logic, the AIC proposition implies (~x OR ~x),
also denoted (x => ~x), which reduces to just (~x).

I.e., the conclusion is (~x), and no contradiction was involved. It's important to note that in classical logic, (A => B) is nothing more than shorthand for the proposition (~A OR B).

EDIT: Here (P OR Q) is the usual inclusive logical disjunction, which is true just whenever at least one of P,Q is true -- not to be confused with the exclusive disjunction (P XOR Q), which is true just when ever exactly one of P,Q is true.

Now we could use (x => ... => ~x) as the basis of an argument of the form "assume x, ... deduce ~x, ... conclude ~x", which *would* have involved the contradiction (x AND ~x). But that's not the only form of argument in town.
--

BTW (if slightly OT), AICs capture the general "forcing chain" idea in which there are several possibilities, one of which must be true, and all of them lead to the same conclusion. This is so because the chain can be read rightward and leftward from any intermediate node, as well as from either "end". E.g., this ...

Code: Select all

x--a==b--x
Therefore ~x.

is equivalent to

Code: Select all

(a => ~x) AND (~a => b => ~x)
Therefore ~x.

because (x--a==b--x) is equivalent to ((a--x) AND (a==b--x)).