The New Sudoku Players' Forum

[Leren]

Hi denis, well, I've still got my dunce cap on standby but there I go again. While I was waiting for your reply I thought of a better approach, which is so simple its effectively tautological.

Code: Select all

a.bdefghjk   b.a

b.a          a.bc

Here is diagram 3 again, this time with added extra candidates to the right of the decimal point in the top left hand cell. Now here is the crazily simple part. We know, by definition, (or by diagram 1 if you will), that they are all false.

So you can simply remove them, tautologically, in any order you like, to arrive at diagram 2. This is basically the reverse of what they do in Hodoku where they put back False candidates to make a UR pattern clearer (ie they essentially move from diagram 1 to diagram 2) by putting back known False a's and b's.

If this line of reasoning is correct, a corollary of this is that, if you can simply move from diagram 1 to diagram 2 by putting back False a's and b's so that it becomes a UR.1. Then since that relies on uniqueness in a unique puzzle, so does UR1.1, a fact which you say you are pretty convinced of but up to now haven't absolutely proven, to your satisfaction. I see that Mauriès Robert is saying basically the same thing, but without a proof, and you say you agree with him.

Leren

[denis_berthier]

Sorry Robert, but your example shows nothing. It is as relevant as an old example given by Denis.
The first condition to produce an example is to have no given in the UR area.
BTW, reading your comments on the UR1.1 logic, it seemed to me that you understood the proof. This example is the proof that I was wrong

OR, it is the case that Robert understood the proof in my first post that there can't be any difference between the two versions of the rule - which you haven't yet understood.
But if YOU are able to produce a counter-example, we are eager to see it.

[champagne]

Sorry Robert, but your example shows nothing. It is as relevant as an old example given by Denis.
The first condition to produce an example is to have no given in the UR area.
BTW, reading your comments on the UR1.1 logic, it seemed to me that you understood the proof. This example is the proof that I was wrong

OR, it is the case that Robert understood the proof in my first post that there can't be any difference between the two versions of the rule - which you haven't yet understood.
But if YOU are able to produce a counter-example, we are eager to see it.

producing a valid counter example is the duty of thoose who can not understand the logic.
EDIT or to be more precise of thoose who tell that the logic is false
EDIT 2 and as for me there is no doubt that the logic is correct, I don't believe that anybody will find it

[denis_berthier]

Code: Select all

a.bdefghjk   b.a
b.a          a.bc

Here is diagram 3 again, this time with added extra candidates to the right of the decimal point in the top left hand cell. Now here is the crazily simple part. We know, by definition, (or by diagram 1 if you will), that they are all false.
So you can simply remove them, tautologically, in any order you like, to arrive at diagram 2. This is basically the reverse of what they do in Hodoku where they put back False candidates to make a UR pattern clearer (ie they essentially move from diagram 1 to diagram 2) by putting back known False a's and b's.

It's clear that I prefer your approach to that of Hodoku. Erasing some candidates already proven to be false is less hair-raising than re-adding some.
So, we have a solution in two steps. In the first step, we prove that these candidates are false. In the second step, having proven they are false, we re-start from the beginning and we erase them in any convenient order. Very smart!

If this line of reasoning is correct, a corollary of this is that, if you can simply move from diagram 1 to diagram 2 by putting back False a's and b's so that it becomes a UR.1. Then since that relies on uniqueness in a unique puzzle, so does UR1.1, a fact which you say you are pretty convinced of but up to now haven't absolutely proven, to your satisfaction. I see that Mauriès Robert is saying basically the same thing, but without a proof, and you say you agree with him.

You prove that the rule is true with uniqueness, but you don't prove there's no proof without uniqueness.

Fundamentally, what I have proven about UR1.1 in my first post is, in the absence of any extra-logical conditions (e.g. uniqueness) my version of it and the version with the "unclued" condition are equivalent in terms of the inferences that they allow. I also gave a counter-example to my version (and Robert found one more). So, I think this pretty much closes the case in the absence of uniqueness.
In case of uniqueness, you've just shown that a UR1.1 allows to exhibit some underlying UR1. Therefore the two are equivalent in this case also.

[Mauriès Robert]

Hi Leren and Denis

