The New Sudoku Players' Forum

[denis_berthier]

a subject that does not deserve so much

As long as we are concerned with Sudoku, I agree. UR1.1 is of zero use. Nobody has been able to provide an example in case of non-uniqueness.
But you have seen that the discussion was also about some general ways of reasoning and approaching Sudoku solving.
First Order Logic (FOL) clearly implies one cannot make a difference between a given and a value deduced from the givens, in terms of the further inferences they allow. Contrary to eleven's unfounded but repeated claims, this has absolutely nothing to do with my model of resolution.
On the other hand, there is RedEd's very smart proof. As a mathematician, I find this type of reasoning highly "perverse". It is obviously non-constructive, as I objected long ago, but on this point (and only on this point) I accept the counter-objection that this is only a restriction from my constructive approach (though I can easily code this type on rule in SudoRules).
But what's discussed here is, considering the logical background recalled in my first post, what's the (other) extra-logical assumption in RedEd's proof? My two cents is uniqueness, because in case of non-uniqueness, it seems that the a/b/b/ac pattern cannot be found in any resolution path if there is no given in the a/b/c part. All the examples examined until now support this conclusion.

[denis_berthier]

Took the original UR1.1 puzzle from Hodoku : .5........6.5.42....8.71...4....36.8.........89.1..7..3...........2.7.1..72.3..9. and removed the 8 from r6c1 : .5........6.5.42....8.71...4....36.8..........9.1..7..3...........2.7.1..72.3..9.
The resulting puzzle has just 3 solutions :
954328167761594283238671459417953628825746931693182745346819572589267314172435896
954382167761594283238671459417953628625748931893126745346819572589267314172435896
954382167761594283238671459417953628825746931693128745346819572589267314172435896
The UR1.1 cells are always the same, so it would appear to work.

In my first answer, I hadn't yet analysed this example.

I've now given it to Sudoku Explainer, disabled its uniqueness rules (BUG and UR) and manually applied SE hints until SE proposed "brute force analysis" (which is probably DFS).
The state reached at this point for the 4 cells is:
79/179/79/379
In spite of the 3 being common to the 3 solutions, there is no hope of finding any UR1.1 here.

[Leren]

denis_berthier wrote : Actually, no. There are more solution with 7/9/9/7 than with 9/7/7/9. It is likely that the puzzle has several independent near-DP.s

Actually yes, there are 14 DP pairs exactly as described and detailed below. Of course I could have been just lucky, not creating some larger DP pattern in the augmented puzzle.

Hidden Text: Show

Code: Select all

      *       **       *
1     954326187761584239238971456415793628627458391893162745349615872586247913172839564
118   754326189961584237238971456415793628627458391893162745349615872586247913172839564
      *       **       *
2     954326187761584239238971465415793628627458391893162754349615872586247913172839546
119   754326189961584237238971465415793628627458391893162754349615872586247913172839546
      *       **       *
3     954326187761584239238971546415793628627458391893162754349615872586247913172839465
120   754326189961584237238971546415793628627458391893162754349615872586247913172839465
      *       **       *
4     954326187761584239238971564415793628627458391893162745349615872586247913172839456
121   754326189961584237238971564415793628627458391893162745349615872586247913172839456
      *       **       *
10    954362187761584239238971456415793628627458391893126745349615872586247913172839564
127   754362189961584237238971456415793628627458391893126745349615872586247913172839564
      *       **       *
11    954362187761584239238971465415723698627498351893156724349615872586247913172839546
128   754362189961584237238971465415723698627498351893156724349615872586247913172839546
      *       **       *
12    954362187761584239238971465415793628627458391893126754349615872586247913172839546
129   754362189961584237238971465415793628627458391893126754349615872586247913172839546
      *       **       *
13    954362187761584239238971546415723698627498351893156724349615872586247913172839465
130   754362189961584237238971546415723698627498351893156724349615872586247913172839465
      *       **       *
14    954362187761584239238971546415723698627849351893156724349615872586297413172438965
131   754362189961584237238971546415723698627849351893156724349615872586297413172438965
      *       **       *
15    954362187761584239238971546415723698627849351893156724389615472546297813172438965
132   754362189961584237238971546415723698627849351893156724389615472546297813172438965
      *       **       *
