The New Sudoku Players' Forum

[qiuyanzhe]

Distinction Theory



1)Definition
Between two rows(columns similar) in a band, we define their distinction to be (columns occupied)+(total kinds of digits)-(number of digits).
As in

Code: Select all

.1..23.4.
4...156..

distinction between the rows is 4.
It could also be seen as "number of open chains",if cells in a same column or having a same digit are linked.
As in

Code: Select all

..12..34.
..34..1..

it can be seen as 1-3-3-1(loop) and 2-4-4, so the distinction is 1.

2) Two rows with distinction 0(and not fully filled)
It is easily seen that the rows are "locked", no information can distinguish the rows. Digits in those empty cells can always be switched to make another solution.
..12..34. 571296348<---> 691285347
..34..21. 693485217<---> 573496218

Related Links:
forming-mugs-from-bug-lite-composites-t3210.html (About 2 lock rows)
post36383.html#p218026 (Example with 58 in r78)

3) Two rows with distinction 1
We could feel that there is little information to distinguish the rows. In some of the 17/18-given puzzles there are rows having such patterns:

Code: Select all

....x.... or ....x....
.........    ....x....

If the whole puzzle except two rows like this are filled without any basic contradiction(no repeat), then there is at least a solution.
So if we ignore the empty cells in these 2 rows and focus on the rest of the grid, there must be unique way to fill.

3.1)
The Pattern

Code: Select all

* . . . . . . . .
* . . . . . . . .
* * * . . . . . .
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *

is a magic pattern.
Proof of 3.1:
Distinction between r12 is 1. If there is a unique solution, there must be only one way to fill r3. For a row with pencilmarks, if it can be solved without extra conditions, there must be a hidden single and a naked single(this can be proved by induction.)And it is obvious that there cannot be a hidden single in r3.

Related Links:
investigation-of-one-band-free-patterns-t30199.html (mentioned this pattern)

3.2)
The Pattern

Code: Select all

abcd | abcd abcd
abcd | abcd abcd
-----+----------
     | abcd abcd

is a deadly pattern.
Proof of 3.2:
Distinction between r12 is 1. So there must be one way to fill r3. But given abcd are all in r12c23, r3c23 can be switched then produce another solution.

Related Links:
post57490.html?hilit=MUGs#p57940 (mentioned this pattern)


3.3)
For the pattern (letter=hidden *=given/irrelevant)

Code: Select all

a a...
a a...
* * *...
b b...

both b's cannot be include in a's simultaneously if distinction between r12 is 1.
Proof of 3.3:Switch b's and there would be another solution.

Here is an example:

Original Puzzle(Source 奕数独)

Code: Select all

12.....5..731.5.......23..1...8..41...45.2..3...4..58.....17..9.913.8...74.....3.

After SDC in c1 and n4

Code: Select all

+----------------------+----------------------+----------------------+
| 1      2      689    | 679    6789   4      | 3      5      678    |
| 69     7      3      | 1      689    5      | 2689   269    4      |
| 4      58     5689   | 679    2      3      | 6789   679    1      |
+----------------------+----------------------+----------------------+
| 2359   356    279    | 8      3679   69     | 4      1      267    |*
| 8      1      4      | 5      679    2      | 679    679    3      |
| 239    36     279    | 4      3679   1      | 5      8      267    |*
+----------------------+----------------------+----------------------+
| 35*    358*   2568   | 26     1      7      | 268    4      9      |
| 26     9      1      | 3      4      8      | 267    267    5      |
| 7      4      268    | 269    5      69     | 1      3      68     |
+----------------------+----------------------+----------------------+

* rows have distinction 1.
35 in N4 are in r46c12, so r7c12 must have another digit, so r7c2=8.
The following puzzle is solvable by r37c23 UR and X-chains, but there is another copy of this pattern.

Hidden Text: Show

Code: Select all

+-------------------+-------------------+-------------------+
| 1     2     (8)   | 679   69    4     | 3     5     67    |
| 69    7     3     | 1     (8)   5     | 269   269   4     |
| 4     5     69    | 679   2     3     | (8)   679   1     |
+-------------------+-------------------+-------------------+
| 5     36    279   | 8     3679  69    | 4     1     267   |
| 8     1     4     | 5     679   2     | 679   679   3     |
| 29    36    279   | 4     3679  1     | 5     8     267   |
+-------------------+-------------------+-------------------+
| 3     8     5     | 26    1     7     | 26    4     9     |
| 26    9     1     | 3     4     8     | 267   267   5     |
| 7     4     26    | 269   5     69    | 1     3     8     |
+-------------------+-------------------+-------------------+

