Uniqueness chains

Advanced methods and approaches for solving Sudoku puzzles

Uniqueness chains

Postby RW » Thu Mar 16, 2006 4:40 pm

I can see that there's been some discussion about techniques that depend uniqueness on this forum. These are techniques that depend on the fact that a puzzle has only one solution. Most discussions have been about the uniqueness square, or some special occassions of more than two pairs linked in a chain. Seems to me that nobody has been able to define any set of comprehensive rules that would apply to all of these chains, so this might be something new.

Uniqueness chains

A uniqueness chain is a chain of any number of non-given numberpairs, whose placings are only determined by other members of the chain, and therefore can be reversed without affecting the rest of the puzzle. The appearance of any such chain can, and must, safely be prevented from happening in any puzzle with one unique solution.

The chains can be built out of three different straight chains that can be combined with cornerblocks. The three different straight chains are:

A) Two pairs (also known as uniqueness squares):

Code: Select all
.. .. ab|ab .. ..
.. .. ab|ab .. ..
.. .. ..|.. .. ..


B) Three pairs with three different numbers:

Code: Select all
.. .. ab|ac .. ..|.. bc ..
.. .. ab|ac .. ..|.. bc ..
.. .. ..|.. .. ..|.. .. ..


C) Three pairs with two different numbers:

Code: Select all
.. .. ab|ab .. ..|.. .. ..
.. .. ab|.. .. ..|.. ab ..
.. .. ..|ab .. ..|.. ab ..


The last applies to any situation where two numbers a and b are would be forced into the same column in each of three boxes next to each other or the same row in each of three boxes on top of each other:

[edit: in all my examples UPPER case letters represent GIVENS and lower case letters possible candidates.]
Code: Select all
*--------------------------*
|.. .. ab|ab .. ..|.. ab ..|
|.. .. ab|ab .. ..|.. ab ..|
|.. .. ab|ab .. ..|.. ab ..|
|--------------------------*
| A .. ..|.. .. ..| B .. ..|
|..  B ..|..  A ..|.. .. ..|
|.. .. ..|.. ..  B| A .. ..|
|--------------------------|
| B  A ..|.. .. ..|.. .. ..|
|.. .. ..|..  B ..|.. ..  A|
|.. .. ..|.. ..  A|.. ..  B|
*--------------------------*


Any placement of numbers a and b would eventually lead to a situation similar to C) => the situation cannot come up in any valid puzzle.

The cornerblock is a box that contains a diagonal pair that acts as a link in both chains.

D) Two 2-pair chains connected:

Code: Select all
ab .. ab|.. .. ..
.. .. ..|.. .. ..
.. .. ..|.. .. ..
-----------------
ab .. ..|.. .. ab
.. .. ..|.. .. ..
.. .. ab|.. .. ab


E) Two 3-pair chains connected:
Code: Select all
*--------------------------*
|ab .. ab|.. .. ..|.. .. ..|
|.. .. ..|.. .. ..|.. .. ..|
|.. .. ..|.. .. ..|.. .. ..|
|--------------------------*
|.. .. ..|.. .. ..|.. .. ..|
|.. .. ab|.. .. ac|bc .. ..|
|.. ab ..|.. .. ac|bc .. ..|
|--------------------------|
|.. .. ..|.. .. ..|.. .. ..|
|.. .. ..|.. .. ..|.. .. ..|
|ab ab ..|.. .. ..|.. .. ..|
*--------------------------*

As we can see from figure E), cornerblocks may connect chains of different types and may connect chains involving different numbers. We can also see that a cornerblock may exist in the middle of a chain.

What we are interested about as solvers are chains that are almost completed:
F)
Code: Select all
*--------------------------*
|..  A ..|.. .. ..| B .. ..|
|..  B ..|.. .. ..|..  A ..|
|.. .. ..|..  A  B|.. .. ..|
|--------------------------*
|ab .. ab|.. .. ..|.. .. ..|
| X ..  X| A .. ..|.. .. ..|
|.. .. ..| B .. ..| A .. ..|
|--------------------------|
| X .. ab|.. .. ..|..  X ab|
|.. .. ..|..  B  A|.. .. ..|
|ab ..  X|.. .. ..|..  b ab|
*--------------------------*

In the example above (x stands for any number other than a or b) the uniqueness chain is only one step from forming. All members except one, the b in box 9, are already forced into position. In this case we can safely remove b as a candidate in (7,9)* and (9,9) as this is the only way to prevent the chain from forming.

