The New Sudoku Players' Forum

[Nick70]

Hrm, I see that the intersections can be eliminated, but not necessarily by a corollary to this technique

I didn't say it was a corollary to your technique. It's something different which happens to be a complement to the rule you mentioned. Each of the two patterns requires that the cells excluded by the other are empty, and excludes the cells that the other requires to be empty.

[ronk]

I didn't say it was a corollary to your technique.

I see it as the same technique. Starting with your illustration ... and adding a few candidates for completeness ... we have ...

Code: Select all

. a .|e . .|* . .
. b .|f . .|. * .
c w d|x g h|+ + .
-----------------
m y n|z r s|. + +
. i .|p . .|. * .
. j .|q . .|* * .
-----------------
* + *|. . *|. . .
. . *|+ * .|. . .
. + .|. . .|. . .

From an equations perspective (equalities and inequalities) ...

Constraining equalities(K):
(a+b)+(c+d)+w=1 (box 1)
(e+f)+(g+h)+x=1 (box 2)
(i+j)+(m+n)+y=1 (box 4)
(p+q)+(r+s)+z=1 (box 5)

"Constrained" inequalities(U):
(a+b)+(i+j)+w+y<=1 (col 2)
(c+d)+(g+h)+w+x<=1 (row 3)
(e+f)+(p+q)+x+z<=1 (col 4)
(m+n)+(r+s)+y+z<=1 (row 4)

In order to eliminate the other candidates in the rows and cols, one must "convert" the inequalities to equalities. Specifically, one must prove equalities(V):
(a+b)+(i+j)+w+y=1 (col 2)
(c+d)+(g+h)+w+x=1 (row 3)
(e+f)+(p+q)+x+z=1 (col 4)
(m+n)+(r+s)+y+z=1 (row 4)

Without proof, I hypothesize that proving equalities(V) is only possible if w=x=y=z=0. If this hypothesis is true, then the technique that eliminates other candidates from the rows and columns is the *same* technique that eliminates the candidates at the intersections of the rows and columns.

[Nick70]

If this hypothesis is true, then the technique that eliminates other candidates from the rows and columns is the *same* technique that eliminates the candidates at the intersections of the rows and columns.

Of course. That's one technique.

The other technique is the one that eliminates the other candidates in the boxes when the interections of rows and columns, and other cells in rows and columns, are empty.

[ronk]

Off topic: Is anyone else experiencing popups from either the sudoku.com or setbb.com? The last batch I received were from inqwire.com ... and I never had the problem before visiting these sudoku sites.

[ronk]

Of course. That's one technique.

The other technique is the one that eliminates the other candidates in the boxes when the interections of rows and columns, and other cells in rows and columns, are empty.

While I'm not sure which word is the "most* appropriate, "corollary" or "complementary" or "inverse" or "reciprocal" all seem somewhat approriate.

After all, from a mathematical perspective, the only difference is the equalities become the inequalities ... and the inequalties become the equalities. Specifically for the previous illustration ...

Constraining equalities(K):
(a+b)+(i+j)+w+y=1 (col 2)
(c+d)+(g+h)+w+x=1 (row 3)
(e+f)+(p+q)+x+z=1 (col 4)
(m+n)+(r+s)+y+z=1 (row 4)

"Constrained" inequalities(U):
(a+b)+(c+d)+w<=1 (box 1)
(e+f)+(g+h)+x<=1 (box 2)
(i+j)+(m+n)+y<=1 (box 4)
(p+q)+(r+s)+z<=1 (box 5)

[Lummox JR]

Hrm, I see that the intersections can be eliminated, but not necessarily by a corollary to this technique

I didn't say it was a corollary to your technique. It's something different which happens to be a complement to the rule you mentioned. Each of the two patterns requires that the cells excluded by the other are empty, and excludes the cells that the other requires to be empty.

I don't follow. If all constraints from both the A and B sets were empty outside of where A and B intersect, then clearly the intersections within A and within B could be removed. However I see no other way to eliminate the intersections between the columns and rows without either testing them individually or by the hidden pattern I mentioned.