()=solved cell
Columns 78 have distinction 1.
If r3c3=r1c5, then r13c3 and r12c5 can be switched. so r3c4=7.

Related Links:
post57490.html?hilit=MUGs#p57940 (example)

Hidden Text: Show

I was using this as the example, after r6c1=5,there is a 13 pair in r5c12,thus there must be a 13 in r78c3 or r9c123. It turns out that after r6c1=5 the puzzle is solvable by singles.

3.4)
If two rows and two columns both having distinction 1, and their crossing (4 cells that they shares)has at most 2 givens, then it is impossible to have unique solution.

Code: Select all

. . . . . . . . .
. . . . . . . . .
. .
. .
. .
. .
. .
. .
. .

We can make addition between pairs, e.g.12+23=13, as they have same effect.
After addition, r3~9c12 will become two pairs. But as distinction between c12 is 1, only one of them can be fixed,so the other can be switched, making another solution due to r12 distinction is 1.(way too fast, sorry..)
Related Links:
symmetric-18s-t2388-135.html (discussed one form of this pattern)
investigation-of-one-crossing-free-patterns-t30977.html (mostly patterns with 3 rows and columns)

qiuyanzhe, 2018/Sep/08

[Serg]

Hi, qiuyanzhe!

2) Two rows with distinction 0(and not fully filled)
It is easily seen that the rows are "locked", no information can distinguish the rows. Digits in those empty cells can always be switched to make another solution.
..12..34. 571296348<---> 691285347
..34..21. 693485217<---> 573496218

Your example can be generalized to configuration in which
a) For any column rows either contain givens (clues) both or contain empty cells both.
b) Both rows contain the same set of digits among their givens.

But you claim much more general statement "Two rows with distinction 0(and not fully filled) ... no information can distinguish the rows". What about other cases?

So if we ignore the empty cells in these 2 rows and focus on the rest of the grid, there must be unique way to fill.

Why?

Serg

[qiuyanzhe]

Hi, Serg!

Your example can be generalized to configuration in whicha) For any column rows either contain givens (clues) both or contain empty cells both.b) Both rows contain the same set of digits among their givens.

Any pattern with Distinction 0 has these properties. Actually Distinction can also be defined as (A+B)/2,where
A=number of columns that contains exactly one given.
B=number of digits that appear exactly once in the rows.
So when distinction=0, A=B=0, the properties hold.
btw I have been wondering what is the best definition of this thing and if there are similar things posted.

qiuyanzhe wrote:So if we ignore the empty cells in these 2 rows and focus on the rest of the grid, there must be unique way to fill.Why?

My idea is that, for 2 rows whose vertical pairs(pairs in the designated rows) are given, we can see the vertical pairs as loop(s), like
| 16 24 39 34 57 68 17 58 29 |
| 16 24 39 34 57 68 17 58 29 | or
1 2 3 4 5 6 7 8 9
6 4 9 3 7 8 1 5 2 --->16-68-85-57-71, 24-43-39-92.
For each loop there are 2 ways to fill the numbers, and when any part of a loop is given, the loop is fixed. And if givens are connected in the loop, no contradiction could occur.
When distinction is 1, we can only fix a connected part of one loop that contain empty cells. It determines that loop and for all other loops we can pick any way to fill.
So for any way to fill the rest of the grid, the two rows become vertical pairs and there is a way to fill the grid.

qiuyanzhe

[dobrichev]

Hi qiuyanzhe,

btw I have been wondering what is the best definition of this thing and if there are similar things posted.

"Distinctions" might be related to this concept although your approach is very different.

[qiuyanzhe]

Hi dobrichev,
Thanks for your link, and I've browsed the topic recently. We have also been thinking about similar things, that how partial UAs can be added to form new (partial) UAs. We are mainly considering about solving, so we are in different fields, but there could be connections between..

qiuyanzhe

[borescoper]

Here is an example for 3.4) pattern

Code: Select all

