The BUG (Bivalue Universal Grave) principle

Advanced methods and approaches for solving Sudoku puzzles

Postby MadOverlord » Sun Dec 04, 2005 2:33 pm

Jeff wrote:MadOverlord, another thing, I don't know why you have ceased using the '+' notation for the BUG grid. Its is so useful and space saving.

My only comment is that the BUG candidates should be the prefix enabling the BUG to be more easily read.


Jeff, I tried the double-grid notation because it was easier to just cut and paste stuff out of my application's log files.

I 100% agree with you that reversing the notation so that the BUG candidates are prefixed is easier to read. I started thinking that my 3rd post or so, but kept it the other way for consistency.
MadOverlord
 
Posts: 81
Joined: 10 June 2005

Postby ronk » Tue Dec 13, 2005 1:12 pm

Can this puzzle be advanced with by the BUG principle? I've taken a stab at the "ab+c" and "ab+cd" notation ... except for the quadvalue.
Code: Select all
 *-----------------------------------------------------------*
 | 3     79    79+5  | 1     2     8     | 49    45+9  6     |
 | 6     4     25    | 3     7     9     | 8     15    12    |
 | 8     1     29    | 5     6     4     | 7     39    23    |
 |-------------------+-------------------+-------------------|
 | 9     5     1     | 7     4     3     | 2     6     8     |
 | 7     3     4     | 2     8     6     | 19    19    5     |
 | 2     8     6     | 9     1     5     | 3     47    47    |
 |-------------------+-------------------+-------------------|
 | 4     27    3     | 8     5     1     | 6     27    9     |
 | 1     6     79    | 4     39    2     | 5     8     37    |
 | 5     29    8     | 6     39    7     | 14    1234  13+4  |
 *-----------------------------------------------------------*

But I got as far as I got ... because I know the answer. Can anyone give a working approach to arrive at the above?

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

Postby Jeff » Tue Dec 13, 2005 3:54 pm

ronk wrote:But I got as far as I got ... because I know the answer. Can anyone give a working approach to arrive at the above?

Hi ronk, Why did you change the grid? The BUG grid you had before was correct. This one is not a BUG.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Tue Dec 13, 2005 4:59 pm

Jeff wrote:
ronk wrote:But I got as far as I got ... because I know the answer. Can anyone give a working approach to arrive at the above?

Hi ronk, Why did you change the grid? The BUG grid you had before was correct. This one is not a BUG.

Because I don't know what I'm doing?:)

I'm under the impression that the eventual fills (pins) of the puzzle must be to to the right of the '+' in the factoring of the candidates. While that was the case for r1c8, it wasn't for r1c3 and r9c9, e.g, so I edited my original grid.

I think the original grid was ...
Code: Select all
 *-----------------------------------------------------------*
 | 3     79    57+9  | 1     2     8     | 49    45+9  6     |
 | 6     4     25    | 3     7     9     | 8     15    12    |
 | 8     1     29    | 5     6     4     | 7     39    23    |
 |-------------------+-------------------+-------------------|
 | 9     5     1     | 7     4     3     | 2     6     8     |
 | 7     3     4     | 2     8     6     | 19    19    5     |
 | 2     8     6     | 9     1     5     | 3     47    47    |
 |-------------------+-------------------+-------------------|
 | 4     27    3     | 8     5     1     | 6     27    9     |
 | 1     6     79    | 4     39    2     | 5     8     37    |
 | 5     29    8     | 6     39    7     | 14    23+14 14+3  |
 *-----------------------------------------------------------*

I get to this grid by choosing bivalues for the BUG grid such that every domain (row, col, box) has exactly two instances of each candidate ... and doing so starting with domains that have a single trivalued cell, and doing the quad-valued cell last.

So it seems maybe only *one* assignment from the right of the '+' in a trivalued cell will avoid the BUG ... but then how do I know which one? r1c8=9 is correct, but r1c3=9 is not correct.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jeff » Tue Dec 13, 2005 5:46 pm

ronk wrote:
Code: Select all
 *-----------------------------------------------------------*
 | 3     79    57+9  | 1     2     8     | 49    45+9  6     |
 | 6     4     25    | 3     7     9     | 8     15    12    |
 | 8     1     29    | 5     6     4     | 7     39    23    |
 |-------------------+-------------------+-------------------|
 | 9     5     1     | 7     4     3     | 2     6     8     |
 | 7     3     4     | 2     8     6     | 19    19    5     |
 | 2     8     6     | 9     1     5     | 3     47    47    |
 |-------------------+-------------------+-------------------|
 | 4     27    3     | 8     5     1     | 6     27    9     |
 | 1     6     79    | 4     39    2     | 5     8     37    |
 | 5     29    8     | 6     39    7     | 14    23+14 14+3  |
 *-----------------------------------------------------------*

