The New Sudoku Players' Forum

[Nick67]

Hi MadOverlord,

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?

Good question. Here's my best guess: if a puzzle is in the state
you describe, and no simple reductions (e.g., via singles or subsets)
are possible, then the grid does indeed contain a BUG (and there
is no need to run the "full test" to see if it is a BUG).

It would be much better if we could prove that, though.

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

If the puzzle contains a BUG, and there is only one poly-valued
cell, the logic of the BUG principle holds no matter how many
candidates are in that poly-valued cell. (That is, one
of the non-BUG candidates must be "true".)

But.... just off the top of my head, I don't think I've seen a puzzle with
a BUG in which the single poly-valued cell had more than 3 candidates.
I could definitely be wrong about that.
[edit: I am wrong about that. But my statement in the previous paragraph is OK.]

MadOverlord, I also have a question for you.
What is your algorithm for identifying a BUG?
Could a player use it, or is it better left to a computer?
I ask because, often a puzzle looks like it contains
a BUG (due to several bivalue cells), but it also
contains several poly-value cells, making it difficult
to identify the BUG. I've spent a lot of time moving
candidates to 1 side of the + sign, later moving
them back, etc., and I wonder if there is a systematic way?

[MadOverlord]

But.... just off the top of my head, I don't think I've seen a puzzle with
a BUG in which the single poly-valued cell had more than 3 candidates.
I could definitely be wrong about that.

Here is a BUG-reduction with a 4-value square:

Code: Select all

+----------------+----------------+----------------+
| 4    2    1    | 7    59   3    | 6    59   8    |
| 3    7    58   | 89   6    4    | 1    59   2    |
| 9    58   6    | 1    28   25   | 7    4    3    |
+----------------+----------------+----------------+
| 2    45   3    | 49   59   6    | 8    7    1    |
| 1    4568 58   | 48   7    25   | 3    26   9    |
| 7    68   9    | 3    28   1    | 5    26   4    |
+----------------+----------------+----------------+
| 8    9    4    | 6    3    7    | 2    1    5    |
| 6    3    2    | 5    1    9    | 4    8    7    |
| 5    1    7    | 2    4    8    | 9    3    6    |
+----------------+----------------+----------------+

MadOverlord, I also have a question for you.
What is your algorithm for identifying a BUG?
Could a player use it, or is it better left to a computer?

It is very straightforward, and I explained it earlier in the thread in some detail; refer back to that, it's on page 2 IIRC. The algorithm will generate a BUG, if it exists, from any puzzle, but I only solve single-polysquare BUGs, as they have the simple reduction.

Regarding whether a 1-polysquare puzzle can always be BUG reduced, consider the existence of the 4-possibility polysquare BUG (the example above).

It is possible to create a 3-possibility state that cannot be BUG reduced (simply remove one of the BUG possibilities from the 4-possibility square)

If you do so, you trigger a pin and the puzzle solves, and even in this case, the basic BUG reduction action ("remove any possibility in the polysquare that appears only once in its row, column or block") still works.

If this is the case, then the 1-polysquare BUG rule becomes blindingly easy to express, so I'd really like to verify that all completely bivalue + 1 polysquare puzzles can be reduced to BUGs.

R

[Nick67]

MadOverlord,

Thanks for the pointer to your algorithm.

Regarding your example, I just want to
see if we agree on the analysis.

Here is the example with the BUG identified:

Code: Select all

+----------------+----------------+----------------+
| 4    2    1    | 7    59   3    | 6    59   8    |
| 3    7    58   | 89   6    4    | 1    59   2    |
| 9    58   6    | 1    28   25   | 7    4    3    |
+----------------+----------------+----------------+
| 2    45   3    | 49   59   6    | 8    7    1    |
| 1   46+58 58   | 48   7    25   | 3    26   9    |
| 7    68   9    | 3    28   1    | 5    26   4    |
+----------------+----------------+----------------+
| 8    9    4    | 6    3    7    | 2    1    5    |
| 6    3    2    | 5    1    9    | 4    8    7    |
| 5    1    7    | 2    4    8    | 9    3    6    |
+----------------+----------------+----------------+


I could be mistaken, but as I see it, the BUG principle lets us
immediately eliminate both BUG candidates in r5c2,
leaving the 5 and 8.

[MadOverlord]

I could be mistaken, but as I see it, the BUG principle lets us immediately eliminate both BUG candidates in r5c2, leaving the 5 and 8.

Yes, that's not at issue AFAICT. The question is, will all bivalue + 1 polyvalue puzzles either (a) be reducible to a BUG, and thus let us apply the simple reduction rule to the polyvalue or (b) effectively be a BUG with 1 of the BUG possibilities already removed, so the reduction can be made anyway.

I ask myself the following question:

Are puzzles with all-bivalue unsolved squares always BUGs? Can you ever get to an all-bivalue state and still have a single-solution puzzle?

The very fact that there are examples like the one I gave, where the polysquare has 4 values, proves that the answer is "yes, there are valid puzzles with all bivalues", because the BUG reduction in this case generates one (that then cracks via a pin)!

