The New Sudoku Players' Forum

by **Jeff** » Sat Nov 26, 2005 6:30 am

Good work, MJ. May I dip in with a little thought.

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.

Notion: BUG grids can have either zero or more than one solution, and so are incompatible with a unique solution puzzle. Hence the puzzle solution must come from the remaining non-BUG choice(s).

BUG Avoidance Postulate 1: When a grid has only one poly-valued cell left, any LBM in the row, column or box must be invalid.

BUG Avoidance Postulate 2: When a grid has two or more poly-valued cells left where individual LBMs do not reduce any cell to single, all of these LBMs must be invalid.
(This may be the mode of isolation required for this principle to work in Tso's example)

BUG Avoidance Postulate 3: Any placement of a candidate which forces all poly-valued cells into a BUG 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.
(not sure when any cells are reduced to singles during the process)

Possible corollary 2: If you have multiple poly-valued cells, and the cells are sufficiently isolated/synchronized such that an individual LBM can be made without affecting others, the LBM would be invalid.
(the definition of sufficiently isolated/synchronized could be the independence of each individual LBM, or single reduction; a difference interpretation of the same outcome as decribed in BUG Avoidance Postulate 2.)

by **Myth Jellies** » Sat Nov 26, 2005 7:18 am

Looks like we are pretty much saying the same things. I think you've identified a "no singles creation" rule of isolation for possible corollary 2 and promoted it to an additional postulate which is exactly the kind of rule mod I was hoping for.

I don't think possible corollary 1 can make use of your parenthetical singles creation check. Either a BUG pattern exists in the current set of candidates or it doesn't. For example, you've already shown that a BUG pattern exists in the candidates for tso's two poly-valued cell example, and both non-BUG selections were part of the puzzle solution. On the other hand, you can't get a BUG pattern out of the candidates for either the grid which leads to the two-cell example or for tso's three poly-valued cell example. (You're not allowed to solve for any unsolved cells when searching for your BUG grid amongst the unsolved candidates.) It might be interesting to see if a BUG grid can be successfully identified and excluded from an initial sudoku grid.

by **Jeff** » Sat Nov 26, 2005 7:31 am

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

I still don't have a proof on this, but just a thought.

When all cells in a grid becomes bivalue, they must be all naked subsets. if one cell can be reduced to a single, then all other bivalue cells will fall as domino and we will have a solution. A BUG is where all bivalue cells are interlocked with no single to start any deduction with. Forcing values in the cells is likely to produce multiple solutions. Therefore, it is invalid and the situation is equivalent to the uniqueness rectangle.

by **Jeff** » Sat Nov 26, 2005 7:37 am

Myth Jellies wrote:It might be interesting to see if a BUG grid can be successfully identified and excluded from an initial sudoku grid.

If this is the case, then the method is very powerful. I have started looking.

by **Nick67** » Sat Nov 26, 2005 1:58 pm

Code: Select all: 1 24 3 | 49 5 6 | 7 8 29 6 24 7 | 1 49 8 | 25 3 259 8 5 9 | 7 3 2 | 6 4 1 ----------------+----------------+---------------- 59 7 8 | 29 6 4 | 25 1 3 2 3 6 | 8 1 5 | 4 9 7 59 1 4 | 3 29 7 | 8 6 25 ----------------+----------------+---------------- 3 8 5 | 24 24 9 | 1 7 6 7 6 1 | 5 8 3 | 9 2 4 4 9 2 | 6 7 1 | 3 5 8

After staring at this puzzle for some time, I finally
realized that there is an elaborate uniqueness pattern here.

Assume that 2 is not the final value of r2c9, and so
the candidates for r2c9 are 5 and 9 only.
Then consider any solution to the puzzle. We could take that
solution and swap the 2 and 4 in box 1, the 4 and 9 in box 2,
the 5 and 9 in box 4, the 2 and 9 in box 5, the 2 and 5 in box 6,
and the 2 and 4 in box 8. Finally, we could do a 3-way swap with the
2, 5, and 9 in box 3. The result would be a second solution, since,
for each time we swapped a number out of a row or column, we swapped
the same number back into that row or column.

This contradicts the fact that the puzzle has a unique solution.
Therefore, the original assumption must be false, and 2 must
be the final value of r2c9.

by **Jeff** » Sat Nov 26, 2005 2:13 pm

Nick 67, From here, could you structure a proof to show that for any grids, if all unsolved cells are bivalues (ie. the grid has a BUG pattern), then the grid will have no unique solution.

by **Nick67** » Sat Nov 26, 2005 3:20 pm

Jeff,

I think so! You all have laid all the groundwork ... now
if I can just add the swapping idea ... I think we
will have the proof.

by **Myth Jellies** » Sat Nov 26, 2005 7:45 pm

Jeff wrote:...From here, could you structure a proof to show that for any grids, if all unsolved cells are bivalues (ie. the grid has a BUG pattern), then the grid will have no unique solution.

I'm pretty sure you have to add the zero-or-two candidate restraint as well. Otherwise, you could take any solved puzzle, "unsolve" any two cells sharing a house, note the bivalue candidate cells and declare, "Oops, no unique solution!"

by **Nick67** » Sat Nov 26, 2005 7:53 pm

Proof: No Bivalue Universal Grave (BUG) has a unique solution.

Code: Select all: Consider any BUG. There are 2 cases to consider: 1) No solution exists. 2) A solution does exist. We can make a new grid by modifying the solution. (So this proof refers to 3 grids: the BUG, the solution, and the "new grid.") Start with box 1 of the solution. There, each candidate in box 1 of the BUG appears in 1 of the 2 cells which it occupies in the BUG. Move each such number to the other cell. Consider the cell being vacated by moving value X. In the BUG, there are 2 candidates in that position: X and Y. Only 1 value can be moved into this cell: Y. And Y must be moved into this cell: there is nowhere else for Y to go. So there will be no "empty cells" and no cells with 2 values created by this moving. We can do the same thing for each box in the solution. After we are done moving values to create the new grid, consider any candidate X in any box in the BUG. X appears in two cells A and B. To create the new grid, we just moved X in the original solution from A to B. There are 3 possibilities for the relative positions of A and B: a) They are in the same row. By the definition of BUG (BTDOB), X also appears in the BUG in another cell C in the same column as A, and in another cell D in the same column as B. C and D must be in the same box. In the original solution, X must have appeared in D (since it appeared in A). So we moved X from D to C in that box. b) They are in the same column. BTDOB, X appears in the BUG in another cell E in the same row as A, and in another cell F in the same row as B. E and F must be in the same box. In the original solution, X must have appeared in F. So we moved X from F to E in that box. c) They are neither in the same row nor the same column. BTDOB, X appears in the BUG in another cell G in the same column as A, and in another cell H in the same column as B. G and H must be in the same box. X also appears in the BUG in another cell I in the same row as A, and in another cell J in the same row as B. I and J must be in the same box. In the original solution, X must have appeared in H and J. So we moved X from H to G, and from J to I. In all 3 of these cases, then, we compensated for moving X from A to B by moving X in other boxes. If we moved X out of a particular column inside one box, then we moved X into that column in another box. If we moved X out of a particular row inside one box, then we moved X into that row in another box. Finally, if we moved X out of a particular row and out of particular column inside one box, then we moved X into that particular row in another box, and moved X into that particular column in yet another box. The above argument is general, so it applies to each candidate in each box of the BUG. Since there are no empty cells and no cells with 2 values in the new grid, and since we compensated for every change to the original solution as described above, we can conclude that the new grid must also be a solution to the puzzle. In summary, we have shown that a BUG either has no solution, or has at least two solutions if it has any solution. We can conclude that no BUG has a unique solution.

