The New Sudoku Players' Forum

[Hajime]

Be careful applying this method in puzzles consisting of overlapping Sudoku's like a Samurai if some of the four cells are within an overlapping part.

[denis_berthier]

Don't quite get what you are saying,

I have added a few lines to my initial post, for better clarity.
In a word, my main point is, UR1.1 (in whichever of its two forms), cannot be proven without the assumption of uniqueness (or some other extra-logical assumption). The presence in a rule of a predicate "unclued" or "non-given" ... is a symptom of such hidden assumptions.

I can provide you with a puzzle that has different variations of UR1.1. It's the sample puzzle that Hodoku uses here.

The link is to the general page for Uniqueness. I don't see which example you mean.

[tarek]

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"

Thanks,
It looks that I always thought that a DP is what you were referring to as "fully exposed deadly pattern". From my work in Puzzle generation and rating in several variants, I found that the only way to apply uniqueness properly is to consider DP as "fully exposed and unrestricted deadly pattern" …

The problem therefore is in the basic definition of DP so that we don't use any adjectives with it.

If we nail the definition of DP correctly (also covering variants) then I think we would reduce ambiguity. The wording as you and Denis showed is important but my thought of a DP is along the lines of "in the absence of extra candidates would result in 2 ways of filling the pattern cells". In a unique puzzle this results in multiple solutions which contradicts the uniqueness and therefore the extra candidates are true to avoid this contradiction (as you said)

With variants you have to be careful in applying DP as there could be Possible external restrictions that can invalidate the DP therefore this potential DP has to be free from these possible restrictions in addition to being fully exposed in order to apply uniqueness techniques

With your use of very precise wording I hope that what I said still makes sense

Be careful applying this method in puzzles consisting of overlapping Sudoku's like a Samurai if some of the four cells are within an overlapping part.

Yes as you have to consider another row & column

tarek

[Leren]

denis_berthier wrote : The link is to the general page for Uniqueness. I don't see which example you mean.

Just scroll down the page a bit and you'll see three slightly different variations of the same solution grid. Leren
'

[Leren]

tarek wrote :The wording as you and Denis showed is important but my thought of a DP is along the lines of "in the absence of extra candidates would result in 2 ways of filling the pattern cells". In a unique puzzle this results in multiple solutions which contradicts the uniqueness and therefore the extra candidates are true to avoid this contradiction (as you said)

Hi Tarek, I still don't think your wording is right. In a unique puzzle, you can fully expose the DP and fill it in both ways, but you won't get two solution grids, you will get two failures, ie you will eventually get at least one cell with 0 candidates.
Try it on an example and I'm pretty sure this is what you'll find. This is what they never say in the teaching sites like Hodoku, and it took me a long time to figure it out.

Leren

[denis_berthier]

With variants you have to be careful in applying DP as there could be Possible external restrictions that can invalidate the DP therefore this potential DP has to be free from these possible restrictions in addition to being fully exposed in order to apply uniqueness techniques

But what this means is only that the DP is nor correctly defined. If other conditions are missing, the pattern is not defined.
This reminds me of Exocets. Champagne introduced some incomplete set of conditions that the user was supposed to complete by ad hoc inferences; the J-Exocet was then defined; it requires no additional conditions.
The problem seems to be similar: when one wants to generalise some pattern that works well, it may be very difficult to fully define useful generalisations.

[tarek]

I'm loving this & hopefully will get closer to your understanding.

If the issue is in using the term "multiple solutions" then would the term "non-single solution" suffice as that would cover "Failures, no solution and invalid"

The wording is approximated now to: "In a unique puzzle, in the absence of extra candidates, The fully exposed DP would prevent the single solution to the puzzle"

If the definition of DP now is the Fully Exposed and Free-from-possible-restrictions DP, Then in a unique puzzle the extra candidates must be "true" to avoid contradicting the single solution assertion.

With variants you have to be careful in applying DP as there could be Possible external restrictions that can invalidate the DP therefore this potential DP has to be free from these possible restrictions in addition to being fully exposed in order to apply uniqueness techniques

