Uniqueness chains

Advanced methods and approaches for solving Sudoku puzzles

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

Postby RW » Sat Mar 18, 2006 6:20 pm

Ah, now I understand. Yes a typo, it should of course be 345. I'll fix it.
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby Myth Jellies » Sat Mar 18, 2006 6:58 pm

Typos notwithstanding; the reverse BUG reduction using the solved digits is very simple to see. Trying to make the reduction using unsolved candidates appears to be very difficult. I'm not sure this is where the thread started out, but I really like where it ended up:) . This should prove useful. Good job, RW:!:
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Sun Mar 19, 2006 12:20 pm

According to the theory of this thread, can I validly place r6c7=1?
Code: Select all
 8    1    9    | 7    4    6    | 2    5    3
 357  345  347  | 2    15   9    | 8    6    14
 6    45   2    | 3    15   8    | 9    7    14
----------------+----------------+---------------
 4    259  17   | 8    6    3    | 15   29   279
 79   6    8    | 1    29   5    | 4    3    279
 359  2359 13   | 4    29   7    |*15   8   *6
----------------+----------------+---------------
 1    49  *5    |*6    3    2    | 7    49   8
 39   8    34   |*5    7    1    |*6    249  29
 2    7   *6    | 9    8    4    | 3    1   *5

What's bothering me is that six of the eight starred cells are givens.

The starting grid is ...
Code: Select all
 .19|.4.|25.
 ...|2.9|...
 6.2|...|9..
 ---+---+---
 4..|8.3|...
 .68|...|43.
 ...|4.7|..6
 ---+---+---
 ..5|...|7.8
 ...|5.1|...
 .76|.8.|31.

... and prior reductions may be found here.

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

Postby RW » Sun Mar 19, 2006 1:01 pm

ronk wrote:According to the theory of this thread, can I validly place r6c7=1?

No, because there are given instances of numbers 5 and 6 that are not included in the reverse BUG pattern (r1c8, r3c1 and r5c2). A quote from my earlier post: "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 Jeff » Sun Mar 26, 2006 5:27 am

RW wrote:"As long as all given instances are included in the potential reverse Bug pattern you may use this technique."

Hi RW, Could you explain why all given instances, but not all given and solved instances, have to be included in the reverse BUG pattern before this technique would work properly.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby RW » Mon Mar 27, 2006 10:07 am

Jeff wrote:Could you explain why all given instances, but not all given and solved instances, have to be included in the reverse BUG pattern before this technique would work properly.

Absolutely. The basic idea is that "if any amount of two numbers A,B form a BUG pattern (take up two spaces in every unit they occupy), the remaining instances of A,B will also form a BUG pattern." So if all given instances are included in one of these, the other will give two solutions. A similar question has been discussed by Vidarino here, conserning a case where he managed to solve some numbers of a potential uniqueness rectangle and only later applied the uniqueness technique on it. This is basically the same idea, but with the reverse bug we are identifying much bigger uniqueness patterns.

Did that make things any clearer?

PS. You can try on Vidarinos puzzle to enter number 1 in r8c2 (complete the rectangle), then solve the remaining numbers 1 and 8 and you will see the reverse BUG formed by the remaining 7 pairs (all givens included).

PPS. If it is possible to from a double solution pattern (=both numbers can go in all included cells, none of the cells has to hold a third number) and you have already solved some of the included cells, the only way you could possibly have got there is with T&E or applying uniqueness technique (as Vidarino did). Not important to the discussion, but an interresting point I think. Can anybody prove me wrong?
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby Jeff » Tue Mar 28, 2006 4:05 pm

RW wrote:..............So if all given instances are included in one of these, the other will give two solutions.

Thanks, RW. There are 3 types of instances, namely given, solved and unsolved. I am interested to know why the solved instances don't have to be included in the reverse BUG pattern for the technique to work properly. Could you list more examples?
Jeff
 
Posts: 708
Joined: 01 August 2005

PreviousNext

Return to Advanced solving techniques