16    954362187761584239238971546415793628627458391893126754349615872586247913172839465
133   754362189961584237238971546415793628627458391893126754349615872586247913172839465
      *       **       *
17    954362187761584239238971564415723698627859341893146725349615872586297413172438956
134   754362189961584237238971564415723698627859341893146725349615872586297413172438956
      *       **       *
18    954362187761584239238971564415723698627859341893146725389615472546297813172438956
135   754362189961584237238971564415723698627859341893146725389615472546297813172438956
      *       **       *
19    954362187761584239238971564415793628627458391893126745349615872586247913172839456
136   754362189961584237238971564415793628627458391893126745349615872586247913172839456
      *       **       *

wrt to your last post (we cross posted). I thought the 3 being in all 3 solutions was just a fluke, which is why I looked for other multiple solution puzzles.

In any event, if I was told that a puzzle may not have a unique solution, I would never play any uniqueness move.

Leren

[denis_berthier]

wrt to your last post (we cross posted). I thought the 3 being in all 3 solutions was just a fluke, which is why I looked for other multiple solution puzzles.
In any event, if I was told that a puzzle may not have a unique solution, I would never play any uniqueness move.

Of course. But they say UR1.1 doesn't depend on uniqueness.

What was surprising is seeing Sudoku Explainer fall into the trap.

[Leren]

Hi denis,

If you look carefully at the 3 solution puzzle, you'll notice that it has a 7 cell unclued DP in r1c56, r5c16, r6c156.

You can split this up into an unclued 4 cell DP (28) in r16c56 and another one (68) in r56c16, with common cell r6c6, which can have 3 values. Note that the UR1.1 cells never formed a DP and resolve uniquely.

Code: Select all

*------------------------------*
| 9  5 4 | 3 *28  *28  | 1 6 7 |
| 7  6 1 | 5  9    4   | 2 8 3 |
| 2  3 8 | 6  7    1   | 4 5 9 |
|--------+-------------+-------|
| 4  1 7 | 9  5    3   | 6 2 8 |
|#68 2 5 | 7  4   #68  | 9 3 1 |
|#68 9 3 | 1 *28 #*268 | 7 4 5 |
|--------+-------------+-------|
| 3  4 6 | 8  1    9   | 5 7 2 |
| 5  8 9 | 2  6    7   | 3 1 4 |
| 1  7 2 | 4  3    5   | 8 9 6 |
*------------------------------*

This is far as I got with just basics, not too fancy chains and of course no uniqueness moves. Can't see why SE wouldn't get this far.

Leren

[denis_berthier]

If you look carefully at the 3 solution puzzle, you'll notice that it has a 7 cell unclued DP in r1c56, r5c16, r6c156.
You can split this up into an unclued 4 cell DP (28) in r16c56 and another one (68) in r56c16, with common cell r6c6, which can have 3 values.

Code: Select all

*------------------------------*
| 9  5 4 | 3 *28  *28  | 1 6 7 |
| 7  6 1 | 5  9    4   | 2 8 3 |
| 2  3 8 | 6  7    1   | 4 5 9 |
|--------+-------------+-------|
| 4  1 7 | 9  5    3   | 6 2 8 |
|#68 2 5 | 7  4   #68  | 9 3 1 |
|#68 9 3 | 1 *28 #*268 | 7 4 5 |
|--------+-------------+-------|
| 3  4 6 | 8  1    9   | 5 7 2 |
| 5  8 9 | 2  6    7   | 3 1 4 |
| 1  7 2 | 4  3    5   | 8 9 6 |
*------------------------------*

It's a nice example how one can reach a DP+1 on 7 cells (and smaller ones).

What I don't see yet is: as we can't use uniqueness for this puzzle, is there anything we can we do with these DPs, except conclude that it is impossible to reach a UR1.1 pattern from this state?

This is far as I got with just basics, not too fancy chains and of course no uniqueness moves. Can't see why SE wouldn't get this far.

Actually, I finally succeeded in getting this far with SE. But very far from using only basics. It requires all sort of complicated chains. And it supposes one rejects all the hints for trying DFS. Which solver did you use?

