Reverse BUG-lite

Advanced methods and approaches for solving Sudoku puzzles

Reverse BUG-lite

Postby RW » Mon Oct 16, 2006 11:15 am

I've earlier described the Reverse BUG which uses an backwards approach to finding complex uniqueness patterns that use only two digits. This is kind of a variation, but it doesn't just identify 2-digit patterns.

Consider two full rows, within the same three boxes:
Code: Select all
123|456|789
456|789|123

Everybody knows that you cannot have an unique puzzle with two empty rows as such. For the two rows above you need at least one given in any puzzle to have an unique solution. Sometimes there can be a smaller unavoidable set within two rows:

Code: Select all
*1 2 3 |*4 5 6 |*7 8 9
*4 5 8 |*7 9 3 |*1 2 6


Columns 1, 4 and 7 form such an unavoidable set, thus there must be at least one given in any of these six cells. Now here's the trick: If one part of 2 rows/columns form an unavoidable set, the remaining part will also form an unavoidable set:

Code: Select all
 1 #2 #3 | 4 #5 #6 | 7 #8 #9
 4 #5 #8 | 7 #9 #3 | 1 #2 #6


You cannot have two rows or columns partially filled so that all filled digits together form an unavoidable set at any point of solving an unique puzzle.

example: If rows 1 and 2 look like this:

Code: Select all
1..|2..|3..
3..|1..|...


you may eliminate candidate 2 from r2c7.

This is so far just an idea that suddenly came to me, haven't had time to look for good examples in puzzles yet. Trying to construct one, I found one where it helps a bit, but doesn't solve the puzzle. At the point when you get stuck with basic technique:

Code: Select all
...4...25..9..57..12.7....42.............256...431...2..3..4.........68...1.8...9
 *-----------*
 |...|4..|.25|
 |..9|..5|7.6|
 |125|7..|.94|
 |---+---+---|
 |2..|...|...|
 |..7|.42|56.|
 |..4|31.|972|
 |---+---+---|
 |..3|..4|...|
 |..2|...|68.|
 |..1|.8.|..9|
 *-----------*

In columns 1 and 2 it is easy to see that a 1 in r4c2 would complete an unavoidable set in two otherwise empty columns => r4c2<>1 => r5c2=1.

And a sligthly more complex example that actually solves a puzzle:

Code: Select all
..76.89..........512...54..2...7.63.318.............9.....978.....4....9.3..2..7.
 *-----------------------*
 | . . 7 | 6 1 8 | 9 2 3 |
 | . . 3 | . 4 . | . . 5 |
 | 1 2 % | . 3 5 | 4 8 . |
 |-------+-------+-------|
 | 2 # # | . 7 4 | 6 3 . |
 | 3 1 8 | . 6 . | . . . |
 |-------|-----3-|---9 . |
 |-------+-------+-------|
 |-------|-3-9 7 | 8 . 2 |
 |-----2-|-4-----|-3---9 |
 | # 3 # | . 2 . | . 7 . |
 *-----------------------*

We almost have an unavoidable set in columns 1 and 2, if r4c2 and r9c1 would take the same value, then the set would be complete. In row 4 there's only two possible cells for digit 9, columns 2 and 3, in row 9 digit 9 has to go in column 1 or 3. As we know that both r4c2 and r9c9 cannot be 9, we can tell that r4c3=9 or r9c3=9, in either case r3c3<>9.

With pencilmarks for anyone who isn't used to look at grids without them:
Code: Select all
 *--------------------------------------------------------------------*
 | 45     45     7      | 6      1      8      | 9      2      3      |
 | 689    689    3      | 279    4      29     | 17     16     5      |
 |*1     *2     -69     | 79     3      5      | 4      8      67     |
 |----------------------+----------------------+----------------------|
 |*2     #59    #59     | 18     7      4      | 6      3      18     |
 |*3     *1      8      | 259    6      29     | 257    45     47     |
 | 467    467    46     | 1258   58     3      | 25     9      18     |
 |----------------------+----------------------+----------------------|
 | 456    456    1456   | 3      9      7      | 8      1456   2      |
 | 5678   5678   2      | 4      58     16     | 3      156    9      |
 |#45689 *3     #14569  | 58     2      16     | 15     7      46     |
 *--------------------------------------------------------------------*


