The New Sudoku Players' Forum

[ronk]

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).

Just to clarify ... "(~x OR ~a)" means either 'x' is false, or 'a' is false, or both are false. Similarly, "(a OR b)" means either 'a' is true, or 'b' is true, or both are true.

[r.e.s.]

Ron,

Right, it's worth emphasising that this is the usual "inclusive OR" (not ot be confused with XOR). Another way of putting it is to say that (A OR B) is true just whenever at least one of A,B is true. I've added a note to that effect in my previous posting.

Thus (a==b) means (a OR b), i.e. at least one of a,b is true,
and (a--b) means (a NAND b), i.e. at least one of a,b is false.

Also, truth tables are probably the best way to justify my comment that "by the rules of classical logic, the AIC proposition implies ... (~x)" in such a way that no contradiction is part of the deduction.

[ravel]

Code: Select all

 *-----------------------------------------------------------------------------*
 | 356     4       1356    | 689     1569    1689    | 578     2       567     |
 | 9       578     567     | 2468    2456    68      | 1       4568    3       |
 | 56      18      2       | 3       14      7       | 9       48      56      |
 |-------------------------+-------------------------+-------------------------|
 | 23567   23579   3567    | 1       23689   4       | 23578   3568    2567    |
 | 8       123579  13567   | 269     2369    369     | 2357    1356    4       |
 | 2346    123     1346    | 7       2368    5       | 238     9       126     |
 |-------------------------+-------------------------+-------------------------|
 | 347     37      8       | 5       13479   2       | 6       13      19      |
 | 1       2357    9       | 46      3467    36      | 2345    35      8       |
 | 2345    6       345     | 489     1349    1389    | 2345    7       1259    |
 *-----------------------------------------------------------------------------*


I tried to write RW's fine elimination as forcing chain:
If r7c5=7 => r8c2=7 => r8c78=25 (=> r8c456=346) => r9c456=189 => r9c9=empty cell => r7c5<>7

This is an equivalent (quadruple) forcing chain (with interesting implications, i think):
r9c9=19 => r9c456<>189 (must contain 3 or 4) => r8c456<>346 (must contain 7) => r8c2<>7 => r7c12=7 => r7c5<>7
r9c9=25 => r8c78<>25 => r8c456<>346 => r8c2<>7 => r7c12=7 => r7c5<>7

Can it be expressed as AIC ?
[Edit:] Ah, i see, that r.e.s. has already done. If this is always possible, MJ would have no reason to avoid eliminations by contradiction. Just rewrite it as AIC and it is a "good" deduction

[Carcul]

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.

I cannot believe this. In other words, you are saying that making deductions by contradictions is "primitive" and deducing "without" them is "mentally superior"? Is that it? If yes, then please give a reasonable answer to this question:

Where lies the inferiority of a contradiction?

[ravel]

I also cant follow this argumentation about contradiction or not.

