Distinction Theory

Advanced methods and approaches for solving Sudoku puzzles

Re: Distinction Theory

Postby eleven » Fri Sep 14, 2018 12:24 am

hm, yes, the flip-flop either leads to 2 pattern solutions in the rows or other deadly patterns (producing a BUG-lite/revetsed).
But because the rows can't be fixed without knowing, where the 2 digits are, there will always be 2 solutions possible.
eleven
 
Posts: 3094
Joined: 10 February 2008

Re: Distinction Theory

Postby borescoper » Fri Sep 14, 2018 3:19 am

this is a deadly pattern which include two rows with distinction 1:
Code: Select all
*--------------------------------------------------------------------------------------------*
|         .         .         .|         .         .         .|         .         .         .|
|         .         .         .|         .         .         .|         .         .         .|
|         .         .         .|         .         .         .|         .         .         .|
|------------------------------+------------------------------+------------------------------|
|         .         .         .|         .         .         .|         .         .         .|
|         .         .         .|         .         .         .|         .         .         .|
|      abcd      abcd         .|         .         .         .|         .         .         .|
|------------------------------+------------------------------+------------------------------|
|      abcd      abcd         .|         X         .         .|         .         .         .|
|      abcd      abcd         .|         Y         .         .|         .         .         .|
|         .         .         .|         .         .         .|         .         .         .|
*--------------------------------------------------------------------------------------------*

in r7 and r8, we put 2 given cells "X" and "Y" in same column, and other cells are unfilled. so, distinction between r78 is 1. certainly, we can put more givens to form 2 rows with "distinction 1", for example:
Code: Select all
|         X         Z         .|         .         .         .|         .         .         .|
|         Z         Y         .|         .         .         .|         .         .         .|

but it will be same.
"abcd" means a unfilled cell with 4 candidates.
there are 3 situations.
1: X and Y are equal to two of a,b,c,d.
2: one of X and Y is equal to one of a,b,c,d.
3: X and Y is not equal to a,b,c,d.

situation 1: X and Y are equal to two of a,b,c,d.
Code: Select all
*--------------------------------------------------------------------------------------------*
|         .         .         .|         .         .         .|         .         .         .|
|         .         .         .|         .         .         .|         .         .         .|
|         .         .         .|         .         .         .|         .         .         .|
|------------------------------+------------------------------+------------------------------|
|         .         .         .|         .         .         .|         .         .         .|
|         .         .         .|         .         .         .|         .         .         .|
|      abcd      abcd         .|         .         .         .|         .         .         .|
|------------------------------+------------------------------+------------------------------|
|      abcd      abcd         #|         a         #         #|         #         #         #|
|      abcd      abcd         #|         b         #         #|         #         #         #|
|         .         .         .|         .         .         .|         .         .         .|
*--------------------------------------------------------------------------------------------*

in situation 1, "a" and "b" is given, the "abcd" cells and the "#" cells is unfilled. r78c12 include a,b,c,d, so, the "#" grids include "c","d", and a number of pairs with same digits.
when we think about a "deadly pattern" in 2 rows, we can ignore the pairs with same digits. for example:
Code: Select all
|         1         b         .|         2         .         .|         .         .         .|
|         a         2         .|         1         .         .|         .         .         .|

Code: Select all
|         b         .         .|         .         .         .|         .         .         .|
|         a         .         .|         .         .         .|         .         .         .|

these 2 patterns cause same effects to the remain cells
so, we consider all of the "#" grids as "c" and "d" in same column. it means that r678c12 and all of the "#" grids formed a "abcd" deadly pattern like this:
Code: Select all
|      abcd      abcd         .|         .         .         .| 
|------------------------------+------------------------------+
|      abcd      abcd         .|         .         c         .|
|      abcd      abcd         .|         .         d         .|
|         .         .         .|         .         .         .|
*-------------------------------------------------------------*


situation 2: one of X and Y is equal to one of a,b,c,d.
Code: Select all
*--------------------------------------------------------------------------------------------*
|         .         .         .|         .         .         .|         .         .         .|
|         .         .         .|         .         .         .|         .         .         .|
|         .         .         .|         .         .         .|         .         .         .|
|------------------------------+------------------------------+------------------------------|
|         .         .         .|         .         .         .|         .         .         .|
|         .         .         .|         .         .         .|         .         .         .|
|      abcd      abcd         .|         .         .         .|         .         .         .|
|------------------------------+------------------------------+------------------------------|
|      abcd      abcd         #|         X         #         #|         #         #         #|
|      abcd      abcd         #|         a         #         #|         #         #         #|
|         .         .         .|         .         .         .|         .         .         .|
*--------------------------------------------------------------------------------------------*

