Between Uniqueness and BUG: BUG Lite

Advanced methods and approaches for solving Sudoku puzzles

Between Uniqueness and BUG: BUG Lite

Postby Myth Jellies » Tue Jan 31, 2006 11:35 am

Theoretically speaking...between our simple 4 cell uniqueness stuff and the BUG, there should exist extended uniqueness cases.

I'm not sure if these have been proposed or noticed yet. The following should also qualify as a multi-solution deadly pattern where uniqueness deductions could apply.
Code: Select all
 .   .   ab  |  bc  .  .  |  ac  .   .
 .   .   .   |  .   .  .  |  .   .   .
 .   .   ab  |  bc  .  .  |  ac  .   .

If you place an extra candidate, x, in any of the lettered cells, that candidate must be true in order to have a unique solution.

You can keep on extending this as well, so long as you follow the BUG rule within your pattern; i.e. every candidate in your pattern cells if it exists in a group, must show up twice in that group. Consider only the pattern cells in the group when applying this rule. For example, this is another deadly pattern...
Code: Select all
 .   .   ab  |  bc  .  ad  |  cd  .   .
 .   .   .   |  .   .  .   |  .   .   .
 .   .   ab  |  bc  .  ad  |  cd  .   .

...and so is this one...
Code: Select all
 .   .   ab  |  bc  .  .  |  .   .   ca
 .   .   .   |  .   .  .  |  .   .   .
 .   .   ab  |  bc  .  .  |  ca  .   .
-------------+------------+------------
 .   .   .   |  .   .  .  |  ca  .   ca
 .   .   .   |  .   .  .  |  .   .   .
 .   .   .   |  .   .  .  |  .   .   .


...but, not this one (the c candidate only shows up once in cols 7 & 9 in the pattern cells)...
Code: Select all
 .   .   ab  |  bc  .  .  |  .   .   cd
 .   .   .   |  .   .  .  |  .   .   .
 .   .   ab  |  bc  .  .  |  cd  .   .
-------------+------------+------------
 .   .   .   |  .   .  .  |  ad  .   ad
 .   .   .   |  .   .  .  |  .   .   .
 .   .   .   |  .   .  .  |  .   .   .

You can kind of envision some of these patterns as mated xy-chains, or a cycle pattern that obeys the BUG rules.

You can get some interesting uniqueness cases out of these, for example...
Code: Select all
 .   .   ab  |  bcx .  adx |  cd  .   .
 .   .   .   |  .   .  .   |  .   .   .
 .   .   ab  |  bcx .  adx |  cd  .   .

...here, you can remove x from all of the unlettered cells in the center box, because you know that x must be true in one of the lettered cells to avoid multiple solutions.

[edit: added BUG's two-or-none rule for pattern building & substituted term "deadly pattern" for "uniqueness setup."]
Last edited by Myth Jellies on Sat Feb 04, 2006 6:40 am, edited 5 times in total.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Myth Jellies » Tue Jan 31, 2006 12:27 pm

Here is a good one from the AUR thread.

Code: Select all
 7   589  59  | 6   259  258 | 3   4    1
 18  4    6   | 35  357  18  | 257 9    25
 2   1359 1359| 579 4    15  | 6   8    57   
--------------+--------------+--------------
 19  169  7   | 4   259  3   | 25  256  8
 389 389  4   | 259 6    25  | 1   2357 257
 5   36   2   | 8   1    7   |*49  36  *49
--------------+--------------+--------------
*169 2    159 | 157 8   *46  |*49  57   3
*369 7    359 | 235 235 *46  | 8   1   *49
 4   135  8   | 135 357  9   | 257 25   6


There is an extended uniqueness setup in the 96-64-49's of the starred cells. In order to avoid multiple solutions, either r7c1 = 1 or r8c1 = 3. Since the 6's are locked in those two cells, whichever one is the 1 or the 3, the other must be a 6. Therefore we can eliminate the 9's from r78c1. This locks the 9's in box 7 column 3 and the puzzle solves easily from there.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby vidarino » Tue Jan 31, 2006 12:50 pm

Darn it, I was going to make a post about this yesterday, but was hijacked by offline duties before I got around to it. ;)

I was working on a puzzle and came across a two-column "ab | bc . . | ac" formation with exactly one extra candidate, and placing that basically solved the puzzle.