So it seems maybe only *one* assignment from the right of the '+' in a trivalued cell will avoid the BUG ... but then how do I know which one? r1c8=9 is correct, but r1c3=9 is not correct.

This BUG grid is correct. It tells us that at least one of the non-BUG candidates is true. A short cut has yet to be fully developed for BUG grids with more than 1 poly-valued cell. However, a back substitution from here can reduce one of the poly-valued cells to a naked pair and the grid can be solved from there using basic rules.

r1c3=9 => r8c3=7 => r8c9=3 => r3c9=2 => r2c8=1 => r2c8=5 => r1c8<>5
r9c8=1 => r2c8=5 => r1c8<>5
r9c8=4 => r9c7=1 => r6c7=9 => r6c8=1 => r2c8=5 => r1c8<>5
r9c9=3 => r3c9=2 => r2c8=1 => r2c8=5 => r1c8<>5
Therefore r1c8<>5 => r1c8=49
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Tue Dec 13, 2005 6:25 pm

Jeff wrote:r1c3=9 => r8c3=7 => r8c9=3 => r3c9=2 => r2c8=1 => r2c8=5 => r1c8<>5
r9c8=1 => r2c8=5 => r1c8<>5
r9c8=4 => r9c7=1 => r6c7=9 => r6c8=1 => r2c8=5 => r1c8<>5
r9c9=3 => r3c9=2 => r2c8=1 => r2c8=5 => r1c8<>5
Therefore r1c8<>5 => r1c8=49

Very nice. However, why did you omit the trivial equation ... r1c8=9 => r1c8<>5 ... for the last non-BUG candidate?

[edit: I ask because all other equations "flow through" r2c8=5 and one might be tempted to make that assignment.]
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jeff » Tue Dec 13, 2005 7:28 pm

ronk wrote:.... why did you omit the trivial equation ... r1c8=9 => r1c8<>5 ... for the last non-BUG candidate?

[edit: I ask because all other equations "flow through" r2c8=5 and one might be tempted to make that assignment.]

The non-BUG candidate '9' must be one of the candidates in r1c8. As long as the 9 is not eliminated when inference are made from other non-BUG candidates, this trivial implication can be omitted.

In summary, the reduced set of candidates in r1c8 is the union of '9' (own non-BUG candidate) and '49' (candidates inferred by other non-BUG candidates).
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Mon Dec 19, 2005 1:13 pm

Nick67 posted this BUG grid here.
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    78+6 | 47   5    1    |
 |----------------+----------------+----------------|
 | 2    9    1    | 8    67   67   | 3    4    5    |
 | 3    7    8    | 2    5    4    | 1    9    6    |
 | 56   46   45   | 1    39   39   | 8    7    2    |
 *--------------------------------------------------*


I had independently come up an identical BUG grid except for r6c6 ...
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    67   67   | 3    4    5    |
 | 3    7    8    | 2    5    4    | 1    9    6    |
 | 56   46   45   | 1    39   39   | 8    7    2    |
 *--------------------------------------------------*

On the basis of Nick67's BUG grid having three 7s in box 5 and mine having three 6s in col 6 (which I hadn't noticed at first), neither seemed any more or less valid than the other. But it got me to wondering whether a ... or even the correct viewpoint might not be r6c6 = 8+67, as this is the only BUG grid with exactly two candidates of each value in each house.

The resulting BUG grid then ...
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    8+67 | 47   5    1    |
 |----------------+----------------+----------------|
 | 2    9    1    | 8    67   67   | 3    4    5    |
 | 3    7    8    | 2    5    4    | 1    9    6    |
 | 56   46   45   | 1    39   39   | 8    7    2    |
 *--------------------------------------------------*

... would lead directly to elimination of r6c6#8 ... without needing to follow any implication chains.

Comments anyone?
Last edited by ronk on Mon Dec 19, 2005 4:59 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Nick67 » Mon Dec 19, 2005 8:46 pm

Hi ronk,