*I define squares (row,column), (7,9) = r7c9

Before we look at more complicated situations, we must make some further observations about the pairs in a chain.The pairs can be divided into strong links and weak links. A strong link is a link that cannot break the uniqueness chain, the candidates are already forced into place. A weak link has at least one optional solution. In example F) boxes 4 and 7 contained strong links, leaving only one weak link in box 9 => We solved it by breaking the chain at the weak link.

At the end of the chain or in the middle of a straight three pair chain a strong link occurs when the two digits involved are forced into a pair in the same column/row (or any three spaces within the same row/column if the chain is of type C)). This means that any pair within the same row/column inside a box is a potentional strong link in an uniqueness chain. The most common use of this technique is when we have one such pair formed and we can see that a inserting a number at some certain point of the puzzle would lead to another strong link of the same numbers forming against it, completing a two pair uniqueness chain => we can rule out that option.

In a cornerblock a strong link occurs when the two digits involved are forced into a 2x2 area that coinsides with the chains on both sides. To explain this I’ll bring back example F) but this time I’ll remove the X:s from boxes 7 and 9:
G)
Code: Select all
*--------------------------*
|..  A ..|.. .. ..| B .. ..|
|..  B ..|.. .. ..|..  A ..|
|.. .. ..|..  A  B|.. .. ..|
|--------------------------*
|ab .. ab|.. .. ..|.. .. ..|
| X ..  X| A .. ..|.. ..  b|
|.. .. ..| B .. ..| A .. ..|
|--------------------------|
|ab .. ab|.. .. ..|..  b ab|
|.. .. ..|..  B  A|.. .. ..|
|ab .. ab|.. .. ..|..  b ab|
*--------------------------*


Now we have a number of different placements for a and b in box 7. First of all, the available candidates do not require them to be diagonal. But, placing them in the same row would complete a 2-pair uniqueness chain with the pair of row 4. Placing them in the same column is impossible, as that would force both numbers a and b into the same square of box 4. This leaves us with two possible diagonal placings, both of which would satisfy the uniqueness chain, if it was completed => the corner block is a strong link. Once again we only have one weak link, box 9. This time we can’t tell exactly where to place the b in box 9, but we can rule it out from (7,9) and (9,9), leaving (5,9) as the only available candidate b in column 9.

If the cornerblock links a chain of type C) to a chain of type A) or B), the strong link occurs if the candidates are forced into a 2x3 area that coincide with the two chains:
H)
Code: Select all
*--------------------------*
|ab ab ab| C .. ..|.. .. ..|
|.. .. ..|..  A ..|.. ..  B|
|.. .. ..| B .. ..|..  A  C|
|--------------------------*
|.. .. ..|.. ..  B| c ..  A|
|ab ab ab|.. .. ac|bc .. ..|
|ab ab ab|.. .. ac|bc .. ..|
|--------------------------|
|.. .. ..| A .. ..|..  B ..|
|.. .. ..|..  B ..| A  C ..|
|ab ab ab|..  C ..|.. .. ..|
*--------------------------*


In this example there is a lot of different possibilities for a and b in square 4. However, we can rule out the possibility of them being in the same column, as this would complete a 2-pair uniqueness-chain between boxes 1 and 7 (and a 3 pair uniqueness chain with boxes 4 and 5 if it was completed). We can also rule out the possibility of them being in the same row , as this would complete a type C) uniqueness chain with boxes 1 and 7. This leaves us with 6 different diagonal options, all of which would satisfy an uniqueness chain similar to figure E) if it was completed => box 4 is a strong link => there is only one weak link in the chain, which can only be broken by placing c in (4,7).

A cornerblock connecting two type C) chains is always a strong link, as it is enough that you get the 2 candidates forced into a 3x3 area of the box. This tells us that we have enough information here to solve b in box 9:
I)
Code: Select all
*-----------*
|...|.A.|B..|
|...|...|...|
|...|..B|.A.|
|-----------|
|...|...|...|
|...|...|...|
|...|...|...|
|-----------|
|...|...|A.X|
|...|.BA|...|
|...|...|..X|
*-----------*