in situation 2, "X" and "a" is given, the "abcd" cells and the "#" cells is unfilled. r78c12 include a,b,c,d, so, the "#" grids include "X","b","c","d", and a number of pairs with same digits.
same as siuation 1, we ignore those pairs, the rest is "X","b","c","d".
no matter how we arrange these 4 digits, there always will be 2 of "abcd" in same column. for example:
Code: Select all
|      abcd      abcd         .|         .         .         .| 
|------------------------------+------------------------------+
|      abcd      abcd         .|         .         X         b|
|      abcd      abcd         .|         .         c         d|
|         .         .         .|         .         .         .|
*-------------------------------------------------------------*

"b" and "d" in same column, together with r678c12, formed a "abcd" deadly pattern.

situation 3: X and Y is not equal to a,b,c,d.
Code: Select all
*--------------------------------------------------------------------------------------------*
|         .         .         .|         .         .         .|         .         .         .|
|         .         .         .|         .         .         .|         .         .         .|
|         .         .         .|         .         .         .|         .         .         .|
|------------------------------+------------------------------+------------------------------|
|         .         .         .|         .         .         .|         .         .         .|
|         .         .         .|         .         .         .|         .         .         .|
|      abcd      abcd         .|         .         .         .|         .         .         .|
|------------------------------+------------------------------+------------------------------|
|      abcd      abcd         #|         X         #         #|         #         #         #|
|      abcd      abcd         #|         Y         #         #|         #         #         #|
|         .         .         .|         .         .         .|         .         .         .|
*--------------------------------------------------------------------------------------------*

in situation 3, "X" and "Y" is given, which are not equal to a,b,c,d; the "abcd" cells and the "#" cells is unfilled. r78c12 include a,b,c,d, so, the "#" grids include "X","Y","a","b","c","d", and a number of pairs with same digits.
same as siuation 1 and 2, we ignore those pairs, the rest is "X","Y","a","b","c","d".
no matter how we arrange these 6 digits, there always will be 2 of "abcd" in same column. for example:
Code: Select all
|      abcd      abcd         .|         .         .         .|         .         .         .|
|------------------------------+------------------------------+------------------------------|
|      abcd      abcd         .|         .         X         Y|         a         .         .|
|      abcd      abcd         .|         .         b         c|         d         .         .|
|         .         .         .|         .         .         .|         .         .         .|
*--------------------------------------------------------------------------------------------*

"a" and "d" in same column, together with r678c12, formed a "abcd" deadly pattern.

so, the pattern in top of the reply is a deadly pattern.

on the other hand, if we change the "abcd" grids to "abc" ( get rid of one grid in r78c12 meanwhile), the deadly pattern still exist, with similar prove precedure.

the example in 3.3):
Code: Select all
*-----------------------------------------------*
|    1    2    .|    .    .    4|    3    5    .|
|    .    7    3|    1    .    5|    .    .    4|
|    4    .    .|    .    2    3|    .    .    1|
|---------------+---------------+---------------|
| 2359  356  279|    8    .    .|    4    1    .|*
|    8    1    4|    5    .    2|    .    .    3|
|  239   36  279|    4    .    1|    5    8    .|*
|---------------+---------------+---------------|
|   35  358    .|    .    1    7|    .    4    9|
|    .    9    1|    3    4    8|    .    .    5|
|    7    4    .|    .    5    .|    1    3    .|
*-----------------------------------------------*

"*" rows have distinction 1. if r7c2<>8, r7c12=35, in B4, 35 locked in r46c12. row46 have distinction 1, so, r7c12 and row46 formed a deadly pattern.
so r7c2=8

back to my example:
Code: Select all
2..437...4.7...2...1.5.247.7.2.4.3.514.2.37.83.9.7.124.2.3.9.47.74.2.6.....764..2