[Edit] I tried Hodoku. It easily reaches the same point as you. I also tried SudoRules and it reaches the same point; the hardest patterns used are whip[3] and bivalue-chain[4].
I don't know what happens with SE.

[Leren]

Hi denis, I used my own solver. Apart from basics, it only needed 5 chains, none fancy branching or networky. I set my solver up to only use chains that solve a cell, which shortens the solution path.

At this stage it should be obvious that the puzzle has 3 solutions, just put any value in r6c6 and you'll get a different valid solution for each value.

BTW, there is another way to look at UR1.1. If you look at Hodoku here you'll see that they make the clever observation that, in my words, " A UR move doesn't go away because you may have eliminated some of the pattern cell candidates. As long as the pattern cell is unclued (even if solved), you can mentally "put back" candidate(s) into it so that you can see a more standard uniqueness move.

So you can picture Red Ed's move as :

Code: Select all

12  12

12  12+3

ie I don't see any fundamental difference between UR1.1 and good old UR 1. Takes a bit of getting used to but it works - one of the best sections in Hodoku IMHO.

Leren

[denis_berthier]

Hi Leren,

Hi denis, I used my own solver. Apart from basics, it only needed 5 chains, none fancy branching or networky. I set my solver up to only use chains that solve a cell, which shortens the solution path.
At this stage it should be obvious that the puzzle has 3 solutions, just put any value in r6c6 and you'll get a different solution for each value.

Cross-posting again. Both Hodoku and SudoRules easily get to the same point, with short chains.

BTW, there is another way to look at UR1.1. If you look at Hodoku here you'll see that they make the clever observation that, in my words, " A UR move doesn't go away because you may have eliminated some of the pattern cells. As long as the pattern cell is unclued, you can mentally "put back" a candidate into it so that you can see a more standard uniqueness move.
So you can picture Red Ed's move as :

Code: Select all

12  12
12  12+3

ie I don't see any fundamental difference between UR1.1 and good old UR 1. Takes a bit of getting used to but it works - one of the best sections in Hodoku IMHO

Yes, but...
1) The usual solving approach based on successive eliminations of candidates pertains to the general approach named "progressive domain restriction" in the domain of Constraint Satisfaction Problems. Re-introducing eliminated candidates is re-enlarging the domains of the variables. It breaks the guarantee of convergence to a solution.
From a computational point of view, having fewer candidates allows to restrict the potential patterns to be used; if we do not eliminate the candidates for good, we may face computational problems.
I have a very concrete example in SudoRules. Braids are more complex than whips. If I allowed deleted candidates to participate in the definition of whips (it'd be an extended definition), I'd get something exactly as powerful as braids (and no more!) but computationally extremely more inefficient.

2) This raises the question of which candidates you may "put back". The condition that they must not be in direct conflict with the givens is inconsistent. What if they are in direct conflict with a value V obtained by Singles? What if V is obtained by slightly more complex rules?

3) In any case, it doesn't guarantee that there is any possibility of finding an UR1.1 by applying some rules in some order.

4) If you have to refer to a possibly camouflaged UR1 in order to justify UR1.1, then the main claim of the UR1.1 believers crumbles: it depends on uniqueness

What I think: the conditions on UR1.1 with the unclued-cells condition are impossible to satisfy; every example we have tried until now corroborates this. Moreover, the reasoning in my first post shows that such a condition cannot have any consequence.

[Serg]

Hi, Denis!
To me, we are discussing 2 different entities.

1. "UR1.1 rule" as you defined it in the beginning of this thread:

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

You repeated "UR1.1 rule" definition, given by Myth Jellies in 2008 (he also invented the name "UR1.1"). This construction ("rule") was introduced by Myth Jellies in discussion with you about "confluence property", and it wasn't intended in any way for practical use. You asked an example to demonstrate feasibility of UR1.1 rule, but it seems such examples don't exist.

2. Unnamed rule introduced by RW in 2006. I defined this rule formally earlier in this thread. There some examples, demonstrating this rule (the first one was given by RW in 2006). I propose to call this rule as "RW's rule". This rule has definitely some practical value and must be discussed separately if somebody is interested in that discussion. Though this rule has something in common with "UR1.1 rule" defined above, I think this is different entity.

Serg

[denis_berthier]

