The New Sudoku Players' Forum

[denis_berthier]

Uniqueness versus name-fixing

I've never had much interest in uniqueness and I probably ignore some rules that have been defined for dealing with it.
All the rules I know (various UR and BUG) deal with a very special kind of uniqueness, that I'd rather call name-fixing: the alternative solutions are obtained by a permutation of the digits (which amounts to a mere renaming).
Indeed, the rules I know are still more limited than this: they bear on only 2 digits.
Such rules, I'd rather call them name-fixing rules than uniqueness rules, because all the alternative solutions have the same structure.

So, I'm wondering:
- are there rules similar to UR or BUG but in relation to more digits?
- Allan, is this in any way related to your notion of an isolated sub-puzzle?


I'm wondering again: are there rules for more complex types of uniqueness, which don't correspond to mere renaming?

[Glyn]

I'm probably out of my depth here but here's my thoughts.

If a complete pattern can be extracted from the unsolved PencilMarks (at any stage) which can be transposed in a number of ways M without disturbing the remainder of the grid then such a pattern can only appear in some multiple of M solutions.

If such a pattern could theoretically have been isolated in the original unsolved cells then its partial destruction during the solving process suggests to me that its transposed sets must also be killed. They exist together or not at all.

A necessary requirement for a solution to be a unique solution is that there is no set of patterns for which M>1.

Over to the experts.

[Allan Barker]

Denis,

I have only a basic understanding of most uniqueness type techniques, only enough to know they are not the same. What I have looked at are URs and more complex UR like logic in true multiple solution puzzles. They all have the property that they become logically isolated from the rest of the puzzle, like a single. But they do get complex so I guess there could be lots more techniques developed in the realm of unique puzzles.

What would a non-renaming multiple solution look like?
.

[Allan Barker]

If such a pattern could theoretically have been isolated in the original unsolved cells then its partial destruction during the solving process suggests to me that its transposed sets must also be killed. They exist together or not at all.

This is somehow related to what I'm trying to see or find in these multiple solutions grids, but it's all not clear to me. For sure, they have the all or none property, if you eliminate any one candidate in the group of solutions, they all go, except for one (which remains as the chosen solution)

[denis_berthier]

I have only a basic understanding of most uniqueness type techniques, only enough to know they are not the same. What I have looked at are URs and more complex UR like logic in true multiple solution puzzles. They all have the property that they become logically isolated from the rest of the puzzle, like a single. But they do get complex so I guess there could be lots more techniques developed in the realm of unique puzzles.

As they are isolated from the rest of the puzzle, I guess all their solutions are obtained by mere renaming.
Did all those you met rely on only 2 digits?

What would a non-renaming multiple solution look like?

Solutions wouldn't be isomorphic through renaming. But if we don't put additional conditions, they could be almost anything. E.g., if the entries are empty: all the completed puzzles.
Obvious cases should be discarded: 2 blank rows (columns) in the same floor (tower).

My initial question was simpler: do we already have any rules for such non-uniqueness? But, perhaps, the good question should be: what other cases of non-uniqueness may lead to interesting uniqueness rules?

[Red Ed]

- are there rules similar to UR or BUG but in relation to more digits?

Not a rule, per se, as you'd never make use of it; but I've seen at least one example of a minimal unavoidable set (and therefore "deadly pattern") that has all nine digits in it! It covered 55 cells.

[JPF]

but I've seen at least one example of a minimal unavoidable set (and therefore "deadly pattern") that has all nine digits in it! It covered 55 cells.

even 60 cells here...

JPF

[Red Ed]

Wow, yes! I don't know how I missed that. Belated congratulations!

[RW]

The Missing Oracle Conjecture Here's what I think everyone is getting at.

Given a puzzle with two solutions and a UR where no candidates have yet been removed, no combination of Sudoku logic can eliminate any candidate in the UR and thus force one of the two solutions.