RW
Last edited by RW on Mon Oct 16, 2006 11:29 am, edited 1 time in total.
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby RW » Mon Oct 16, 2006 3:27 pm

Time for a better example:
Code: Select all
 *-----------*
 |...|...|.83|
 |..1|38.|.46|
 |.23|...|.1.|
 |---+---+---|
 |7..|15.|.34|
 |...|..7|8..|
 |.6.|.4.|.7.|
 |---+---+---|
 |..5|8..|...|
 |...|5..|...|
 |2.7|4.1|...|
 *-----------*

Will give you a hard time, unless you happen to spot the Reverse BUG-lite in rows 7 and 8 (r8c3<>8).

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Carcul » Mon Oct 16, 2006 4:04 pm

RW wrote:Time for a better example:(...)Will give you a hard time, unless you happen to spot the Reverse BUG-lite in rows 7 and 8 (r8c3<>8).


That puzzle is a superb example.

RW wrote:And a sligthly more complex example that actually solves a puzzle:(...)


Another good example. But here's another solution:

Code: Select all
 *-----------------------------------------------------------*
 | 45     45     7     | 6      1      8  | 9      2      3  |
 | 689    689    3     | 279    4      29 | 17     16     5  |
 | 1      2      69    | 79     3      5  | 4      8      67 |
 |---------------------+------------------+------------------|
 | 2      59     59    | 18     7      4  | 6      3      18 |
 | 3      1      8     | 259    6      29 | 257    45     47 |
 | 467    467    46    | 1258   58     3  | 25     9      18 |
 |---------------------+------------------+------------------|
 | 456    456    1456  | 3      9      7  | 8      1456   2  |
 | 5678   5678   2     | 4      58     16 | 3      156    9  |
 | 45689  3      14569 | 58     2      16 | 15     7      46 |
 *-----------------------------------------------------------*

Please note that if r2c7=7 then we would have Three Incompatible Unique Rectangles: a contradiction situation. So, r2c7<>7 and the puzzle is solved.

As a general comment, I find this way of thinking (reverse BUG-lite) very smart, but I guess one will seldom find it in a puzzle, unless the puzzle is specially designed so as to be possible to apply it, which is a pity.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby re'born » Mon Oct 16, 2006 7:52 pm

Carcul,

Just to make sure that I am following:

Carcul wrote:
Code: Select all
 *-----------------------------------------------------------*
 | 45     45     7     | 6      1      8  | 9      2      3  |
 | 689    689    3     | 279*   4      29*| 17     16     5  |
 | 1      2      69    | 79     3      5  | 4      8      67 |
 |---------------------+------------------+------------------|
 | 2      59     59    | 18     7      4  | 6      3      18 |
 | 3      1      8     | 259*#  6      29*| 257#   45     47 |
 | 467    467    46    | 1258#  58     3  | 25#    9      18 |
 |---------------------+------------------+------------------|
 | 456    456    1456  | 3      9      7  | 8      1456   2  |
 | 5678   5678   2     | 4      58     16 | 3      156    9  |
 | 45689  3      14569 | 58     2      16 | 15     7      46 |
 *-----------------------------------------------------------*

Please note that if r2c7=7 then we would have Three Incompatible Unique Rectangles: a contradiction situation. So, r2c7<>7 and the puzzle is solved.
Is the deduction as follows? If r2c7=7, then the UR in r25c46<29> implies that r5c4=5. On the other hand, if r2c7, then the UR in r56c47<25> implies that (using r5c4=5) r6c4=[18]. But then the naked pair in r6c49<18> implies that r6c5=5, a contradiction. Where is the third incompatible unique rectangle you had in mind?


Carcul wrote:As a general comment, I find this way of thinking (reverse BUG-lite) very smart, but I guess one will seldom find it in a puzzle, unless the puzzle is specially designed so as to be possible to apply it, which is a pity.


