The New Sudoku Players' Forum

[RW]

The Reverse-BUG has previously been discussed here, but as that discussion is hidden in a thread on another subject, I decided to define it in an own thread.

The Reverse-BUG requires some knowledge about unavoidable sets, more specifically two digit unavoidable sets. An unavoidable set is a set of cellvalues that cannot be solved uniquely if none of the values are given. Two digit unavoidable sets always take up exactly two cells in each unit (row, column and box) they occupy. There’s several such sets in every grid, minimum amount is 36 and the theoretical maximum is 144. They come in various shapes and sizes, some are marked here:

Code: Select all

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

A special feature for 2-digit unavoidable sets is that unless all 18 instances of the two digits are included, the remaining instances of the digits will also form an unavoidable set:

Code: Select all

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

When making a puzzle from the grid above, at least one of the cells marked ’*’ AND one of the cells marked ’#’ must be among the given values, or the puzzle has multiple solutions.

The Reverse-BUG makes use of this special feature. If all given values of digits ’A’ and ’B’ were included in one 2-digit unavoidable set, smaller than 18 cells, then the puzzle would have multiple solutions. Therefore we cannot complete such a set in an unique solution puzzle.

If the given instances of digits ’A’ and ’B’ are placed like this:

Code: Select all

A . . | B . .
B . . | * . .

then the cell marked ’*’ cannot have the value A in an unique puzzle.

An example:

Code: Select all

.7.2..3..6.21..45.....7...8....6...4...8.7...5...3....7...5.....69..87.5..5..3.6.
 *-----------------------------------------------------------*
 | 189   7    -18    |*2     4     5     | 3     19    6     |
 | 6     3    *2     |*1     8     9     | 4     5     7     |
 | 19    5     4     | 3     7     6     | 129   129   8     |
 |-------------------+-------------------+-------------------|
 | 1238  1289  1378  | 5     6     12    | 129   78    4     |
 | 124   1249  6     | 8     12    7     | 5     1239  39    |
 | 5     128   178   | 9     3     4     | 6     78    12    |
 |-------------------+-------------------+-------------------|
 | 7     128   138   | 6     5     12    | 1289  4     39    |
 | 123   6     9     | 4     12    8     | 7     123   5     |
 | 1248  1248  5     | 7     9     3     | 128   6     12    |
 *-----------------------------------------------------------*
r1c3<>1

A type 1 UR and one XY-wing then solves the puzzle. Some other examples can be found here and here.

The reverse-BUG is a very rare creature, but when it appears it is very easy to spot as you only need to consider already solved cells. The smaller the creature is, the easier it is to spot. When it gets big enough, it is usually easier to spot the potential deadly pattern from the unsolved cells:

(UR-puzzle posted by Mike Barker here.)

Code: Select all

...1.49..7..9..42....7..6...6........2...5...8...3...4.8.....7....5.....231.6...5
 *-----------------------------------------------------------*
 | 3    *5     6     | 1     2    *4     | 9     8     7     |
 | 7     1     8     | 9    *5     6     |*4     2     3     |
 | 9    *4     2     | 7     8     3     | 6    *5     1     |
 |-------------------+-------------------+-------------------|
 |#45    6    -3459  | 28    7     19    | 25    13    89    |
 | 1     2     39    | 68   *4    *5     | 7     36    89    |
 | 8     79    579   | 26    3     19    |-25    16   *4     |
 |-------------------+-------------------+-------------------|
 |#45    8    #45    | 3     9     2     | 1     7     6     |
 | 6     79    79    |*5     1     8     | 3    *4     2     |
 | 2     3     1     |*4     6     7     | 8     9    *5     |
 *-----------------------------------------------------------*
Reverse-BUG in r1c26, r2c57, r3c28, r5c56, r6c79, r8c48, r9c49: r6c7<>5
UR in r47c13: r4c3<>45

RW

[Havard]

Another great post RW, thanks!

The only thing I don't quite understand is why you think it is so rare? To me this seems like something that would happen quite often? I guess I'll have to program it up and see for myself!

Havard

[keith]

edit: Removed question following response from RW
Keith

[RW]

And, should the above quote (and, perhaps other diagrams also) be qualified by "unless one of the values is given in the initial cells"?

No, as I said if all given values 'a' and 'b' are included. Read once more about the special feature of 2-digit unavoidable sets and you'll understand.

The only thing I don't quite understand is why you think it is so rare? To me this seems like something that would happen quite often?

I think it is rare, because if you want to find an useful example then all instances of the two digits must be included. The normal UR (or BUG-lite) can usually be found even if there is several unsolved instances of the digits that aren't included in the pattern. To be honest with you, I haven't seen a good (small pattern) example yet in any puzzle not constructed by myself specifically to give a small Reverse-BUG. But I'm not a programmer and haven't made a solver that would check through large numbers of puzzles, so I can't know for sure.