Doh! Good catch. My BUG pattern was not a BUG after all,
for the reason you mentioned (3 7's in box 5).
I'll edit my post.

I'm afraid that your proposed BUG doesn't
quite work either, as there are 3 7's in column 5.
Last edited by Nick67 on Mon Dec 19, 2005 6:05 pm, edited 1 time in total.
Nick67
 
Posts: 113
Joined: 24 August 2007

Postby ronk » Mon Dec 19, 2005 8:54 pm

Nick67 wrote:I'm afraid that your proposed BUG doesn't
quite work either... as there are 3 6's in column 6.

After writing that I thought the deduction should be r6c6="8+67" ... I pasted in the wrong grid (now edited).

But it's still not a BUG grid either, since there are still three 7's in col 5. (If you're so inclined, I'd appreciate you editing your quote of my grid to reflect that.)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jeff » Mon Dec 19, 2005 9:29 pm

Hi, Nick67 & Ronk

The only way that this grid can be cascaded into a BUG is when r7c5=6 as follows:

Code: Select all
  *-------------------------------------------------*
 | 69+5 8    45   | 46   1    59  | 2    3    7    |
 | 7    46   2    | 3    48   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  | 47   5    1    |
 |----------------+---------------+----------------|
 | 2    9    1    | 8    6     7  | 3    4    5    |
 | 3    7    8    | 2    5    4   | 1    9    6    |
 | 56   46   45   | 1    39   39  | 8    7    2    |
 *-------------------------------------------------*

Would this imply that r7c5=6, r2c5=48, r7c6=7 and r6c6=68; ie. 4 eliminations at once? If this is the case, then we could have a Corollary 4 saying that any placement of a candidate which enables a BUG grid with non-BUG candidate(s) to be formed is a valid move.
Last edited by Jeff on Mon Dec 19, 2005 10:18 pm, edited 1 time in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Nick67 » Tue Dec 20, 2005 12:37 am

Jeff,

Jeff wrote:The only way that this grid can be cascaded into a BUG is when r7c6=6 as follows:


I'm pretty sure you meant that r7c5=6, which is a very helpful observation.

I suggest that we don't have to go quite so far as to assign a 6 to r7c5, though.
I'm not sure we can justify that yet.
Instead, please see my following post.
Nick67
 
Posts: 113
Joined: 24 August 2007

Postby Nick67 » Tue Dec 20, 2005 12:41 am

Here is the original grid:

Code: Select all
+-------------+---------------+----------+
| 569  8   45 | 456  1    59  | 2   3  7 |
| 7    46  2  | 3    468  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  | 467  2    678 | 47  5  1 |
+-------------+---------------+----------+
| 2    9   1  | 8    67   67  | 3   4  5 |
| 3    7   8  | 2    5    4   | 1   9  6 |
| 56   46  45 | 1    39   39  | 8   7  2 |
+-------------+---------------+----------+


Thanks to Jeff's and ronk's very helpful comments,
I have now identified the BUG shown below. I believe
this is the elusive correct BUG that ronk and I were
searching for.


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

After placing the 8 in r2c6, the rest of my proposed
solution in my original post is OK. I will
copy it here for convenience:

Next we can place 8 in r5c5, 4 in r5c1, 8 in r6c1,
7 in r5c7, and 4 in r6c7. These are all singles.

Again we are left with a BUG, this time with just
1 extra candidate, the 5 in r1c1:

Code: Select all

 *--------------------------------------------------*
 | 69+5  8   45   | 46   1    59   | 2    3    7    |
 | 7    46   2    | 3    46   8    | 5    1    9    |
 | 59   1    3    | 57   79   2    | 6    8    4    |
 |----------------+----------------+----------------|
 | 1    2    7    | 45   34   35   | 9    6    8    |
 | 4    5    6    | 9    8    1    | 7    2    3    |
 | 8    3    9    | 67   2    67   | 4    5    1    |
 |----------------+----------------+----------------|
 | 2    9    1    | 8    67   67   | 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, that single extra candidate
must be the final value of that cell. So r1c1=5.

After that, just several singles remain.
Nick67
 
Posts: 113
Joined: 24 August 2007

Postby Jeff » Tue Dec 20, 2005 2:41 am

Nick67 wrote:I'm pretty sure you meant that r7c5=6, which is a very helpful observation.

I suggest that we don't have to go quite so far as to assign a 6 to r7c5, though.
I'm not sure we can justify that yet.

Thanks Nick, I have edited my post. It'll be nice if you could help to prove the Corollary proposed.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Nick67 » Tue Dec 20, 2005 3:05 am

Jeff wrote:If this is the case, then we could have a Corollary 4 saying that
any placement of a candidate which enables a BUG grid
with non-BUG candidate(s) to be formed is a valid move.


Jeff, I am not sure that we would be able to prove such a corollary.
Instead, I suggest the following approach: if the placement of a candidate
helps to create a BUG grid, then we can simply include that value
in the BUG grid. All other candidates in that cell become "extra candidates."
And we can use this approach even if the cell is a bivalue cell.
Then we can use the BUG logic just as we have been using it.

My previous post is a good example, I think. You recognized that
r7c5=6 (instead of r7c5=67) would help to create a BUG.
I took your idea and changed it a bit: instead of actually assigning
the value 6 to r7c6, I included the 6 in the BUG, and listed the 7
as an extra candidate for that cell. Then I just used the usual
BUG logic.
Nick67
 
Posts: 113
Joined: 24 August 2007

PreviousNext

Return to Advanced solving techniques