Of course I can't seem to find it again now (it was randomly picked from my database), but if I find it again, I'll post it here as a less convoluted example.:)

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby Myth Jellies » Wed Feb 01, 2006 3:48 am

vidarino wrote:Darn it, I was going to make a post about this yesterday, but was hijacked by offline duties before I got around to it....


:)No excuses, Vidar, you probably get up about 10 hours before I do. That should be enough of a head start!:)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Myth Jellies » Thu Feb 02, 2006 8:48 am

Here is one from the BUG thread.

Code: Select all
+-----------------+----------------+----------------+
| 7    49    6    | 5    1    3    | 48   489  2    |
|*14  *14+39 2    | 8    6    49   | 7    5    349  |
| 5    349   8    | 7    49   2    | 34   1    6    |
+-----------------+----------------+----------------+
| 3    6     7    | 9    2    5    | 148  48   14   |
| 9    2     5    | 4    8    1    | 36   367  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    347  347  |
+-----------------+----------------+----------------+


The starred cells highlight two mated 14-48-81 chains which form an extended uniqueness deadly pattern. Since the 1's are locked in the starred box 1 cells, we know that r2c2 = 39 and r2c1 = 1 which blows the puzzle to pieces.

Another convoluted extended uniqueness monster from the same BUG thread...
Code: Select all
+----------------+----------------+-----------------+
| 9    6    8    | 24   7    24   | 3    5    1     |
|*57   3    4    | 8    1   *56   | 9    2   *67    |
|*57   1    2    |*56   3    9    | 4   *67   8     |
+----------------+----------------+-----------------+
| 13   28   9    | 247  248  1247 | 6    38   5     |
| 4    7   *56   | 3    89  *56   | 28   1    29    |
| 13   28  *56   |*56   289  12   | 7    389  4     |
+----------------+----------------+-----------------+
| 2    59   1    | 79   6    38   | 58   4    37    |
| 8    59   3    | 1    24   247  | 25  *67  *67+29 |
| 6    4    7    | 29   5    38   | 1    89   239   |
+----------------+----------------+-----------------+

Here the starred cells highlight mated 65-57-76 uniqueness chains. The locked 6's in the starred box 9 cells should lead to an easy puzzle solution with r8c9 = 29 and r8c8 = 6.
Last edited by Myth Jellies on Thu Feb 02, 2006 5:34 am, edited 1 time in total.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Jeff » Thu Feb 02, 2006 9:34 am

Very well, MJ.:D So, is this a "Partial BUG" or a "uniquiness pattern type n"?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Myth Jellies » Thu Feb 02, 2006 10:03 am

I would definitely call these extended uniqueness patterns rather than partial BUG; mainly because you would probably search for these patterns in the same way you search for two-candidate deadly patterns. If the one candidate changes, you just have to continue on to see if it gets back to that original candidate. These BUG thread examples would simply be type 1 extended uniqueness, while the first puzzle example would be type 4 extended uniqueness.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Jeff » Thu Feb 02, 2006 11:57 am

Hi MJ, Correct me if I am wrong. I got a feeling that there should be a couple rules governing these extended uniqueness patterns.

  • All nodes of a bivalue locked set must be included in the BUG chain.
  • All bivalue locked set in the BUG chain must appear in each unit of the BUG chain.
Otherwise, it would just be a continuous xy-chain, which is not qualified for consideration of uniqueness.
Last edited by Jeff on Thu Mar 16, 2006 7:18 pm, edited 1 time in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Myth Jellies » Thu Feb 02, 2006 12:09 pm

Code: Select all
 7    49   6   | 5    1    3   | 48   489  2   
 1   *39   2   | 8    6   *49  | 7    5    349
 5   *39+4 8   | 7   *49   2   | 34   1    6   
---------------+---------------+----------------
 3    6    7   | 9    2    5   | 148  48   14 
 9    2    5   | 4    8    1   | 36   367  37 
 4    8    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 
 8    1    39  | 2   *49   6   | 5   *34+7 347


Oops! As the above grid shows, you can't have a pairing that shows up only on diagonals like the 49 in the above grid. Neither r3c2 = 4 nor r9c8 = 7 are valid moves in this grid. Thus the pattern below is not a deadly patterns because the cd pair only show up on a diagonal and not ever in the same row/column within a box.
Code: Select all
 .   .   ab  |  bc  .  .  |  .   .   cd
 .   .   .   |  .   .  .  |  .   .   .
 .   .   ab  |  bc  .  .  |  cd  .   .
