The New Sudoku Players' Forum

[denis_berthier]

UR1.1, again
I've never been very interested in rules based on the assumption of uniqueness, but the topic came out a few days ago in a conversation with Robert and it reminded me of an older conversation with Red Ed about UR1.1.
[2020/02/20: Added for clarity]:
1) The following discussion is not about rule UR1 but about UR1.1 (also named AR1 in Hodoku).
2) The following discussion is not about UR1.1 being true or not when one makes the assumption of uniqueness. It is about whether it can be proven without that assumption (or some other assumption yet to be explicited).

[2020/02/20: Added for clarity] As most discussions in any forum, this quickly spreads to unrelated topics. So, I'll keep this introductory post updated for the reader who wants a quick summary. At the end, I'll add relevant objections to my point of view and my answers.


UR1.1, definition
The UR1.1 rule I'll discuss is: if the following pattern of four cells spanning two rows, two columns and two blocks appears in a grid, then the value of the fourth cell is 3.

Code: Select all

1 2
2 13

[2020/02/20: Added for clarity] The standard definition of rule UR1.1 has an additional condition: the 4 UR cells must be "unclued". But I'll show later in this post that this condition is logically irrelevant.
[2020/02/20: Added for clarity] For contrast, the UR1 rule always supposes the assumption of uniqueness and it relies on the following pattern, where there's no need to make any assumption about "unclued" cells:

Code: Select all

12 12
12 123

There's no debate about UR1 (except whether one should accept the assumption of uniqueness, but that's a totally different topic.)


RedEd's formulation of UR1.1 and his proof
see http://forum.enjoysudoku.com/post63659.html#p63659
[2020/02/20: Added for clarity] RedEd puts the usual additional conditions on the rule: none of the 4 cells may have any givens. He then claims to have a proof independent on the assumption of uniqueness

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.

My old answer to RedEd's proof
If you continue reading the above-mentioned thread, you'll see that I found the proof very smart, but I had two objections:

Using a kind of reasoning similar to RedEd's, let me show that any puzzle that can be solved with UR1.1 can be solved without it.
Suppose there is a puzzle P that can be solved thanks to the application of UR1.1 but that couldn't without it. Define P' as P plus one of the 3 entries in the UR1.1 pattern [supposing UR1.1 was used once; add similar entries if UR1.1 was used several times]. Then, by the very definition of P, P' can't be solved. As the entry added to P was proven from the axioms of P, it can't have introduced a contradiction in P'; nor can it have introduced a non-uniqueness problem. We thus get a contradiction.
Notice that this doesn't mean UR1.1 would be useless: it may still lead to simpler solutions.

[2020/02/20 added for keeping this post up-to-date]: there's indeed a stronger result, with almost the same proof: any elimination that can be made with UR1.1 can be made in FOL without it

RedEd's "basic fact"

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.

on which his whole proof rests, becomes obviously false if we accept only constructive solutions: how could r1c1 = 2 be constructively proved from the axioms of Sudoku and the entries when r1c1 = 1 has already been constructively proved at the time the UR1.1 pattern is detected? (or, to put it differently, how could two contradictory values be constructively proved if the puzzle is consistent?)
Conclusion: RedEd's proof has an implicit assumption: we must accept any kind of solution, including non constructive ones, e.g. those obtained by recursive backtracking with guessing.