RW

[keith]

edit: Removed question following response from RW
Keith

[RW]

In the text you say (lower case) 'a' and 'b'.

In the "code" you have only upper case
...
Is there a difference?

No, there's no difference. I can edit it if it's confusing.

RW

[RW]

This puzzle was posted by GregFiore here, but I want to mention it in this thread also as another possible way to apply the Reverse-BUG.

Code: Select all

3....84....7..46.8....1..7.9....352...1...7...341....6.1..9....6.35..2....24....7
 *--------------------------------------------------------------------*
 | 3      256    569    | 2679   2567   8      | 4      1      259    |
 | 1      25     7      | 239    235    4      | 6      359    8      |
 | 2458   24568  5689   | 2369   1      259    | 39     7      2359   |
 |----------------------+----------------------+----------------------|
 | 9      678    68     | 678    4      3      |*5     *2      1      |
 | 258    2568   1      | 2689   2568   259    | 7      34     34     |
 | 257    3      4      | 1      25     257    | 89     89     6      |
 |----------------------+----------------------+----------------------|
 | 47     1      5+8    | 2+38   9      27     |#38     6     -345    |
 | 6      47     3      |*5      78     1      |*2      489    49     |
 | 58     9     *2      | 4      38     6      | 1      5+38   7      |
 *--------------------------------------------------------------------*

The given and solved digits '2' and '5' would all be included in one unavoidable set size 8 if r7c3<>8, r7c4<>38 and r9c8<>38. The ’38’ in r7c7 can see all these cells and be used like an UR type 3 to eliminate ’3’ and ’8’ from all other cells that can see r7c7 and the other mentioned cells => r7c9<>3.

After this the puzzle can be solved by the short xy-chain in r7c37 and r9c15 (r7c4 and r9c8<>3).

If you choose to do the XY-chain eliminations first, you get here:

Code: Select all

 *--------------------------------------------------------------------*
 | 3      256    69     | 2679   67     8      | 4      1      25     |
 | 1      25     7      | 39     25     4      | 6      39     8      |
 | 245    24568  689    | 2369   1      259    | 39     7      25     |
 |----------------------+----------------------+----------------------|
 | 9      678    68     | 678    4      3      |*5     *2      1      |
 | 25     2568   1      | 2689   68     259    | 7      34     34     |
 | 257    3      4      | 1      25     257    | 89     89     6      |
 |----------------------+----------------------+----------------------|
 | 47     1     *5      |-28     9      27     | 38     6      34     |
 | 6      47     3      |*5      78     1      |*2      48     9      |
 | 8      9     *2      | 4      3      6      | 1     *5      7      |
 *--------------------------------------------------------------------*

and can then solve the puzzle with the basic Reverse-BUG elimination r7c4<>2.

RW

[tso]

[DELETED -- misunderstood the concept]

[RW]

I found several instances that were of little use. But this one is nice:

Code: Select all

 
 *-----------*
 |...|24.|9.7|
 |.2.|9..|...|
 |1..|.37|...|
 |---+---+---|
 |...|..8|.3.|
 |7.8|4.9|6.5|
 |.5.|6..|...|
 |---+---+---|
 |...|17.|..4|
 |...|..4|.2.|
 |3.4|.82|...|
 *-----------*


I'm afraid that is not a valid exclusion. If you are referring to the 4-6 unavoidable set, then there are several given digits '4' that are not included. All given instances of both digits must be included in the pattern if you are to make the exclusion. Look at these grids:

Code: Select all

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

Here ALL given digits 5 and 7 are included in an unavoidable set size 4 - the puzzle has two solutions. But in this grid:

Code: Select all

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

There is one given digit '7' not included in the unavoidable set - the puzzle has an unique solution.

RW

[ravel]

There was a nice BUG-reversed sample in Ruuds forum here (also discussed here, but i could not find it)

[RW]

There was a nice BUG-reversed sample in Ruuds forum here (also discussed here, but i could not find it)

todays Daily Nightmare is not from my own collection. It's a scrambled version of one presented by somebody on a forum far far away...

This is the forum far far away, and the original unscrambled puzzle was used as my first example in the Effortless Extremes-thread. Also posted to the Benchmark Sudoku list just a few hours before it was published as a Daily Nightmare... In the future, if you choose to publish puzzles that I've spent hours creating by hand, could you please at least inform me about it?

RW

[ravel]

IMHO Ruud should be sentenced to implement the reverse BUG and scan his 50000 for it

[fermat]

And the sorting is painless, coding..some trouble.

Sorry RW, you should have been credited, yet, published is available, at least it was scrambled.

Ick, why did I get in this. OK, I have some published, I do that under several names. I think about rights, just not sure I have any, or who's toes I dance on.

Is the clue pattern the factor?
The final grid?

Who is to know??