After the BUG reduction, we have:

Code: Select all

+----------+----------+----------+
| 4  2  1  | 7  59 3  | 6  59 8  |
| 3  7  58 | 89 6  4  | 1  59 2  |
| 9  58 6  | 1  28 25 | 7  4  3  |
+----------+----------+----------+
| 2  45 3  | 49 59 6  | 8  7  1  |
| 1  58 58 | 48 7  25 | 3  26 9  |
| 7  68 9  | 3  28 1  | 5  26 4  |
+----------+----------+----------+
| 8  9  4  | 6  3  7  | 2  1  5  |
| 6  3  2  | 5  1  9  | 4  8  7  |
| 5  1  7  | 2  4  8  | 9  3  6  |
+----------+----------+----------+


So clearly, since you could add some extra possibilities to another square in that version of the puzzle, you can generate a puzzle that has 1 polysquare and all the rest bivalue but cannot create a BUG (it will, of course, have a pin you should have caught). For example, add 26 to R1C8, to get:

Code: Select all

+----------------+----------------+----------------+
| 4    2    1    | 7    59   3    | 6    2569 8    |
| 3    7    58   | 89   6    4    | 1    59   2    |
| 9    58   6    | 1    28   25   | 7    4    3    |
+----------------+----------------+----------------+
| 2    45   3    | 49   59   6    | 8    7    1    |
| 1    58   58   | 48   7    25   | 3    26   9    |
| 7    68   9    | 3    28   1    | 5    26   4    |
+----------------+----------------+----------------+
| 8    9    4    | 6    3    7    | 2    1    5    |
| 6    3    2    | 5    1    9    | 4    8    7    |
| 5    1    7    | 2    4    8    | 9    3    6    |
+----------------+----------------+----------------+


If you somehow got to that state (missing the pin), then if you looked at the polysquare, you'd think you could remove 59 (since they only appear once in R1), and you'd screw up.

So perhaps the rule (and the BUGHOOD test, btw) could be "you can only remove a possibility from the polysquare if it appears only once in the square's row, column ***AND*** block; if it appears once in some but twice in others, then you've missed a pin or messed up"

Interesting...

I really need the logicians to work this over.

[Jeff]

Are puzzles with all-bivalue unsolved squares always BUGs? Can you ever get to an all-bivalue state and still have a single-solution puzzle?

Hi MadOverload, When the BUG principle is considered, it is always at the point where a grid could go no further via basic rules such as naked subsets, ie. naked pair, naked triple and so forth. On this basis, the answer is definitely yes. However, if the all-bivalue state is unconditional, then the answer is definitely no. I think you have looked too close and forgot where we were coming from. The following grid can be further reduced via a naked pair so the BUG principle is not applicable yet.

Code: Select all

+----------+----------+----------+
| 4  2  1  | 7  59 3  | 6  59 8  |
| 3  7  58 | 89 6  4  | 1  59 2  |
| 9  58 6  | 1  28 25 | 7  4  3  |
+----------+----------+----------+
| 2  45 3  | 49 59 6  | 8  7  1  |
| 1  58 58 | 48 7  25 | 3  26 9  |
| 7  68 9  | 3  28 1  | 5  26 4  |
+----------+----------+----------+
| 8  9  4  | 6  3  7  | 2  1  5  |
| 6  3  2  | 5  1  9  | 4  8  7  |
| 5  1  7  | 2  4  8  | 9  3  6  |
+----------+----------+----------+


[Myth Jellies]

Of course, one cannot really legitimately create a rule that assumes the solver has found and reduced all naked/hidden subsets. That is why a BUG grid is defined as a grid where all unsolved cells have two candidates, AND, for each unsolved candidate digit, when it appears in a box, row, or column, it appears exactly twice.

[MadOverlord]

Of course, one cannot really legitimately create a rule that assumes the solver has found and reduced all naked/hidden subsets. That is why a BUG grid is defined as a grid where all unsolved cells have two candidates, AND, for each unsolved candidate digit, when it appears in a box, row, or column, it appears exactly twice.

That, I think, is the key point I need to make.

Can an inverted comment also be made?

"If the puzzle is down to all bivalue + 1 polyvalue square and you cannot construct a BUG, then you have missed a force, pin, naked or hidden set somewhere"

[Jeff]

Define what you mean by BUG+1

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

[vidarino]

Hi all.

I have recently tried to implement a simple BUG detector in my solver, but when testing it, I seem to have stumbled across a false positive. This is a partially solved board from Susser's "Sample BUG";

Code: Select all

    7    25    59       1     4     3       8    29     6
   39     6     8       2     7    59      35    14    14
  239    14    14       6     8    59       7    29    35

    8    45    45       7     9     6       1     3     2
    6     9     7       3     1     2       4     5     8
    1     3     2      48     5    48       6     7     9

    5    17     6      89     2   178      39   148   134
   29     8    19      45     3    14      25     6     7
    4   127     3     589     6   178     259    18    15