Code: Select all
*-----------------------------------------------*
|    2    .    .|    4    3    7|    .    .    .|
|    4    .    7|    .    .    .|    2    .    .|
|    .    1    .|    5    .    2|    4    7    .|
|---------------+---------------+---------------|
|    7   68    2|    .    4    .|    3    .    5|
|    1    4    .|    2    #    3|    7    .    8|
|    3  568    9|    .    7    .|    1    2    4|
|---------------+---------------+---------------|
|    .    2    .|    3    .    9|    .    4    7|
|    .    7    4|    .    2    .|    6    .    .|
|    .    .    .|    7    6    4|    .    .    2|
*-----------------------------------------------*


in b5, if "#" grid is not 568, 568 are locked in r46c46. distinction of r46 is 1, with r46c2=568, formed a deadly pattern.
so r5c5=5
BTW: this example is not very good, becaurse the givens in r46 is too many. it cause that if r5c5<>5, r46c2/r46c46/r8c46 formed "abcd" deadly pattern of 1568.

borescoper
borescoper
 
Posts: 20
Joined: 11 June 2016

Re: Distinction Theory

Postby blue » Fri Sep 14, 2018 7:29 am

Hi boroscoper,

Interesting !

In the first line of your post, you're really saying that this is a deadly pattern, right ?

Code: Select all
abcd abcd . |
------------+
abcd abcd . | (*)
abcd abcd . | (*) rows having distincion 1

I still think you're making your example, more complicated than it needs to be.
Why not just say that if r4c4 isn't a 9, you would have an instance of the pattern, and put a 9 in r4c4 ?

The other way, involving 5r5c5, requires you to notice that with no 5 in r5c5, either 1) 1568r46c6 would form a hidden quad in b5, and eliminate 9r4c4, or 2) r5c5 would contain a 9, which would eliminate 9r4c4 -- both approaches, producing an instance of the deadly pattern.

Still, though, the hidden quad route is interesting.
I can see where in a more complicated example, it could come in handy.

BTW: this example is not very good, becaurse the givens in r46 is too many (...)

Understood.
blue
 
Posts: 979
Joined: 11 March 2013

Re: Distinction Theory

Postby qiuyanzhe » Fri Sep 14, 2018 3:15 pm

This is an example of case 3.4(Distinction-1 columns and Almost Distinction-1 rows)

Original Puzzle:
..5.236.8...6..9..6..9...5.....928..1.....3....6.....1.....9.8.4372.....8...3.7.2
(Inspired by this puzzle, puzzle found by ssxsssxs using his program, and re-edited by borescoper and me.)
After Singles:
Code: Select all
+----------------------+----------------------+----------------------+
| 79     479    5      | 47     2      3      | 6      1      8      |
| 27     1247   8      | 6      1457   1457   | 9      3      47     |
| 6      147    3      | 9      1478   1478   | 2      5      47     |
+----------------------+----------------------+----------------------+
| 3      57     4      | 1      9      2      | 8      67     567    |
| 1      2579   29     | 8      4567   4567   | 3      24679  45679  |
| 2579   8      6      | 3      457    457    | 45     2479   1      |
+----------------------+----------------------+----------------------+
| 25     1256   12     | 457    14567  9      | 145    8      3      |
| 4      3      7      | 2      1568   1568   | 15     69     569    |
| 8      1569   19     | 45     3      1456   | 7      469    2      |
+----------------------+----------------------+----------------------+

Columns 56 have distinction 1. If rows 23 have distinction 1 then it is a deadly pattern.
So r2c1 is not 2, r2c1=7.
SE 7.1->1.5
(It seems there are still too many givens in rows 23. We would try to get better examples.)
qiuyanzhe
 
Posts: 94
Joined: 21 August 2017
Location: China

Re: Distinction Theory

Postby eleven » Sat Sep 15, 2018 9:16 am

Cool.

i checked borescopers claim and came to the same result - in a slightly different way, but not simpler to explain.
eleven
 
Posts: 3094
Joined: 10 February 2008

Re: Distinction Theory

Postby ssxsssxs » Tue Sep 18, 2018 5:04 am

more examples
Code: Select all
....12......3..4..3..4..15...6.41..74.....3..........5.17..4..6..2.........82.9..  SE 8.5->2.8
....12......3..4..3..4..15...6.41...7.....5....2.....8.51..4..6..8.........72.9..  SE 9.1->2.8
Last edited by ssxsssxs on Wed Sep 19, 2018 4:01 pm, edited 1 time in total.
User avatar
ssxsssxs
 
Posts: 168
Joined: 22 January 2014

