The New Sudoku Players' Forum

[Allan Barker]

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.

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.
.

[Allan Barker]

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.

.

[denis_berthier]

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...".

[Red Ed]

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.

[David P Bird]

Deleted

[ronk]

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

[Allan Barker]

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.

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.

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.
.

[Myth Jellies]

Without question IMO, to every possible uniqueness pattern

Well every possible 2-solution uniqueness pattern. MUGs and extended uniqueness would probably be excepted.

[StrmCkr]

removed

[Myth Jellies]

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.

[Allan Barker]

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.
.

[Red Ed]

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?

[Red Ed]

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.

[Allan Barker]

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?

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]

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.

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.