But what this means is only that the DP is nor correctly defined. If other conditions are missing, the pattern is not defined.
This reminds me of Exocets. Champagne introduced some incomplete set of conditions that the user was supposed to complete by ad hoc inferences; the J-Exocet was then defined; it requires no additional conditions.
The problem seems to be similar: when one wants to generalise some pattern that works well, it may be very difficult to fully define useful generalisations.

I'm hopeful that with a proper & generalised definition to DP that we can address these ambiguities.

tarek

[tarek]

Not wishing to expand the scope of this thread, I just wanted to explain the notion of: Free or unrestricted DP

Observe this Anti-Knight toroidal sudoku Puzzle:

Code: Select all

+-------------+-------------+-------------+
| 3   9   4   | 7   5   8   | 2   1   6   |
| 6   1   2   | 4   9   3   | 8   7   5   |
| 57  7   8   | 2   1   6   | 3   9   4   |
+-------------+-------------+-------------+
| 7   3   56  | 8   2   1   | 56  4   9   |
| 78  4   9   | 6   3   5   | 1   2   7   |
| 1   2   56  | 9   7   4   | 567 3   8   |
+-------------+-------------+-------------+
| 2   6   3   | 5   4   7   | 9   8   1   |
| 4   8   1   | 3   6   9   | 57  5   2   |
| 9   5   7   | 1   8   2   | 4   6   3   |
+-------------+-------------+-------------+

The potential 56 DP pattern in r46c37 is actually not a DP at all because of the anti-Knight restriction which is evident from the solution

Code: Select all

394758216
612493875
578216394
736821549
849635127
125974638
263547981
481369752
957182463


The 5 in r3c1 would prevent placement of 5 in r4c3 therefore the 56 pattern can't be true & can't be used in uniqueness techniques
I also presented the puzzle in this state to show that r6c7 can't be 7.
The Electronic solver has to know if this is an unrestricted DP or not

[eleven]

Hi Denis,

yes, of course you don't need UR1.1 to eliminate a certain candidate, because each false candidate would lead to a classical contradiction, which can be proved with a chain, net, braid, backtracking or whatever. It just would be more elegant to use the UR1.1.

With 3 givens for me this not a a UR1.1, but a reverse BUG pattern, a uniqueness pattern. You can eliminate the 3, if there are no more givens in the 2 rows or the 2 columns.

The main reason, that you hardly will find UR1.1 solutions posted, is that the big majority of solvers does use uniqueness techniques. Before they arrive at a UR1.1 pattern, they would have eliminated the candidate with a UR.

For those, who do not want to use uniqueness methods, it should be a nice thing, because it is such a simple (though very rare) pattern.

The nicest thing for me is the proof. Most non-uniqueness technique are proved by "can't go there, because it is occupied by others" or a contradiction ending with "otherwise a cell would be empty or a digit could not be placed in a house" etc. Here the contradiction is, that on the one hand you already eliminated a candidate in one of the three 2-digit cells (proved it wrong), but on the other hand it would be part of a solution, if a solution would be possible with the remaining UR1.1 candidate in the 4th cell with extra candidate(s).

Example
Suppose you have a UR type 1 in your candidates grid.

Code: Select all

 12 . . | 12  . .
 12 . . | 123 . .

And you can eliminate 1r1c1 with a kite (no 1 in the * cells)

Code: Select all

 12 . . | 12  . . | * * 1
 12 . . | 123 . . | * * *
 .  . . | .   . . | 1 * *
 --------------------------
 1  * * | *   * * | 1 * *

Then you get a UR1.1

Code: Select all

 2 . . | 1  . .
 1 . . | 23 . .

If 2r2c4 would be part of a solution,

Code: Select all

 2 x x | 1  x x
 1 x x | 2  x x

then also

Code: Select all

 1 x x | 2  x x
 2 x x | 1  x x

would be a solution (you still would have all 9 digits in all houses and all givens in the grid). But this is not possible, because the kite eliminated 1r1c1 - contradiction.
Note that if one of the digits was a given, you could not flip it in the soulution. But the proof is definitely valid, if none was a given. I really don't mind, if Denis accepts that, but he is free to use it