...437.....7...2...1.5.2.7.7.2.4.3 .51..2.3..83.9.7.1.4.2.3.9.4...4...6.....764...

Code: Select all

+-------------------+-------------------+-------------------+
| 2     569   568   | 4     3     7     | 589   158   169   |
| 4     359   7     | 1689  189   168   | 2     358   39    |
| 689   1     368   | 5     89    2     | 4     7     369   |
+-------------------+-------------------+-------------------+
| 7     68    2     | 1689  4     168   | 3     69    5     |
| 1     4     56    | 2     59    3     | 7     69    8     |
| 3     568   9     | 68    7     568   | 1     2     4     |
+-------------------+-------------------+-------------------+
| 568   2     168   | 3     158   9     | 58    4     7     |
| 589   7     4     | 18    2     158   | 6     1358  139   |
| 589   39    138   | 7     6     4     | 589   158   2     |
+-------------------+-------------------+-------------------+

Columns 46 have distinction 1, and r46c2=568.
To avoid deadly pattern, 568 cannot be locked into r46c46.
So r5c5=5.

[Serg]

Hi, qiuyanzhe!

Your example can be generalized to configuration in which a) For any column rows either contain givens (clues) both or contain empty cells both. b) Both rows contain the same set of digits among their givens.

Any pattern with Distinction 0 has these properties.

It looks like true.

btw I have been wondering what is the best definition of this thing and if there are similar things posted.

I can recommend blue's post dated by Mar 13, 2014 11:53 pm in the thread Investigation of one-crossing-free patterns.

qiuyanzhe wrote:So if we ignore the empty cells in these 2 rows and focus on the rest of the grid, there must be unique way to fill.Why?

My idea is that, for 2 rows whose vertical pairs(pairs in the designated rows) are given, we can see the vertical pairs as loop(s), like
| 16 24 39 34 57 68 17 58 29 |
| 16 24 39 34 57 68 17 58 29 | or
1 2 3 4 5 6 7 8 9
6 4 9 3 7 8 1 5 2 --->16-68-85-57-71, 24-43-39-92.
For each loop there are 2 ways to fill the numbers, and when any part of a loop is given, the loop is fixed. And if givens are connected in the loop, no contradiction could occur.
When distinction is 1, we can only fix a connected part of one loop that contain empty cells. It determines that loop and for all other loops we can pick any way to fill.
So for any way to fill the rest of the grid, the two rows become vertical pairs and there is a way to fill the grid.

But you wrote about unique way of filling. What can you say about uniqueness of filling?

Hope you see the 3rd possible 2-row configuration with distinction=1:
1........
...1.....

Serg

[qiuyanzhe]

Hi Serg,

I can recommend blue's post dated by Mar 13, 2014 11:53 pm in the thread Investigation of one-crossing-free patterns.

I have not read through this post before, and this is really an informative one. Thanks for the link!

But you wrote about unique way of filling. What can you say about uniqueness of filling?

I don't quite understand what you mean.. The logic here is that,
For any way of filling r3-9, we can fill r12 to get a solution.
If we have multiple ways of filling r3-9, then we can get a solution from each, making multiple solutions.
So there must be only one way to fill r3-9, after which r12 forms exactly one loop.

Hope you see the 3rd possible 2-row configuration with distinction=1:

Code: Select all

1........
...1.....

I think I've seen this configuration, and it has nothing special to me. It's just less common.

qiuyanzhe

[Serg]

Hi, qiuyanzhe!

3.1)
The Pattern

Code: Select all

* . . . . . . . .
* . . . . . . . .
* * * . . . . . .
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *

is a magic pattern.
Proof of 3.1:
Distinction between r12 is 1. If there is a unique solution, there must be only one way to fill r3. For a row with pencilmarks, if it can be solved without extra conditions, there must be a hidden single and a naked single(this can be proved by induction.)And it is obvious that there cannot be a hidden single in r3.

What "extra conditions" do you mean?

Please, prove statement "there must be a hidden single and a naked single".

It is not obvious for me "that there cannot be a hidden single in r3".

Serg

[qiuyanzhe]

Hi Serg,

What "extra conditions" do you mean?

It means all the restrictions are their candidates. I just thought there must be some words.. sorry for the confusion.

Please, prove statement "there must be a hidden single and a naked single".

We name a "puzzle" like

Code: Select all

 | 1567 25 347 45 267 124 1367 |