.... I see that Mauriès Robert is saying basically the same thing, but without a proof, and you say you agree with him.

I did indeed write:

It seems to me that it is impossible, in a puzzle, to see the following UR1.1 configuration appearing
a b
b ac
otherwise than :
- either because a and b are data,
- or because it is possible to eliminate by logical resolution procedures (basic techniques, AIC, track, braid, etc...) candidates b and a (in red) from a following UR1 configuration
ab ba
ba abc

My reasoning leading to this statement, in the non-trivial case where a/b/a are not data, is as follows:
The elimination of some candidates from the four cells where UR1.1 will appear is done with the basic techniques (singles, alignments, closed sets), but under no circumstances will a and b be eliminated by this means in these cells, because otherwise UR1.1 would not appear.
Thus, after this stage of resolution the configuration will be the following where the . are remaining candidates:
(ab...) (ba...)
(ba.) (abc....)
The reason why UR1.1 appears is that the candidates not belonging to UR1.1 have been eliminated one by one using advanced techniques, first (confluence property) the candidates represented by . to achieve the configuration of an UR1
(ab) (ba)
(ba) (abc)
But perhaps you'll have a problem with that reasoning?
Robert

[denis_berthier]

It seems to me that it is impossible, in a puzzle, to see the following UR1.1 configuration appearing
a b
b ac
otherwise than :
- either because a and b are data,
- or because it is possible to eliminate by logical resolution procedures (basic techniques, AIC, track, braid, etc...) candidates b and a (in red) from a following UR1 configuration
ab ba
ba abc

My reasoning leading to this statement, in the non-trivial case where a/b/a are not data, is as follows:
The elimination of some candidates from the four cells where UR1.1 will appear is done with the basic techniques (singles, alignments, closed sets), but under no circumstances will a and b be eliminated by this means in these cells, because otherwise UR1.1 would not appear.
Thus, after this stage of resolution the configuration will be the following where the . are remaining candidates:
(ab...) (ba...)
(ba.) (abc....)
The reason why UR1.1 appears is that the candidates not belonging to UR1.1 have been eliminated one by one using advanced techniques, first (confluence property) the candidates represented by . to achieve the configuration of an UR1
(ab) (ba)
(ba) (abc)
But perhaps you'll have a problem with that reasoning?

Interesting approach.
Trying to use the confluence property to change the order of the eliminations/assertions is a good idea, but you need to be more precise about how to do it.
Suppose you want to eliminate x but you only have a resolution path where this elimination depends on the previous elimination/assertion of y, z.... Then you want to invert the eliminations. How? First try:
First keep the same resolution path, but do not effectively eliminate/assert y, z... Just remember that they are false/true. You can then continue the same path until x is eliminated (*). Then the confluence property ensures you can still eliminate/assert y, z, ...
If you need to do several inversions, you can restart this as many times as necessary.
Of course, this proof supposes that the set of rules you are using has the confluence property. But, if you haven't yet used uniqueness, I don't know other rules that could break confluence.

(*)But this first try breaks at this point. The rule that eliminated x in the original path may no longer be available (because it may have relied on y, z, ... being eliminated/asserted). And the confluence property doesn't guarantee that another rule will be available to do the same job.
The confluence property doesn't guarantee that the eliminations/assertions can be done in any arbitrary order.

[Edit] The last remark also applies to procedures like T&E(1). That's why T&E(1) may have to be repeated several times for each candidate. Otherwise the final result would depend on the particular order used to try the candidates.

[Mauriès Robert]

Hi Denis,
With regard to my earlier proposed demonstration of UR1.1 (a/b/b/ac), You write :

*.... The confluence property doesn't guarantee that the eliminations/assertions can be done in any arbitrary order.

In this case, rather than invoking confluence to ensure that candidates can be eliminated in a chosen order, the reasoning is as follows:
x being one of the candidates different from a b and c in one of the cells of the probable UR1.1, it is possible* to construct a resolution tree (DFS) from x which leads to a contradiction, otherwise x not being eliminated, there would not be the expected UR1.1 in these four cells.
It is obvious that with this procedure, some eliminations can be tedious, but this is not the problem since it is only a question here of establishing the proof of the result.
Robert
* the number of puzzle candidates is finited