RW,

What he said.

When you wrote the your thread on the Hidden Bug, I asked for someone to check out how often it occurred in the Topxxxx Lists, but I don't remember there being much or any response. Any chance someone (Mike Barker???) will take up the challenge of coding this into their solver and giving us some idea just how ubiquitous a pattern this is?
re'born
 
Posts: 551
Joined: 31 May 2007

Postby ronk » Mon Oct 16, 2006 8:26 pm

rep'nA wrote:Where is the third incompatible unique rectangle you had in mind?

It would have to be UR(18) Type 1 in r46c49.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby RW » Mon Oct 16, 2006 8:30 pm

rep'nA wrote:When you wrote the your thread on the Hidden Bug, I asked for someone to check out how often it occurred in the Topxxxx Lists, but I don't remember there being much or any response.

I don't know if anyone has coded any reverse/hidden bug patterns yet. I think this BUG-lite version should be a bit more common than the reverse BUG, which in turn should be a lot more common than the hidden BUG. So far I have only seen one reverse BUG in a puzzle I hadn't created myself, posted here a few months ago.

Even though they are rare, the nice thing with these patterns is that when they appear they can be very powerful and allow you to eliminate candidates that would be extremely hard to eliminate otherwise. If you wish to make the elimination I did in my last example by some chain, you'd have to use colors on the way before you reach a contradiction. For all non-uniqueness techniques you can always find the contradiction within the cells of the pattern you use.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Carcul » Mon Oct 16, 2006 8:35 pm

That's right Rep'nA and Ronk:

Code: Select all
 *-----------------------------------------------------------*
 | 45     45     7     | 6      1      8  | 9      2      3  |
 | 689    689    3     | 29     4      29 | 7      16     5  |
 | 1      2      69    | 79     3      5  | 4      8      6  |
 |---------------------+------------------+------------------|
 | 2      59     59    | 18     7      4  | 6      3      18 |
 | 3      1      8     | 259    6      29 | 25     45     47 |
 | 467    467    46    | 1258   58     3  | 25     9      18 |
 |---------------------+------------------+------------------|
 | 456    456    1456  | 3      9      7  | 8      1456   2  |
 | 5678   5678   2     | 4      58     16 | 3      156    9  |
 | 45689  3      14569 | 58     2      16 | 15     7      46 |
 *-----------------------------------------------------------*

Because of the UR in cells r46c49, r6c4<>1,8. Then we have TIUR's:

UR r25c46 => r5c4=5; UR r56c47 => r5c4=9.

So r2c7<>7.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby RW » Mon Oct 16, 2006 8:43 pm

carcul wrote:Another good example. But here's another solution: ... Please note that if r2c7=7 then we would have Three Incompatible Unique Rectangles: a contradiction situation. So, r2c7<>7 and the puzzle is solved.


If you wish to use the URs, you could as well first do the UR type 1 elimination for r46c49, then you get to a UR+2kx in r25c46 with the bivalue cell in r3c4 and may eliminate 9 from r5c4. After this the type 1 UR in r56c47 solves the puzzle.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby re'born » Tue Oct 17, 2006 8:37 am

Ronk and Carcul,

Thanks for pointing me towards the third UR. That is a very pleasing deduction.

RW,

Here is another alternative along your last line of thought.

UR1 eliminates [18] in r6c4, then UR+2kx (or whatever the notation is now) eliminates [5] in r5c4. Finally, UR1 forces r2c4=7 solving the puzzle.
re'born
 
Posts: 551
Joined: 31 May 2007

Re:

Postby Luke » Sat May 26, 2012 4:21 pm

RW wrote:Time for a better example:
Code: Select all
 *-----------*
 |...|...|.83|
 |..1|38.|.46|
 |.23|...|.1.|
 |---+---+---|
 |7..|15.|.34|
 |...|..7|8..|
 |.6.|.4.|.7.|
 |---+---+---|
 |..5|8..|...|
 |...|5..|...|
 |2.7|4.1|...|
 *-----------*