Re: Distinction Theory

Postby David P Bird » Tue Sep 18, 2018 1:40 pm

This is the full grid from ssxssxs after basics:
Code: Select all
 *-------------------------*-------------------------*-------------------------*
 | 56789   56789   4       | 5679    <1>     <2>     | 678     36789   389     |
 | 1256789 256789  1589    | <3>     56789   56789   | <4>     26789   289     |
 | <3>     26789   89      | <4>     6789    6789    | <1>     <5>     289     |   
 *-------------------------*-------------------------*-------------------------*
 | 2589    3       <6>     | 259     <4>     <1>     | 28      289     <7>     |
 | <4>     25789   589     | 25679   56789   56789   | <3>     12689   1289    |
 | 12789   2789    189     | 2679    36789   36789   | 268     4       <5>     |
 *-------------------------*-------------------------*-------------------------*
 | 589     <1>     <7>     | 59      359     <4>     | 258     238     <6>     |
 | 5689    45689   <2>     | 1       35679   35679   | 578     378     348     |
 | 56      456     3       | <8>     <2>     567     | <9>     17      14      |
 *-------------------------*-------------------------*-------------------------*

Unsolved
r2 (1256789)r2c1235689 }
r3 (26789)r3c23569 } distinction = 2

c5 (356789)r235678c4 }
c6 (356789)r235689c5 } distinction = 1
[Aside this unsolved digits/positions notation is my way of checking the distinctions; count the unique underlines and divide by 2.]

We can see that if (5)r2c1 was true (6789)r23c56 would be locked and the distinction between r2 & r3 would be 1, so it can be eliminated

However, if (1)r2c1 is eliminated the distinction would also reduce to 1 but (56789)r23c56 would be left. From my reading of the earlier proofs, this pattern has not yet been analysed and shown to be deadly, so this elimination is unsound. Have I missed something?
David P Bird
2010 Supporter
 
Posts: 1043
Joined: 16 September 2008
Location: Middle England

Re: Distinction Theory

Postby eleven » Wed Sep 19, 2018 3:12 pm

yes, a full proof is missing for 3.4.
here i am sure, that you can eliminate the 1, because if the rest of the puzzle is solved, 4 of the 5 digits in the crossing cells remain, and 2 of them will be undetermined in the rest of the rows (can be switched between the rows - together with other digits or alone), and 2 of the same 4 digits are undetermined in the (rest of the) columns.
so you have the same situation as in a MUG with the 4 digits.
i am not sure yet about the cases with up to 2 digits given in the crossing cells.
eleven
 
Posts: 3094
Joined: 10 February 2008

Re: Distinction Theory

Postby borescoper » Wed Sep 19, 2018 4:17 pm

David P Bird wrote:This is the full grid from ssxssxs after basics:
Code: Select all
 *-------------------------*-------------------------*-------------------------*
 | 56789   56789   4       | 5679    <1>     <2>     | 678     36789   389     |
 | 1256789 256789  1589    | <3>     56789   56789   | <4>     26789   289     |
 | <3>     26789   89      | <4>     6789    6789    | <1>     <5>     289     |   
 *-------------------------*-------------------------*-------------------------*
 | 2589    3       <6>     | 259     <4>     <1>     | 28      289     <7>     |
 | <4>     25789   589     | 25679   56789   56789   | <3>     12689   1289    |
 | 12789   2789    189     | 2679    36789   36789   | 268     4       <5>     |
 *-------------------------*-------------------------*-------------------------*
 | 589     <1>     <7>     | 59      359     <4>     | 258     238     <6>     |
 | 5689    45689   <2>     | 1       35679   35679   | 578     378     348     |
 | 56      456     3       | <8>     <2>     567     | <9>     17      14      |
 *-------------------------*-------------------------*-------------------------*

Unsolved
r2 (1256789)r2c1235689 }
r3 (26789)r3c23569 } distinction = 2

c5 (356789)r235678c4 }
c6 (356789)r235689c5 } distinction = 1
[Aside this unsolved digits/positions notation is my way of checking the distinctions; count the unique underlines and divide by 2.]

We can see that if (5)r2c1 was true (6789)r23c56 would be locked and the distinction between r2 & r3 would be 1, so it can be eliminated