as "1*n-puzzle".

For a 1*n-puzzle, we have subsets(regard singles as 1-subset) technique, to partition the puzzle to several subsets.
As Naked Subsets and Hidden Subsets are complementary, we can just use Naked Subsets.
We see when no useful subsets exist, the puzzle is partitioned to several parts, each part being a 1*k-puzzle. There is no subset in these 1*k-puzzles.

We claim that, For every 1*k-puzzle that does not contain a subset(name it an elementary 1*k-puzzle), no pencilmarks can be eliminated.

For 1 cell it is obvious. For an n-cell pattern,
Suppose we give r1c1=1, then we may get some subset eliminations, after that we can get several smaller subsets.
Note that it is impossible for a cell to have all pencilmarks eliminated by subsets. ...*

Proof of *
If so, there is a cell C, after elimination of a Naked Subsets S, no candidate is left(Two Naked Subsets with one after another, form a larger Naked Subset).
Then before giving r1c1=1, S∪C is a Naked Subset of (1∪(digits in S)).
This subset can eliminate 1@r1c1, so there was a subset before giving r1c1=1, contradiction.[/hidden]
So the new 1*(n-1)-puzzle can be partitioned to smaller elementary 1*k-puzzles.

Code: Select all

| 1 23 23 456 56 46 78 0 79 | <--
| 1 23 23 456 56 46 78 456 79 | <--
|1 23 23 23456 2356 2346 78 23456 79 | <--
|123456789 *123 *123 *123456 *2356 *2346 78 *23456 79 |

The 1*1-elementary puzzle | 1 | has a solution.
The elementary 1*2-puzzle | 12 12 | has two solutions.
By mathematical induction, any elementary 1*k-puzzle has a solution and no pencilmarks can be eliminated.

So if a 1*n-puzzle has unique solution, it must be able to be partitioned to 1*1-puzzles.

Code: Select all

A maximal pencilmark grid could be:
| 1 12 123 1234 12345 123456 1234567 12345678 123456789 |

So there is a Naked Single and a Hidden Single.

(I think there must be a more elegant explanation..)

It is not obvious for me "that there cannot be a hidden single in r3".

In the pattern

Code: Select all

* . . . . . . . .
* . . . . . . . .
* * * . . . . . .
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *

we see for any digit that doen't occur in r3c123, its pencilmark appears once in r3c456, and once in r3c789.

qiuyanzhe

[eleven]

hi qiuyanzhe,

this month i am basically offline, apart from some wifi connections with my small handy display.
Your idea seems to be interesting, but is very unclear to me. That starts with your definition over givens, but then you state, that the MUG lines have distinction 1, where givens could be anywhere.
Also your first elimination sample does not look correct to me. Note, that there is a 5 in r3c2. If it is part of the solution, you cannot switch anything.
Doubts also for borescoper's sample. With a 1 in r4c4 i can't see a uniqueness pattern.

i hope, other members will join to clarify these things.
greetings from sun, sea and wind.

[blue]

Hi eleven,

i hope, other members will join to clarify these things.

I'll give it a try.

-----

Your idea seems to be interesting, but is very unclear to me. That starts with your definition over givens, but then you state, that the MUG lines have distinction 1, where givens could be anywhere.

I think the idea is supposed to be that if you had a solution to the pattern's pencilmarks, embedded in a complete grid; and in that grid, you cleared the cells from the pattern; then the two rows would have distinction 1.

Combining qiuyanzhe's ideas for the MUG (3.2) with his proof method from (3.1), you can also get that this is a also a MUG:

Code: Select all

abcdef | abcdef abcdef abcdef | abcdef
abcdef | abcdef abcdef abcdef | abcdef
-------+----------------------+-------
       | abcdef abcdef abcdef |       

-----

Also your first elimination sample does not look correct to me. Note, that there is a 5 in r3c2. If it is part of the solution, you cannot switch anything.

It's a cheat to look at the unique solution, though -- just like it would be a cheat to look at the solution to a puzzle where a UR technique was employed, and worry over the fact that the UR couldn't have been present, anyway.
I think he has things confused, in his description for the "a's & b's" pattern. (Apologies, if he & his are wrong.)
What the puzzle seems to be getting at, is that this is a deadly pattern:

Code: Select all