-------------+------------+------------
 .   .   .   |  .   .  .  |  ad  .   ad
 .   .   .   |  .   .  .  |  .   .   .
 .   .   .   |  .   .  .  |  .   .   .
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Myth Jellies » Thu Feb 02, 2006 1:11 pm

Jeff wrote:Hi MJ, Correct me if I am wrong. I got a feeling that there should be a couple rules governing these extended uniqueness patterns.

  • All nodes of a bivalue locked set must be included in the BUG chain.
  • All links between nodes in the BUG chain must be either in row units (horizontal) or column units (vertical).
Otherwise, it would just be a continuous xy-chain, which is not qualified for consideration of uniqueness.


Yeah, my previous post illustrates that we can't be too cavalier. We know that the following is a six cell uniqueness deadly pattern...
Code: Select all
 .   .   .   |  ab  .  .  |  .   .   ab
 .   .   .   |  .   .  .  |  .   .   .
 .   .   .   |  ab  .  .  |  ab  .   .
-------------+------------+------------
 .   .   .   |  .   .  .  |  ab  .   ab
 .   .   .   |  .   .  .  |  .   .   .
 .   .   .   |  .   .  .  |  .   .   . 


One might reason that you could extend that to the pattern
Code: Select all
 .   .   ac  |  bc  .  .  |  .   .   ab
 .   .   .   |  .   .  .  |  .   .   .
 .   .   ac  |  bc  .  .  |  ab  .   .
-------------+------------+------------
 .   .   .   |  .   .  .  |  ab  .   ab
 .   .   .   |  .   .  .  |  .   .   .
 .   .   .   |  .   .  .  |  .   .   .

Even though this seems to work so long as I don't leave a pure diagonal pairing, it is quite possible that I have just been lucky. Have to review what makes a deadly pattern deadly, I guess. I will put this one on probation until I either come up with a proof for it, or it is disproven by a counter-example.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Myth Jellies » Thu Feb 02, 2006 1:44 pm

I think the rule needs to be similar to that for the BUG grid; i.e. in just the base pair cells and only considering the base pair candidates, if a candidate shows up in a group, it must show up exactly twice.

This grid
Code: Select all
 .   .   ac  |  bc  .  .  |  .   .   ab
 .   .   .   |  .   .  .  |  .   .   .
 .   .   ac  |  bc  .  .  |  ab  .   .
-------------+------------+------------
 .   .   .   |  .   .  .  |  ab  .   ab
 .   .   .   |  .   .  .  |  .   .   .
 .   .   .   |  .   .  .  |  .   .   .

and all the good examples so far, satisfy this deadly pattern rule.

In the counter example post above, and in the pattern below, this rule is not satisfied.
Code: Select all
 .   .   ab  |  bc  .  .  |  .   .   cd
 .   .   .   |  .   .  .  |  .   .   .
 .   .   ab  |  bc  .  .  |  cd  .   .
-------------+------------+------------
 .   .   .   |  .   .  .  |  ad  .   ad
 .   .   .   |  .   .  .  |  .   .   .
 .   .   .   |  .   .  .  |  .   .   .


So maybe this should be renamed BUG-Light:D
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby tarek » Thu Feb 02, 2006 1:54 pm

To add to the Extended theory,

It seems that the rectangles can be actually QUADRANGLES (when sharing 2 boxes & 2 lines)
User avatar
tarek
 
Posts: 2529
Joined: 05 January 2006

Postby aeb » Fri Feb 03, 2006 1:52 am

Myth Jellies wrote:I think the rule needs to be similar to that for the BUG grid; i.e. in just the base pair cells and only considering the base pair candidates, if a candidate shows up in a group, it must show up exactly twice.
... So maybe this should be renamed BUG-Light:D


Maybe what you want to do is what I called the local BUG principle on
http://homepages.cwi.nl/~aeb/games/sudoku/solving15.html ?
aeb
 
Posts: 83
Joined: 29 January 2006

Re: Between Uniqueness and BUG: The Extended Uniqueness Theo

Postby Moschopulus » Fri Feb 03, 2006 11:58 am

