The New Sudoku Players' Forum

[champagne]

[But I think, Denis is also right when he say that similar idea should be true for clue cells. Suppose we have a valid puzzle with solution grid, having U4 hitted by one clue cell. We can now change this clue cell to the value from the second U4 permutation. Now we have another valid puzzle, because number of puzzles' solutions must be the same. I need more time to ponder this idea ...]

Serg

Hi Serg,

Another explanation in line with eleven’s post

First of all, a reminder of the ”deadly pattern context”.
In a solution grid, you find many patterns where without a given, a puzzle would not lead to a unique solution. They are called unavoidable sets. The smaller one is the pattern known as UR in a puzzle. All unavoidable sets are hit by a given in a sudoku.

If you have in your PM a deadly pattern (something that would be an unavoidable set in the final solution(s) of the puzzle), It’s a fact that you have no given for this “deadly pattern”, you can see it in the pm.

To make it simple, we consider here the UR “deadly pattern”

The puzzle can have multiple solutions, all of them including the 4 cells unavoidable set, part of them with one of the the 2 digits patterns.

If the solution is unique, the UR can not contain only 2 digits. This is the classical use of the UR eliminations. A puzzle known as having a unique solution can not produce such a solution.

If we don’t know how many solutions has the puzzle (other unavoidable sets can have no given) then the UR rule can not be used for this specific UR

But assume as in our example that one digit of the 2 possible unavoidable set values is proven not valid. Then we have a contradiction.

Having no clue in the 4 cells unavoidable set pattern, the permutation of the digits in the four cells gives a valid solution with the same given and all other cells unchanged
Having one digit cleared, the second solution is not possible

The only possibility is that no solution with the four digits will come. We have a classical UR potential for eliminations.

[denis_berthier]

ONE MORE OBJECTION to RedEd "PROOF" of UR1.1

For ease of reading, tel me recall RedEd's proof, that was in my first post. All the further posts from believers in this proof have only consisted of repeating it with no new argument. As a result, it remains a good starting point.

Definition: an a/b/b/a pattern in a solution grid is anything isomorphic to that shown below:

Code: Select all

 .  .  . | .
 a  .  . | b
 b  .  . | a
---------+---
 .  .  . | .

Fact: if a solution grid (not necessarily unique) contains an a/b/b/a pattern on four unclued cells, C, then C=b/a/a/b is also a solution.

Theorem: if a puzzle-in-progress (that does not necessarily have a unique solution) has pencilmarks as shown below on four unclued cells then the bottom right value resolves to '3':

Code: Select all

 .  .  . | .
 1  .  . | 2
 2  .  . | 13
---------+---
 .  .  . | .

Proof: suppose to the contrary the bottom right value resolves to '1'. Then (vacuously) the solution grid contains the 1/2/2/1 pattern on four unclued cells, C. So, by the Fact above, C=2/1/1/2 is also a solution. But wait! - the pencilmarks do not allow that other solution - contradiction

The flaw I mentioned in this thread is related to using the condition 'unclued". Although it relies only on very basic logic, it seems to be too technical for being understood on this forum.

One more objection I now have is about the conclusion of the "Theorem" part. RedEd's conclusion is merely "contradiction". But wait! When a contradiction is found at the end of some proof, it only means that the supposed conclusion of the proof is inconsistent with all the hypotheses used for the proof.

What REdEd's proof really implies is:
- EITHER the value in the 4th cell must be 1 in the conditions of the theorem
- OR the conditions of the theorem are impossible (i.e. the a/b/b/ac pattern cannot appear if the 4 UR cells were unclued)

[Edited 2020/02/24 for clarification of my objection]: Of course, the second case is included in the first, but in standard mathematical practice, no one would merely jump to the general conclusion (first case above) when there are strong indications that the second particular case is indeed the real one.
Notice that if the second conclusion is true, this makes the theorem of the form FALSE => elimination. The theorem cannot even be said to be false (based only on this objection). It's merely an irrelevant tautology. So, this objection is not about the proof being correct or not, it's about it being irrelevant.

Note that both I and champagne have already come to the intuitive conclusion that the conditions are very unlikely to happen, based on vain tries for building an example.

[Edited 2020/02/24 for clarification of the remaining challenge]:It seems to me, as I already stated, that it should be a priority for the believers in the UR1.1 rule (with the "unclued" cells condition) to exhibit an example for a multi-solution puzzle (so that the implicit use of some assumption of uniqueness can be discarded Good luck!

[champagne]

Note that both I and champagne have already come to the intuitive conclusion that the conditions are very unlikely to happen, based on vain tries for building an example.

It seems to me, as I already stated, that it should be a priority for the believers in the UR1.1 rule to exhibit an example. Good luck!

champagne sees small chances to produce a UR1.1 but
for me there is no flaw in the proof
the above example has exactly the same proof and we have the path to reach the position

Note: the contradiction is nearly the same as for the uniqueness. In one case, the contradiction comes from a given, in the other case, the contradiction comes form the cleared candidate. This is AFAIK the only logic proof to validate the use of such rules.

[denis_berthier]

for me there is no flaw in the proof

The flaw is in the conclusion. Formally, I agree that one can write a conclusion A => B in any case, even if A is false. However, no one would seriously write it as a theorem when it is extremely likely that A is always false.

I don't know which "above example" you're mentioning. If it's about the UR1 rule, the problem is different as everybody has examples (and moreover, there's no extra condition on unclued cells).

[champagne]

I don't know which "above example" you're mentioning. If it's about the UR1 rule, the problem is different as everybody has examples (and moreover, there's no extra condition on unclued cells).