Those objections remain valid. But I think I can now have simpler and stronger arguments. (I may have already written this or part of this somewhere, but I'm not sure.)


Some basic reminders of First Order Logic (FOL) and their consequences
Theorem 1: Let S be a theory in FOL (e.g. the theory consisting of the 4 basic Sudoku axioms plus the givens of a puzzle P). Let T be a theorem of S, i.e. any formula that can be deduced from the axioms of T according to the principles of FOL (e.g. the assertion of a candidate as a value for some cell: rc=n). Then any formula F derivable from S+T is derivable from S.
The proof is obvious: take any proof of F using T and replace any mention of T in it by the proof of T in S. This gives a proof of F that doesn't explicitly use T.
Corollary (formal version): any candidate asserted at any step of a resolution of a puzzle (based on the principles of FOL) can be used in further steps exactly as if it was a given.
Corollary (intuitive version 1): FOL cannot make any difference between a given and a value derived from the givens.
Corollary (intuitive version 2): any tentative rule trying to make any difference between a given and a value derived from the givens is extra-logical.
[2020/02/20: Added for clarity]
1) the assumption of uniqueness IS the typical example of something extra-logical
2) using a predicate "unclued" or "not-a-given" or anything similar is the mark of some extra-logical input


Consequence for RedEd's proof
Due to the presence of the word "unclued" in it, the "fact" on which RedEd's proof relies is meaningless in FOL. As a result, the apparent paradox in RedEd's theorem and the theorem itself merely vanish into nothingness.
As a second result, any tentative formulation of an UR1.1 rule can only be what I first stated, without any mention of unclued cells.
[2020/02/20: Added for clarity] As a third result, if rule UR1.1 was somehow valid, it could only be because of some dependence on the assumption of uniqueness (or on some other extra-logical assumption).


Validity of the tentative UR1.1 rule?
The tentative UR1.1 rule under consideration here is as I stated it at the start: if the following pattern of four cells spanning two rows, two columns and two blocks:

Code: Select all

1 2
2 13

appears in a grid, then the value of the fourth cell is 3.
I can't see any logical reason why, if the first three cells are given, the fourth couldn't be 1.
This is not a proof that the rule is not valid, but I'm almost sure anyone can find a counter-example, e.g. a puzzle with the following template of givens:

Code: Select all

1 2
2 1

[2020/02/20: Added for keeping this post up-to-date] If you scroll downwards in this page, you'll see I have finally found (quite easily) a single-solution puzzle with such a pattern:

Code: Select all

12345678.
4......1.
5.9......
2176.4..5
3...1....
6..5231..
7.1..28..
8......2.
9.......3


[2020/02/24: Added for keeping this post up-to-date]
After some tweaking, I also found a puzzle directly contradicting the UR 1.1 rule as I stated it (scroll downwards):

Code: Select all

12345678.
4......1.
5.9......
2.76.4..5
3...1....
69.5231..
7.1..28..
8......2.
9.......3

The content of cells r1r4 x c1c2 is:

Code: Select all

1 2
2 18

UR1.1 would assign the value 8 to r4c2. But the unique solution has value 1 for that cell.


Final question
Is there any example of a real puzzle where a pure logic resolution leads to a situation with the

Code: Select all

1 2
2 13

pattern, where none of the four cells were given?
If not, all the discussions of UR1.1 were pointless.
[2020/02/20: Added for keeping this post up-to-date] Leren has found 5 single-solution puzzles in Hodoku with such a pattern. Scroll downwards in this page. I've then tried to generate more using Sudoku Explainer and it's quite easy.

[2020/02/20: Added for keeping this post up-to-date] At this point, all the single-solution puzzles satisfying the conditions of the above "final question" have the 3 in their unique solution. After trying with Sudoku Explainer, it seems very difficult to build one where the 3 is not in the solution. Conversely, it is very easy to build multi-solution puzzles where the 1, the 2 and the 3 in the last cell are in different solutions. This corroborates the above proof that UR1.1, if somehow valid, must depend on the assumption of uniqueness.


[2020/02/20: added for completeness]Main objections to my point of view: forthcoming

[creint]

No, if multiple subsolutions like UR exists then main puzzle has never a single solution.

An invalid sudoku but with logic you can fill in 3 of the 4 cells from UR r34c47.

Code: Select all