This is basically all I’ve found out so far about the techinque. There is of course still some special situations, like the uniqueness circle that basicly consists of 4 cornerblocks.
J)
Code: Select all
ab .. ab|ab .. ab
.. .. ..|.. .. ..
ab .. ab|ab .. ab
-----------------
ab .. ab|ab .. ab
.. .. ..|.. .. ..
ab .. ab|ab .. ab


With this knowledge of strong and weak links we can tackle very long chains:
K)

Code: Select all
*-----------*
|..X|..A|..X|
|..A|...|..X|
|B..|..D|A.C|
|-----------|
|...|X..|.AX|
|...|.B.|.C.|
|...|A..|..X|
|-----------|
|.B.|.A.|C.D|
|..X|DX.|...|
|...|XX.|...|
*-----------*

This looks hopeless, so let’s write in the candidates:
L)
Code: Select all
*--------------------------*
|cd cd  X|bc ..  A|bd bd  X|
|cd cd  A|bc .. ..|bd bd  X|
| B .. ..|.. ..  D| A ..  C|
|--------------------------*
| d  d bc| X cd ..|bd  A  X|
|ad ad ..|..  B ..| d  C ..|
| d  d bc| A cd ..|bd bd  X|
|--------------------------|
|..  B ..|..  A ..| C ..  D|
|ac ac  X| D  X bc|.. .. ab|
|ac ac  D| X  X bc|.. .. ab|
*--------------------------*


This still looks hopeless, but let’s try to read it starting from box 9, going left. Here it is apparent that we have a type B) chain with one closed end and a cornerblock* at the other end. All links are strong. Looking up from box 7 tells us that we have another type B) chain with two strong cornerblocks at the end and one weak link in the middle. Now we are in box one and continue following the chain right. Here’s a third type B) chain starting and ending with a cornerblock, all links are strong. From box 3 we look down and see a weak cornerblock, which mean this is a type A) chain, both pairs are cornerblocks, one is weak. Going left again from box 6 we see a type B) chain that starts with this weak cornerblock and finally closes the chain at the end. Now we can conclude that we have a 10-pair uniqueness chain with eight strong links and two weak links.

Two weak links? How can we know where to break the chain? Well, in this case it is quite easy. First, remove candidate d from (6,7) as this would complete the bcd uniqueness chain in boxes 4-5-6. Now there is 3 possible squares left for d in box 7, two of which would make the link strong, (4,7) and (6,8). At this point we can see that placing d in any of those squares would, together with the d in box 5, also enforce the a-d link in box 4, thus completing the chain. Conclusion: If the link in box 6 is strong, all links in the chain are strong** => box 6 must be weak, we place d in (5,7). Quite a lot of work for one number, but that is still one number more than one could ever solve with any other technique.

* Of course, we don’t know yet that it is a cornerblock. It becomes a cornerblock only when we find that the chain continues. If we found that the chain doesn’t continue, it wouldn’t be a strong cornerblock, but a weak endingblock.

** The first step (removing d from (6,7)) was actually unnecessary, as it would also satisfy the final conclusion. We could have solved it directly by noticing that placing d in any square that satisfies the strong links in boxes 4 or 6, would force the d in the other of these boxes into the strong link as well. I removed the candidate only to focus your attention on one chain. In fact, placing d in (6,7) would lead to two completed uniqueness chains, one in boxes 4-5-6 and another in boxes 9-8-7-4-1-2-3.


That's it. Comments anybody?

I've made some related problems that can be found at http://www.sudoku.org.uk/discus/messages/1/679.html?1142353323 if anybody is interrested.
Last edited by RW on Sat Mar 18, 2006 1:35 pm, edited 2 times in total.
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Carcul » Thu Mar 16, 2006 5:05 pm

Hi RW.

First, welcome to this forum.
That description is very interesting, but, if I have understood correctly your post, some of us have already written about Unique Patterns (Unique Rectangles, Unique Loops, and others Unique Patterns) and Almost Unique Patterns. Personally, I have written this thread about Almost Unique Rectangles and this post about others Almost Unique Patterns. Recently, I have been using Almost Almost Unique Patterns (about which I intend to write a post, when I have some time). Myth Jellies and others have also written about others Unique Patterns (Bug-Lite and Mug-Lite). So, I don't see anything new in your description. Besides, it is always a good pratice to show a given theoretical idea with some real examples. You only show in your diagrams some complicated and hypothetical situations. Also, in some of your diagrams you show, in the same unit, more than two cells populated by the same two candidates, which looks strange.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby RW » Thu Mar 16, 2006 9:41 pm