So if someone wants to generate good examples, it could be done e.g. this way. Look for puzzles, which can be solved with a UR type 1, but are very hard without it. Under those, look if one of the UR candidates can be eliminated in a simple way in one of the 3 cells without extra candidates, say with a kite. Then this kite and the UR1.1 would crack a very hard puzzle without using the assumption, that the puzzle has only one solution.

[Leren]

I think I've gone about as far as I can go on this topic, but let me sign off with a bit of fun. I'm going to test the (not universally acknowledged) suggestion, that a fully exposed UR pattern will lead to a zero solution state.

No waffle here, Just a concrete example. So lets take the Hodoku example on this topic on UR Type 1's here.

I know it's in the link but I'll just repeat what they say "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."

My underlining, so let's take their first puzzle as an example. Here it is .....896.1..7......675..3..21...78....489...37....4..5.219....4................26

Here is the correctly played UR move:

Code: Select all

*---------------------------------------*
| 5   34    2  | 134  134  8  | 9   6 7 |
| 1  *3-89 *89 | 37   367  69 | 4   5 2 |
| 49  6     7  | 5    24   29 | 3   8 1 |
|--------------+--------------+---------|
| 2   1     3  | 6    5    7  | 8   4 9 |
| 6   5     4  | 8    9    1  | 2   7 3 |
| 7  *89   *89 | 23   23   4  | 6   1 5 |
|--------------+--------------+---------|
| 8   2     1  | 9    67   56 | 57  3 4 |
| 3   47    6  | 1247 1247 25 | 157 9 8 |
| 49  479   5  | 147  8    3  | 17  2 6 |
*---------------------------------------*

and here is the solution:

Code: Select all

*-----------------------*
| 5 4 2 | 3 1 8 | 9 6 7 |
| 1 3 8 | 7 6 9 | 4 5 2 |
| 9 6 7 | 5 4 2 | 3 8 1 |
|-------+-------+-------|
| 2 1 3 | 6 5 7 | 8 4 9 |
| 6 5 4 | 8 9 1 | 2 7 3 |
| 7 8 9 | 2 3 4 | 6 1 5 |
|-------+-------+-------|
| 8 2 1 | 9 7 6 | 5 3 4 |
| 3 7 6 | 4 2 5 | 1 9 8 |
| 4 9 5 | 1 8 3 | 7 2 6 |
*-----------------------*

All very nice. Now let's fully expose the 89 UR pattern in r23c26 and see if we can find those two other solutions in this .. er .. unique solution puzzle

Well, luckily for me I can trick this up in my own solver, by manually removing the 3 from r2c2 and then just let it rip. This is what I get.

Code: Select all

*-------------------------*
| 5 3  2  | 4 1 8 | 9 6 7 |
| 1 89 89 | 7 3 6 | 4 5 2 |
| 4 6  7  | 5 x 2 | 3 8 1 |
|---------+-------+-------|
| 2 1  3  | 6 5 7 | 8 4 9 |
| 6 5  4  | 8 9 1 | 2 7 3 |
| 7 89 89 | 2 3 4 | 6 1 5 |
|---------+-------+-------|
| 8 2  1  | 9 6 5 | 7 3 4 |
| 3 4  6  | 2 1 x | 5 9 8 |
| 9 7  5  | 4 8 3 | 1 2 6 |
*-------------------------*