. 6 8 . 2 7 5 4 9
2 7 4 5 6 9 8 1 3
. 5 9 . 4 8 . 6 7
4 3 5 . 7 6 . 9 8
8 2 1 4 9 3 6 7 5
7 9 6 8 1 5 4 3 2
5 4 2 7 3 1 9 8 6
6 1 3 9 8 2 7 5 4
9 8 7 6 5 4 3 2 1

UR1.1 reduces possible solutions on invalid sudoku. In this case gives a single solution, while it had 2 solutions.

You can get all the solutions with brute-force.
Following statement is false if solving means finding a single solution with logic:

any puzzle that can be solved with UR1.1 can be solved without it

I think a valid sudoku cannot contain this property where all cells of the ur were empty.

[denis_berthier]

Following statement is false if solving means finding a single solution with logic:

any puzzle that can be solved with UR1.1 can be solved without it

Not only is it not false, but I can make it much stronger, with almost the same proof:
any elimination that can be made with UR1.1 can be made in FOL without it

[denis_berthier]

Hi Leren,
I agree that UR rules are often very ill presented, but you're missing my point.
First, I'm not discussing UR1, but the very special UR1.1.
And I'm not discussing whether one should accept the assumption of uniqueness or not. Everyone is free to do as they like, depending, as you say, on their trust on their puzzle provider.

This is about UR1:

Well, it's easy to answer your Final question first.
Here is a puzzle from a Hodoku collection of exemplars : ...3..1.8.5.4...9.39..6...7.342..............96..3...1..871...5.....2....4.6.8... You can apply "pure logic" to arrive at the following PM :

Code: Select all

*-----------------------------------*
| 4 7 26  | 3 29 59  | 1    256  8  |
| 8 5 126 | 4 27 17  |*6-23 9   *23 |
| 3 9 12  | 8 6  15  | 4    25   7  |
|---------+----------+--------------|
| 1 3 4   | 2 8  67  | 5    67   9  |
| 2 8 5   | 1 79 679 | 67   3    4  |
| 9 6 7   | 5 3  4   | 28   28   1  |
|---------+----------+--------------|
| 6 2 8   | 7 1  3   | 9    4    5  |
| 5 1 3   | 9 4  2   | 78   78   6  |
| 7 4 9   | 6 5  8   |*23   1   *23 |
*-----------------------------------*

So far, so good. But how did I arrive at the conclusion that r2c7 is not 2 and not 3. Pure logic ? I think not. It's because I trust that the puzzle maker would never publish a puzzle with 2 or possibly 3 solutions.

In SudoRules, I do have rules for UR1 to UR4. I never use them. But if anyone wants to use them, they can.

[Leren]

OK, I've replaced my previous diatribe by a shorter and more to the point post. Here is a puzzle from a Hodoku Exemplar list.

.5........6.5.42....8.71...4....36.8.........89.1..7..3...........2.7.1..72.3..9. With some simple moves you can get to the following PM

Code: Select all

*-------------------------------------------*
|*9  5  4    | 3   268  268 | 1   68   *7   |
|*7  6  1    | 5   89   4   | 2   38   *3-9 |
| 2  3  8    | 69  7    1   | 45  456   459 |
|------------+--------------+---------------|
| 4  1  57   | 79  259  3   | 6   25    8   |
| 56 2  3567 | 478 4568 68  | 9   345   1   |
| 8  9  356  | 1   2456 256 | 7   2345  345 |
|------------+--------------+---------------|
| 3  48 56   | 468 1    9   | 458 7     2   |
| 56 48 9    | 2   4568 7   | 3   1     456 |
| 1  7  2    | 468 3    568 | 458 9     456 |
*-------------------------------------------*

The 4 cells marked * meet your Final Question specification exactly with 9 instead of 1 and 7 in stead of 2. r2c9 <> 9 so = 3.

This move is described as Avoidable Rectangle, and is quite rare, but it does exist. The naming of this move has an interesting history, as the actual situation encountered would be more correctly named Almost Avoidable Rectangle.