[denis_berthier]

x being one of the candidates different from a b and c in one of the cells of the probable UR1.1, it is possible* to construct a resolution tree (DFS) from x which leads to a contradiction, otherwise x not being eliminated, there would not be the expected UR1.1 in these four cells.
It is obvious that with this procedure, some eliminations can be tedious, but this is not the problem since it is only a question here of establishing the proof of the result.

ok, this works

[eleven]

It seems to me that it is impossible, in a puzzle, to see the following UR1.1 configuration appearing
a b
b ac
otherwise than :
- either because a and b are data,
- or because it is possible to eliminate by logical resolution procedures (basic techniques, AIC, track, braid, etc...) candidates b and a (in red) from a following UR1 configuration
ab ba
ba abc
Therefore, since the use of UR1 is justified only by the announced uniqueness of the solution of the puzzle, the same applies to the use of UR1.1 which no other reason can justify.
Sincerely
Robert

I did not understand, what you mean. That you can never reach a UR1.1 pattern, when solving a puzzle ? Of course you can. Just eliminate one of the bivalues. I said this in this thread and gave an example 2008 here.

[eleven]

Here is an example for the RW's rule.

....5..6.......5.445..79.8..47326..562..9.43.........6..6.3.74...48.53...32.17.58
With basics you come here:

Code: Select all

+-------------------+-----------------+-----------------+
| #127+8 #17  138   | #12   5    4    | *19   6    39   |
| #12     6    9    | #12   8    3    |  5    7    4    |
|  4      5    13   |  6    7    9    |  12   8    23   |
+-------------------+-----------------+-----------------+
| *18     4    7    |  3    2    6    | *89   19   5    |
|  6      2    18   |  5    9    18   |  4    3    7    |
|  3      9    5    |  7    4    18   |  28   12   6    |
+-------------------+-----------------+-----------------+
|  5      8    6    |  9    3    2    |  7    4    1    |
| #17    #17   4    |  8    6    5    |  3    29   29   |
|  9      3    2    |  4    1    7    |  6    5    8    |
+-------------------+-----------------+-----------------+

There are 2 combined UR's 12r12c14 and 17r19c12, with a single extra candidate 8 (you also get that by eliminating 12 and 17 from r1c1).
Additionally there is an xy-wing 189 (*-ed cells), which eliminates 1 from r1c1.
So you can safely set 8 in r1c1 without assuming uniqueness.

....5..6.......5..45..79.8..47326..562..9.43.........6..6.3.74...48.53...32.17.58
Without the 4 in r2c9 (3 solutions) you come here with a kite 8:

Code: Select all

+-------------------+-------------------+-------------------+
| 1278  17    1389  | 12    5     348   | 19    6     349   |
| 128   6     139   | 12    48    348   | 5     7     349   |
| 4     5     13    | 6     7     9     | 12    8     23    |
+-------------------+-------------------+-------------------+
| 18    4     7     | 3     2     6     | 89    19    5     |
| 6     2     18    | 5     9     18    | 4     3     7     |
| 3     9     5     | 7     48    148   | 28    12    6     |
+-------------------+-------------------+-------------------+
| 5     8     6     | 9     3     2     | 7     4     1     |
| 17    17    4     | 8     6     5     | 3     29    29    |
| 9     3     2     | 4     1     7     | 6     5     8     |
+-------------------+-------------------+-------------------+

Here you could eliminate 17 from r1c1 and for the 12 UR there is a UR type 3, which would eliminate 1r12c1 (easier to see with the external candidates 1r48c1).
So after using the xy-wing 189, which eliminates 1r1c1 you can safely eliminate 7r1c1 and 1r2c1.

With this one (no 5 in r3c2, 2 solutions)
....5..6.......5.44...79.8..47326..562..9.43.........6..6.3.74...48.53...32.17.58
you need harder steps to arrive here, where you safely can remove the 7 from r1c1:

Code: Select all