Can you detail the logic used to eliminate the intra-A or intra-B intersections (in this case, the intersections between the columns and rows) in the general case?

[Nick70]

However I see no other way to eliminate the intersections between the columns and rows without either testing them individually or by the hidden pattern I mentioned.

I didn't say it was possible. I said that the "hidden pattern" is a complement to yours.

The "backbone" of the pattern remains the same (the intersection of 2 rows and 2 cols with 4 boxes). The cells required to be empty and the cells that get excluded are swapped in the two patterns.

This is an interesting symmetry regardless of the method you use to deduct it. If you want to deduct them using the same method you can use forcing chains or the equations shown by ronk.

[Nick70]

I didn't say it was possible.

Actually...

If you have a set, A, of N constraints which do not have the same placements, and they share the same N other constraints (set B), you can eliminate all choices in B which do not occur in A.

Set A is the 4 boxes. Set B is the 2 rows and 2 cols. The placements in the 4 boxes are disjoint (obviously since they are 4 boxes). Then you can eliminate all choices in the rows/cols that don't occur in the 4 boxes.

Is that right?

At that point you can apply the reasoning you said to have found for the case when all the choices are constrained to set A and set B--though I don't think that's a "corollary" as you stated.

[Lummox JR]

If you have a set, A, of N constraints which do not have the same placements, and they share the same N other constraints (set B), you can eliminate all choices in B which do not occur in A.

Set A is the 4 boxes. Set B is the 2 rows and 2 cols. The placements in the 4 boxes are disjoint (obviously since they are 4 boxes). Then you can eliminate all choices in the rows/cols that don't occur in the 4 boxes.

Is that right?

At that point you can apply the reasoning you said to have found for the case when all the choices are constrained to set A and set B--though I don't think that's a "corollary" as you stated.

I think I may be seeing something here now. My initial reasoning was based on the fact that no overlaps can occur within A. This makes sense because if you satisfy two members of A, you'll end up with an unsatisfied B. Since B was where we would make eliminations, one of those choices that would be eliminated would still be valid in that case.

However when set B has the overlaps, the same logic does not apply, thoguh originally I thought it did. If you choose one of the column/row intersections within B, from the example you posted, you'll satisfy two members of B but only one A. Then you have N-1 members of A which must fit in N-2 members of B. This is impossible, so the intersections can be eliminated. Likewise if you try to place something in B that is outside of A, you'll have a case of N members of A trying to fit into N-1 members of B. So this, then, is the hidden pattern.

Now that I see this, I'll have to modify the formal definition of this technique:

If you have a set of N constraints, A, whose collective choices each satisfy only one member of A, which also collectively fit N constraints in set B, all choices in B that lie outside of A or that fit more than one member of B may be eliminated.

And suddenly that hidden pattern makes perfect sense.

[ronk]

It occurred to me last night that there's another kind of constraint subset worth mentioning that I did not initially explore. In this kind you have N rows and columns, whose values do not overlap and all occur within N boxes. Observe:

Code: Select all

. . -|+ . .|* . .
- + .|+ - -|. * .
+ . +|. + .|. . .
-----------------
+ . +|. + +|. . .
. + .|. - .|. * .
. + -|+ . -|* * .
-----------------
* . *|. . *|. . .
. . *|. * .|. . .
. . .|. . .|. . .

The above is actually my (hopefully correct) merge of your two diagrams.

After giving priority to lower level techniques (including simple coloring), I was surprised to only find one occurrence of the above pattern in the top870. At the point of interest for puzzle #438 ...

