Isolated Subpuzzles and Local Uniqueness

Advanced methods and approaches for solving Sudoku puzzles

Isolated Subpuzzles and Local Uniqueness

Postby Allan Barker » Sat Nov 08, 2008 7:59 am

Note added by Glyn The remainder of this post was moved to allow a deeper discussion of the issues to take place without overburdening the posts here
Confluence and rules for uniquenessthat led to it.

denis_berthier wrote:I'm not claiming that some notion of an "isolated sub-puzzle" couldn't be defined. I'm claiming that it has not been.

You are correct, so let me at least define what I mean by decoupled or isolated sub puzzles, ISPs.

Isolated Sub-Puzzles

An isolated sub-puzzle is any group of candidates that clears all other candidates from all sets (row, column, box, and cell) that it occupies. The most common examples are a single and a four-cell UR. After an ISP clears its sets of other candidates, it no longer has any logical connection with the rest of the puzzle. (Here, logic means based on Sudoku's first rule, the original 324 constraints.)

One way to see this is using cover sets. A single is a set with one candidate that can be covered with any of the other 3 sets in which the candidate sits. It therefore clears these other 3 sets. A 4-cell UR forms 4 different continuous nice loops that clear all 16 sets that contain the UR. Note, such patterns are only isolated after they clear their sets.

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.

If the conjecture is true then UR1.1 type logic does not require the oracle of uniqueness rather, the oracle's absence (the puzzle's uniqueness) is discovered by the logical elimination of one or more of the potential UR's candidates. The conjecture also has implications with respect to trial and error, which can eliminate candidates in a UR and produce individual solutions.

I have always assumed the conjecture to be true and have searched extensively for the elusive contrary example. However, an absolute proof also seems elusive. When a UR is isolated from the rest of the puzzle, the proof is trivial. The problem is proving it for all grids. At least the following should be true.

1. A unique puzzle has no logic that can eliminate a candidate belonging to its solution.

2. This must also apply to the individual solutions of a 2-solution puzzle thus, no logic external to the UR can eliminate any of the 8 potential candidates of a UR. This is because any external logic that can remove a UR candidate would destroy the puzzle if the other solution were manually removed first.

3. The only remaining way to eliminate a UR candidate must then be a combination of external logic with some of the UR's own candidates. This is the hard part to disprove. Perhaps someone knows of a simple way.

Proving the missing oracle principle would be very useful (granted, it is already useful). If correct, it could indicate the presence of unknown or unintended trial and error in a set of rules or a solver, when the rules or solver is able to eliminate candidates from a UR or isolate any of the puzzle's solutions. One observation, my set solver can find all the solutions to multiple solution puzzles but it must find them simultaneously, it can't find them sequentially nor find only some of them.
.
Last edited by Allan Barker on Wed Nov 12, 2008 1:27 pm, edited 1 time in total.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby Allan Barker » Sat Nov 08, 2008 8:06 am