\ab - cells with no candidate for 'a' or 'b', filled cells are allowed
(*) - rows having distinction 1
  ? - can include one or two filled cells (as long as neither values are is 'a' or 'b')

\ab \ab \ab |
?   ?   \ab | (*)
?   ?   \ab | (*)
------------+
ab ab   .   |

His follow up example, seems like a diabolically fiendish way of getting at the idea that the 'ab' pair can be a remote pair too, as in these patterns:

Code: Select all

\ab \ab \ab |
?   ?   \ab | (*)
?   ?   \ab | (*)
------------+
ab .    ab  |
.  .    .   |
.  .    .   |
------------+
.  ab   ab  |


\ab \ab \ab |
?   ?   \ab | (*)
?   ?   \ab | (*)
------------+---
ab .    .   | ab
.  ab   .   | ab

-----

Doubts also for borescoper's sample. With a 1 in r4c4 i can't see a uniqueness pattern.

I don't see anything there either.

Added: Ahh, now I do, but it's an example of the 3.3 (a's & b's) pattern, not the 3.4 pattern.
The 8's and 6's are locked in r46c46 in (b5), and columns 4 & 6 have distinction 1.
To avoid the 3.3 pattern, the 8's and 6's can't be locked in r46c2, so r6c2 must be 5.

Incidently, that, forces r5c5 to be a 5, which was boroscoper's claim.
Also, the only other place for a 5 in b5, is r6c6, and that would have locked an 86 into r46c2, producing the deadly 3.3 pattern.

[blue]

Continuing a bit more with boroscoper's puzzle, reproduced here:

Code: Select all

+-------------------+-------------------+-------------------+
| 2     569   568   | 4     3     7     | 589   158   169   |
| 4     359   7     | 1689  189   168   | 2     358   39    |
| 689   1     368   | 5     89    2     | 4     7     369   |
+-------------------+-------------------+-------------------+
| 7     68    2     | 1689  4     168   | 3     69    5     |
| 1     4     56    | 2     59    3     | 7     69    8     |
| 3     568   9     | 68    7     568   | 1     2     4     |
+-------------------+-------------------+-------------------+
| 568   2     168   | 3     158   9     | 58    4     7     |
| 589   7     4     | 18    2     158   | 6     1358  139   |
| 589   39    138   | 7     6     4     | 589   158   2     |
+-------------------+-------------------+-------------------+

We can also apply qiuyanzhe's "3.4" idea, to this puzzle.

Columns 4 and 6, have distinction 1.
Rows 4 and 6, have distinction 2.

If r4c8 held a 9, then the distinction between rows 4 and 6, would drop to 1, and by "3.4", if the remaining cells had one solution, then they would have at least two solutions. Using a "uniqueness assumption" then, we can eliminate 9r4c8.

[ Just to be cute, here: If r5c5 held a 9, it would eliminate 9r4c4, and force the 9r4c8 from above.
So once again, we could say that "uniqueness" demands that r5c5=5. ]

[eleven]

Thanks blue,
so i understand this 3.3 pattern that way: either the 2 digits in the box are in the same row, and we have a UR, or they can flip-flop in the diagonal to force a different solution of the other cells of the 2 rows with distinction 1.
Nice findings on borescoper's sample, which now i can understand too.

So there should be some potential in this pattern for solvers, though i guess that it is not common in random puzzles.

I am still not happy with the definition(s), maybe it's better to formulate them seperateley for the givens and the candidates cases.

[blue]

Hi eleven,

so i understand this 3.3 pattern that way: either the 2 digits in the box are in the same row, and we have a UR, or they can flip-flop in the diagonal to force a different solution of the other cells of the 2 rows with distinction 1.

Yes, "and/but" there's one more option for the case when they're on a diagonal: the 4 box values can rotate 1/4 turn in the direction that
causes them to switch columns. (Example below).

Code: Select all

d a . | c         a c . | d
b c . | d         d b . | c
------+--   <->   ------+--
a b . |           b a . |

Added: There's still one more option, where a complete 2-row UA appears in the two rows, in cells that were originally unfilled. That would be the only option, in a case where the one "open" 2-row UA in the rows (the one that gave them "distinction 1"), closed up in a way that included one of the "ab" columns, but not both. The other "ab" column, in that case, would be in a different 2-row UA (and there could be others as well).