Code: Select all

 *--------------------------------------------------------------------*
 | 3      9      1248   | 6      2458   1248   | 58     4578   4578   |
 | 128    14     7      | 12358  23458  1238   | 69     458    69     |
 | 5      6      48     | 7      9      48     | 1      2      3      |
 |---------------- -----+----------------------+----------------------|
 | 146789 37     134689 | 2389   2378   5      | 2389   1478   4789   |
 | 4789   2      3489   | 389    1      389    | 3589   6      45789  |
 | 1789   5      1389   | 4      2378   6      | 2389   178    789    |
 |----------------------+----------------------+----------------------|
 | 24     8      5      | 23     6      234    | 7      9      1      |
 | 12679  37     12369  | 12589  258    1289   | 4      58     568    |
 | 1469   14     169    | 1589   458    7      | 568    3      2      |
 *--------------------------------------------------------------------*

... and mapping only candidate 4 we have ...

Code: Select all

 . . 4 | . 4 4 | . 4 4
 . 4 . | . 4 . | . 4 .
 . . 4 | . . 4 | . . .
-------+-------+-------
 4 . 4 | . . . | . 4 4
 4 . 4 | . . . | . . 4
 . . . | . . . | . . .
-------+-------+-------
 4 . . | . . 4 | . . .
 . . . | . . . | . . .
 4 4 . | . 4 . | . . .

... with constrained candidates (constrained by rows 3 and 7, and columns 2 and 5) confined to boxes 1, 2, 7, and 8. Using your and Nick70's notation, the pattern and eliminations are ...

Code: Select all

 . . - | . + - | . * *
 . + . | . + . | . * .
 . . + | . . + | . . .
-------+-------+-------
 * . * | . . . | . * *
 * . * | . . . | . . *
 . . . | . . . | . . .
-------+-------+-------
 + . . | . . + | . . .
 . . . | . . . | . . .
 - + . | . + . | . . .

Puzzle #37 also displayed the pattern, but only after a couple of modifications by a "forward implication chains" technique.

[Lummox JR]

Unfortunately the example from #438 isn't a great example of this technique, since the same result can be found via coloring. Where did #37 show this?

[ronk]

Where did #37 show this?

After rather simple steps plus "forward implication" eliminations r5c2<>7, r5c3<>7, and r4c7<>3 ...

Code: Select all

 *-----------*
 |12.|456|..9|
 |4.6|...|...|
 |7.9|...|...|
 |---+---+---|
 |2.7|514|69.|
 |641|938|..2|
 |.95|..2|..4|
 |---+---+---|
 |.6.|2..|8..|
 |572|...|.3.|
 |.1.|...|...|
 *-----------*
 
 *-----------------------------------------------------------*
 | 1     2     38    | 4     5     6     | 37    78    9     |
 | 4     358   6     | 1378  2789  1379  | 1235  125   1358  |
 | 7     358   9     | 138   28    13    | 12345 12456 13568 |
 |-------------------+-------------------+-------------------|
 | 2     38    7     | 5     1     4     | 6     9     38    |
 | 6     4     1     | 9     3     8     | 57    57    2     |
 | 38    9     5     | 67    67    2     | 13    18    4     |
 |-------------------+-------------------+-------------------|
 | 39    6     34    | 2     479   13579 | 8     145   157   |
 | 5     7     2     | 168   4689  19    | 149   3     16    |
 | 389   1     348   | 367   4679  3579  | 2459  2456  567   |
 *-----------------------------------------------------------*


... with a digit 3 pattern of ...

Code: Select all

 . . + | . . . | + . .
 . + . | * . * | - . +
 . + . | * . * | - . +
-------+-------+-------
 . + . | . . . | . . +
 . . . | . . . | . . .
 + . . | . . . | + . .
-------+-------+-------
 * . * | . . * | . . .
 . . . | . . . | . . .
 * . * | * . * | . . .


Not impressive either I'm afraid. While my code isn't identifying patterns that don't really exist ... it may be missing patterns that really do exist. I'll look closer for a bug in the next few days.

Unfortunately the example from #438 isn't a great example of this technique, since the same result can be found via coloring.

My simple coloring didn't pick it up. Can you give me a hint?

[Lummox JR]

Complete simple coloring subsumes fishy cycles, and a fishy cycle is what Sudoku Susser identified when I ran the puzzle through that. I'll demonstrate with your candidate 4's from #438:

Code: Select all

. . *|. * *|. * *
. c .|. * .|. * .
. . a|. . A|. . .
-----+-----+-----
* . *|. . .|. * *
* . *|. . .|. . *
. . .|. . .|. . .
-----+-----+-----
b . .|. . B|. . .
. . .|. . .|. . .
* C .|. b .|. . .

Now using the language of exclusions, a!c (a excludes c; they can't both be true), A!B, and b!C. Using the rule x!y + Y!z -> x!z, we can propagate the exclusions.

a!c + C!b -> a!b,c
A!B + b!C -> A!B,C
b!C + c!a -> b!a,C
B!A + a!c -> B!A,c
c!a + A!B -> c!a,B
C!b + B!A -> C!A,b

In complete simple coloring, if two colors exclude each other, you can eliminate anything that touches their conjugates. That is, since we proved a!b, at least one of them must be false, so either A or B or both must be true. (Although we know it's not both here because A!B.) Therefore, you can eliminate the unlabeled candidate in column 6. This turns out to prove that a=B and A=b. You can do similar eliminations to find out that a=C and A=c as well.

Code: Select all

. . -|. * -|. * *
. c .|. * .|. * .
. . a|. . A|. . .
-----+-----+-----
* . *|. . .|. * *
* . *|. . .|. . *
. . .|. . .|. . .
-----+-----+-----
b . .|. . B|. . .
. . .|. . .|. . .
- C .|. b .|. . .

Or, you can take a shortcut with the above information. Since you know a!b and A!B, then a=B and A=b. And since a!c and A!C, a=C and A=c. Once you recolor the graph it's even easier to make the eliminations above, since it's easier to see where a and A intersect.

Code: Select all

. . -|. * -|. * *
. A .|. * .|. * .
. . a|. . A|. . .
-----+-----+-----
* . *|. . .|. * *
* . *|. . .|. . *
. . .|. . .|. . .
-----+-----+-----
A . .|. . a|. . .
. . .|. . .|. . .
- a .|. A .|. . .

[ronk]

Another aspect of this technique I didn't explore in my original post is that you can have either set, A or B, be the set that mixes two types of constraints.

There is a discussion here which has the look of mixed constraint types, but I can't figure it out.

The puzzle ...

Code: Select all

 ...|37.|569
 5.9|82.|137
 ..7|9..|...
 ---+---+---
 4.8|6.9|..1
 .76|...|9..
 9..|2.7|6.8
 ---+---+---
 .92|7.3|..6
 7..|.6.|.9.
 6..|.9.|...

 
 28     28     14     | 3      7      14     | 5      6      9       
 5      46     9      | 8      2      46     | 1      3      7       
 13     136    7      | 9      15     156    | 248    248    24     
 ---------------------+----------------------+---------------------
 4      235    8      | 6      35     9      | 237    257    1       
 123    7      6      | 145    13458  158    | 9      245    2345   
 9      135    135    | 2      1345   7      | 6      45     8       
 ---------------------+----------------------+---------------------
 18     9      2      | 7      1458   3      | 48     1458   6       
 7      13458  1345   | 145    6      1258   | 2348   9      2345   
 6      13458  1345   | 145    9      1258   | 23478  124578 2345   


... with candidate 5's ...

Code: Select all

 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . 5 5 | . . .
 ------+-------+-------
 . 5 . | . 5 . | . 5 .
 . . . | + - - | . - +
 . 5 5 | . 5 . | . 5 .
 ------+-------+-------
 . . . | . + . | . + .
 . 5 5 | + . - | . . +
 . 5 5 | + . - | . - +

The eliminations are those identified by the author 'Pep'. I showed r7, c4, and c9 as constraints ... but view those skeptically. Note that candidates exist at the intersects.

[Lummox JR]

Now that's a pretty interesting case. I had a lot of trouble spotting at first what it was doing. Apparently the A set is r7, c4, c9, and the B set is r5, b8, and b9. What's unusual is that this particular subset has mixed constraint types in both A and B.