When someone says, i would use those bad contradictions, i could always answer, i dont need the contradiction and write it (backwards) as forcing chain without contradiction. But fact is, that eliminations by contradiction are easier to spot than those multiple forcing chains (or equivalent AIC's) and thats the reason, why i use them.

Also i cannot see, why the AIC method (which i dont want to critisize, we just saw, how mighty it is) - starting with a strong link adding a weak and a strong link, looking for a deduction, adding 2 more links etc. - should be a less "brute force" technique. You neither know in advance, where to start nor where to go to for effective eliminations. So instead of "trying numbers" it is "trying links".

[ronk]

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.

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.

RW and MJ, thanks for the help. To paraphrase Henry Higgins ... "By jove, I think I've got it! I've really got it!" ... but we won't know for sure until the next MUG appears.

[r.e.s.]

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.

I cannot believe this. In other words, you are saying that making deductions by contradictions is "primitive" and deducing "without" them is "mentally superior"? Is that it? If yes, then please give a reasonable answer to this question:

Where lies the inferiority of a contradiction?

You're putting words in my mouth! To say that AIC deductions don't *need* to focus on contradictions is not to speak in terms of inferior/superior.

[r.e.s.]

But fact is, that eliminations by contradiction are easier to spot than those multiple forcing chains (or equivalent AIC's) and thats the reason, why i use them.

IMO, if a person spots something -- anything -- in the puzzle that allows a logical deduction to be made, then it would be silly not to do so.

Spotting potential contradictions and making moves logically designed to avoid them is among the most reasonable of approaches, ISTM; indeed, I expect that any logical deduction *can* be formulated in these terms.

Also i cannot see, why the AIC method [...] should be a less "brute force" technique. You neither know in advance, where to start nor where to go to for effective eliminations. So instead of "trying numbers" it is "trying links".

I think this is a most important issue concerning any type of chaining method, whether it's called "AIC", "Nice Loops", or whatever. Typically it's a matter of degree to which one can recognise the spatial pattern in which the target logic pattern will appear (e.g. naked pairs, which stand out well); but in some cases (e.g. many bivalue cells leading to a "remote pair" or to an "xy-chain"), the pattern may stand out well enough to make it a much more-feasible target than would need "brute force searching".

Of course many AICs practically shout for attention, due to the ease of locating and combining a small number of strong links. <This thread> has examples.

[Myth Jellies]

... but we won't know for sure until the next MUG appears.

You really don't need to wait for a MUG...

Code: Select all

+-------------------+-------------------+-------------------+
| 8    #47   *347   | 25   *37    9     | 6     25    1     |
| 9     6     1     | 258   4     258   | 57    37    23    |
| 5     2    *37    | 6    *137  #17    | 4     9     8     |
+-------------------+-------------------+-------------------+
| 3     457   6     | 1     8     457   | 9     25    24    |
| 12    8     47    | 2457  9     23457 | 15    6     34    |
| 12    45    9     | 245   6     2345  | 158   38    7     |
+-------------------+-------------------+-------------------+
| 7     1     8     | 9     2     6     | 3     4     5     |
| 6     3     2     | 478   5     478   | 78    1     9     |
| 4     9     5     | 3     17    178   | 2     78    6     |
+-------------------+-------------------+-------------------+

...to avoid the 37-UR marked by asterisks, either of the hashed cells must be a 7. This means that neither r1c5 nor r3c3 can be a 7 (of course you can use the UR strong link logic instead).

As to the brute force/contradiction debate, there have been some good points raised on both sides of the issue. I'd like to chew on them a little bit.

[Myth Jellies]

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"?

I call that an Almost Locked Set of 4 digits (abcd) in 3 cells. You can always take a simple ALS and pull out any one digit to form a strong inference between that digit and the remaining digits all AND-ed together
a = (b & c & d)
There's nothing obviously wrong to me about noting the naked and hidden singles in the (b & c & d) subset as you try to figure out where a weak link can apply.

In the end, the AIC showed that set A must contain a 6. Therefore, I could deduce that any cell which saw all of the 6's in set A could not be a 6. I did this without using any of the deleted 6's in my "AIC-pattern" at all. Thus there was "action at a distance" (more than one, as several 6's were deleted).

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?

Not really. I have an AIC that is C = D. Thus I know C or D must be true. Since both C and D are weakly linked to B, I know B must be false, and B is not part of my AIC. You are right, that it is possible to stumble onto this while searching with something else in mind, but it is still a valid AIC deduction. Would I feel bad about stumbling onto it? Not a bit. Think of the extra parts of the chain as extra unused lines in a B&B plot, etc.

[ravel]

Some more thoughts about it. I looked at Daj's first chain eliminating 3 from r7c2=3:
[r7c2]=3 => [r7c8]=1 => [r7c9]=9
=> [r6c9]=1 => [r6c2]=2 => [r9c1]=2 => [r9c9]=5 => [r8c8]=3 => [r9]=INVALID

Code: Select all

 *-----------------------------------------------------------------------------*
 | 356     4       1356    | 689     1569    1689    | 578     2       567     |
 | 9       578     567     | 2468    2456    68      | 1       4568    3       |
 | 56      18      2       | 3       14      7       | 9       48      56      |
 |-------------------------+-------------------------+-------------------------|
 | 23567   23579   3567    | 1       23689   4       | 23578   3568    2567    |
 | 8       123579  13567   | 269     2369    369     | 2357    1356    4       |
 | 2346    123     1346    | 7       2368    5       | 238     9       126     |
 |-------------------------+-------------------------+-------------------------|
 | 347     37      8       | 5       13479   2       | 6       13      19      |
 | 1       2357    9       | 46      3467    36      | 2345    35      8       |
 | 2345    6       345     | 489     1349    1389    | 2345    7       1259    |
 *-----------------------------------------------------------------------------*


Added some omitted steps:
r7c2=3 (=> r6c2<>3, r9c3<>3) => r7c8=1 (=> r9c9<>1) => r7c9=9 (=> r9c9<>9) => r6c9=1 => r6c2=2 (=> r8c2<>2) => r9c1=2 (=> r9c7<>2) => r9c9=5 => (r9c7<>5, r8c8=3 => r9c7<>3) => r9c3=4 => r9c7<>4 => r9c7 is empty

This is definitely a proof, that all candidates in r9c7 force r7c2<>3, because "r7c2=3 => r9c7 is empty" is equivalent to "any candidate in r9c7 => r7c2<>3".
It also can be written as quadruple forcing chain without contradiction, where eventually "case distinctions" or nested forcing chains are needed, when the elimination chain uses multiple inferences.

This one is a bit shorter, starting with the candidates in r6c2:
r6c2=3 => r7c2<>3
r6c2=1 => r6c9<>1 => r79c9=1 => r6c8=3 => r7c2<>3
r6c2=2 => r8c2<>2 => r9c1=2 => r8c7=2 (=> r9c9<>2) => r9c7=4 =>
(r9c3=35) {r9c3=3 => r7c2<>3} or {r9c3=5 => r79c9=19 => r6c8=3 => r7c2<>3}

Now i tried to write it as an AIC:
3[r6c2]=
{ (either r6c2=3 or r6c2=1 or r6c2 = 2)
1[r6c2]-[r6c9]=[r79c9]-[r7c8]=3[r7c8]
OR
2[r6c2]-[r8c2]=[r9c1]-[r9c79]=2[r8c7]-4[r8c7]=[r9c9]-[r9c3]=
{
(either r6c2=3 or r7c8=3 or r9c3=3 or r9c3=5 and r8c7=2 - also on the right side of = )
3[r9c3]
OR
2[r8c7]&5[r9c3]-(2v5)[r9c9]=19[r79c9]-1[r7c8]=3[r7c8]
}
}
=> Either r6c2=3 or r7c8=3 or r9c3=3 => r7c2<>3.

So i see much equivalence between elimination chains, forcing nets and AIC's (or NL's). For me elimination chains are easier to find and easier to denote as forcing nets (just to read from left to right), but AIC's (and NL's) provide additional information, which is useful especially for closed chains.

[daj95376]

Code: Select all

 *-----------------------------------------------------------------------------*
 | 356     4       1356    | 689     1569    1689    | 578     2       567     |
 | 9       578     567     | 2468    2456    68      | 1       4568    3       |
 | 56      18      2       | 3       14      7       | 9       48      56      |
 |-------------------------+-------------------------+-------------------------|
 | 23567   23579   3567    | 1       23689   4       | 23578   3568    2567    |
 | 8       123579  13567   | 269     2369    369     | 2357    1356    4       |
 | 2346    123     1346    | 7       2368    5       | 238     9       126     |
 |-------------------------+-------------------------+-------------------------|
 | 347     37      8       | 5       13479   2       | 6       13      19      |
 | 1       2357    9       | 46      3467    36      | 2345    35      8       |
 | 2345    6       345     | 489     1349    1389    | 2345    7       1259    |
 *-----------------------------------------------------------------------------*


I tried to write RW's fine elimination as forcing chain:
If r7c5=7 => r8c2=7 => r8c78=25 (=> r8c456=346) => r9c456=189 => r9c9=empty cell => r7c5<>7

This is an equivalent (quadruple) forcing chain (with interesting implications, i think):
r9c9=19 => r9c456<>189 (must contain 3 or 4) => r8c456<>346 (must contain 7) => r8c2<>7 => r7c12=7 => r7c5<>7
r9c9=25 => r8c78<>25 => r8c456<>346 => r8c2<>7 => r7c12=7 => r7c5<>7

Can it be expressed as AIC ?
[Edit:] Ah, i see, that r.e.s. has already done. If this is always possible, MJ would have no reason to avoid eliminations by contradiction. Just rewrite it as AIC and it is a "good" deduction

I've been studying forcing chains and have found the definitions and examples to be confusing and contradictory at times. However, I'm pretty sure there's an error in the statement above where I highlighted a step.

[ravel]

Thanks Daj,
since the fact, that only 2 and 5 remain for the cells r8c78 follows from the triple 346 in r8c456, this should have been denoted before.
So better is:

If r7c5=7 (=> r8c2=7) => r8c456=346 (=> r8c78=25) => r9c456=189 => r9c9=empty cell => r7c5<>7

[Edit: But i remember now, that the point was, that RW saw it as hidden pair, which followed from r8c2<>25, so the chain was not incorrect]

[daj95376]

ravel,

I was trying to (politely) point out that cell [r8c8] does not have a 2 in it.

[ravel]

Of course you are right, but for the deduction is is sufficient to know that 2 and 5 have to go to row 8 of box 9 (therefore cannot be in r9c9). As i said, i followed RW's argumentation, when i wrote the chain.