Edits:
1. Changed this: "Without actually finding the solution,
we can consider making a new grid by modifying the solution"
to this: "We can make a new grid by modifying the solution."

by **tso** » Sun Nov 27, 2005 1:42 am

Five BUGs:
============================================================
I

Start grid:

Code: Select all: 1 . 6 | . . 7 | . . . . 4 7 | 8 . . | . . 3 2 8 . | 5 1 . | . . 9 -------+-------+------ . . . | . . 3 | . . 5 . . 2 | . . . | 9 . . 6 . . | 9 . . | . . . -------+-------+------ 4 . . | . 3 8 | . 7 2 8 . . | . . 5 | 3 9 . . . . | 6 . . | 1 . 8

After all basic tactics:

Code: Select all: 1 9 6 | 3 2 7 | 8 5 4 5 4 7 | 8 . . | 2 1 3 2 8 3 | 5 1 4 | 7 6 9 -------+-------+------ 9 1 4 | . . 3 | 6 . 5 . 5 2 | 4 . . | 9 . . 6 . 8 | 9 5 . | 4 . . -------+-------+------ 4 6 9 | 1 3 8 | 5 7 2 8 . 1 | . 4 5 | 3 9 6 . . 5 | 6 . . | 1 4 8

Code: Select all: 1 9 6 | 3 2 7 | 8 5 4 5 4 7 | 8 69 69 | 2 1 3 2 8 3 | 5 1 4 | 7 6 9 ---------------+----------------+------------- 9 1 4 | 27 78 3 | 6 28 5 37 5 2 | 4 68 16 | 9 38 17 6 37 8 | 9 5 12 | 4 23 17 ---------------+----------------+------------- 4 6 9 | 1 3 8 | 5 7 2 8 27 1 | 27 4 5 | 3 9 6 37 237 5 | 6 79 29 | 1 4 8

