Isolated Subpuzzles and Local Uniqueness

Advanced methods and approaches for solving Sudoku puzzles

Postby denis_berthier » Mon Nov 10, 2008 3:32 am


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?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby Glyn » Mon Nov 10, 2008 5:42 am

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.
Glyn
 
Posts: 357
Joined: 26 April 2007

Postby Allan Barker » Mon Nov 10, 2008 8:10 am

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
 
Posts: 266
Joined: 20 February 2008

Postby Allan Barker » Mon Nov 10, 2008 8:23 am

Glyn wrote: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)
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby denis_berthier » Mon Nov 10, 2008 8:36 am

Allan Barker wrote: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?

Allan Barker wrote: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?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby Red Ed » Mon Nov 10, 2008 10:55 am

denis_berthier wrote:- 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.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby JPF » Mon Nov 10, 2008 11:41 am

Red Ed wrote: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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby Red Ed » Mon Nov 10, 2008 12:33 pm

Wow, yes! I don't know how I missed that. Belated congratulations!:)
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Isolated Subpuzzles

Postby RW » Mon Nov 10, 2008 1:03 pm

Allan Barker wrote: 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.

denis_berthier wrote: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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby David P Bird » Mon Nov 10, 2008 1:51 pm

Deleted
Last edited by David P Bird on Wed Nov 12, 2008 9:08 am, edited 2 times in total.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Postby coloin » Mon Nov 10, 2008 5:17 pm

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   |
+-------------+-------------+-------------+
coloin
 
Posts: 1637
Joined: 05 May 2005

Re: Isolated Subpuzzles

Postby Allan Barker » Mon Nov 10, 2008 5:37 pm

RW wrote:
Allan Barker wrote: 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.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby RW » Mon Nov 10, 2008 7:59 pm

David P Bird wrote: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:
A long time ago I wrote: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.

David P Bird wrote: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

Allan Barker wrote: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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby denis_berthier » Mon Nov 10, 2008 9:15 pm

Part of a post from the other thread:

Allan Barker wrote: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".
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby Allan Barker » Mon Nov 10, 2008 9:30 pm

RW wrote: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.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

PreviousNext

Return to Advanced solving techniques