Will give you a hard time, unless you happen to spot the Reverse BUG-lite in rows 7 and 8 (r8c3<>8).

RW


I am missing something very fundamental here.

What makes the above example a R B-l and this one not?

Code: Select all
+-------+-------+-------+
| . . . | 6 . 9 | 5 . 2 |
| . . . | . 8 . | . . . |
| . . 1 | . . 7 | . . . |
+-------+-------+-------+
| 6 . . | . . . | 4 7 . |
| 1 5 . | .*3 . | . 8*6 |
| . 9 8 | .*. . | . .*3 |
+-------+-------+-------+
| . . . | 2 . 5 | 8 . . |
| . . . | . 7 . | . . . |
| 5 . 4 | 3 . 6 | . . . |
+-------+-------+-------+
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Re: Re:

Postby ronk » Sat May 26, 2012 4:37 pm

Luke451 wrote:I am missing something very fundamental here.

What makes the above example a R B-l and this one not?

I think the cells of the 2-row reverse BUG-Lite pattern must be the only cells in the two rows with clues or placements.

I don't know this technique well enough to venture a statement for larger patterns.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Re:

Postby Luke » Sat May 26, 2012 8:51 pm

ronk wrote:
Luke451 wrote:I am missing something very fundamental here.

What makes the above example a R B-l and this one not?

I think the cells of the 2-row reverse BUG-Lite pattern must be the only cells in the two rows with clues or placements.

I don't know this technique well enough to venture a statement for larger patterns.

Thanks, Ron, I think that's it.

In this example, there are extra givens in the rows, but the only given (or solved?) 1s and 2s on the grid are within the pattern.

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    |
 *-----------------------------------------------------------*


I think the same holds true for larger two digit patterns like this.

Code: Select all
*--------------------------------------------*
|3589 1289 1235| 4    7    126| 12  3689 3689|
| 4    7    123| 26   9    8  | 12   5    36 |
| 89   12   6  | 3    5    12 | 7    489  489|
|--------------------------------------------|
| 6    345  7  | 9   -28   23 | 58   348 *1  |
|*1    35   9  | 568  4    7  | 568 *2    368|
|*2    345  8  | 56  *1    36 | 569  7   3469|
|--------------------------------------------|
| 389 1289  4  | 128 2369  5  | 689  689  7  |
|3578  6    35 | 78   38   9  | 4   *1   *2  |
| 789 1289  12 |1278  268  4  | 3    689  5  |
*--------------------------------------------*

The only given (or solved?) 1s and 2s in the puzzle are found within the pattern.
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Re: Reverse BUG-lite

Postby aran » Sun May 27, 2012 2:59 pm

Luke
On those reverse-BUG points recently raised by you : I did notice one or two question marks in your text, so here is another viewpoint.
The best way IMO to contemplate any potential reverse-DP configuration is to concentrate on the remainder.
Just to be clear on definitions : a reverse-DP is a configuration with givens which but for those givens would be a DP in its own right.
Rather than define the term "Remainder" it will emerge naturally in what follows.

The capital point is this :
there must be no givens in the remainder.

So with that preamble, consider all four examples you have given

Example 1
Code: Select all
*-----------*
 |...|...|.83|
 |..1|38.|.46|
 |.23|...|.1.|
 |---+---+---|
 |7..|15.|.34|
 |...|..7|8..|
 |.6.|.4.|.7.|
 |---+---+---|
 |..5|8..|...|
 |...|5..|...|
 |2.7|4.1|...|
 *-----------*

Potential reverse-UR : 58r78c34.
Remainder : 1234679r78c1256789.
This remainder has no givens, and were it to exist would constitute a super 7-candidate MUG
(Proof of MUG : if S is any solution, then so is W, where W results from the switch between the relative cells of S)
Hence the potential reverse-DP is deadly

