The New Sudoku Players' Forum

[Jeff]

This is a continuation of the "Is there a simpler way to solve this?" thread where the BUG principle was discovered. Earlier related threads include "The 'n digits sharing n cells' principle" and "A beautiful n-digits/n-cells uniqueness example".

The following statements describes the most up-to-date findings utilising the BUG principle:

Definition:

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

A BUG-Lite is a partial BUG pattern that exhibits similar properties of a BUG where all nodes in the pattern are bivalue and if a candidate exists in a row, column, or box, it shows up exactly twice. (example)

A poly-valued cell for the purposes of this thread is a cell having more than two candidates.

A Local Bivalue Move or Localized BUG Move (LBM) is the selection of one or 2 candidates from a cell that causes each candidate in the 2-candidate selections in that row, column, or box show up exactly twice. (example, example)

A non-BUG candidate is a candidate that is excluded during a LBM from a cell. All non-BUG candidates are not part of a BUG.

A BUG+n is a BUG that has exactly n number of poly-valued cells. A BUG+1 is a BUG that has exactly one poly-valued cell left.

Theorem:

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 non-BUG candidates. (proof)

Corollary 1: If a BUG can be formed out of the list of candidates by LBMs (without solving for any candidate), then the solution to the puzzle must make use of at least one non-BUG candidate. (example, example)

Corollary 2: Any deductions implied by all non-BUG candidates in the grid must be valid. (example)

Corollary 3: Any placement of a candidate which removes all non-BUG candidates is an invalid move. (example, example)

Corollary 4: Any placement of a candidate which forces a grid into a BUG+1 is a valid move. (example)

Corollary 5: Corollaries 1, 2 and 3 can be applied to a BUG-Lite.

[Nick70]

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.

This is not "any" LBM but the LBM--which is unique.
Also I don't see why you say "LBM in the row, column or box". It's the LBM on that cell, period.

This isn't a "postulate", BTW. It's a theorem following from the BUG principle (which has been proven by Nick67).

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, at least one of these LBMs must be invalid.

I don't understand the requirement that LBMs do not reduce any cell to single. They never do (though we might need to prove this or change the definition).

This isn't a postulate either.

BUG Avoidance Postulate 3: Any placement of a candidate which forces all poly-valued cells into a BUG is an invalid move.

This isn't a postulate either, it's a corollary of the previous one.

Possible corollary 1: If you can form a BUG grid from your set of candidates without any cells being reduced to singles, then the solution to the puzzle must come from the set of non-BUG candidates.

I don't understand this one.

Possible corollary 2: From a set of non-BUG candidates, the grid can be completely solved or be reduced by back substitution of the corresponding non-BUG candidate into each poly-valued cell.

I don't understand this either. If you are saying that all polyvalue cells should be reduced to the non-LBM possibilities, this has already been proven wrong.

[Nick70]

Here is the first example of a BUG application with a cell containing more than 3 candidates:

Code: Select all

1    28   3     | 4    5    6     | 7    289  89   
4    5    7     | 3    89   29    | 12   6    18   
6    28   9     | 7    18   12    | 4    5    3   
----------------+-----------------+----------------
9    7    4     | 5    3    8     | 12   12   6   
5    3    6     | 19   2    19    | 8    4    7   
8    1    2     | 6    4    7     | 9    3    5   
----------------+-----------------+----------------
27   9    1     | 28   6    3     | 5    78   4   
27   6    5     | 28   19   4     | 3    1789 189 
3    4    8     | 19   7    5     | 6    19   2   

The "classic" solution is noticing the xy-wing in r2c5, r2c9, r8c5 that excludes 1 from r8c9, and this solves the puzzle.

However we can also apply the BUG principle to say that r1c8=8, r8c8=19, r8c9=8 (each one of the three forces the other two through cells r7c8 and r9c8).

[Jeff]

Possible corollary 1: If you can form a BUG grid from your set of candidates without any cells being reduced to singles, then the solution to the puzzle must come from the set of non-BUG candidates.

I don't understand this one.

Possible corollary 2: From a set of non-BUG candidates, the grid can be completely solved or be reduced by back substitution of the corresponding non-BUG candidate into each poly-valued cell.

I don't understand this either. If you are saying that all polyvalue cells should be reduced to the non-LBM possibilities, this has already been proven wrong.

Thanks Nick. Still thinking about these two. Need more time.

[Jeff]

......(each one of the three forces the other two through cells r7c8 and r9c8).

This is what I meant to say in Possible corollary 2, but my expression ability is limited. Can you help?

[Nick70]

Here is an application of the BUG principle with three quadrivalue cells:

Code: Select all

