Uniqueness chains

Advanced methods and approaches for solving Sudoku puzzles

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: 1010
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: 1010
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: 1010
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: 1010
Joined: 16 March 2006

Postby RW » Sat Mar 18, 2006 11:14 am

Myth Jellies wrote: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'm not sure if I understand you here, but I don't think there is any difference if the digits are solved or given. In my example you could remove two 1:s and one 2 and still have the same unique solution:
Code: Select all
*-----------*
|...|9..|..4|
|...|...|5..|
|76.|.8.|...|
|-----------|
|2..|...|1..|
|..1|*.9|..5|
|..4|7*.|9.2|
|-----------|
|1..|.4.|...|
|..7|.25|8.1|
|..2|*..|...|
*-----------*

In this case you would eventually solve these instances of one and two and then the original rule would apply, even if the pattern includes already solved numbers. In another case, say you solved number 2 in r1c2 by trial and error, the pattern would also apply. As long as all given instances are included in the potential reverse Bug pattern you may use this technique.

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

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

RW wrote:Here is a situation where it (more than 2 digits) would apply:
Code: Select all
*-----------*
|A..|B..|..C|
|B..|.C.|..A|
|C..|..A|..B|
|-----------|
|...|...|...|
|...|...|...|
|...|ABC|...|
|-----------|
|...|...|...|
|...|...|...|
|...|CA*|...|
*-----------*


Unfortunately, I don't think this is an improvement over two digits, because...
Code: Select all
*-----------*
|A..|B..|...|
|B..|...|..A|
|...|..A|..B|
|-----------|
|...|...|...|
|...|...|...|
|...|AB.|...|
|-----------|
|...|...|...|
|...|...|...|
|...|.A*|...|
*-----------*

...this alone should be enough to prevent you from placing B in the starred cell, correct? I think you ran into the same thing I did in my second pattern attempt.:)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby RW » Sat Mar 18, 2006 12:37 pm

Myth Jellies wrote:I think you ran into the same thing I did in my second pattern attempt.


Just realised my mistake and came back to correct it, but you were there first... It seems like we won't need to consider reverse bugs with more than two numbers, as these can always be defined by numberpairs alone. In my solution above:
Code: Select all
*-----------*
|A..|B..|..C|
|B..|.C.|..A|
|C..|..A|..B|
|-----------|
|.ab|...|.c.|
|..c|...|ab.|
|...|ABC|...|
|-----------|
|.b.|...|ca.|
|.ca|...|b..|
|...|CAB|...|
*-----------*

the non given can also be broken down into three diferent two-digit bug patterns. So, yes you are right, there is no improvement over two digits. My original theorem should be rewritten as:
Code: Select all
If all appearances of two numbers (a,b) 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.


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

Postby ronk » Sat Mar 18, 2006 1:50 pm

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

:idea:Wow, I've been following along ... apparently too casually ... because this is the first I've realized upper case letters represented the GIVENS. Where was that first explained?

Realizing that, I should get a lot more out of a re-read of this thread.:)

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby RW » Sat Mar 18, 2006 2:09 pm

Ron wrote:Wow, I've been following along ... apparently too casually ... because this is the first I've realized upper case letters represented the GIVENS. Where was that first explained?

Oops, sorry... should have been clearer.

Here's a better example of a reverse bug in action:
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  |
*--------------------------------------------*

There is a lot of candidates 1 and 2 around the grid. They actually almost form a 5-pair uniqueness chain that is very hard to identify among them. However, looking at the solved instances of 1 and 2 we can see that they almost form an reverse Bug that would be completed if number 2 went in r4c5 => We can remove candidate 2 from r4c5.

RW
Last edited by RW on Sat Mar 18, 2006 2:21 pm, edited 1 time in total.
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby gsf » Sat Mar 18, 2006 4:51 pm

I think this pencilmark grid has a typo
[4,3] needs a 3 to make it solvable
(edit: ha -- a typo in a msg illustrating a typo -- [4,2] needs a 3)
Last edited by gsf on Sat Mar 18, 2006 1:42 pm, edited 1 time in total.
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby RW » Sat Mar 18, 2006 5:32 pm

gsf wrote:I think this pencilmark grid has a typo
[4,3] needs a 3 to make it solvable


:?:I've just entered the solved numbers three times into simple sudoku solver, to make sure I don't do any typos, and every time I got the same answer: Valid Sudoku - One and only one solution !

Code: Select all
*-----------*
|591|476|238|
|473|298|156|
|826|351|794|
|-----------|
|637|982|541|
|159|647|823|
|248|513|679|
|-----------|
|384|125|967|
|765|839|412|
|912|764|385|
*-----------*


Can you explain?
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby gsf » Sat Mar 18, 2006 5:40 pm

ha -- my post had a typo too (edited to fix the typo)
your pencilmark grid has [4,2]={459}
but the solution has [4,2]=3
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Next

Return to Advanced solving techniques