Myth Jellies wrote:Theoretically speaking...between our simple 4 cell uniqueness stuff and the BUG, there should exist extended uniqueness cases.

I'm not sure if these have been proposed or noticed yet. The following should also qualify as a multi-solution deadly pattern where uniqueness deductions could apply.
Code: Select all
 .   .   ab  |  bc  .  .  |  ac  .   .
 .   .   .   |  .   .  .  |  .   .   .
 .   .   ab  |  bc  .  .  |  ac  .   .




Any unavoidable set gives rise to a uniqueness criterion. There are thousands of unavoidable sets, and so there are thousands of uniqueness criteria.

There is one unavoidable set of size 4, called the uniqueness rectangle here.
12.......
.........
.........
21.......

There are four types of unavoidable sets of size 6:

Code: Select all
12.......
.........
.........
2.1......
.........
.........
.12......
.........
.........

12.......
.........
.........
23.......
.........
.........
31.......
.........
.........

123......
.........
.........
231......
.........
.........
.........
.........
.........

12.......
.........
.........
2..1.....
.1.2.....
.........
.........
.........
.........


There are nine types of unavoidable set of size 8:

Code: Select all
T1
-----------
1..|2..|3..
.2.|3..|1..
...|...|...
-----------
21.|
...|
...|
-----------

T2
-----------
1..|2..|...
.2.|...|1..
...|1..|2..
-----------
21.|
...|
...|
-----------

T3
-----------
1..|2..|...
.2.|1..|...
...|...|...
-----------
2..|.1.|
.1.|.2.|
...|...|
-----------

T4
-----------
1..|2..|...
.2.|1..|...
...|...|...
-----------
2..|...|1..
.1.|...|2..
...|...|...
-----------

T5
-----------
1..|2..|...
.2.|.1.|...
...|...|...
-----------
2..|1..|
.1.|.2.|
...|...|
-----------

T6
-----------
12.|3..|...
..3|1..|...
...|...|...
-----------
231|
...|
...|
-----------

T7
-----------
1..|2..|4..
2..|3..|...
3..|4..|1..
-----------

T8
-----------
12.|3..|4..
34.|2..|1..
...|...|...
-----------

T9
-----------
12.|4..|...
34.|1..|...
...|...|...
-----------
23.|
...|
...|
-----------


We discussed these over on the pseudo-puzzles thread:

http://forum.enjoysudoku.com/viewtopic.php?t=2747

Ocean and Red Ed did a lot of work in classifying the small ones.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Re: Between Uniqueness and BUG: The Extended Uniqueness Theo

Postby ronk » Fri Feb 03, 2006 5:38 pm

Myth Jellies wrote:The following should also qualify as a multi-solution deadly pattern where uniqueness deductions could apply.
Code: Select all
 .   .   ab  |  bc  .  .  |  ac  .   .
 .   .   .   |  .   .  .  |  .   .   .
 .   .   ab  |  bc  .  .  |  ac  .   .

If you place an extra candidate, x, in any of the lettered cells, that candidate must be true in order to have a unique solution.

A real live example from #1151 of the top1465:
Code: Select all
 .32|...|.6.
 ...|6.9|...
 9..|2..|.43
 ---+---+---
 7..|.84|9..
 ..4|...|..6
 .5.|.1.|...
 ---+---+---
 .9.|8..|...
 .2.|..3|7..
 5..|...|.9.


 1     3     2     | 47    47    8     | 5     6     9
 8     4     5     | 6     3     9     | 2     17    17
 9    *67   *67    | 2     5     1     | 8     4     3
-------------------+-------------------+------------------
 7    *16   *16    | 35    8     4     | 9     235   25
 3     8     4     | 579   279   257   | 1     57    6
 2     5     9     | 37    1     6     | 34    378   478
-------------------+-------------------+------------------
 46    9     137   | 8     2467  257   | 346   1235  1245
 46    2     18    | 1459  469   3     | 7     158   1458
 5    *17   *1378  | 147   2467  27    | 346   9     1248

Valid eliminations are r9c3<>1 and r9c3<>7.

[edit: Deleted references to an invalid UR(46) type 3.]
Last edited by ronk on Sat Feb 04, 2006 9:38 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4691
Joined: 02 November 2005
Location: Southeastern USA

Next

Return to Advanced solving techniques

cron