OMG, what have we got here ? The 89 UR is fully exposed and can be swapped either way, and the rest of the puzzle solves easily in singles, but r3c5 and r8c6 (which I've put an x in) have no candidates

Apparently my solver returns a failure to solve. What's worse, the solution counter function warns me that the puzzle has 0 solutions !

What's going on here ? Is there a bug in my solver ? Hodoku assured me that I would be able to find two solutions but I can't find them. Could it be that Hodoku is telling porkies (just re-read that underlined section) ?

I'll let you be the judge. Well, that was just a bit of fun but there really is a serious message in there.

Leren

[denis_berthier]

Hi Leren,
A normal resolution rule cannot suppose there is a solution (there is no means to express this); It says:
- either: if X is a candidate, then X must be in any solution
- or: if X is a candidate, then X cannot be in any solution

The UR rule, based on the assumption of uniqueness, is different. It doesn't conclude on your red-coloured sentence. It says instead: If those candidates were eliminated, then any solution would allow to build a second solution. It doesn't have to suppose there is a solution.

[denis_berthier]

Not wishing to expand the scope of this thread, I just wanted to explain the notion of: Free or unrestricted DP

I understand it as: a DP for Sudoku is not necessarily a DP for another game based on the same grid. In another game, it may have to satisfy extra-conditions defined by the game (not by the current resolution state). Is that what you mean?

[denis_berthier]

Hi eleven

yes, of course you don't need UR1.1 to eliminate a certain candidate, because each false candidate would lead to a classical contradiction, which can be proved with a chain, net, braid, backtracking or whatever. It just would be more elegant to use the UR1.1.

But in practice, we don't have to use non-pattern-based methods to replace the UR1.1; very simple rules are generally enough.

The nicest thing for me is the proof. [...] Here the contradiction is, that on the one hand you already eliminated a candidate in one of the three 2-digit cells (proved it wrong), but on the other hand it would be part of a solution, if a solution would be possible with the remaining UR1.1 candidate in the 4th cell with extra candidate(s).

To sum it up: you have proven that a candidate is impossible under the given conditions (it has been eliminated by normal logic), but it would be true under other conditions.

Example
Suppose you have a UR type 1 in your candidates grid.

Code: Select all

 12 . . | 12  . .
 12 . . | 123 . .

And you can eliminate 1r1c1 with a kite (no 1 in the * cells)

Code: Select all

 12 . . | 12  . . | * * 1
 12 . . | 123 . . | * * *
 .  . . | .   . . | 1 * *
 --------------------------
 1  * * | *   * * | 1 * *

Then you get a UR1.1

Code: Select all

 2 . . | 1  . .
 1 . . | 23 . .

If 2r2c4 would be part of a solution,

Code: Select all

 2 x x | 1  x x
 1 x x | 2  x x

then also

Code: Select all

 1 x x | 2  x x
 2 x x | 1  x x

would be a solution (you still would have all 9 digits in all houses and all givens in the grid). But this is not possible, because the kite eliminated 1r1c1 - contradiction.
Note that if one of the digits was a given, you could not flip it in the soulution. But the proof is definitely valid, if none was a given. I really don't mind, if Denis accepts that, but he is free to use it

But this "proof" is exactly what I showed doesn't work in my first post. You should read it without prejudices. As soon as you introduce some condition as "if none was a given", you are making some extra-logical assumption. It's not a matter of whether I accept it or not (note that the only thing I don't accept is that UR1.1 doesn't depend on uniqueness), it's a matter of how First Order Logic works. Trying to make it personal will not change it.
Another way to see the flaw in your reasoning is, you consider UR1.1 as a special case of UR1; it is not.

[Leren]

denis_berthier wrote : ... The UR rule, based on the assumption of uniqueness, is different. It doesn't conclude on your red-coloured sentence. ...

I think I'm agreeing with you here, the red sentence, which was Hodoku's, not mine, Is clearly absurd (it's an oxymoron), hence the humorous tone in my post.

The more serious note is that these types of "explanations" on teaching sites have influenced the language, and possibly the thinking, of many solvers, some of them very talented and experienced.

Leren

[denis_berthier]

denis_berthier wrote : ... The UR rule, based on the assumption of uniqueness, is different. It doesn't conclude on your red-coloured sentence. ...

I think I'm agreeing with you here, the red sentence, which was Hodoku's, not mine, Is clearly absurd (it's an oxymoron), hence the humorous tone in my post.
The more serious note is that these types of "explanations" on teaching sites have influenced the language, and possibly the thinking, of many solvers, some of them very talented and experienced.

Yes, it's sad to see the same errors repeated ad nauseam.