The New Sudoku Players' Forum

[tso]

[quote="Jeff]
Since r5c8=2 will promote a bivalue universal death situation, r5c8 must be 4. And this completes the grid.[/quote]

I don't understand this -- could you explain?

[Nick70]

In this case, r7c2 is still the only tri-value cell in its row, column and box BUT none of the other cells in its three houses share a house with another tri-value or greater cell. Would we be able to correctly apply the tactic to r7c2 in this case?

I don't think so, because even if the other bivalue cells don't directly share a house with trivalues, they are still influenced by it through other cells.

I think the only case when the tactic can be applied is when a single trivalue cell is left, and all others are bivalues. And even in that case, we haven't proven it's a correct tactic, i.e. we haven't proven that a grid where all cells are bivalues cannot have a single solution.

[Nick70]

Since r5c8=2 will promote a bivalue universal death situation, r5c8 must be 4. And this completes the grid.

I don't understand this -- could you explain?

If R5C8=2, then R5C1=48, R4C8=13 and R6C8=14, leaving only bivalues in the grid.

[Jeff]

.....we haven't proven that a grid where all cells are bivalues cannot have a single solution.

Thanks Nick.

I can't provide a general proof. However, it is not difficult to conceive that all grids consisting of 4 unsolved bivalue cells cannot exist. Consider 3 cases as follows:

Code: Select all

Case 1

 .     .     .   |   .     .     .   |   .     .     .
 .     xy     .  |   .     .     .   |   .     xy     .
 .     .     .   |   .     .     .   |   .     .     .
-----------------+-------------------+-----------------
 .     .     .   |   .     .     .   |   .     .     .
 .     xy     .  |   .     .     .   |   .     xy     .
 .     .     .   |   .     .     .   |   .     .     .
-----------------+-------------------+-----------------
 .     .     .   |   .     .     .   |   .     .     .
 .     .     .   |   .     .     .   |   .     .     .
 .     .     .   |   .     .     .   |   .     .     .

This case can't happen because r2c2 is the only unsolved cell in box 1, and likewise for r5c2, r2c8 & r5c8.

Code: Select all

Case 2

 .     .     .   |   .     .     .   |   .     .     .
 .     xy     .  |   .     .     .   |   .     xy     .
 .     .     xy  |   .     .     .   |   .     xy     .
-----------------+-------------------+-----------------
 .     .     .   |   .     .     .   |   .     .     .
 .     .     .   |   .     .     .   |   .     .     .
 .     .     .   |   .     .     .   |   .     .     .
-----------------+-------------------+-----------------
 .     .     .   |   .     .     .   |   .     .     .
 .     .     .   |   .     .     .   |   .     .     .
 .     .     .   |   .     .     .   |   .     .     .

This case can't happen because r2c2 is the only unsolved cell in col 2, and likewise for r3c3.

Code: Select all

Case 3

 .     .     .   |   .     .     .   |   .     .     .
 .     xy     .  |   .     .     .   |   .     xy     .
 .     xy     .  |   .     .     .   |   .     xy     .
-----------------+-------------------+-----------------
 .     .     .   |   .     .     .   |   .     .     .
 .     .     .   |   .     .     .   |   .     .     .
 .     .     .   |   .     .     .   |   .     .     .
-----------------+-------------------+-----------------
 .     .     .   |   .     .     .   |   .     .     .
 .     .     .   |   .     .     .   |   .     .     .
 .     .     .   |   .     .     .   |   .     .     .

This case implies that there is no unique solution.

I would imagine, by induction, a grid where all cells are bivalues will lead to contradictions or multiple solutions.
MJ refers these conditions as 'bivalue universal death' or BUD for short.
I incline to call it 'bivalue universal grave' or BUG for short

[Nick70]

This case implies that there is no unique solution.

I'd love to prove it by induction, however I don't see a way to prove that if it's true for N bivalue cells then it's true for N+1 bivalue cells.

[Myth Jellies]

Jeff,

Well done! I was concentrating so hard on the trivalue cells, that I completely overlooked the fact that a single intersection cell could affect all three. Very impressive!

[Myth Jellies]

It seems apparent, that for a BUD/BUG pattern, a digit must appear as a candidate in each house either 0 or at least 2 times. Looking at it empirically, perhaps we can prove that for a BUD/BUG pattern, each digit must appear EXACTLY twice within a house, or not at all.

That might give us the constraints we need for a proof.

In addition, it might provide some parity type observations/operations which could help unlock tso's example.

[tso]

Here's example with two tri-value cells and the rest bi-value.

The starting position:

Code: Select all

 . 1 3 | . . 9 | . . .
 8 . . | 1 . 5 | . . .
 . . 9 | . 8 . | 5 . .
 ------+-------+------
 1 . 5 | . . 8 | . 7 .
 . 9 . | . . . | . 4 .
 . 7 . | 9 . . | 1 . 6
 ------+-------+------
 . . 6 | . 1 . | 3 . .
 . . . | 2 . 7 | . . 8
 . . . | 8 . . | 9 1 .

After other methods short of xy-forcing chains:

Code: Select all

 5 1 3 | . . 9 | . 8 .
 8 6 4 | 1 . 5 | 7 9 .
 7 2 9 | 4 8 . | 5 . 1
 ------+-------+------
 1 . 5 | . . 8 | 2 7 9
 6 9 2 | . . 1 | 8 4 .
 . 7 8 | 9 . 2 | 1 . 6
 ------+-------+------
 9 8 6 | 5 1 4 | 3 2 7
 . . 1 | 2 9 7 | . . 8
 2 . 7 | 8 . . | 9 1 .

Code: Select all

 5    1    3    | 67   267  9    | 46   8    24
 8    6    4    | 1    23   5    | 7    9    23
 7    2    9    | 4    8    36   | 5    36   1
 ---------------+----------------+-------------
 1    34   5    | 36   46   8    | 2    7    9
 6    9    2    | 37   57   1    | 8    4    35
 34   7    8    | 9    45   2    | 1    35   6
 ---------------+----------------+-------------
 9    8    6    | 5    1    4    | 3    2    7
 34   345  1    | 2    9    7    | 46   56   8
 2    45   7    | 8    36   36   | 9    1    45

This can be solved by a 5 cell forcing chain, but I tried to apply the "n digits sharing n cells" principle, though I've been advised that it won't work if there is more than a single cell with more than two candidates -- this position has two of them.


Looking first at r8c2:

Column 2 -- forming a [34] pair implies r9c2=5.
Column 2 -- forming a [45] pair implies r4c2=3.
Row 8 -- forming a [34] pair implies r8c7=6.
Row 8 -- forming a [456] triple implies r8c1=3.
Box 7 -- forming a [34] pair implies r9c2=5.
Box 7 -- forming a [45] pair implies r8c1=3.

Now looking at r1c5:

Column 5 -- forming a [236] triple implies r5c5=7
Column 5 -- forming a [4567] quad implies r9c5=3
Row 1 -- forming a [67] pair implies r1c7=4
Row 1 -- forming a [246] triple implies r1c4=7
Box 2 -- forming a [67] pair implies r3c6=3
Box 2 -- forming a [236] triple implies r1c4=7


All of these implications turn out to be true and reduce the puzzle to singles.

Is this just a coincidence? Am I just as likely to find a puzzles with two tri-value cells left in which the implications of this type will be false? Or is there a reason why it *does* work in this case -- the position and/or the relationship of the two tri-value cells. Maybe the fact that the two tri-value cells have no candidates in common?

[Nick70]

First of all let me tell how I would proceed to apply the BUD principle.

r1c5:
the remaining cells in row 1 form a open xy-chain 24-46-67
the remaining cells in column 5 form a open xy-chain 23-36-64-45-57
the remaining cells in box 2 form a open xy-chain 23-36-67

to close all those chains, r1c5 would have to be 27, which can be excluded leaving r1c5=6.

r8c2:
the remaining cells in row 8 form a open xy-chain 34-46-65
the remaining cells in column 2 form a open xy-chain 34-45
the remaining cells in box 7 form a open xy-chain 34-45

to close all those chains, r8c2 would have to be 35, which can be excluded leaving r8c2=4.


Now, why does this work? I have no idea. What I can tell is that all the bivalue cells are again all interconnected, so fixing any one of them either completes the puzzle or brings to a contradiction.

[Jeff]

All of these implications turn out to be true and reduce the puzzle to singles.
Is this just a coincidence? Am I just as likely to find a puzzles with two tri-value cells left in which the implications of this type will be false? Or is there a reason why it *does* work in this case -- the position and/or the relationship of the two tri-value cells. Maybe the fact that the two tri-value cells have no candidates in common?

Consider the link-cells between the 2 trivalue cells, namely r4c2=34, r4c5=46, r1c7=46 and r8c7=46. I believe the principle works in this 2-trivalue case because these link-cells remain unchanged when the trivalue cells are reduced to a BUG. In other words, this 2-trivalue case is acting as if it was 2 individual trivalue cases.

Code: Select all

Original grid with link-cells highlighted:

 5    1    3    | 67   267  9    |<46>  8    24
 8    6    4    | 1    23   5    | 7    9    23
 7    2    9    | 4    8    36   | 5    36   1
 ---------------+----------------+-------------
 1   <34>  5    | 36  <46>  8    | 2    7    9
 6    9    2    | 37   57   1    | 8    4    35
 34   7    8    | 9    45   2    | 1    35   6
 ---------------+----------------+-------------
 9    8    6    | 5    1    4    | 3    2    7
 34   345  1    | 2    9    7    |<46>  56   8
 2    45   7    | 8    36   36   | 9    1    45

Code: Select all

Grid reduced to a BUG:

 5    1    3    | 67  [27]  9    |<46>  8    24
 8    6    4    | 1    23   5    | 7    9    23
 7    2    9    | 4    8    36   | 5    36   1
 ---------------+----------------+-------------
 1   <34>  5    | 36  <46>  8    | 2    7    9
 6    9    2    | 37   57   1    | 8    4    35
 34   7    8    | 9    45   2    | 1    35   6
 ---------------+----------------+-------------
 9    8    6    | 5    1    4    | 3    2    7
 34  [35]  1    | 2    9    7    |<46>  56   8
 2    45   7    | 8    36   36   | 9    1    45

In order to avoid the BUG, r1c5=6 and r8c2=4.

I think the key to solve a grid using this principle for whatever number of trivalue cells is to avoid BUG. So, the first step is to reduce the grid into a BUG, then the true candidates will stand out. A BUG may be obtained through reduction of a bivalue link-cell (refer example below) or through reduction of all trivalue cells to bivalues (refer example above).

Code: Select all

BUG reduction through reduction of a bivalue link-cell:

 1    7    4    | 8    3    2    | 5    9    6   
 5    9    3    | 4    6    1    | 2    7    8   
 6    8    2    | 9    5    7    | 34   34   1   
----------------+----------------+----------------
 28   6    7    | 5    12   48   | 9    123  34   
 248  1    9    | 7    48   3    | 6   <24>  5   
 24   3    5    | 12   9    6    | 8    124  7   
----------------+----------------+----------------
 3    24   1    | 6    28   48   | 7    5    9   
 9    24   8    | 12   7    5    | 13   6    34   
 7    5    6    | 3    14   9    | 14   8    2

Since r5c8=2 will promote a BUG. In order to avoid the BUG, r5c8=4.

In summary, the 'n digits sharing n cells' principle works when a grid can be reduced to a bivalue universal grave (BUG).

[Nick70]

I believe the principle works in this 2-trivalue case because these link-cells remain unchanged when the trivalue cells are reduced to a BUG. In other words, this 2-trivalue case is acting as if it was 2 individual trivalue cases.

I'm not sure about this argument, I'd rather see it in the same way as the other example (the one with three trivalue cells):

If r4c2 = 4, then r8c2 reduces to 35, and r1c5 reduces (through r4c5) to 27, leaving us in a BUD situation. Therefore r4c2 must be 3.

[Jeff]

If r4c2 = 4, then r8c2 reduces to 35, and r1c5 reduces (through r4c5) to 27, leaving us in a BUD situation. Therefore r4c2 must be 3.

Could you post the grid with such BUD situation. I suspect that, by putting r4c2=4, it won't be much of a BUD situation left.

[Nick70]

Could you post the grid with such BUD situation. I suspect that, by putting r4c2=4, it won't be much of a BUD situation left.

That's actually right, all the bivalue cells are strongly linked so setting any of them will complete the puzzle or lead to a contradiction. An important question at this point is: does it matter? Or is the observation about the trivalue cells still valid?

[Jeff]

I would try to identify a BUG if it doesn't take more than just a few steps looking ahead.

[Myth Jellies]

How is this for a consolidation of this thread so far, with a few extras tossed in?

Definition: A Bivalue Universal Grave (BUG) is any grid in where all the unsolved cells have two candidates, and if a candidate exists in a row, column, or box, it shows up exactly twice.

Definition: A Poly-valued Cell for the purposes of this thread is a cell having more than two candidates.

Definition: A Local Bivalue Move (LBM or localized BUG move) is the selection of two candidates from a poly-valued cell that cause the row, column, and box containing that cell to have all bivalue cells and to have all candidates in that row, column, or box show up exactly twice.

When you have only one poly-valued cell, an LBM should lead to a BUG.

BUG Avoidance Postulate 1: BUG grids can have either zero or more than one solution, and so are incompatible with a unique solution puzzle. Therefore, any move which turns a grid into a BUG must be invalid. Hence the puzzle solution must come from the remaining non-BUG choice(s).

BUG Avoidance Postulate 2: Any move which forces all poly-valued cells into an LBM is an invalid move.

Possible corollary 1: If you can form a BUG grid from your set of candidates, then the solution to the puzzle must come from the set of non-BUG candidates. If this is true, then you should be able to apply it anytime in the solving process; not just at the end game.

Possible corollary 2: If you have multiple poly-valued cells, and the cells are sufficiently isolated/synchronized, then any LBM for those cells would be invalid. At issue here is what is the definition of sufficiently isolated/synchronized.