Unfortunately this term was used for something else at the time (I believe Jason knows something about this), so to avoid confusion, for this situation the Almost was dropped.

I've got 4 more example puzzles from the Hodoku list if you want them.

Leren

[denis_berthier]

Hi Leren,
I don't know what happened. After posting my answer, I saw that your original post had disappeared.

OK, I've replaced my previous diatribe by a shorter and more to the point post. Here is a puzzle from a Hodoku Exemplar list.
.5........6.5.42....8.71...4....36.8.........89.1..7..3...........2.7.1..72.3..9. With some simple moves you can get to the following PM

Code: Select all

*-------------------------------------------*
|*9  5  4    | 3   268  268 | 1   68   *7   |
|*7  6  1    | 5   89   4   | 2   38   *3-9 |
| 2  3  8    | 69  7    1   | 45  456   459 |
|------------+--------------+---------------|
| 4  1  57   | 79  259  3   | 6   25    8   |
| 56 2  3567 | 478 4568 68  | 9   345   1   |
| 8  9  356  | 1   2456 256 | 7   2345  345 |
|------------+--------------+---------------|
| 3  48 56   | 468 1    9   | 458 7     2   |
| 56 48 9    | 2   4568 7   | 3   1     456 |
| 1  7  2    | 468 3    568 | 458 9     456 |
*-------------------------------------------*

The 4 cells marked * meet your Final Question specification exactly with 9 instead of 1 and 7 in stead of 2. r2c9 = 3.
This move is described as Avoidable Rectangle, and is quite rare, but it does exist.

That's a very interesting example. It shows that the UR1.1 discussion is not totally void of content.
Of course, it doesn't change my critics of UR1.1.
What does Hodoku do after reaching this resolution state?
Do you by chance know how to generate a puzzle with a given template? (my last but one question, the template being
1 2
2 1)

I've got 4 more example puzzles from the Hodoku list if you want them.

Yes, please

[Leren]

Here are the 5 Avoidable Rectangle puzzles from the Hodoku Exemplar list I have.

...195..2635..........3...88.........5.9..71.1..2....9..468..51......4.......7.2.
..5...........268.7....14.....1.68.....3......87...1.38.12.43...3..6..2.26.......
.86.4....2........1...76.9....4.7...8...9......9683.7....752..8.......457..3..1..
.6.....7....8456.2...73....83....2.52.6...9..57.2..................78.566...591.3
.5........6.5.42....8.71...4....36.8.........89.1..7..3...........2.7.1..72.3..9.

You may have to play around with the Hodoku solution path a bit to get to the AR state.

here is a link to the Hodoku article on ARs.

Leren

[denis_berthier]

Here are the 5 Avoidable Rectangle puzzles from the Hodoku Exemplar list I have.

...195..2635..........3...88.........5.9..71.1..2....9..468..51......4.......7.2.
..5...........268.7....14.....1.68.....3......87...1.38.12.43...3..6..2.26.......
.86.4....2........1...76.9....4.7...8...9......9683.7....752..8.......457..3..1..
.6.....7....8456.2...73....83....2.52.6...9..57.2..................78.566...591.3
.5........6.5.42....8.71...4....36.8.........89.1..7..3...........2.7.1..72.3..9.
You may have to play around with the Hodoku solution path a bit to get to the AR state.

Thanks, I'll see what I can do with them

here is a link to the Hodoku article on ARs.

I had a look at that Hodoku article about AR. It's illuminating:

Avoidable Rectangles differ from Unique Rectangles in that some cells of the UR have already been placed. If placing the remaining cell(s) would cause an UR, the sudoku maker would have had to supply one of the four cells as a given to avoid a possible second solution (hence the name). If therefore none of the already placed cells in the UR are givens, all UR Type x rules can be applied without change. There is one important difference though: Due to the placements sometimes only one of the UR candidates remains possible for the target cell. This can be confusing, but the logic still holds.