denis berthier wrote:For the "believers" (David's word) of UR1 or UR1.1 independent of some uniqueness assumption, as the arguments remain a matter of faith and not logic, I suggest you discuss this in another thread.


Denis, sorry, its late here and I clicked before seeing your last post. Maybe tomorrow I or someone could start a new thread, then I would move this there.

.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby denis_berthier » Sat Nov 08, 2008 8:38 am

Allan, I appreciate that you make a clear difference between a conjecture and a rule.
The only remaining way to eliminate a UR candidate must then be a combination of external logic with some of the UR's own candidates. This is the hard part to disprove.

I've been saying the same thing in another form: "there are so convoluted chains that can eliminate candidates...".
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby Red Ed » Sat Nov 08, 2008 1:01 pm

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

How can this possibly be only a conjecture?

There are two solutions, so how can "logic" force one of them? Any definition of "logic" that permits such a sin is worthless IMHO.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby David P Bird » Sat Nov 08, 2008 1:45 pm

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

Postby ronk » Sat Nov 08, 2008 2:09 pm

David P Bird wrote:In this pattern I believe we can also be sure that the digits c and d can't both be false using the same reasoning.
Code: Select all
|----------|----------|----------|
|    bc    |       ab |          |
|          |       ab | ab       |
|    ab    |          | ad       |
|----------|----------|----------|
The question is how far can we stretch this piece of elastic?

Without question IMO, to every possible uniqueness pattern:!:
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Allan Barker » Sat Nov 08, 2008 7:05 pm

Fisrt, I am a strong "believer". I have come across this point many times and searched for the exception, using puzzles with up to 6 or more solutions. Zip. My permutation solver should find all possible eliminations of UR candidates but, at least where I searched, there were none. I have come to believe this is a fundamental property.

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

How can this possibly be only a conjecture?

There are two solutions, so how can "logic" force one of them? Any definition of "logic" that permits such a sin is worthless IMHO.

OK, here's what is bothering me, and why. I will talk about a simple 4-cell UR but the discussion is applies to all manner of MS puzzles. I discuss only MS puzzles and the possibility of eliminating at least one candidate from one solution, thus resolving the solutions.

Take a 2 solution puzzle with a UR that has solutions A and B. The puzzle's two solutions are then P + A, and P + B, so P is the "rest of the puzzle". Also consider more complex MS puzzles.

Consider the UR early in the solution path where most or all of the 16 sets occupied by the UR have other candidates, i.e., the UR is not yet separate from the puzzle. There are vast numbers of logic chains, loops, and whatnot that may contain candidates from any combination of P, A, and B.

Both P + A and P + B are valid solutions.

However, solutions A and B are incompatible and coexist only because they are balanced and complete. If any one candidate is removed then one solution removes the other using only logic in A and B. It is a stable contradiction.

As I showed above, it s not possible for logic in P alone to remove candidates in A or B. So the last resort would be a combination of logic in say P + A eliminating a candidate in B.

The reason this is troublesome to me is that B is in contradiction to P + A. Is there some combination of logic in P + A that breaks the deadlock between A and B that allows the elimination of a candidate on B? Is there a way to prove it can't happen?

Adding to the worry, hard puzzles are full of complex logic containing both true and false candidates but the logic cannot resolve to eliminate any of the false candidates, until bang, one more contradiction is applied and at least some wrong candidates are eliminated.

Last, how is it that I can assume that multiple solutions can't ever be resolved? In general, it is not unusual for multiple solution problems to be resolvable. Other processes like backtracking and algorithm X have no problem resolving the individual solutions.

So back to Red Ed's question.

Red Ed wrote:There are two solutions, so how can "logic" force one of them?

Well, I don't think they can but I worry about a the scenario where P + A can combine to eliminate a candidate in B, which contradicts P + A. I guess I am looking to understand which proof rules out this specific scenario and how.
.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby Myth Jellies » Sat Nov 08, 2008 7:09 pm

Without question IMO, to every possible uniqueness pattern

Well every possible 2-solution uniqueness pattern. MUGs and extended uniqueness would probably be excepted.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby StrmCkr » Sat Nov 08, 2008 7:11 pm

removed
Last edited by StrmCkr on Sat Dec 13, 2014 6:23 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 663
Joined: 05 September 2006

Postby Myth Jellies » Sat Nov 08, 2008 7:47 pm

Allan,

If P+A and P+B are complementary uniqueness subsolutions

By definition, you can't determine P+A to the exclusion of P+B unless A contains one of your original givens

We eliminate that case from consideration up front. So your worrisome scenario can never be realized.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Allan Barker » Sat Nov 08, 2008 8:31 pm

Myth Jellies wrote:Allan,

If P+A and P+B are complementary uniqueness subsolutions

By definition, you can't determine P+A to the exclusion of P+B unless A contains one of your original givens

We eliminate that case from consideration up front. So your worrisome scenario can never be realized.


Myth, It's entirely possible I have my head full of complex thinking and I am missing some very simple point. I do it often. But, can you be more specific as how the definition precludes this case or how this case is ruled out up front?

One reason that I want such an iron clad understanding is that proving this can never happen, even for complex cases has some powerful ramifications.

Thanks, it is not my intention to be obstinate, it is by genetic endowment.
.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby Red Ed » Sun Nov 09, 2008 1:38 am

Allan> ... head full of complex thinking ...

I'm no psychologist, but I wonder: do you ever worry, when you have a bivalue cell, that the wrong value will combine in some bad way with the rest of the puzzle to eliminate the right value?:D
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Red Ed » Sun Nov 09, 2008 2:57 am

Allan wrote:An isolated sub-puzzle is any group of candidates that clears all other candidates from all sets (row, column, box, and cell) that it occupies. The most common examples are a single and a four-cell UR. After an ISP clears its sets of other candidates, it no longer has any logical connection with the rest of the puzzle. (Here, logic means based on Sudoku's first rule, the original 324 constraints.)

... Note, such patterns are only isolated after they clear their sets.


I don't think you need that last sentence.

Let D be a "deadly pattern" as defined by sudopedia. When D is positioned over a collection of unclued cells in a puzzle-in-progress, we can define the remainder with respect to D to be the puzzle candidates not in D.

That's probably super-unclear, so let me show an example.
Code: Select all
                   .  .  . | .            .  .  . | .        .  .  . | .
                   1  .  . | 2            12 .  . | 12       x  .  . | x
                   2  .  . | 13           12 .  . | 12       x  .  . | 3
The remainder of  ---------+---  w.r.t.  ---------+---  is  ---------+---
                   .  .  . | .            .  .  . | .        .  .  . | .

('x' means 'no candidates')


Fact: if the puzzle has a unique solution then at least one clue in the remainder w.r.t. a deadly pattern must be true.
(In the example above, 3 must be true.)

I don't think I've said anything new there.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Allan Barker » Sun Nov 09, 2008 3:17 am

Red Ed wrote:Allan> ... head full of complex thinking ...

I'm no psychologist, but I wonder: do you ever worry, when you have a bivalue cell, that the wrong value will combine in some bad way with the rest of the puzzle to eliminate the right value?:D

Hmm, nice point but no, I worry about a bi-value set with two right values either of which can combine with a good puzzle and make the other wrong.:(
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby Allan Barker » Sun Nov 09, 2008 4:11 am

Red Ed wrote:
Allan wrote:An isolated sub-puzzle is any group of candidates that clears all other candidates from all sets (row, column, box, and cell) that it occupies. The most common examples are a single and a four-cell UR. After an ISP clears its sets of other candidates, it no longer has any logical connection with the rest of the puzzle. (Here, logic means based on Sudoku's first rule, the original 324 constraints.)

... Note, such patterns are only isolated after they clear their sets.


I don't think you need that last sentence.

Maybe it's wrong, and that's the answer. I have always considered this isolation to be a special property, so maybe it is isolated from the begining.

Red Ed wrote:Let D be a "deadly pattern" as defined by sudopedia. When D is positioned over a collection of unclued cells in a puzzle-in-progress, we can define the remainder with respect to D to be the puzzle candidates not in D.

Suggestive of the same thing.

I'll still look for the why though.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Next

Return to Advanced solving techniques