However, if (1)r2c1 is eliminated the distinction would also reduce to 1 but (56789)r23c56 would be left. From my reading of the earlier proofs, this pattern has not yet been analysed and shown to be deadly, so this elimination is unsound. Have I missed something?

i think the prove procedure of 3.4 is similar as 3.3.
in this example, the distinction of c56 is 1.if we consider the givens of c56 as X and Y, according to my reply above(replied few days ago), we always can consider those unfilled grids in c56 (except r23c56) as a PAIR of digits filled in r23c56, no matter which 4 digits filled in r23c56. so, if r2c1=1, r23 have distinction 1, with this PAIR, formed a 3.3 distinction 1 deadly pattern.
borescoper
borescoper
 
Posts: 20
Joined: 11 June 2016

Re: Distinction Theory

Postby eleven » Wed Sep 19, 2018 8:07 pm

ok, but does it hold with 1 or 2 givens in the crossing cells ?
and if so, why ?
edit: ah, i see. with one given it works for 3 digits the same way. and 2 givens [edit2:] always must end in a bug-lite.
Last edited by eleven on Wed Sep 19, 2018 10:29 pm, edited 1 time in total.
eleven
 
Posts: 3094
Joined: 10 February 2008

Re: Distinction Theory

Postby David P Bird » Wed Sep 19, 2018 9:55 pm

Borescoper,
Thanks for your response. I am more of a solver than a mathematician and, up until now, the explanations have been too imprecise for me to be able to follow easily. However, I appreciate the effort you and qiuyanzhe have put into attempting to find the right words to express your ideas in a foreign language.

It would be better for me if you identified cells as being either 'unsolved' or 'known'. The known cells are those holding singles because they were either givens in the puzzle or have been solved by the player. We then have the sets of known digits (values) and known cell positions (row/column numbers) in the two houses to compare to provide the distinction value between them.

It will be interesting to see if you are able to expand your ideas further.

David PB
David P Bird
2010 Supporter
 
Posts: 1043
Joined: 16 September 2008
Location: Middle England

Re: Distinction Theory

Postby borescoper » Wed Sep 19, 2018 11:25 pm

David PB:
thanks for your understanding. it's very hard for me to express in foreign language. in Eleven's reply he said he came to same to same result in a slightly different way. maybe he can help to express it in his way? :D
borescoper
 
Posts: 20
Joined: 11 June 2016

Re: Distinction Theory

Postby eleven » Thu Sep 20, 2018 12:03 pm

its a bit hard on the handy, but David will not have a problem to verify it himself (if he has not yet done).
the trick is, to look at the 7 columns, which dont have the 4 digit pattern, as solved outside the two distinction 1 rows.
If there would be no given in the 2 rows (distinction 0), you are left then with a pair of candidates in each column, where 1-4 must be in the 7 columns one time, the other digits twice, e.g. like this:

1234 1234 89 | 78 16 45 | 67 25 39
1234 1234 89 | 78 16 45 | 67 25 39

To get distinction 1, exactly 1 different number is given in the one row (implying another number in the other, given or not).
the point is, that however you do that, you cannot fix all digits 1-4. there will always be a pair of them unsolved (note that you have 9 digits for 7 columns and 5-9 have to be in both rows) - and in the unsolved cells the digits can be switched in the rows.

the rest i said above.

for the verification also the mentioned "melting" of cells is useful, e.g. you can replace (45) and (25) by (42).
givens like
7 8 9
8 9 7
simply can be ignored.
then distinction 1 rows always melt to (a,b) and (c,d), where a,b,c,d are out of 1-4, and one pair is given.

btw the 3.4 case with 2 givens can only be a reversed bug-lite pattern.
eleven
 
Posts: 3094
Joined: 10 February 2008

Re: Distinction Theory

Postby eleven » Thu Sep 20, 2018 3:37 pm

for completeness, because case 3.1 - in blue's definition - is a bit different:
here the pair 12, which is restricted to the 4 cells, could be fixed by the givens and the rest of the columns.
if it is fixed to 1 row, it must be in the other row of the 4 cells, building a UR.
if it is fixed to different rows, there must be another undetermined pair, say ab, now building a MUG equivalent pattern with 12 (the other digits also being fixed outside of the 4 cells).
if 12 is not fixed, it builds a MUG equivalent pattern with 2 other digits in the 4 cells.
eleven
 
Posts: 3094
Joined: 10 February 2008

Previous

Return to Advanced solving techniques