The easy BUG exclusion replaces a 6 cell xy-type forcing chain.

This one is interesting to me because it is solved using *only* easy, basic tactics plus BUG -- which couldn't be any easier.

============================================================
II

In this one, BUG allows the identical exclusion that would have required a bilocation chain or simple coloring.

Code: Select all: 5 . . | . . . | . . . 2 . . | 8 1 3 | 4 . . . . 9 | 6 . . | . . 7 ------+-------+------ . . 7 | . . 8 | . 2 . . 3 . | 2 . 5 | . 7 . . 8 . | 3 . . | 6 . . ------+-------+------ 3 . . | . . 9 | 7 . . . . 1 | 4 8 6 | . . 2 . . . | . . . | . . 6

============================================================
III

This one required a variety of tactics, ending with either BUG or a short bi-location chain or simple coloring:

Code: Select all: . . . | 7 . 3 | . 5 . . . . | 2 1 . | . . . 3 . 6 | . 8 . | . . . -------+-------+------ 6 . 9 | . . . | . 2 5 . . 3 | . . . | 6 . . 5 4 . | . . . | 8 . 3 -------+-------+------ . . . | . 3 . | 7 . 1 . . . | . 6 7 | . . . . 1 . | 9 . 5 | . . .

Code: Select all: . . . | 7 . 3 | . 5 6 . 5 . | 2 1 6 | 9 3 8 3 . 6 | 5 8 . | . . 7 -------+-------+------ 6 8 9 | 3 7 . | . 2 5 . 7 3 | . 5 . | 6 . 9 5 4 . | 6 . . | 8 7 3 -------+-------+------ . 6 5 | . 3 . | 7 9 1 9 3 . | 1 6 7 | 5 8 . . 1 . | 9 . 5 | 3 6 .

Code: Select all: 18 29 18 | 7 49 3 | 24 5 6 47 5 47 | 2 1 6 | 9 3 8 3 29 6 | 5 8 49 | 124 14 7 ----------------+----------------+------------- 6 8 9 | 3 7 14 | 14 2 5 12 7 3 | 48 5 28 | 6 14 9 5 4 12 | 6 29 19 | 8 7 3 ----------------+----------------+------------- 24 6 5 | 48 3 28 | 7 9 1 9 3 24 | 1 6 7 | 5 8 24 78 1 78 | 9 24 5 | 3 6 24

============================================================
IV

Code: Select all: . 7 . | . . 5 | 1 . . 2 5 . | . 4 . | . 6 . . . 4 | . . . | . 9 . ------+-------+------ 7 4 . | 6 9 . | . . . 9 . . | . 5 . | . . 7 . . . | . 8 4 | . 1 6 ------+-------+------ . 6 . | . . . | 2 . . . 3 . | . 6 . | . 8 1 . . 7 | 4 . . | . 5 .