Hi Carcul,

Thank you for your feedback. I looked through these examples you mentioned before posting, as you said there's been writings about Unique Rectangles, Unique Loops and Almost Unique Patterns. I read them all through more carefully again, but I still couldn't find any universal theory.

What I did find was a comment by Myth Jellies at http://forum.enjoysudoku.com/viewtopic.php?t=3056 , which wasn't followed up:

Myth Jellies wrote: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.


Correct me if I'm wrong, but I think I just answered this question. Any pattern of pairs where all candidates are forced into strong links of a uniqueness chain is a deadly pattern, because any possible solution would result in what you call a BUG.

I also noticed that you all talk about pairs, when uniqueness patterns can be derived from a lot more possible squares than just two within a unit. For example this pattern seems to have gone unnoticed:
C)
Code: Select all
*--------------------------*
|.. .. ab|ab .. ..|.. ab ..|
|.. .. ab|ab .. ..|.. ab ..|
|.. .. ab|ab .. ..|.. ab ..|
|--------------------------*
| A .. ..|.. .. ..| B .. ..|
|..  B ..|..  A ..|.. .. ..|
|.. .. ..|.. ..  B| A .. ..|
|--------------------------|
| B  A ..|.. .. ..|.. .. ..|
|.. .. ..|..  B ..|.. ..  A|
|.. .. ..|.. ..  A|.. ..  B|
*--------------------------*


Not to mention this pattern,

Code: Select all
*--------------------------*
|.. .. ..|..  A ..| B .. ..|
|ab ab ab|.. .. ..|.. .. ..|
|.. .. ..|.. ..  B|..  A ..|
|--------------------------*
|ab ab ab|ab .. ..|.. .. ab|
|ab ab ab|ab .. ..|.. .. ab|
|ab ab ab|ab .. ..|.. .. ab|
|--------------------------|
|.. .. ..|.. .. ..| A  B ..|
|.. .. ..|..  B  A|.. .. ..|
|ab ab ab|.. .. ..|.. .. ..|
*--------------------------*


where one link in the chain is a unit with all squares open for both candidates a and b, but no option could lead to an unique solution (example i from above if solved incorrectly, sorry about the typo in the original).

Carcul wrote:it is always a good pratice to show a given theoretical idea with some real examples. You only show in your diagrams some complicated and hypothetical situations.


I chose to do the diagrams by displaying the minimum amount of data required to find the solution, as this in my opinion is a lot clearer than putting up a full puzzle with all possibilities on display. I want to stress once more that I want to show a theory that unites all possible patterns, not just focus on some special case. Another reason is of course that I have never seen a chain longer than five pairs in an actual puzzle. All I can give right now is this example of a type C chain in action:

Code: Select all
*-----------*
|...|.19|..7|
|.3.|..5|1..|
|..1|6..|.9.|
|-----------|
|1.2|94.|..6|
|...|..1|...|
|39.|5.2|418|
|-----------|
|.4.|.56|2.1|
|.1.|72.|.8.|
|52.|19.|...|
*-----------*


Pardon me for not writing in all the candidates, I'm the oldschool kind of guy who only solve in ink keeping all the candidates inside my head, freak out if the paper (or screen) is full of small numbers... But I'll talk you through this, it is very simple.

Either r8c6 or r9c6 has to be 4 => r1c4 and r2c4 contains a 2-4 pair. This also leads to a 2-4 pair in r3c1 and r3c9 (only left in row). R2c9 is also either 2 or 4 (only possible numbers for square). Now we have these 5 squares that must contain either 2 or 4:
Code: Select all
*--------------------------------*
|..  ..  ..|*24  1   9|..  ..   7|
|..   3  ..|*24 ..   5| 1  .. *24|
|*24 ..   1| 6  ..  ..|..   9 *24|
|--------------------------------|
| 1  ..   2| 9   4  ..|..  ..   6|
|..  ..  ..|..  ..   1|..  ..  ..|
| 3   9  ..| 5  ..   2| 4   1   8|
|--------------------------------|
|..   4  ..|..   5   6| 2  ..   1|
|..   1  ..| 7   2  ..|..   8  ..|
| 5   2  ..| 1   9  ..|..  ..  ..|
*--------------------------------*


We can see that either number 2 or number 4 in box 1 has to go in another column than column 1, otherwise we would have a deadly pattern. Number 2 must go in column one, therefore we can remove candidate 4 from r3c1.

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