+----------------+----------------+----------------+
| 2378 17   138  | 12   5    4    | 129  6    239  |
| 12   169  19   | 126  8    3    | 5    7    4    |
| 4    156  35   | 126  7    9    | 12   8    23   |
+----------------+----------------+----------------+
| 18   4    7    | 3    2    6    | 89   19   5    |
| 6    2    18   | 5    9    18   | 4    3    7    |
| 35   59   359  | 7    4    18   | 28   12   6    |
+----------------+----------------+----------------+
| 58   58   6    | 9    3    2    | 7    4    1    |
| 17   17   4    | 8    6    5    | 3    29   29   |
| 9    3    2    | 4    1    7    | 6    5    8    |
+----------------+----------------+----------------+

Of course these multi solution puzzle eliminations don't make the puzzle much easier, but they exist and are easy to spot for solvers used to uniqueness patterns.
And i am sure, that much better examples can be found, if there is really searched for.

[Mauriès Robert]

Hi Eleven,
You write:

It seems to me that it is impossible, in a puzzle, to see the following UR1.1 configuration appearing
a b
b ac
otherwise than :
- either because a and b are data,
- or because it is possible to eliminate by logical resolution procedures (basic techniques, AIC, track, braid, etc...) candidates b and a (in red) from a following UR1 configuration
ab ba
ba abc
Therefore, since the use of UR1 is justified only by the announced uniqueness of the solution of the puzzle, the same applies to the use of UR1.1 which no other reason can justify.
Sincerely
Robert

I did not understand, what you mean. That you can never reach a UR1.1 pattern, when solving a puzzle ? Of course you can. Just eliminate one of the bivalues. I said this in this thread and gave an example 2008 here.

What I am saying in this comment is that, apart from the case where a and b are data in the cells not containing c, the appearance of a UR1.1 comes from a UR1 that can be identified in the earlier stages of resolution. And that only this can justify the placement of c.
Moreover, Denis and I have given in this thread 3 examples of puzzles that demonstrate that nothing else can justify the use of a UR1.1.
- a single solution puzzle where the UR1.1 rule is not respected (Denis)
- a multiple solution puzzle where the rule UR1.1 is respected by all the solutions (Denis)
- a multiple solution puzzle where the UR1.1 rule is not respected for some solutions (me).
Sincerely
Robert
PS : I note that in 2008 you were using tracks, at least the same notations that I use today !

[eleven]

To clarify some wording.
The uniqueness assumption means, that the solver trusts the puzzle creator, that the puzzle is unique. Then and only then any uniqueness technique can be used safely. Uniquenes techniques therefore are per definition invalid for multi solution puzzles, and it is a contradiction in terms (oxymoron) to talk about uniqueness, when speaking about valid techniques for multi solution puzzles.

However RW himself did that, because his method is very similar and related to unique rectangles (also BUG lites and many MUG's can be used). But this only refers to the use of the same patterns, and partially the same eliminations, and has nothing to do with the common understanding of uniqueness, where a puzzle must have exactly one solution.

In the uniqueness case (UR's) we can eliminate all, what leads to two possible ways of solving the UR cells, whereas in the non-uniqueness case (RW rule) we show, that one way of solving the pattern is impossible, therefore the other one must be impossible too and we can eliminate all, which leads to that one.

So yes, for RW's rule you need the same patterns as for the uniqueness methods, but there is no hidden uniqueness in the rule itself.

What the proofs for both methods have in common is, that (like the 16 clue proof) they use the fact, that in an unavoidable set of a solution grid digits can be exchanged to get another solution grid. Different to unique puzzles the solutions of multi solution puzzles have unavoidable sets without a clue (but precisely not, where RW's rule is applicable).

[Hajime]

UR or UR1.1 is not applicable for overlapping Sudoku's?
Consider a Samurai with
ab ba
ba abc
in the first Sudoku (#1) and
abc x
bc c
in the middle Sudoku (#3) and abc is in the overlapping box.
Then you cannot solve Sudoku #1 first and state c in abc (UR constraint).
Because if you solve Sudoku #3 first, then there will be an a in abc.
Correct?
If abc is not in an overlapping area UR is applicable?

[eleven]

UR or UR1.1 is not applicable for overlapping Sudoku's?

Not with overlapping boxes (cells), because you have an additional constraint from the other sudoku (like in the diagonal cells of an X-Sudoku).

[creint]

Yes deadly patterns are still there.
But you can't apply them unless you know what all the constraints are doing.