The BUG (Bivalue Universal Grave) principle

Advanced methods and approaches for solving Sudoku puzzles

Postby Jeff » Tue Dec 20, 2005 3:52 am

Nick67 wrote:I am not sure that we would be able to prove such a corollary.

Nice move. Your alternative approach is definitely a positive move that can be added to the reference library.

However, I think the proposed corollary would work too if there is only one single non-BUG candidate left in the BUG grid after the placement of a digit.

The reason being that: For any BUG grid that has only one non-BUG candidate, a unique solution can be obtained by placing the remaining non-BUG candidate in the poly-valued cell. It follows that any move that can create a BUG grid with one single non-BUG candidate is a valid move too.

I am not too sure for BUG grid with 2 or more non-BUG candidates left after the single digit placement though.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Tue Dec 20, 2005 5:45 am

Nick67 wrote:By the BUG principle, at least one of the "extra candidates" must be the correct final value for the related cell.
This implies that r2c6=8, as shown below:

r1c1=5 => r1c3=4 => r1c4=6 => r2c6=8
r2c5=6 => r2c6=8
r6c6=7 => r7c6=6 => r2c6=8
r7c5=7 => r7c6=6 => r2c6=8
r7c6=6 => r2c6=8

After placing the 8 in r2c6, the rest of my proposed
solution in my original post is OK.

Good dig, your persistence has paid off. However, after obtaining the BUG grid, I thought the objective was to eliminate a candidate in a BUG cell. If that's not a requirement of the BUG principle, there is at least a certain "elegance" in doing so. For example ...

r1c1=5 => r1c3=4 => r1c4=6 => r2c6=8 => r6c6<>8
r2c5=6 => r2c6=8 => r6c6<>8
r7c5=7 => r7c6=6 => r2c6=8 => r6c6<>8
r7c6=6 => r2c6=8 => r6c6<>8

... eliminates candidate 8 in r6c6, and then your deduction of r2c6=8 immediately follows.

If you think this is a nitpicking distinction, I apologize in advance for bringing it up.:)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Nick67 » Tue Dec 20, 2005 10:03 am

ronk, I definitely don't mind you bringing up the point.

But I don't quite see why it might be preferable to remove
a candidate from one of the cells containing extra candidates,
over removing a candidate from one of the bivalue cells.

Maybe I have been influenced by previous examples.
For example, please consider this BUG (from a puzzle in another thread):

Code: Select all
 *--------------------------------------------------*
 | 3    2    56   | 8    7    4    | 1    56   9    |
 | 68   9    4    | 3    1    56   | 2    7    58+6 |
 | 1    7    58+6 | 2    56   9    | 68   3    4    |
 |----------------+----------------+----------------|
 | 68   4    7    | 59   89   1    | 56   2    3    |
 | 9    68   2    | 4    56   3    | 58+6 1    7    |
 | 5    1    3    | 7    2    68   | 4    9    68   |
 |----------------+----------------+----------------|
 | 4    3    18   | 19   89   2    | 7    56   56   |
 | 7    68   16   | 15   3    58   | 9    4    2    |
 | 2    5    9    | 6    4    7    | 3    8    1    |
 *--------------------------------------------------*


Here it just seems natural to use the BUG to prove that r3c7 must be 8.
(And indeed, after that placement, only singles remain.)
Nick67
 
Posts: 113
Joined: 24 August 2007

Postby ronk » Tue Dec 20, 2005 11:57 am

Nick67 wrote:
Code: Select all
 *--------------------------------------------------*
 | 3    2    56   | 8    7    4    | 1    56   9    |
 | 68   9    4    | 3    1    56   | 2    7    58+6 |
 | 1    7    58+6 | 2    56   9    | 68   3    4    |
 |----------------+----------------+----------------|
 | 68   4    7    | 59   89   1    | 56   2    3    |
 | 9    68   2    | 4    56   3    | 58+6 1    7    |
 | 5    1    3    | 7    2    68   | 4    9    68   |
 |----------------+----------------+----------------|
 | 4    3    18   | 19   89   2    | 7    56   56   |
 | 7    68   16   | 15   3    58   | 9    4    2    |
 | 2    5    9    | 6    4    7    | 3    8    1    |
 *--------------------------------------------------*