You repeated "UR1.1 rule" definition, given by Myth Jellies in 2008 (he also invented the name "UR1.1"). This construction ("rule") was introduced by Myth Jellies in discussion with you about "confluence property", and it wasn't intended in any way for practical use.

Is this really how the UR1.1 appeared? I don't know. And I've lost track of these old threads. But it's true anyway that it disrupts confluence when it is introduced in a theory that has it.

You asked an example to demonstrate feasibility of UR1.1 rule, but it seems such examples don't exist.

At least, nobody has provided any example.

2. Unnamed rule introduced by RW in 2006. I defined this rule formally earlier in this thread. There some examples, demonstrating this rule (the first one was given by RW in 2006). I propose to call this rule as "RW rule". This rule has definitely some practical value and must be discussed separately if somebody is interested in that discussion. Though this rule has something in common with "UR1.1 rule" defined above, I think this is different entity.

There's already an UR1 rule (I have no idea who invented it), with clear conditions and supposing uniqueness, for which there's no debate (see the Hodoku doc). I'm not sure of your tentative definition, but it's a good idea if you want to explain it in another thread. Can you make it more general than the usual UR1?...

[Mauriès Robert]

Hi Denis and Leren,
I will not hide from you that I have difficulty following your many exchanges on this subject, so what I am going to write may be trivial or already said, unless it is downright untrue.
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

[Serg]

Hi, Denis!

... Can you make it more general than the usual UR1?...

I am not quite understand - what generalization do you mean.

Unformally speaking, UR1 prevents appearing U4 unavoidable set (or Deadly Pattern) permutations by "breaking" them by extra digit. RW's rule deals with the same U4 unavoidable set, but only when one permutation of UA set is prohibited by some external technique. The rule says - if the first permutation is prohibited, then the second permutation will be prohibited too.

Of course, RW's rule can be generalized for all possible strongly minimal UA sets (U6, ...) or all Deadly Patterns.

Serg

[StrmCkr]

Unique rectangle uses strong link and matches a M- ring frequently.

If you want a non uqiness argument for the 1.1 redeced ur. Strong links and weaklinks still exsist in peniclmark states even if you clear digits from a non given cell same as the ur concept.

Ill see if i can find the mring examples from the past.

81 string vs 729 string. 81 is real the 729 is cause and effect blr from the inital clues are they only pms that are permently removed.

Side note adding/removing clues change the starting state
Removing pencilmarks does not.

[Leren]

Just to answer some of the comments by denis on my previous post.

For the avoidance of any semantic misunderstanding the phrase I used was mentally "put back". By this I meant that you don't actually reintroduce the eliminated candidate, you just imagine what the puzzle was like before you eliminated it.
As to whether the imagined reintroduced candidate is True or False in the solution, in fact it's always False (after all, it has been eliminated). Whether it's elimination was "easy" or "hard" is irrelevant.

There is a similar trick that comes up, for example, in UR type 6's. I've got an example where I can eliminate 4 candidates in a 4 cell UR Type 6 pattern, but if I make the eliminations sequentially, I will miss some of the others. What I do is check all of the 8 UR digits in the pattern, to see if they can be proven False. A candidate that has already been proven False is not immediately eliminated and may form part of the proof that another candidate is False.
So you might characterise this as "delaying the elimination of a False candidate" rather than "reintroducing" it.

As to the issue of whether I'm a UR1.1 believer, I am, but I also believe it relies on uniqueness, so I'm not one of "them", whoever "they" are.

The 3 solution puzzle seemed to support the non-uniqueness argument, but that was only because the non-uniqueness did not involve any of the UR1.1 cells, so it seemed to work.

Imagine if I was told that the puzzle had multiple solutions, but that the solutions for Boxes 1 and 3 were unique. Then I suppose you could use UR1.1 if it came up in those boxes, but who on earth would propose such a "contrived" puzzle?

Leren

[tarek]

wrt Sukaku Explainer,

The GUI still does a Brute Force Check Before advanced techniques. Currently it would prevent advancing puzzles via "Solve Step" button if it doesn't have a single solution.

In the current Sukaku explainer. Some initial puzzle related checks have been disabled to allow The use of Pencilmark sudoku (Sukaku). This means that Currently it trusts the puzzle to have a single solution until we reach the advanced techniques stage