Postby Ruud » Thu Mar 16, 2006 10:20 pm

Hi RW,

a little help from a "new school" kinda guy. This is the moment the cycle is appearing:

Code: Select all
.---------------.---------------.---------------.
|*248  6    45  |*24   1    9   | 358  2345 7   |
| 79   3    79  |*24   8    5   | 1    6   *24  |
|*24   58   1   | 6    3    7   | 58   9   *24  |
:---------------+---------------+---------------:
| 1    578  2   | 9    4    38  | 357  35   6   |
| 48   578  45  | 38   6    1   | 3579 235  2359|
| 3    9    6   | 5    7    2   | 4    1    8   |
:---------------+---------------+---------------:
| 79   4    789 | 38   5    6   | 2    37   1   |
| 6    1    3   | 7    2    4   | 59   8    59  |
| 5    2    78  | 1    9    38  | 6    347  34  |
'---------------'---------------'---------------'


In my opinion, this is what we used to call a type-1 Unique Swordfish. Digit 8 in r1c1 cannot be removed, so it must be placed.

I've seen better examples, this one dissolves in a few steps...

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby Carcul » Thu Mar 16, 2006 11:23 pm

Hi RW.

RW wrote:All I can give right now is this example of a type C chain in action:


Nice puzzle, but...

RW wrote:Pardon me for not writing in all the candidates, I'm the oldschool kind of guy who only solve in ink keeping all the candidates inside my head, freak out if the paper (or screen) is full of small numbers...


...perhaps that's the reason why you haven't noticed that your puzzle only need naked and hidden singles, locked candidates, and naked pairs and triples to be solved, nothing more complicated than that: we don't need to invoque uniqueness to solve it.

RW wrote:For example this pattern seems to have gone unnoticed:


Those patterns are not unnoticed for me, but I think they are extremely hard to find/use in a puzzle. But, as you seem to like these kind of patterns and don't show us any "real" one, and as I am a nice guy, I will leave the following puzzle for you as an exercise,

Code: Select all
 *-----------*
 |5..|..1|..8|
 |...|...|6..|
 |...|.62|57.|
 |---+---+---|
 |.9.|2.5|1..|
 |..4|.1.|3..|
 |..8|3.9|.2.|
 |---+---+---|
 |.76|98.|...|
 |..5|...|...|
 |8..|1..|..3|
 *-----------*

which I call "Eppstein Puzzle". In this puzzle there is, after the basic steps, an interesting "possible" unique pattern that can be used in a one step solution for the grid. Perhaps this is a good puzzle for you to show better the concept of "Uniqueness Chains".

RW wrote:Correct me if I'm wrong, but I think I just answered this question.


In that case I need to read your post more carefully, because I still don't get the new thing that you have introduced.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby Jeff » Thu Mar 16, 2006 11:47 pm

RW wrote:
Myth Jellies wrote: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.

Correct me if I'm wrong, but I think I just answered this question. Any pattern of pairs where all candidates are forced into strong links of a uniqueness chain is a deadly pattern, because any possible solution would result in what you call a BUG.

Hi RW, it appears that you didn't read on after MJ had made the above statement in response to my comments. MJ made the above statement on Feb 2nd, and the issue was resolved on Feb 3rd. The final product is called BUG-Lite and has been included in the first post of the BUG thread as a member of the BUG family.

By the way, similar to BUG, BUG-Lite considers bivalue locked sets (not just pairs) within each unit. However, your notion that a uniqueness pair can be in more than just two cells within a unit is quite interesting.:D Be good if you can give us a real example on that. Thanks
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby vidarino » Fri Mar 17, 2006 12:07 am

Speaking of BUG-Lites and Uniqueness patterns, here's a little beauty I spotted recently;

Code: Select all
 56   *456   8     |  7     1    *46    |  2     9     3
 37    37   *46    | *46    9     2     |  1     8     5
 2     1     9     |  3     58    58    |  4     6     7
-------------------+--------------------+--------------------
 16   *456   2     | *46    7     9     |  3     15    8
 136  -3456 *456   |  8     2    *46    |  7     15    9
 8     9     7     |  5     3     1     |  6     2     4
-------------------+--------------------+--------------------
 4     58    1     |  2     58    3     |  9     7     6
 9     5678  56    |  1     4     578   |  58    3     2
 57    2     3     |  9     6     578   |  58    4     1