Here it just seems natural to use the BUG to prove that r3c7 must be 8.

Your example has a property which may relatively unique. Specifically, every non-BUG candidate implies an exclusion at every other poly-valued cell and every implication chain employs an identical placement (r3c7=8, in your example).

Nick67 wrote:But I don't quite see why it might be preferable to remove a candidate from one of the cells containing extra candidates, over removing a candidate from one of the bivalue cells.

I'm just taking Jeff's Corollary 2 very literally.
Jeff wrote:Corollary 2: Any exclusion implied by all non-BUG candidates in the grid must be valid.

But given the existence of the above property, I certainly don't have a problem with "skipping" to the placement.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Nick67 » Wed Dec 21, 2005 1:17 am

Hi ronk,

Thanks for all your careful consideration of my comments.
I think we may have reached a standoff? We seem
to have 2 different views, regarding the removal
of candidates using BUGs.

Thanks also for your excellent idea of assigning just 1 candidate in a
cell to a BUG. Without that idea, I could not
have come up with a correction to my original mistake
that started our discussion. The key to the correction was
splitting up a bivalue cell, so that 1 candidate was in the BUG,
and 1 was an extra candidate. (And Jeff's comments directed
me to the correct cells, where I could use this approach.)

I'm sure I will use that idea again.
Nick67
 
Posts: 113
Joined: 24 August 2007

Postby Nick67 » Thu Dec 22, 2005 2:26 am

Hi ronk,
I think we may have reached a standoff?

I'd like to say more on the matter after all. Please let me return to your
original objection:
Good dig, your persistence has paid off. However, after obtaining the BUG grid,
I thought the objective was to eliminate a candidate in a BUG cell. If that's
not a requirement of the BUG principle, there is at least a certain "elegance"
in doing so.

(By "BUG cell" I'm pretty sure you mean one of the cells that
contains "extra candidates.")

My question is: why would there be such a restriction? If I can reason
deductively (using the BUG principle) for the removal of a particular
candidate, then I claim that is a valid and elegant move, no matter
where that candidate lies.

Earlier, I wrote this a little differently:
But I don't quite see why it might be preferable to remove a candidate from one
of the cells containing extra candidates, over removing a candidate from one of
the bivalue cells.

And you responded:
I'm just taking Jeff's Corollary 2 very literally.
Jeff wrote:Corollary 2: Any exclusion implied by all non-BUG candidates in the grid must
be valid.


But this corollary does not seem to indicate the preference described in my
quote above. I interpret "any exclusion" to mean the removal of any
candidate, anywhere in the grid.

In summary, I claim that the following argument from my earlier post is
not only correct (I think we agree on that already), but also
has good style:
Code: Select all
 *--------------------------------------------------*
 | 69+5  8   45   | 46   1    59   | 2    3    7    |
 | 7    46   2    | 3    48+6 68   | 5    1    9    |
 | 59   1    3    | 57   79   2    | 6    8    4    |
 |----------------+----------------+----------------|
 | 1    2    7    | 45   34   35   | 9    6    8    |
 | 48   5    6    | 9    78   1    | 47   2    3    |
 | 48   3    9    | 67   2    68+7 | 47   5    1    |
 |----------------+----------------+----------------|
 | 2    9    1    | 8    6+7  7+6  | 3    4    5    |
 | 3    7    8    | 2    5    4    | 1    9    6    |
 | 56   46   45   | 1    39   39   | 8    7    2    |
 *--------------------------------------------------*

By the BUG principle, at least one of the "extra candidates"
must be the correct final value for the related cell.
This implies that r2c6=8, as shown below:

r1c1=5 => r1c3=4 => r1c4=6 => r2c6=8
r2c5=6 => r2c6=8
r6c6=7 => r7c6=6 => r2c6=8
r7c5=7 => r7c6=6 => r2c6=8
r7c6=6 => r2c6=8
Nick67
 
Posts: 113
Joined: 24 August 2007

Postby ronk » Thu Dec 22, 2005 3:10 am

Nick67 wrote:
ronk wrote:I thought the objective was to eliminate a candidate in a [edit: cell containing extra candidates].
Jeff wrote:Corollary 2: Any exclusion implied by all non-BUG candidates in the grid must be valid.

I interpret "any exclusion" to mean the removal of any candidate, anywhere in the grid.

After reconsideration, I have to agree. Corollary 2 doesn't restrict the location whatsoever.

Nick67 wrote:By the BUG principle, at least one of the "extra candidates" must be the correct final value for the related cell. This implies that r2c6=8, as shown below:

r1c1=5 => r1c3=4 => r1c4=6 => r2c6=8
r2c5=6 => r2c6=8
r6c6=7 => r7c6=6 => r2c6=8
r7c5=7 => r7c6=6 => r2c6=8
r7c6=6 => r2c6=8

But if r2c6 were a poly-valued cell, the [edit: implication chains] would necessarily read ...
r1c1=5 => r1c3=4 => r1c4=6 => r2c6<>6
r2c5=6 => r2c6<>6
r6c6=7 => r7c6=6 => r2c6<>6
r7c5=7 => r7c6=6 => r2c6<>6
r7c6=6 => r2c6<>6
... and I personally prefer maintaining that style for an elimination from a bivalued cell. [edit: all implications above erroneously ended "r2c6<>8"]

However, that was not my original "objection". That objection ... that your elimination was from a poly-valued cell ... is hereby withdrawn.

I apologize for wasting your time, Ron
Last edited by ronk on Thu Dec 22, 2005 12:08 am, edited 2 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Nick67 » Thu Dec 22, 2005 3:39 am

Thanks Ron. I'm glad we agree. Very good of you to reply so quickly.
And I will definitely consider your comments regarding implication chains.
Nick67
 
Posts: 113
Joined: 24 August 2007

Postby Jeff » Mon Dec 26, 2005 8:36 am

Jeff wrote:For any BUG grid that has only one non-BUG candidate, a unique solution can be obtained by placing this non-BUG candidate in the poly-valued cell. It follows that any move that can force an 'all-but-one BUG' (ie. a BUG grid with all-but-one non-BUG candidate) is a valid move too.

Here is a good example posted by TopRank with the following BUG grid. Some back substitutions should eliminate a candidate from here.

Code: Select all
 *-----------------------------------------------------------*
 | 4     18    7     | 58    6     15    | 3     2     9     |
 | 6     28    9     | 78+2  37+28 23    | 4     5     1     |
 | 5     12    3     | 4     12    9     | 6     8     7     |
 |-------------------+-------------------+-------------------|
 | 7     9     5     | 6     13    13    | 2     4     8     |
 | 8     4     6     | 57+2  27    25    | 9     1     3     |
 | 1     3     2     | 9     4     8     | 5     7     6     |
 |-------------------+-------------------+-------------------|
 | 9     6     4     | 1     5     7     | 8     3     2     |
 | 3     5     1     | 2+8   8+2   6     | 7     9     4     |
 | 2     7     8     | 3     9     4     | 1     6     5     |
 *-----------------------------------------------------------*

Alternatively, a placement of 8 in r8c5 cascades the grid into an 'all-but-one BUG'. Therefore this placement is a valid move.

Code: Select all
  *--------------------------------------------------*
 | 4    18   7    | 58   6    15   | 3    2    9    |
 | 6    28   9    | 78   37+2 23   | 4    5    1    |
 | 5    12   3    | 4    12   9    | 6    8    7    |
 |----------------+----------------+----------------|
 | 7    9    5    | 6    13   13   | 2    4    8    |
 | 8    4    6    | 57   27   25   | 9    1    3    |
 | 1    3    2    | 9    4    8    | 5    7    6    |
 |----------------+----------------+----------------|
 | 9    6    4    | 1    5    7    | 8    3    2    |
 | 3    5    1    | 2    8    6    | 7    9    4    |
 | 2    7    8    | 3    9    4    | 1    6    5    |
 *--------------------------------------------------*