this example

See this first post about the topic from 2006

has been commented in the posts above. It is a wider view on what happen when a deadly pattern is partially solved. The UR1.1 is an extreme situation. In fact, one elimination in the deadly pattern is enough.

for me there is no flaw in the proof

The flaw is in the conclusion. Formally, I agree that one can write a conclusion A => B in any case, even if A is false. However, no one would seriously write it as a theorem when it is extremely likely that A is always false.

Many eliminations in the sudoku world are based on similar contradictions.

if
"A" => 'X' true
"A" => 'X' false
then "A is false

in most cases, "X" is the status of a candidate,
here
'A' is "we have a 2 digits solution in the UR"
and 'X' is "the solution grid has a unique solution regarding the corresponding deadly pattern"

I can't see here any room for a flaw.

[Leren]

I don't know whether this may be useful but here goes anyway. Hodoku also has several puzzles that come under the title Avoidable Rectangle Type 2.

Code: Select all

*-----------*
|9..|...|6..|
|..1|..6|.38|
|7.6|.8.|...|
|---+---+---|
|...|...|.76|
|..4|1..|...|
|.5.|947|.2.|
|---+---+---|
|2..|...|..5|
|...|25.|...|
|...|.9.|..1|
*-----------*
9.....6....1..6.387.6.8...........76..41......5.947.2.2.......5...25........9...1

The trick here is that you can get easily to the following position with just basics and an XY Wing:

Code: Select all

*---------------------------------------*
| 9  8      235 | 35   12 135 | 6 4   7 |
| 45 24     1   | 457  27 6   | 9 3   8 |
| 7  34     6   | 34   8  9   | 5 1   2 |
|---------------+-------------+---------|
| 1  29     2-9 | 58   3  58  | 4 7   6 |
| 3  7      4   | 1    6  2   | 8 5   9 |
| 6  5      8   | 9    4  7   | 1 2   3 |
|---------------+-------------+---------|
| 2  146-9 *79  | 678  17 148 |*3 689 5 |
| 8  136-9 *39  | 2    5  13  |*7 69  4 |
| 45 346    357 | 3678 9  348 | 2 68  1 |
*---------------------------------------*