Note the starred 46'es forming a dangerous loop. However, three of them (R1C2, R4C2 and R5C3) have an extra 5, one of which must be true. Therefore we can safely eliminate the 5 in R5C2, since it can see all of the extras.

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby RW » Fri Mar 17, 2006 10:21 am

Thank you for all the replies, I'll read them through more carefully when later when I have more time.

vidarino wrote:Note the starred 46'es forming a dangerous loop.

That's a good example of what I referred to above as a uniqueness circle:

Code: Select all
ab .. ab|ab .. ab
.. .. ..|.. .. ..
ab .. ab|ab .. ab
-----------------
ab .. ab|ab .. ab
.. .. ..|.. .. ..
ab .. ab|ab .. ab

Note that the pattern would still apply, even if r1c4, r5c4, r2c6 and r4c6 weren't solved yet.

Get back to your other answers later.

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

Postby RW » Fri Mar 17, 2006 5:27 pm

I suddenly realised that I've been trying to define any uniqueness pattern starting from the wrong end. A uniqueness chain, or bug-lite, as you call it is not defined by candidates in empty squares, but by numbers already on the grid. Here's my theory:

Code: Select all
If all appearances of n numbers (2>1) together fill a space that defines a bug  (appear 2 times in each unit they occupy), then the remaining appearances of these numbers will also form a bug.


[edit: Changed 'n' to '2' as there is no need to consider larger groups.]

And here's the proof:

Code: Select all
In any sudoku all numbers appear once in each row, column and box. This means that any group G of 2 different numbers fills 2 spaces in each of the 9 rows, columns and boxes. Removing any amount k of groups G where all the instances can be defined by k columns, rows and boxes, will leave us with 9-k columns, rows and boxes, where each unit will have exactly 2 spaces reserved for the 2 numbers of group G.


That was complicated, an example to show what I mean:

The least amount of data we need to make a reduction based on uniqueness is this:

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


Assume these are the only given, or logically solved, instances of numbers 1 and 2 on the grid. If we placed number 2 in r1c4, then we would have two numberpairs that can be defined by two rows (1 and3) two columns (1 and 4) and 2 boxes (1 and 2). That means that in each other unit left on the grid there has to be exactly two spaces reserved for numbers 1 and 2, which in the end will lead to a bug => we can safely remove candidate 2 from r1c4.

Do you aprove? Object? Know this already?

-RW
Last edited by RW on Sun May 28, 2006 2:42 pm, edited 2 times in total.
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby vidarino » Fri Mar 17, 2006 5:45 pm

RW wrote:
Code: Select all
1..|...|...
...|...|...
2..|1..|...
-----------
...|...|...
...|...|...
...|...|...
-----------
...|...|...
...|...|...
...|...|...


Assume these are the only given, or logically solved, instances of numbers 1 and 2 on the grid. If we placed number 2 in r1c4, then we would have two numberpairs that can be defined by two rows (1 and3) two columns (1 and 4) and 2 boxes (1 and 2). That means that in each other unit left on the grid there has to be exactly two spaces reserved for numbers 1 and 2, which in the end will lead to a bug => we can safely remove candidate 2 from r1c4.

Do you aprove? Object? Know this already?


Ah, but the 2 can only safely be removed from R1C4 if and only if none of the other cells (R1C1, R3C1, R3C4) were given as initial clues for the puzzle. Because if one or more of them were given, if would eradicate the potential ambiguity of the pattern.

There is a thread (started by yours truly:) ) about a very similar situation here.

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby RW » Fri Mar 17, 2006 8:51 pm

vidarino wrote:Ah, but the 2 can only safely be removed from R1C4 if and only if none of the other cells (R1C1, R3C1, R3C4) were given as initial clues for the puzzle. Because if one or more of them were given, if would eradicate the potential ambiguity of the pattern.


Vidarino,

I'm sorry, but you seem to have misunderstood. What I'm talking about here is actually the exact opposite to what you mentioned in your tread. You could call it a reverse BUG if you like. I'm saying that if all given, or solved instances of a group of numbers in the grid form a pattern similar to a Bug (or a MUG, Multivalue Universal Grave, is there such a term?) then all the missing numbers of that group will also form a Bug.

I repeat the problem, this time with a 2 inserted in the forbidden square and all the candidates out:

Code: Select all
*--------------------------*
| 1 .. ..| 2 .. ..|.. .. ..|
|.. .. ..|.. .. ..|12 12 12|
| 2 .. ..| 1 .. ..|.. .. ..|
|--------------------------|
|.. 12 12|.. 12 12|12 12 12|
|.. 12 12|.. 12 12|12 12 12|
|.. 12 12|.. 12 12|12 12 12|
|--------------------------|
|.. 12 12|.. 12 12|12 12 12|
|.. 12 12|.. 12 12|12 12 12|
|.. 12 12|.. 12 12|12 12 12|
*--------------------------*


If there is only these instances of numbers 1 and 2 in the grid, you may never find an unique solution. The problem is that as we can see there is 7 missing instances of numbers 1 and 2. These can go in 7 different rows, 7 different columns and 7 different boxes. This means that 2 squares in each unit must be reserved for them, which in the end would lead to a situation where you have 14 (1,2) pairs on the grid that form a BUG.

Code: Select all
*--------------------------*
| 1 .. ..| 2 .. ..|.. .. ..|
|.. .. ..|.. .. ..|12 12 ..|
| 2 .. ..| 1 .. ..|.. .. ..|
|--------------------------|
|.. 12 ..|.. .. ..|.. 12 ..|
|.. .. 12|.. .. 12|.. .. ..|
|.. .. ..|.. 12 ..|.. .. 12|
|--------------------------|
|.. .. ..|.. .. 12|12 .. ..|
|.. .. ..|.. 12 ..|.. .. 12|
|.. 12 12|.. .. ..|.. .. ..|
*--------------------------*

You may rearrange all these pairs in any way possible and still end up with a Bug.

What I am trying to say here is that you don't need to base your uniqueness solvingtechniques on empty squares and their possible candidates. Especially if there is lots of unsolved candidates in the grid they might be easier to spot based on numbers already solved or given. like in my example where we can predict an otherwise extremely complex 14-square Bug (or 7-pair uniqueness chain) by looking at three given numbers.

Did this make it any clearer?

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

Postby vidarino » Fri Mar 17, 2006 9:19 pm

Ah, sorry, I should have read your post more carefully. Apologies.

That's an interesting twist on uniqueness; Identifying patterns that would force a BUG elsewhere. I'm not sure I grasp it completely just yet, but it does appear to make sense.:)
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby RW » Fri Mar 17, 2006 9:56 pm

Here's an example:

Original puzzle:

Code: Select all
 *-----------*
 |...|9..|..4|
 |...|...|5..|
 |76.|.8.|...|
 |---+---+---|
 |2..|...|1..|
 |..1|2.9|..5|
 |..4|71.|9.2|
 |---+---+---|
 |1..|.4.|...|
 |..7|.25|8.1|
 |..2|1..|...|
 *-----------*


After the basic steps we have:
Code: Select all
 *--------------------------------------------------------------------------------------*
 | 358      12       358      | 9        3567     1236     | 2367     123678   4        |
 | 4        12       389      | 36       367      1236     | 5        1236789  36789    |
 | 7        6        359      | 45       8        1234     | 23       1239     39       |
 |----------------------------+----------------------------+----------------------------|
 | 2        9        368      | 45       356      3468     | 1        3678     3678     |
 | 368      7        1        | 2        36       9        | 346      3468     5        |
 | 3568     358      4        | 7        1        368      | 9        368      2        |
 |----------------------------+----------------------------+----------------------------|
 | 1        35       356      | 8        4        367      | 2367     235679   3679     |
 | 9        34       7        | 36       2        5        | 8        346      1        |
 | 3568     3458     2        | 1        9        367      | 3467     34567    367      |
 *--------------------------------------------------------------------------------------*



As you all can see there is a dangerous (1,2) uniqueness pattern lurking in boxes 1-3. Yes, this can be solved by the traditional uniqueness technique as this happens to be a common 3-pair Bug-lite (we can remove candidate 2 from r7c7). But, we can also look at the situation the other way around. Actually already in the starting grid we can see that r7c7 can't be number 2, as this would complete a bug pattern together with r4c1,r4c7,r5c3,r5c2,r6c5,r6c9,r7c1,r8c5,r8c9,r9c3 and r9c4. Of course, we could also apply the normal bug-lite technique already in the starting grid.

