## Is there a simpler way to solve this?

Advanced methods and approaches for solving Sudoku puzzles
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.)
Jeff

Posts: 708
Joined: 01 August 2005

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.
Myth Jellies

Posts: 593
Joined: 19 September 2005

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

Posts: 708
Joined: 01 August 2005

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

Posts: 708
Joined: 01 August 2005

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

Posts: 113
Joined: 24 August 2007

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

Posts: 708
Joined: 01 August 2005

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

Posts: 113
Joined: 24 August 2007

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!"
Myth Jellies

Posts: 593
Joined: 19 September 2005

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 leasttwo 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."
Nick67

Posts: 113
Joined: 24 August 2007

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

Posts: 798
Joined: 22 June 2005

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?
Myth Jellies

Posts: 593
Joined: 19 September 2005

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.
Myth Jellies

Posts: 593
Joined: 19 September 2005

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

Posts: 708
Joined: 01 August 2005

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

Posts: 593
Joined: 19 September 2005

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

Posts: 156
Joined: 16 June 2005

PreviousNext