Note that r78c7 are not givens but have been resolved to 3 and 7 without any uniqueness arguments.

So, one of r78c3 must be 9 to prevent a 73 DP in r78c37, but we've shown by non UR arguments that the "other way" for the DP is impossible.

There is a bunch of these in their exemplar list, but you may have to fudge the solution path to get to the AR position

Hidden Text: Show

9.....6....1..6.387.6.8...........76..41......5.947.2.2.......5...25........9...1
..2....95.892...6.4...5......18...2.........9.9.621..8..8913...............4..38.
.....78...169...7....1..56.8..........5..3...3...4.2...7...2......859..24...1..3.
..4..8675.2.....3937..5..8.........75...16.9......5.....76........9....324.....1.
1....2.5..2......3..46.8..72..........74..9.6.6..9.........6......1...8...5..32.4
7.1..8...695.......8.9..6.....4.6.........8.....5..26.........9.79..1.....625.1.4
.85....6......47...3....1.........5.6...43....7.82.3.....45967..........9.416...3
.......31.96...7.25..............8..7.94.........329.......8..5.32.5..1...1..9.87
......93...27....57.....8.......3....4..9...6..8..1374..5.8719....9......6.......
...185....83.2.5..........726..5.7.3..9....6.73............6.59.4......2..79.....
2...1.....17...5....6754.2....82..5.......6.4....71...6....3......2..79...968....
3.....7...4....2...79.3.46872...............9.91......1...52......7.138.4.2.6...1
........1.6.5...9.4..7..8....8.............45.31.64...853.....2..21....6.....3...
32.5.........94..7.......3.....7..4.8431....9..68.......948..5.........4....12.8.
1.9.......4......5...1....3..3.186.....9.7.3.5................8.....435..18.6..72
......132.6.5.3...8.....6.9..............184....938..12.5..4.....41......1..9...8

Leren

<edit> Added - 9 in r4c3 after comment by denis_berthier

[denis_berthier]

I don't know whether this may be useful but here goes anyway. Hodoku also has several puzzles that come under the title Avoidable Rectangle Type 2.

Code: Select all

*-----------*
|9..|...|6..|
|..1|..6|.38|
|7.6|.8.|...|
|---+---+---|
|...|...|.76|
|..4|1..|...|
|.5.|947|.2.|
|---+---+---|
|2..|...|..5|
|...|25.|...|
|...|.9.|..1|
*-----------*
9.....6....1..6.387.6.8...........76..41......5.947.2.2.......5...25........9...1

The trick here is that you can get easily to the following position with just basics and an XY Wing:

Code: Select all

*---------------------------------------*
| 9  8      235 | 35   12 135 | 6 4   7 |
| 45 24     1   | 457  27 6   | 9 3   8 |
| 7  34     6   | 34   8  9   | 5 1   2 |
|---------------+-------------+---------|
| 1  29     2   | 58   3  58  | 4 7   6 |
| 3  7      4   | 1    6  2   | 8 5   9 |
| 6  5      8   | 9    4  7   | 1 2   3 |
|---------------+-------------+---------|
| 2  146-9 *79  | 678  17 148 |*3 689 5 |
| 8  136-9 *39  | 2    5  13  |*7 69  4 |
| 45 346    357 | 3678 9  348 | 2 68  1 |
*---------------------------------------*

Note that r78c7 are not givens but have been resolved to 3 and 7 without any uniqueness arguments.
So, one of r78c3 must be 9 to prevent a 73 DP in r78c37, but we've shown by non UR arguments that the "other way" for the DP is impossible.

One of r78c3 must be 9 because there's no other place for 9 in c3.
Moreover, this is not a UR1.1 pattern, but you already suggested it.

[denis_berthier]

for me there is no flaw in the proof

The flaw is in the conclusion. Formally, I agree that one can write a conclusion A => B in any case, even if A is false. However, no one would seriously write it as a theorem when it is extremely likely that A is always false.