I agree that this is a bad example, as there is already so many instances of 1 and 2 out on the grid. As soon as I find a better one I'll post it. It seems to me that a reverse Bug would be at it's best when there is as few candidates as possible of the involved numbers out on the grid.
Last edited by RW on Sun May 28, 2006 2:44 pm, edited 1 time in total.
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Myth Jellies » Sat Mar 18, 2006 3:43 am

Code: Select all
*-----------*
|...|...|...|
|...|...|...|
|...|...|...|
|-----------|
|2..|...|1..|
|..1|2..|...|
|...|.1.|..2|
|-----------|
|1..|...|*..|
|...|.2.|..1|
|..2|1..|...|
*-----------*

Taking your example and cutting it down to what we really need to concern ourselves with.... We cannot place a 2 in the starred cell because if we do, we leave ourselves with an unavoidable BUG in the remaining unsolved boxes. This looks like a nice addition to the Uniqueness arsenal. Since you only concern yourself with solved cells, it should be very easy to spot.

Just to reword, I note that the solved cells and the deduction cell obey the exactly 2 or none per group rule. Or you can couple the other digit with the solved one and note that it satisfies the BUG-lite rule. That would be okay (and obviously true) for the entire puzzle, but it should be avoided in any partial solution of the puzzle which includes all solved candidates of that digit?

I think this could be very fruitful! How would you be able to use more than 2 digits and see this using only the solved cells? For example, can we say that the starred cell cannot equal 3 if we have shown all of the solved cells for 1, 2, and 3 in some of the cases below?

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

Code: Select all
*-----------*
|...|...|...|
|...|...|...|
|...|...|...|
|-----------|
|...|...|...|
|...|...|...|
|...|...|...|
|-----------|
|1..|2..|*..|
|3..|1..|...|
|2..|3..|1..|
*-----------*
[edit: doh, obviously the second one can't be 3 because of the other 1's and 3's]
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby RW » Sat Mar 18, 2006 10:52 am

Hi MJ

Myth Jellies wrote:How would you be able to use more than 2 digits and see this using only the solved cells?


I've been working on this problem too last night. My conclusion is that you can use it if, and only if, the amount n of numbers in your group occupies n spaces in every unit.

Your first example:
Code: Select all
*-----------*
|...|...|...|
|...|...|...|
|...|...|...|
|-----------|
|...|...|...|
|...|...|...|
|...|...|...|
|-----------|
|1..|2..|*..|
|...|...|...|
|2..|3..|1..|
*-----------*

would not work, as the three numbers only occupy two spaces in each column and box. Here's one example where we can see the relationship between GIVENS and non givens:

Code: Select all
*-----------*
|...|a.b|..c|
|..c|...|b.a|
|.ab|.c.|...|
|-----------|
|..a|...|.cb|
|c..|.b.|.a.|
|.b.|.ac|...|
|-----------|
|A..|B..|C..|
|.c.|..a|.b.|
|B..|C..|A..|
*-----------*

After solving all the other numbers we could have solved r5c1, r1c4 and r2c7 as only space left in column and r8c2, r8c6 and r8c8 as only space left in box. The other numbers could have been solved from these.

Here is a situation where it would apply:
Code: Select all
*-----------*
|A..|B..|..C|
|B..|.C.|..A|
|C..|..A|..B|
|-----------|
|...|...|...|
|...|...|...|
|...|ABC|...|
|-----------|
|...|...|...|
|...|...|...|
|...|CA*|...|
*-----------*

Here we could remove candidate b from r9c6 as this would complete a pattern where all numbers ABC occupy exactly three spaces in each unit. If b went in r9c6, then any solution
Code: Select all
*-----------*
|A..|B..|..C|
|B..|.C.|..A|
|C..|..A|..B|
|-----------|
|.ab|...|.c.|
|..c|...|ab.|
|...|ABC|...|
|-----------|
|.b.|...|ca.|
|.ca|...|b..|
|...|CAB|...|
*-----------*

would also occupy three spaces in each unit. This gives us 6 solutions as we could swap around number a, b and c in 6 ways. In this particular case we seem to get 24 solutions, at least I can't come up with a solution that wouldn't hold the two b-c uniqueness pairs.

I know that it is highly hypothetical that any situation involving three numbers came up in a puzzle, but if it did, we could solve it like this. A pattern that involves more than three numbers and would meet the requirements seems impossible to me, so I think my original rule should be refrased to (n=2 or 3). Agree?

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

Next

Return to Advanced solving techniques