The BUG (Bivalue Universal Grave) principle

Advanced methods and approaches for solving Sudoku puzzles

Postby Carcul » Sun Jan 08, 2006 4:16 pm

Hi Ronk.

Ronk wrote:BTW, are you suggesting an elimination using the BUG principle cannot be made?


Of course not. I was just showing an alternative solution to this grid using the AUR. I didn´t try to apply the BUG principle, but I think there are to many polivalued cells. So, I found more easy to use the AUR, and more interesting, because I am noting that most of the puzzles where one can find an AUR can be easily (immediatily) solved using this type of logic.

BTW, (and this is just a personal opinion) I think you should not stick only to what you are good at. My way of thinking is precisely the opposite. But you (or someone else) please feel free to disagree.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby Jeff » Sun Jan 08, 2006 5:24 pm

ronk wrote:................Which translates to implication chains ( Jeff said I should stick to what I'm good at.:) ):

r4c9=1 => r4c7<>1 => r1c8=9
r4c9<>1 => r4c9=4 => r4c8<>4 => r4c8=8 => r1c8<>8
r4c9<>1 => r8c9=1 => r8c7<>1 => r8c7=6 => r5c7<>6 => r5c7=3 => r3c7<>3 => r3c7=4 => r1c8<>4

Hi Ronk, The translation is spot on. If you can translate a nice loop into implication streams, then you should have no problem in writing the correct nice loop notations. Well done!:D
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Sun Jan 08, 2006 5:28 pm

Neunmalneun wrote:Based on the uniqueness rule we know that r5c8=6 or one of the cells r9c8/r9c9=4. The combination of the BUG principle with the uniqueness rule seems to give a valid hint to r9c8=4 (which solves the puzzle easily)

Hi Neunmalneun, Welcome to the forum. I can understand the bit with the uniqueness rule. Could you explain how the BUG principle helps to conclude that r9c8=4?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Mon Jan 09, 2006 4:05 pm

Jeff wrote:
Neunmalneun wrote:Based on the uniqueness rule we know that r5c8=6 or one of the cells r9c8/r9c9=4. The combination of the BUG principle with the uniqueness rule seems to give a valid hint to r9c8=4 (which solves the puzzle easily)

I can understand the bit with the uniqueness rule. Could you explain how the BUG principle helps to conclude that r9c8=4?

Hi Jeff, since Neunmalneun hasn't yet responded, let me take a crack at it.

There are nine non-BUG candidates, at least one of which must be TRUE to prevent a BUG grid. Three of them are r5c8=3, r9c8=4, and r9c9=3.
Code: Select all
  7    49     6  |  5     1     3  | 48    89+4   2 
 14    13+49  2  |  8     6    49  |  7     5    39+4 
  5    39+4   8  |  7    49     2  | 34     1     6 
 ----------------+-----------------+-----------------
  3     6     7  |  9     2     5  | 18+4  48    14 
  9     2     5  |  4     8     1  | 36    67+3  37 
 48    48     1  |  6     3     7  |  9     2     5 
 ----------------+-----------------+-----------------
  6     7    39  |  1     5    49  |  2    34     8 
  2     5     4  |  3     7     8  | 16    69    19 
 18    18    39  |  2    49     6  |  5    37+4  47+3

Coincidentally, these same three cells are part of an almost unique rectangle for which we have the AUR grid ...
Code: Select all
  7    49     6  |  5     1     3  | 48    48+9   2 
 14  1349     2  |  8     6    49  |  7     5   394 
  5   394     8  |  7    49     2  | 34     1     6 
 --------------------------------------------------
  3     6     7  |  9     2     5  | 48+1  48    14 
  9     2     5  |  4     8     1  | 36    37+6  37 
 48    48     1  |  6     3     7  |  9     2     5 
 --------------------------------------------------
  6     7    39  |  1     5    49  |  2    34     8 
  2     5     4  |  3     7     8  | 16    69    19 
 18    18    39  |  2    49     6  |  5    37+4  37+4

Since r9c8=4 is the only common placement preventing both the BUG and the AUR grid, Neunmalneun's deduction is the placement is valid. His deduction certainly seems logically correct to me.

[edit 1 & 4: corrected three typos in the above]
[edit 2 and 3: added and amended the following clarification]

[edit 5: CORRECTION: That r9c8=4 was a correct placement was a "happy accident" ... the equivalent of a guess ... because the logic was faulty. Read on if you wish to know where the logic flaw occurred.]

In general, given that ...
  1. at least one member of set AUR must be true, and
  2. at least one member of set BUG must be true, and
  3. the intersection of sets AUR and BUG contain exactly one member
... then that single member of the intersection must be true.

For this example, specifically ...
AUR = {r5c8=6, r9c8=4, r9c9=4} (of which at least one must be true), and
BUG = {r5c8=3, r9c8=4, r9c9=3, ..., ..., } (of which at least one must be true)

The only set member common to (in the intersection of) sets AUR and BUG is r9c8=4. Therefore r9c8=4 must be true.

That set BUG also contains other unlisted members is irrelevant. The unlisted members of set BUG are for cells that are not common to set AUR, and would thus not be contained in the intersection anyway.

[edit 5: CORRECTION: r9c8=4 is indeed the only set member common to the intersection of sets AUR and BUG, but taking the intersection of AUR and BUG is only valid if the criteria were ...
AUR = {r5c8=6, r9c8=4, r9c9=4} (of which exactly one must be true), and
BUG = {r5c8=3, r9c8=4, r9c9=3, ..., ..., } (of which exactly one must be true)

But the criteria is "at least one", not "exactly one", so both the method and conclusion were invalid. Just as likely or even more likely, the correct placements might have been r5c8=6 and/or r9c9=4 to fulfill the AUR set requirement, and one or more of the unlisted placements of the BUG set.]
Last edited by ronk on Thu Jan 12, 2006 9:16 am, edited 5 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jeff » Mon Jan 09, 2006 4:50 pm

ronk wrote:There are nine non-BUG candidates, at least one of which must be TRUE to prevent a BUG grid. Three of them are r5c8=3, r9c8=4, and r9c9=4 (should be r9c9=3).

Hi Ronk, How did you conclude that r9c8=4 is one of the true non-BUG candidates?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Neunmalneun » Mon Jan 09, 2006 5:17 pm

The deduction ronk made was exactly what I had in mind (though I would not have been able to write it as elegantly since English is not my first language).

We have six non-BUG canditates in the boxes 3, 6 and 9. As carcul pointed out the canditates in r1c8 and r5c7 don't "fit" to the uniquness rule (in the 48-AUR in r1c78/r4c78). The same can be said for the non-BUG canditate (r5c8=3) in the 37-AUR (in r5c89/r9c89). Finally the non-BUG candidate in r2c9 (=4) would force the uniqueness pattern in the cell r9c9 as r2c9=4 > r9c9 > 37. So it seems strongly likely (if not logically compelling) that r9c8=4.
Neunmalneun
 
Posts: 52
Joined: 22 December 2005

Postby Jeff » Mon Jan 09, 2006 6:20 pm

Neunmalneun wrote:So it seems strongly likely (if not logically compelling) that r9c8=4.

Hi Neunmalneun, your english is very good.:D Anyway, does this mean that you are having second thought on the deduction?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Neunmalneun » Mon Jan 09, 2006 7:03 pm

The deduction is consistent with the two AUR's in the boxes 3, 6 and 9 and with seven (out of nine) non-BUG candidates. But if I understood the BUG rule correctly only one of the non-BUG canditates MUST be right. So I am not quite sure if it is possible that one of the non-BUG candidates in box 1 could be right and all other non-BUG candidates could be false. The solution gives a clue that our guess was right, but I wonder if it is not only a (good) guess.
Neunmalneun
 
Posts: 52
Joined: 22 December 2005

Postby Carcul » Mon Jan 09, 2006 7:36 pm

Hi Neunmalneun.

Neunmalneun wrote:The deduction is consistent with the two AUR's in the boxes 3, 6 and 9


Can you explain this a little better?

Neunmalneun wrote:But if I understood the BUG rule correctly only one of the non-BUG canditates MUST be right.


I don't think this is correct. The BUG principle states that at least one of the non-BUG candidates must be correct.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby ronk » Mon Jan 09, 2006 8:01 pm

Jeff wrote:
ronk wrote:There are nine non-BUG candidates, at least one of which must be TRUE to prevent a BUG grid. Three of them are r5c8=3, r9c8=4, and r9c9=4 (should be r9c9=3).

Hi Ronk, How did you conclude that r9c8=4 is one of the true non-BUG candidates?

Truth be told, I've spent way to much time shuffling digits back and forth from one side of the '+' sign to the other ... and then having to conclude a grid is not BUG-gable.:D But this one seemed to work out.

When a grid looks like it might be BUG-gable, my general approach is to BUG-split candidates in polyvalued cells that are:
  1. the only polyvalued cell in three units (row, col, & 3x3 box),
  2. the only polyvalued cell in two units,
  3. the only polyvalued cell in one unit, and then
  4. any remaining multiple polyvalued cells in one unit. (Always hoping there are none.)
For purposes of the above, a cell that has been BUG-split is no longer counted as a polyvalued cell.

So for this BUG grid ...
Code: Select all
  7    49     6  |  5     1     3  | 48    89+4   2 
 14    13+49  2  |  8     6    49  |  7     5    39+4 
  5    39+4   8  |  7    49     2  | 34     1     6 
 ----------------+-----------------+-----------------
  3     6     7  |  9     2     5  | 18+4  48    14 
  9     2     5  |  4     8     1  | 36    67+3  37 
 48    48     1  |  6     3     7  |  9     2     5 
 ----------------+-----------------+-----------------
  6     7    39  |  1     5    49  |  2    34     8 
  2     5     4  |  3     7     8  | 16    69    19 
 18    18    39  |  2    49     6  |  5    37+4  47+3

... the sequence probably went something like ...

r4c7, r5c8, r1c8, r2c9, r9c9, r9c8, r3c2, and the quad-valued cell r2c2 last.

Highlighting each digit in your favorite editor certainly helps cut down on errors. Then, if I'm going to publish the BUG grid, I uncheck "Block Invalid Moves" in Angus Johnson's Simple Sudoku, eliminate all the non-BUG candidates, and ...
  1. highlight pairs to be sure only pairs are left, and
  2. highlight digits one digit at a time to be sure each candidate occurs exactly twice in each unit.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jeff » Tue Jan 10, 2006 2:59 am

Hi Ronk, This is excellent. I am going to link this description to the LBM definition in the first post. Thank you.:D

Jeff wrote:
ronk wrote:There are nine non-BUG candidates, at least one of which must be TRUE to prevent a BUG grid. Three of them are r5c8=3, r9c8=4, and r9c9=4 (should be r9c9=3).

Hi Ronk, How did you conclude that r9c8=4 is one of the true non-BUG candidates?

Sorry about my expression ability. But, my question was:

Knowing that at least one of the non-BUG candidates is true, how did you conclude that r9c8=4 is one of such true non-BUG candidates which enabled the puzzle under reference to be solved?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Tue Jan 10, 2006 12:18 pm

Jeff wrote:Sorry about my expression ability. But, my question was:

Knowing that at least one of the non-BUG candidates is true, how did you conclude that r9c8=4 is one of such true non-BUG candidates which enabled the puzzle under reference to be solved?

Hi Jeff, I edited my prior post to hopefully clarify the conclusion. But it was Neunmalneun's conclusion, not mine. I merely concluded he was correct.

Although my experience with BUG and AUR grids is very limited, it appears that grids that are BUG-gable are the very same grids where it makes sense to look for AURs. And since the number of non-AUR candidates would often be much smaller than the number of non-BUG candidates ... combining the two techniques seems sensible too ... especially for the solver inclined to use the BUG principle.

Jeff wrote:This is excellent. I am going to link this description to the LBM definition in the first post. Thank you.:D

The flowers are appreciated.:D You're welcome.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jeff » Tue Jan 10, 2006 1:14 pm

ronk wrote:In general, given that ...
  1. at least one member of set AUR must be true, and
  2. at least one member of set BUG must be true, and
  3. the intersection of sets AUR and BUG contain exactly one member
... then that single member of the intersection must be true.

For this example, specifically ...
AUR = {r5c8=6, r9c8=4, r9c9=4} (of which at least one must be true), and
BUG = {r5c8=3, r9c8=4, r9c9=3, ..., ..., } (of which at least one must be true)

The only set member common to (in the intersection of) sets AUR and BUG is r9c8=4. Therefore r9c8=4 must be true.

That set BUG also contains other unlisted members is irrelevant. The unlisted members of set BUG are for cells that are not common to set AUR, and would thus not be contained in the intersection anyway.

Hi Ronk, What if only the 'other unlisted' non-BUG candidate(s) is/are true and the rest all false.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Tue Jan 10, 2006 1:34 pm

Jeff wrote:
ronk wrote:For this example, specifically ...
AUR = {r5c8=6, r9c8=4, r9c9=4} (of which at least one must be true), and
BUG = {r5c8=3, r9c8=4, r9c9=3, ..., ..., } (of which at least one must be true)

The only set member common to (in the intersection of) sets AUR and BUG is r9c8=4. Therefore r9c8=4 must be true.

Hi Ronk, What if only the 'other unlisted' non-BUG candidate(s) is/are true and the rest all false.

Sacre bleu, that is true ... which makes the conclusion r9c8=4 a "happy accident". I hate it when that happens.:( [edit: Corrections added to the original post 1-12-06]
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby MadOverlord » Tue Jan 31, 2006 3:18 pm

One of my Susser users sent me this interesting BUG. In it, all the polyvalue squares have the same possibilities, as follows:
Code: Select all
+-------------+-------------+-------------+
| 3   4   7   | 6   1   2   | 8   5   9   |
| 9   6   8   | 5   7   3   | 1   2   4   |
| 5   12  12  | 4   9   8   | 7   3   6   |
+-------------+-------------+-------------+
| 8   9   5   | 12  3   14  | 24  6   7   |
| 124 12  6   | 7   24  9   | 5   8   3   |
| 7   3   24  | 8   5   6   | 24  9   1   |
+-------------+-------------+-------------+
| 6   8   3   | 12  24  7   | 9   14  5   |
| 124 7   124 | 9   6   5   | 3   14  8   |
| 14  5   9   | 3   8   14  | 6   7   2   |
+-------------+-------------+-------------+

and the solution is:

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


I am wondering if there is a simple rule that can be stated about such configurations. Note that the two polyvalue squares that are in a single-polyvalue group (R5C1 in R5/B4 and R8C3 in C3/B7) both solve to the extra value, 2.
MadOverlord
 
Posts: 81
Joined: 10 June 2005

PreviousNext

Return to Advanced solving techniques