According to Corollary 1, r2c5=2 and the rest is trivial.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Thu Dec 29, 2005 5:00 am

I am about to add the following statements to the first post of this thread. Please advise if there is any thing else that I should know.

Definition: An all-but-one BUG is a BUG grid with all-but-one non-BUG candidate.

Corollary 4: Any placement of a candidate which forces an 'all-but-one BUG' is a valid move. (Example)
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Nick67 » Thu Dec 29, 2005 9:14 am

Hi Jeff,

Here's a possible alternative to the definition:

Definition: A BUG+1 is a BUG grid plus exactly one non-BUG candidate.

I like BUG+1 because it is so short and because the + sign
ties in with our use of the + sign to show non-BUG candidates in grids.

Regarding the corollary, earlier in the thread you wrote this:

Jeff wrote:The reason being that: For any BUG grid that has only one non-BUG
candidate, a unique solution can be obtained by placing the remaining
non-BUG candidate in the poly-valued cell. It follows that any move that
can create a BUG grid with one single non-BUG candidate is a valid move too.


I don't quite follow this argument. Of course I agree with the first sentence.
After that I am unsure.

On the other hand, I realize you have used the corollary to solve some puzzles.

My vote would be to call this corollary a conjecture for now. However,
if you disagree, that's OK, please feel free to proceed.
Nick67
 
Posts: 113
Joined: 24 August 2007

Postby Jeff » Thu Dec 29, 2005 10:20 am

Thanks Nick for your input. First post updated. Corollary 4 is on probation.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby MadOverlord » Sat Dec 31, 2005 7:59 pm

I have some quick theoretical questions, to help me properly document BUG patterns.

* Can one automatically say that any puzzle with only 1 poly-valued square (the rest 2-valued) can be BUG-reduced?

My thinking is no, but I wanted to make sure.

* Can you do the BUG reduction if the poly-valued square has 4 or more possibilities?

My thinking is yes.
MadOverlord
 
Posts: 81
Joined: 10 June 2005

Postby Jeff » Sat Dec 31, 2005 8:20 pm

Hi MadOverlord, I am not sure I understand your questions correctly. However, here are my answers.

MadOverlord wrote:1) Are all puzzles with all unsolved squares having 2 possibilities automatically BUGs?

This condition won't happen for a puzzle with unique soloution.

MadOverlord wrote:2) Can one automatically say that any puzzle with only 1 poly-valued square (the rest 2-valued) can be BUG-reduced?

It can be BUG+1 reduced.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby MadOverlord » Sat Dec 31, 2005 9:25 pm

Jeff wrote:Hi MadOverlord, I am not sure I understand your questions correctly. However, here are my answers.

MadOverlord wrote:1) Are all puzzles with all unsolved squares having 2 possibilities automatically BUGs?

This condition won't happen for a puzzle with unique soloution.



The question I am asking, more specifically, is, do all valid puzzles that have 1 poly-value square and the rest bivalue contain BUGs, thus enabling simple progress,

or

Do you also have to do the each possibility appearing twice in each row-column-block test in order to determine BUGdom?

MadOverlord wrote:2) Can one automatically say that any puzzle with only 1 poly-valued square (the rest 2-valued) can be BUG-reduced?

It can be BUG+1 reduced.


Define what you mean by BUG+1 reduced; do you mean you can just remove the possibilities that appear only once in the other squares of the poly-value square's row, column or block from the poly-value square (which you can do if you do the full BUGhood test).

Just trying to distill my explanation down to the minimum needed.
MadOverlord
 
Posts: 81
Joined: 10 June 2005

PreviousNext

Return to Advanced solving techniques