All this is pure nonsense. The proof for UR explicitly relies on the presence of the a and b candidates in the 4 cells. AR can therefore not be considered as a particular case of UR and invoking the proof of UR as a proof of AR, as Hodoku does, is utterly absurd.
I don't remember if you included this in your examples of nonsense about Uniqueness, but if not, you can add it.

[denis_berthier]

Finally, using Sudoku Explainer, I found manually a valid puzzle with the
1 2
2 1
pattern of givens in r1r4 x c1c2:

Code: Select all

12345678.
4......1.
5.9......
2176.4..5
3...1....
6..5231..
7.1..28..
8......2.
9.......3


After some tweaking, I found a puzzle directly contradicting the UR 1.1 rule:

Code: Select all

12345678.
4......1.
5.9......
2.76.4..5
3...1....
69.5231..
7.1..28..
8......2.
9.......3


The content of cells r1r4 x c1c2 is:
1 2
2 18
UR1.1 would assign the value 8 to r4c2. But the unique solution has value 1 for that cell.
[I have the SE pic but I don't know how to attach a pic.]

[Leren]

Hi Denis,

I removed my original post because I re-read Red Ed's UR1.1 and thought I was off topic. I would say that it is correct, with the proviso that the 21/12 pattern, which he shows as being completely removed from the 4 cells, has been done so without any previous Uniqueness move. Since the 21/12 pattern is invalid, so is the 12/21 pattern, and you can place the 3.

I checked that first Hodoku AR puzzle, and unfortunately they applied a prior UR to remove one of the AR candidates, so it seems that it was an argument in a circle.

There is supposed to be a feature to turn off particular moves in Hodoku, but I tried it but it didn't seem to work. Maybe it's a bug in Hodoku, or maybe I need to do something else.

Yes, I agree that the Hodoku description of AR's is absolute rubbish, hence my belief in a conspiracy theory about how Uniqueness moves are described on teaching sites.

Perversely though, the moves always work, because puzzles are never published with a valid 12/21 pattern without a given in one of the cells.

Leren

[Leren]

Hi Denis, cross posted again.

Just looking quickly at your example, you appear to have 3 givens in the 12/21 pattern cells. That's OK. I should have said that UR1.1 also requires that none of the 4 cells has a given.

Also, just rereading that Hodoku AR description again, it's confusing, but maybe not entirely False. They say that if a 12/21 pattern was valid, you would have to place a given in one of the cells.

On the other hand, what they don't say, is that if the 12/21 pattern was not valid, you would not have to place a given in one of the cells. However this second case is not True in logic, it's a convention, so the "logic" always appears to work, even though it's not strictly, well, logical.

So, just summarising this, puzzle makers have 2 options with 12/21 patterns. 1. If the pattern is valid, they have to put at least one given in the 4 cells or discard the puzzle. 2. If it's not valid, they don't have to put a given in the 4 cells.

Leren

[tarek]

Coming late to this conversation,

I thought that in a unique puzzle, the deadly pattern would result in more than 1 solution which is in contradiction with the uniqueness assumption. All of the uniqueness techniques aim to prevent this contradiction.

The problem therefore is in the definition of the deadly pattern. If the pattern is not deadly (i.e. has only one way of filling the candidates 1 and 2 in your example) then The elimination (even if correct) doesn't rely on the uniqueness assumption.

tarek

[Leren]

tarek wrote : I thought that in a unique puzzle, the deadly pattern would result in more than 1 solution ..... .

Hi Tarek, you have been caught by exactly the same way I was for many years, until I realised the truth. That part of your post is patently absurd, but I don't blame you, because you have been taught to think that way by reading the confusing descriptions on many of the teaching sites, and perversely, this faulty thinking doesn't result in you making any false eliminations, which just reinforces your belief.

A correct statement would go something like " ... in a unique puzzle, a fully exposed deadly pattern would result in a contradiction, so at least one other candidate in the DP cells must be true"

So, in both cases (to keep things simple just think of a Type 1 UR with 12 in a DP configuration with one extra cell having a 3), we would both place the 3 there.

But according to your statement, taken literally, if you didn't place the 3, there would be 2 other solutions ie the puzzle would have 3 solutions.

So, how do you know that the puzzle in fact doesn't have 3 solutions ? Well, there is no a priori way to deduce this, you take it on faith that the puzzle designer has ensured that a fully exposed DP would result in a contradiction.

Now I'm not trying to be holier than thou here. I thought exactly the way you did, until, in a Str8ts puzzle some years back, someone posted a puzzle with 3 solutions, any of the digits in the 3 candidate cell would produce a valid puzzle solution.

I played the UR move, entered the 3 and thought no more about it. Then one of the more astute Str8ts solvers pointed out that placing the other 2 values in the DP cell would also result in a valid solution, so the puzzle had 3 solutions.

So, I thought, what was going on here ? Were you supposed to place the 3 and regard the other 2 solutions as less valid than the one the UR move picked ?

Well, I thought that the geniuses on this forum would know more about this than me, so I started a thread on this question here.

I think it's fairly clear that the prevailing opinion was that a puzzle should only have one solution, otherwise it should be regarded as "unfair" although it must be admitted that not everyone agrees with this POV.

So, thinking about this a bit more, I came to the conclusion that a fully exposed DP must have either 0 solutions, or 2 solutions, and that in a unique solution puzzle, the 0 solution case is always used.

But which case do they always talk about on sites like Hodoku ? The 2 solution case. So, Hodoku talks about the 2 solution case here and says this

"A UR Type 1 exists, if one of the four cells of a possible UR has additional candidates. If those candidates were eliminated, the UR would exist, causing two solutions."

I can't believe this, it's absolute rubbish ! If you eliminate the extra candidates the number of solutions must be 0. Otherwise, if you place one of the other candidates the number of solutions must be 3 or more.

I think I'd better stop there, I'm having another UR rubbish description attack.

Leren

PS I'm aware of the Sudokus of Shame thread here, which is supposed to be a list of sites that put up puzzles having more than one solution.

I know Hodoku doesn't actually do this, but the way they explain how a UR Type 1 works, shouldn't they get an honourable (or is that dishonourable?) mention ?

Leren

PPS OK I'm back for more punishment. The gulity party this time is Andrew Stuart here. I'll just lift a few sentences from his UR page :

Unique Rectangles takes advantage of the fact that published Sudokus have only one solution.

There are two solutions to any Sudoku with this deadly pattern. If you have achieved this state in your solution something has gone wrong.

If the 1/5 were removed from that cell we would have a Deadly Pattern. This cannot be allowed to happen so its safe to remove 2 and 9 from that cell.

Again, if we read though this material carefully and take it literally, we have another example of a unique solution puzzle with at least 3 solutions (sic).

Leren

[denis_berthier]

Just looking quickly at your example, you appear to have 3 givens in the 12/21 pattern cells. That's OK. I should have said that UR1.1 also requires that none of the 4 cells has a given.

For some people yes, but look at my discussion of this point in the first post.

[Leren]

Hi Denis,

Don't quite get what you are saying, but I can provide you with a puzzle that has different variations of UR1.1. It's the sample puzzle that Hodoku uses here.

Note that it has an interchangable set of 68's in r24c13. In fact it has more than one such set. If r1c3 has 6 there is then another set 56 in r12c39.

Now here is the cool bit. Irrespective of which version of the grid you have there is always 14/43 in r13c17. In fact I think there are more of each type in this grid, if you keep on looking.

Leren

PS. Maybe there should be a UR Explanations of Shame thread, to list those sites whose UR explanations "merit" such an "honour". I've shown two, but I'll bet there are plenty more.

Leren