This is easy to prove. Whenever you eliminate a candidate based on any logical technique, rule, combination of logic, or whatever you wish to call it, you do so because if this candidate was true, the remaining puzzle would not be solvable. You make the elimination because you can logically prove a contradiction caused by the eliminated candidate. In a multisolution puzzle, the deadly candidates in the deadly pattern do all lead to a solution, none of them leads to a contradiction, therefore none of them may be eliminated using logic.

All the rules I know (various UR and BUG) deal with a very special kind of uniqueness, that I'd rather call name-fixing: the alternative solutions are obtained by a permutation of the digits (which amounts to a mere renaming).

This is true for all 2-digit unavoidable sets but not for minimal unavoidable sets using more than 2 digits (lots of techniques using such sets have been defined). It shouldn't be true for BUGs either. Could you show me a BUG where you have found this property?

RW

[David P Bird]

Deleted

[coloin]

There are very many unavoidable sets in every solution grid.

Even with 2-digits there are either 1,2,3 or 4 sets for every pair of 2 clues in every solution grid.

The 36 pairs [8+7+6+5+4+3+2+1] of 2-digit combinations defines every essentially different solution grid.

However......

Try solving this puzzle/subpuzzle !!

Code: Select all

+---+---+---+
|...|..3|...|
|46.|1..|...|
|589|2.7|1..|
+---+---+---+
|..4|6.8|597|
|.56|...|.3.|
|.98|...|..4|
+---+---+---+
|841|...|.52|
|632|..1|...|
|9.5|3..|...|
+---+---+---+

solved simply [includes "virtual" pencil marks which are invalid]

Code: Select all

+-------------------+-------------------+-------------------+
| 12    12    7     | 4589  45689 3     | 4689  468   5689  |
| 4     6     3     | 1     589   59    | 27    27    589   |
| 5     8     9     | 2     46    7     | 1     46    3     |
+-------------------+-------------------+-------------------+
| 123   12    4     | 6     123   8     | 5     9     7     |
| 127   5     6     | 479   12479 249   | 28    3     18    |
| 1237  9     8     | 57    12357 25    | 26    126   4     |
+-------------------+-------------------+-------------------+
| 8     4     1     | 79    79    6     | 3     5     2     |
| 6     3     2     | 458   458   1     | 4789  478   89    |
| 9     7     5     | 3     248   24    | 468   1468  168   |
+-------------------+-------------------+-------------------+

"real" pm grid

Code: Select all

+-------------+-------------+-------------+
| 12  12  7   | 5   4   3   | 9   8   6   |
| 4   6   3   | 1   8   9   | 7   2   5   |
| 5   8   9   | 2   6   7   | 1   4   3   |
+-------------+-------------+-------------+
| 123 12  4   | 6   13  8   | 5   9   7   |
| 7   5   6   | 4   9   2   | 8   3   1   |
| 13  9   8   | 7   13  5   | 2   6   4   |
+-------------+-------------+-------------+
| 8   4   1   | 9   7   6   | 3   5   2   |
| 6   3   2   | 8   5   1   | 4   7   9   |
| 9   7   5   | 3   2   4   | 6   1   8   |
+-------------+-------------+-------------+

[Allan Barker]

The Missing Oracle Conjecture Here's what I think everyone is getting at.

Given a puzzle with two solutions and a UR where no candidates have yet been removed, no combination of Sudoku logic can eliminate any candidate in the UR and thus force one of the two solutions.

This is easy to prove. Whenever you eliminate a candidate based on any logical technique, rule, combination of logic, or whatever you wish to call it, you do so because if this candidate was true, the remaining puzzle would not be solvable. You make the elimination because you can logically prove a contradiction caused by the eliminated candidate. In a multisolution puzzle, the deadly candidates in the deadly pattern do all lead to a solution, none of them leads to a contradiction, therefore none of them may be eliminated using logic.

Thanks, RW, this is exactly the type and kind of logical argument I am looking for, it goes back to the very beginning of why we make eliminations, but there is one remaining problem, at least, that I see.