The 239 in R3C1 is assumed to be a BUG+1 candidate, and counting the candidates makes it want to put a 9 in there (three 9s, two of all the others). This is wrong, however, and leads to a conflicting board later on. 2 is the right value for that cell.

On closer inspection I found out that the 9 can be eliminated with a simple force loop check, which takes the puzzle onward to the real BUG sample the board was supposed to demonstrate.

Can anyone offer some insight into what I need to do to avoid this false one? Can BUG hunting only be done after the board has been subject to certain other tests first? If so, which ones?

Thanks.

[ronk]

Code: Select all

    7    25    59       1     4     3       8    29     6
   39     6     8       2     7    59      35    14    14
  239    14    14       6     8    59       7    29    35

    8    45    45       7     9     6       1     3     2
    6     9     7       3     1     2       4     5     8
    1     3     2      48     5    48       6     7     9

    5    17     6      89     2   178      39   148   134
   29     8    19      45     3    14      25     6     7
    4   127     3     589     6   178     259    18    15


The 239 in R3C1 is assumed to be a BUG+1 candidate, and counting the candidates makes it want to put a 9 in there (three 9s, two of all the others). This is wrong, however, and leads to a conflicting board later on. 2 is the right value for that cell.

While there are indeed three 9s in row 3, column 1, and box 1, "the rule" you are trying to apply is only valid in "BUG+1" grids, meaning there is only 1 non-BUG candidate on the entire grid. Your grid is a "BUG+8" grid.

I think your BUG grid would look like ...

Code: Select all

 *-----------------------------------------------------------*
 |  7    25    59  |    1     4     3  |    8    29     6    |
 | 39     6     8  |    2     7    59  |   35    14    14    |
 |23+9   14    14  |    6     8    59  |    7    29    35    |
 |-----------------+-------------------+---------------------|
 |  8    45    45  |    7     9     6  |    1     3     2    |
 |  6     9     7  |    3     1     2  |    4     5     8    |
 |  1     3     2  |   48     5    48  |    6     7     9    |
 |-----------------+-------------------+---------------------|
 |  5    17     6  |   89     2  17+8  |   39  48+1  34+1    |
 | 29     8    19  |   45     3    14  |   25     6     7    |
 |  4  27+1     3  | 59+8     6  78+1  | 29+5    18    15    |
 *-----------------------------------------------------------*

I say "think" because I've done this by hand and it's easy to make mistakes doing so.

But whatever the BUG grid, we only know that at least one of the non-BUG candidates is the correct placement (for a grid that has a unique solution). So we must now find one (or more) exclusion(s) implied by each and every non-BUG candidate. For this grid, that's eight implication chains all leading to the same exclusion.

[vidarino]

While there are indeed three 9s in row 3, column 1, and box 1, "the rule" you are trying to apply is only valid in "BUG+1" grids, meaning there is only 1 non-BUG candidate on the entire grid. Your grid is a "BUG+8" grid.

Ahh! That makes a heck of a lot more sense. Time to refine my algorithms, it seems.

Thanks for your feedback.

[ronk]

I've now gotten to where I can obtain the BUG+N grid accurately, but often can't seem to find an elimination after that. Vidinaro's puzzle earlier is a case in point. Here is another.

Puzzle #87 of the top95 ...

Code: Select all

 ...|5.3|...
 ...|.6.|7..
 5.8|...|.16
 ---+---+---
 36.|.2.|...
 ...|4.1|...
 ...|.3.|..5
 ---+---+---
 67.|...|2.8
 ..4|.7.|...
 ...|2..|5..

... can be taken to this point with basic techniques ...

Code: Select all

 7.6|513|..2
 ..2|86.|75.
 5.8|7.2|.16
 ---+---+---
 367|925|...
 925|481|...
 ..1|637|925
 ---+---+---
 67.|15.|2.8
 254|378|...
 ...|2.6|5..

... at which point (I'm pretty sure) it has the 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

Does anyone see an elimination in there?

TIA, Ron

[edit: columnized the BUG grid]

[Neunmalneun]

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)

[Carcul]

Another possibility is the following:

we have a type 2 almost unique rectangle in cells r1c78/r4c78 with the link [r1c8]=9|1=[r4c7], and we can write

[r1c8]=9|1=[r4c7]-1-[r4c9](-4-[r4c8]-8-[r1c8])=1=[r8c9]-1-[r8c7]-6-[r5c7]-3-[r3c7]-4-[r1c8]

which implies r1c8<>4,8 => r1c8=9 and that solve the puzzle.

Carcul

[ronk]

Another possibility is the following:

we have a type 2 almost unique rectangle in cells r1c78/r4c78 with the link [r1c8]=9|1=[r4c7], and we can write

[r1c8]=9|1=[r4c7]-1-[r4c9](-4-[r4c8]-8-[r1c8])=1=[r8c9]-1-[r8c7]-6-[r5c7]-3-[r3c7]-4-[r1c8]

which implies r1c8<>4,8 => r1c8=9 and that solve the puzzle.

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

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