Example 2
(all of the candidates below are givens)
Code: Select all
    +-------+-------+-------+
    | . . . | 6 . 9 | 5 . 2 |
    | . . . | . 8 . | . . . |
    | . . 1 | . . 7 | . . . |
    +-------+-------+-------+
    | 6 . . | . . . | 4 7 . |
    | 1 5 . | .*3 . | . 8*6 |
    | . 9 8 | .*. . | . .*3 |
    +-------+-------+-------+
    | . . . | 2 . 5 | 8 . . |
    | . . . | . 7 . | . . . |
    | 5 . 4 | 3 . 6 | . . . |
    +-------+-------+-------+

Potential reverse-UR : 36r56c59
Remainder 1 : 1245789r1234789c59 : which contains givens
Remainder 2 :...see below
Hence the potential reverse-DP is not deadly

Example 3
.7.2..3..6.21..45.....7...8....6...4...8.7...5...3....7...5.....69..87.5..5..3.6.
Code: Select all
*-----------------------------------------------------------*
 | 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    |
 *-----------------------------------------------------------*

Potential reverse-UR 12r12c34
I think the original thinker behind this elegant piece of logic was RW.
Obviously the remainder in rows 1 and 2 is of no interest (eg r1c2=given).
But noting that 1 and 2 do not appear as givens anywhere else on the grid, it follows that if the reverse-DP is posited, then the remainder constituted by all those non-given 1+2 candidates must produce a (12)BUG-lite.
Note (to remove your question marks) that the presence of 12 as assigneds in the remainder is irrelevant. it is enough that there be no 12 givens.
Hence the potential reverse-UR is deadly.

Example 4
Code: Select all
    *--------------------------------------------*
    |3589 1289 1235| 4    7    126| 12  3689 3689|
    | 4    7    123| 26   9    8  | 12   5    36 |
    | 89   12   6  | 3    5    12 | 7    489  489|
    |--------------------------------------------|
    | 6    345  7  | 9   -28   23 | 58   348 *1  |
    |*1    35   9  | 568  4    7  | 568 *2    368|
    |*2    345  8  | 56  *1    36 | 569  7   3469|
    |--------------------------------------------|
    | 389 1289  4  | 128 2369  5  | 689  689  7  |
    |3578  6    35 | 78   38   9  | 4   *1   *2  |
    | 789 1289  12 |1278  268  4  | 3    689  5  |
    *--------------------------------------------*

Potential reverse-BUG-lite :12r4c59 12r5c18 12r6c15 12r8c89
As in example 3, the remainder, constituted by all remaining 12 contains no 12 as givens.
Therefore if the reverse-BUG-lite is posited, then the reminder is a BUG-lite.
Again assigneds in that remainder are irrelevant.
Hence the potential reverse-BUG-lite is deadly
aran
 
Posts: 334
Joined: 02 March 2007

Re: Re:

Postby ronk » Sun May 27, 2012 9:21 pm

Luke451 wrote:In this example, there are extra givens in the rows, but the only given (or solved?) 1s and 2s on the grid are within the pattern.

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    |
 *-----------------------------------------------------------*

RW called this one a reverse-BUG, rather than reverse-BUG-Lite. For the former, the entire grid is considered, for the latter something less. As of now, the only reverse BUG-lite pattern I know of is in two lines. RW has indicated that there are three line patterns, but never gave an example AFAIK.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Reverse BUG-lite

Postby aran » Mon May 28, 2012 10:25 am

If the term "Reverse-DP" (Reverse Bug/Reverse Bug-lite etc) refers to the structure under consideration and not to the Remainder (ie the veritable potential deadly structure), then strictly speaking the structure should be given the name it would bear were no givens involved.
Thus in the above example, the structure r12c34 would be referred to as a Reverse-UR.
If the term refers however to the Remainder (but I don't think this is the intention) then the above structure would be referred to as a Reverse Bug-Lite.
In any case of course, none of these structures is a deadly pattern : that is none of them can usefully be examined without reference to the remainder of the grid.
That is, the potential Reverse structure turns out to be deadly only if the Remainder exists as a potential deadly structure..
The point of "Reverse" structures is that they are...pointers to the Remainder ie hinting at the possible existence of a less-easily detected potential deadly structure.
aran
 
Posts: 334
Joined: 02 March 2007

Next

Return to Advanced solving techniques