For any one solution you choose, the UR region is full of possible contradictions. As evidence, if any one candidate is removed from any one multiple solution, the logic in the UR region itself quickly destroys the damaged solutions, sometimes all but one solution. So the contradictions are there, but seem protected as long as each solution is complete and intact.

The problem is interesting, and I am trying to see it in a logical since because that logic might help understand why some puzzles are so difficult.

[RW]

This leaves us with two possible assassin types:
Type1: an (a) candidate external to the Q loop cells - if true one leg of the Q loop from (b) to the victim(a) is supplanted by the leg to the assassin(a) to break the loop. (It makes no difference if assassin is in some unknown position in a containing set or group node.)
Type2 a third candidate (c) in the same cell as victim (a) - if true the Q loop is broken as this will also eliminate (b) from the same cell. (Again it makes no difference if the exact identity of (c) is unknown when it is one of a set.)

Yes, this is true. Here's another take on the same issue:

There is three different ways to interfere with the pattern from the outside:

1. Place an A somewhere else in one of the involved units, has to remove both candidates a in that unit and prevents both of the possible solutions in the deadly pattern.

2. Place an B somewhere else in one of the involved units, has to remove both candidates b in that unit and prevents both of the possible solutions in the deadly pattern.

3. Place a third number C on any of the four corners, removes both candidates a and b in that cell and prevents both of the possible solutions in the deadly pattern.

2. In any fully assigned Sudoku grid we can follow one or more two-digit (a) - (b) loops traversing alternately along rows and columns

I hope you don't miss the interesting technique derived from this observation: http://forum.enjoysudoku.com/viewtopic.php?t=4431

For any one solution you choose, the UR region is full of possible contradictions. As evidence, if any one candidate is removed from any one multiple solution, the logic in the UR region itself quickly destroys the damaged solutions, sometimes all but one solution. So the contradictions are there, but seem protected as long as each solution is complete and intact.

There are no contradictions in a deadly pattern in a multisolution puzzle. If you remove one candidate, you destroy a valid solution. This cannot be done using logic.

The examples you are thinking of, where potential correct solutions have been destroyed, have all been based on false logic. This situation may happen if you use uniqueness technique in a multisolution puzzle. Uniqueness technique is not logical in such a puzzle. The multiple solutions removes the technique's logical foundation and it cannot be considered an option here, when discussing removal of candidates in deadly patterns.

RW

[denis_berthier]

Part of a post from the other thread:

It seems we now arrive at the same point, that which I referred to as the Missing Oracle of Uniqueness. Given a multiple solution puzzle where no candidates have yet been removed from the multiple solutions, no combination of Sudoku logic can eliminate any candidate in the multiple solutions and thus force one of the solutions.

Unless I'm missing your point, it seems obvious to me.
Consider the logical theory ST+P consisting of the Sudoku axioms plus the specific entries of the puzzle. Then, from the completeness and consistency theorems of FOL, being provable from ST+P (I guess this is what you mean by a "combination of Sudoku logic ") and being true in all the models of ST+P, i.e. in all the solutions of P, is equivalent.
If you suppose non uniqueness, as the cells with multiple candidates in the UR will have different values in different models, these values can't be proven from ST+P - which is equivalent to saying the other candidates can't be deleted by any "combination of Sudoku logic".

[Allan Barker]

The examples you are thinking of, where potential correct solutions have been destroyed, have all been based on false logic. This situation may happen if you use uniqueness technique in a multisolution puzzle. Uniqueness technique is not logical in such a puzzle. The multiple solutions removes the technique's logical foundation and it cannot be considered an option here, when discussing removal of candidates in deadly patterns.

Granted and understood. I am looking at real multiple solution puzzles where it's known that, as long as all solutions remain intact, that standard logic cannot remove these candidates, and thus can't resolve the solutions. The candidates and constraints are arranged in some kind of protective arrangement that prevents contradictions. Removal of any single candidate (T&E or mouse click) disturbs this logic producing contradictions that wipe out one or many of the solutions. My aim is understanding the nature this logical structure, probably in terms of sets/linksets/constraints. This is a mental exercise not really related to uniqueness techniques.