Many eliminations in the sudoku world are based on similar contradictions.
if
"A" => 'X' true
"A" => 'X' false
then "A is false
in most cases, "X" is the status of a candidate,

This is totally unrelated to my statement.
This is totally different. This is proof by cases.

[champagne]

...
This is totally unrelated to my statement.
This is totally different. This is proof by cases.

so the proof for the UR1.1 is a proof by cases, I did not know the name

[Leren]

denis_berthier wrote : One of r78c3 must be 9 because there's no other place for 9 in c3.

Actually there were three 9's in Column 3, so the argument is non-trivial. I've fixed my post. Thanks for spotting the typo.

Leren

[eleven]

ONE MORE FLAW in RedEd "PROOF" of UR1.1

First of all, there is no flaw in Red Ed's proof, and crying that out in big blue letters does not change that.
It definitely says "if a puzzle-in-progress ... has pencilmarks as shown", then .... So there is no flaw, even if no such pattern would exist.

[As nobody has ever been able to give an example where the conditions of the proof are satisfied, the alternative conclusion cannot be discarded so easily.
...
It seems to me, as I already stated, that it should be a priority for the believers in the UR1.1 rule to exhibit an example. Good luck!

The examples have been found already in the old times, before you started to doubt this rule. Here is one with a pure UR1.1 from 2008.

If you want a recent application, you can find it here.


Concerning your other flaw claim i can only repeat, that it is your limited sudoku model, which cannot do trivial things like to find out, which cells have no givens, that prevents you from following this simple proof.

[Serg]

Hi, all!
I think the rule RW introduced in 2006 is not "UR1.1 rule", but his original rule. Let me call it as "RW's rule".
The first example was given by RW in 2006 (see thread Logical use of uniqueness technique in an uniqueness test, dedicated to this technique), several recent examples were posted in this thread too.

This is my attempt to define - what is "RW's rule".

RW rule of Sudoku candidates elimination
----------------------------------------------------
This rule describes just another rule of candidates elimination during solving of Sudoku puzzles.
Let's consider 4 empty cells of any Sudoku puzzle - A, B, C, D located in a such way, that A and B are placed in the same row X, C and D are placed in the same row Y (X <> Y), A and C are placed in the same column Z, B and D are placed in the same column T (Z <> T). Additionally, A and B must be placed in the same box P AND C and D must be placed in the same box Q (P <> Q) OR A and C must be placed in the same box R AND B and D must be placed in the same box S (R <> S). One possible example of cells arrangement is given below.

Code: Select all

+-----+-----+-----+
|. . .|. . .|. . .|
|. . A|B . .|. . .|
|. . C|D . .|. . .|
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+

If there exists pair of candidate digits (a,b) such, that solutions of given puzzle may contain the next fragment (candidate sets of A, B, C, D permit such configuration)

Code: Select all

+-----+-----+-----+
|. . .|. . .|. . .|
|. . a|b . .|. . .|
|. . b|a . .|. . .|
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+

but any solution must not contain the next fragment (candidate sets of A, B, C, D prohibit such configuration)

Code: Select all

+-----+-----+-----+
|. . .|. . .|. . .|
|. . b|a . .|. . .|
|. . a|b . .|. . .|
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+

then any solution of the puzzle must not contain fragment

Code: Select all

+-----+-----+-----+
|. . .|. . .|. . .|
|. . a|b . .|. . .|
|. . b|a . .|. . .|
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+

End of definition.

Serg

[Edited. I corrected some typos and added comments.]
[Edited2. I changed the name of described rule.]

[denis_berthier]

Real world:

Many eliminations in the sudoku world are based on similar contradictions.
if
"A" => 'X' true
"A" => 'X' false
then "A is false
in most cases, "X" is the status of a candidate,

This is totally unrelated to my statement.
This is totally different. This is proof by cases.

champagne's world

...
This is totally unrelated to my statement.
This is totally different. This is proof by cases.

so the proof for the UR1.1 is a proof by cases, I did not know the name

Where did I see the proof of UR1.1 is a proof by cases?

[tarek]

One thing for sure, despite the inflammatory nature of some exchanges, This discussion has been useful! So thanks to all participating.

If there exists pair of candidate digits (a,b) such, that solutions of given puzzle may contain the next fragment (candidate sets of A, B, C, D permit such configuration)
but any solution must not contain the next fragment (candidate sets of A, B, C, D prohibit such configuration)
then any solution of the puzzle must not contain fragment
End of definition.

Why don't we use: "Then (Candidates + Fragments) would prevent a single solution to the puzzle" which is then used as definition of DP. We can then move to say: "In a single solution puzzle, therefore, the extra candidates must be true"

tarek

[denis_berthier]

ONE MORE FLAW in RedEd "PROOF" of UR1.1

First of all, there is no flaw in Red Ed's proof, and crying that out in big blue letters does not change that.
It definitely says "if a puzzle-in-progress ... has pencilmarks as shown", then .... So there is no flaw, even if no such pattern would exist.

As I already answered to champagne, this flaw is nor exactly in the proof (my bad for negligent writing), it is in writing a "theorem" when there is no example for the conditions.

[As nobody has ever been able to give an example where the conditions of the proof are satisfied, the alternative conclusion cannot be discarded so easily.
...
It seems to me, as I already stated, that it should be a priority for the believers in the UR1.1 rule to exhibit an example. Good luck!

The examples have been found already in the old times, before you started to doubt this rule. Here is one with a pure UR1.1 from 2008.

Unless I've become suddenly unable to read, the pattern in this example is not the pattern discussed here. It is:

Code: Select all

ab ab
ab ac


Code: Select all

 3    9   *28   | 7   *28   1    | 6    4    5
 1    7    6    | 5    4    38   | 38   9    2
 4    5   *28   | 6   *23   9    | 7    18   13
----------------+----------------+---------------
 567  4    3    | 128  57   268  | 189  1256 1679
 567  2    9    | 138  57   4    | 138  1568 1367
 567  8    1    | 23   9    236  | 4    256  367
----------------+----------------+---------------
 2    3    7    | 89   68   5    | 19   16   4
 9    6    5    | 4    1    7    | 2    3    8
 8    1    4    | 239  36   23   | 5    7    69

If you want a recent application, you can find it here.

The pattern is an UR1+1 (or whatever name it should be called), not an UR1.1:

Code: Select all

abc ab
abd ab


Code: Select all

----------.-----------------.-------------------.
| 4  2  1  |  5      9   37  |  6     378   378  |
| 9  3  5  |  8      6   27  |  247   47    1    |
| 8  6  7  | *14+3  *14  123 |  239   5     39   |
:----------+-----------------+-------------------:
| 1  4  68 |  2      5   369 |  379   3789  3789 |
| 2  7  3  | *14+9  *14  8   |  5    ^149   6    |
| 5  9  68 |  134    7   136 |  134   2     348  |
:----------+-----------------+-------------------:
| 7  5  4  |  6      3   19  |  8    ^19    2    |
| 3  8  9  | ^17     2   4   | ^17    6     5    |
| 6  1  2  |  79     8   5   |  3479  3479  3479 |
'----------'-----------------'-------------------'

All this is not very convincing!!!

Concerning your other flaw claim i can only repeat, that it is your limited sudoku model, which cannot do trivial things like to find out, which cells have no givens, that prevents you from following this simple proof.

I'm disappointed. I thought you were smarter than repeating indefinitely the same absurdities (which I already answered), instead of finding counter-arguments or flaws in my proof (which depends only on basic logic, not on any particular model, as I already told you). But I guess you didn't even care to read my proof or my answers.