7     2     69     | 5     3     69     | 8     1     4     
89    4689  5      | 1     2     48     | 3     69    7     
1     3     48     | 69    7     48     | 5     69    2     
-------------------+--------------------+-------------------
6     1     2      | 8     4     5      | 9     7     3     
5     47    47     | 3     9     1      | 6     2     8     
3     89    89     | 7     6     2      | 1     4     5     
-------------------+--------------------+-------------------
89    6789  6789   | 4     1     3      | 2     5     69   
4     69    3      | 2     5     69     | 7     8     1     
2     5     1      | 69    8     7      | 4     3     69   

The BUG principle allows us to say that either r2c2=89 or r7c2=69 or r7c3=89. Putting those together, we can say that r2c2=489, r7c2=679 and r7c3=789. The triple in box 1 then solves the puzzle.

[Nick70]

Here is a clean application of the BUG principle with a lot of unassigned cells (30 bivalues and 1 trivalue):

Code: Select all

4     78    6      | 3     9     5      | 78    2     1     
37    9     25     | 8     1     26     | 57    36    4     
38    1     25     | 7     4     26     | 58    9     36   
-------------------+--------------------+-------------------
2     36    14     | 14    5     8      | 36    7     9     
16    78    378    | 16    2     9      | 4     5     38   
9     5     48     | 46    3     7      | 2     1     68   
-------------------+--------------------+-------------------
78    2     78     | 9     6     3      | 1     4     5     
5     4     9      | 2     8     1      | 36    36    7     
16    36    13     | 5     7     4      | 9     8     2     

[Nick70]

......(each one of the three forces the other two through cells r7c8 and r9c8).

This is what I meant to say in Possible corollary 2, but my expression ability is limited. Can you help?

We could say that any exclusion implied by all non-LBM moves in the grid must be valid, because at least one of the non-LBM moves must be true. This is the general principle used in forcing chains.

[Myth Jellies]

I think we can interpret theorem 2 in the following way:

If you can form a BUG grid out of your list of candidates (without solving for any candidate), then the solution to the puzzle must make use of at least one candidate that is not part of that BUG grid

Actually, I think this could replace both theorem 1 and 2.

[tso]

[Intro deleted to avoid repetition.]

For those who just want to use the tactic in it's basic form, here's all you need to know in layperson's English:

If your Sudoku has ONE cell with THREE candidates and all other undecided cells have TWO candidates -- you can immediately fill that three-candidate cell. Just check which candidate appears THREE TIMES in the row, column or box in which this three-candidate cell resides. That candidate is the one that goes in the three candidate cell.

For example, the following puzzle takes nothing but singles to go from the opening position ...

Code: Select all

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

... to here ...

Code: Select all

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

Code: Select all

  2    9    8    | 47   567  56   | 3    1    45   
  7    4    5    | 2    1    3    | 6    9    8   
  1    3    6    | 48   58   9    | 2    7    45   
 ----------------+----------------+----------------
  5    1    4    | 6    3    8    | 7    2    9   
  6    2    9    | 17   57   15   | 8    4    3   
  8    7    3    | 9    4    2    | 1    5    6   
 ----------------+----------------+----------------
  4    5    2    | 18   68   16   | 9    3    7   
  3    8    1    | 5    9    7    | 4    6    2   
  9    6    7    | 3    2    4    | 5    8    1   

At this point, until very recently, most of us would solved this with an xy-wing or forcing chain. Instead, simply look at the row, column or box in which the lone three candidate cell sits. In each case, the candidate 5 is the only one that appears three times -- all others appearing twice or not at all. The BUG principle allows you to place the 5 in the r1c5.

[Myth Jellies]

Another early BUG/BUD thread with an example and debate.

[Jeff]

BUG Description revised. Thanks Nick, Tso and MJ.

[Nick70]

Theorem 3 doesn't seem to be the "reverse" of the previous ones...

BTW I would call the BUG principle a theorem and the others corollaries.

[Jeff]

Theorem 3 doesn't seem to be the "reverse" of the previous ones....

Corollary 1 & 2 (was Theorem 1 & 2) - a BUG forces the placement of candidate(s).

Corollary 3 (was Theorem 3) - Placement of a candidate forces a BUG.

[Nick70]

Corollary 1 & 2 (was Theorem 1 & 2) - a BUG forces the placement of candidate(s).

A BUG doesn't force the placement of any candidate, it's to AVOID a BUG that you make certain actions--which can be either placement of a candidate or, more commonly, exclusion of others.

E.g. in corollary 1 if you have a single quadrivalue cell you'd remove the two LBM candidates leaving a bivalue. In corollary 2 you always make exclusions only.

And in corollary 3 you exclude a candidate in order to avoid a BUG.