Code: Select all: 6 7 9 | 8 . 5 | 1 . 4 2 5 3 | 1 4 9 | 7 6 8 . . 4 | . 7 6 | . 9 . -------+-------+------ 7 4 . | 6 9 . | . . . 9 . 6 | . 5 . | . 4 7 3 2 5 | 7 8 4 | 9 1 6 -------+-------+------ 4 6 . | 5 . . | 2 7 9 5 3 2 | 9 6 7 | 4 8 1 . 9 7 | 4 . . | 6 5 3

Code: Select all: 6 7 9 | 8 23 5 | 1 23 4 2 5 3 | 1 4 9 | 7 6 8 18 18 4 | 23 7 6 | 35 9 25 ----------------+----------------+------------- 7 4 18 | 6 9 13 | 358 23 25 9 18 6 | 23 5 123 | 38 4 7 3 2 5 | 7 8 4 | 9 1 6 ----------------+----------------+------------- 4 6 18 | 5 13 38 | 2 7 9 5 3 2 | 9 6 7 | 4 8 1 18 9 7 | 4 12 28 | 6 5 3

At this point, an XY-wing could be used reduce the puzzle to singles.

Just before the XY-wing are TWO tri-value cells. If both are reduced to create BUG:

Code: Select all: 6 7 9 | 8 23 5 | 1 23 4 2 5 3 | 1 4 9 | 7 6 8 18 18 4 | 23 7 6 | 35 9 25 ----------------+----------------+------------- 7 4 18 | 6 9 13 | 58 23 25 9 18 6 | 23 5 12 | 38 4 7 3 2 5 | 7 8 4 | 9 1 6 ----------------+----------------+------------- 4 6 18 | 5 13 38 | 2 7 9 5 3 2 | 9 6 7 | 4 8 1 18 9 7 | 4 12 28 | 6 5 3

Rows 4 and 5, columns 6 and 7, boxes 5 and 6 are now all bivalue trips, quads or quints and no resulting singles created.
The two *link* cells, r4c6 and r5c7 remain unchanged. I *think* this is enough to allow me to use BUG to place 3's in both tri-value cells.
(Did I get that right? Feel free to re-word or invalidate my deduction here.)

============================================================
V

Code: Select all: . . . | . . . | . 1 . . . . | 1 5 . | . . 3 . . 4 | . . . | 8 . 2 -------+-------+------ . 7 . | . . 9 | . . . . 1 . | . . . | . 7 8 . . . | 8 . . | 1 5 . -------+-------+------ . . 1 | . . 3 | . . 9 5 . . | . 2 7 | . . . . 6 7 | . 8 . | 4 . .

Solving for singles only leaves:

Code: Select all: 6 . . | 2 9 4 | 5 1 7 7 . . | 1 5 8 | 6 4 3 1 5 4 | 7 3 6 | 8 9 2 -------+-------+------ 8 7 5 | . 1 9 | 2 3 . . 1 . | 3 . 5 | 9 7 8 9 . . | 8 7 2 | 1 5 . -------+-------+------ . . 1 | 5 . 3 | 7 . 9 5 . . | . 2 7 | 3 . 1 3 6 7 | 9 8 1 | 4 2 5

Code: Select all: 6 38 38 | 2 9 4 | 5 1 7 7 29 29 | 1 5 8 | 6 4 3 1 5 4 | 7 3 6 | 8 9 2 ----------------+----------------+------------- 8 7 5 | 46 1 9 | 2 3 46 24 1 26 | 3 46 5 | 9 7 8 9 34 36 | 8 7 2 | 1 5 46 ----------------+----------------+------------- 24 248 1 | 5 46 3 | 7 68 9 5 489 89 | 46 2 7 | 3 68 1 3 6 7 | 9 8 1 | 4 2 5

At this point, an X-wing in 4s followed by either an XY-wing or BUG exclusion finishes it off.

However, as in the previous puzzle, just before the XY-wing are TWO tri-value cells, though in this case, they are in the same house.
If both are reduced to create BUG:

Code: Select all: 6 38 38 | 2 9 4 | 5 1 7 7 29 29 | 1 5 8 | 6 4 3 1 5 4 | 7 3 6 | 8 9 2 ----------------+----------------+------------- 8 7 5 | 46 1 9 | 2 3 46 24 1 26 | 3 46 5 | 9 7 8 9 34 36 | 8 7 2 | 1 5 46 ----------------+----------------+------------- 24 28 1 | 5 46 3 | 7 68 9 5 49 89 | 46 2 7 | 3 68 1 3 6 7 | 9 8 1 | 4 2 5

... then row 7 and 8, column 2 and box 7 all contain bivalue quads or quints.
There are no singles.
It *seems* as if I can I deduce that r7c2=4 and r8c2=8.
However, r7c2 should actually hold a 2.

I believe this implies that all I can really deduce is that EITHER r7c2=4 OR r8c2=8, which is true, but of very little help in a solution.

I also believe that this shows that *if* BUG can work with more than one tri-value cells, they cannot be in the same house.

by **Myth Jellies** » Sun Nov 27, 2005 2:53 am

Well that last grid definitely kills possible corollary number 1. There is a BUG grid in the possibles and one of the remainders is not used.

I assume postulate 2 is still alive since if you have two poly-valued cells in a house, you can't make a legitimate LBM?

by **Myth Jellies** » Sun Nov 27, 2005 3:12 am

Correct me if I am wrong, but the 4 or 8 choice actually means that you could adjust your grid to the following:

Code: Select all: 6 38 38 | 2 9 4 | 5 1 7 7 29 29 | 1 5 8 | 6 4 3 1 5 4 | 7 3 6 | 8 9 2 ----------------+----------------+------------- 8 7 5 | 46 1 9 | 2 3 46 24 1 26 | 3 46 5 | 9 7 8 9 34 36 | 8 7 2 | 1 5 46 ----------------+----------------+------------- 24 24 1 | 5 46 3 | 7 68 9 5 89 89 | 46 2 7 | 3 68 1 3 6 7 | 9 8 1 | 4 2 5

You can then use the newly found naked pairs in cell 7 to solve the puzzle. So perhaps the BUG reduction here wasn't totally worthless.

by **Jeff** » Sun Nov 27, 2005 8:56 am

Myth Jellies wrote:Correct me if I am wrong, but the 4 or 8 choice actually means that you could adjust your grid to the following:

I don't think you can do that. Reason being that the back substitutions involved box 7 only. If the back substitutions are performed in column 2 instead, the resultant candidate grid is different; it could exclude both correct placements in r7c2 and r8c2.

The LBM tells us that either r7c2=4 or r8c2=8, or both. The trick now is how to make use of this piece of information.

by **Myth Jellies** » Sun Nov 27, 2005 10:11 am

Jeff,

I am not sure I see your logic. Let me explain mine a little more clearly.

The BUG candidate grid implies that either r7c2 = 4, or r8c2 = 8, or both.

If r7c2 = 4, then directly, r8c2 = 89. (note that if you want to go up the column and say r8c2 = 9 here, it does not affect the outcome.)
If r8c2 = 8, then directly, r7c2 = 24.

Combined, because this is an "or" condition, we can at least say that
(r7c2 = 4 OR r8c2 = 8) =>
r7c2 = (union of 4 and 24) = 24
AND
r8c2 = (union of 89 and 8) = 89.

It may very well be that this type of ORing logic is what we are supposed to be doing whenever we have more than one poly-valued cell and a BUG in the candidates. It works for the others (of course their answers were synchronized so that one implied the other, i.e. both were true.)

by **Nick70** » Sun Nov 27, 2005 10:46 am

Myth Jellies wrote:It may very well be that this type of ORing logic is what we are supposed to be doing whenever we have more than one poly-valued cell and a BUG in the candidates. It works for the others (of course their answers were synchronized so that one implied the other, i.e. both were true.)

Excellent observation! This is definitely the path to follow, since it will reduce the trivalue cells to bivalues in every case when a deduction can be made--and therefore force the completion of the puzzle through naked subsets.

The New Sudoku Players' Forum

Is there a simpler way to solve this?