The concept of a RESOLUTION RULE and its applications

Advanced methods and approaches for solving Sudoku puzzles

Postby eleven » Fri Nov 07, 2008 3:19 am

denis_berthier wrote:3 cells are already decided. So there's no 1 and 2 to exchange.
Yes, but the decision possibly only was correct under the condition, that also the 3 must (or can) be true.
It keeps being a fact, that in a valid solution to a puzzle, that has such a deadly pattern, by exchanging the 2 numbers in the 4 cells you get a valid solution again, which - if none of the 4 numbers were given - exactly holds all givens of the original sudoku.
eleven
 
Posts: 1535
Joined: 10 February 2008

Postby denis_berthier » Fri Nov 07, 2008 3:27 am

eleven wrote:
denis_berthier wrote:3 cells are already decided. So there's no 1 and 2 to exchange.
Yes, but the decision possibly only was correct under the condition, that also the 3 must (or can) be true.
It keeps being a fact, that in a valid solution to a puzzle, that has such a deadly pattern, by exchanging the 2 numbers in the 4 cells you get a valid solution again, which - if none of the 4 numbers were given - exactly holds all givens of the original sudoku.

I never debated the standard UR, which you are always referring to.

In the case under discussion, UR1.1, 3 cells are decided, the fourth has two values (1 and 3) - which obviously supposes that none of them is yet known to be false (the 3 can be true, as you put it).

In case of UR1.1, there is no deadly pattern, there is nothing to exchange and there is no sensical conclusion.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby David P Bird » Fri Nov 07, 2008 3:28 am

If an orthogonal rectangle of cells contained in two boxes is restricted to two candidates it is isolated (or decoupled according to Allan Barker) from the rest of the puzzle and would need one of the cells to be a given to be resolvable. This is because whatever deductions are made in the rest of the main puzzle, they won't achieve a reduction in either of the two digits in the isolated rectangle.

This therefore requires that (lacking a given) any such rectangle must contain a minimum of three digits to prevent it becoming an isolated two-digit sub-puzzle.

If we are able to eliminate one of a digit pair from any of the four cells we therefore show that they don't make an isolated two-digit sub-puzzle and so must contain a third digit. We can therefore exclude any candidate which would reduce the four cells to being restricted to two digits.

This theorem if you like, states that lacking a given, any orthogonal rectangle of cells contained in two boxes must contain a minimum of three digits to be resolvable. It makes no assumptions about uniqueness for the puzzle as a whole, but merely identifies whether or not any such rectangles would be resolvable or not with respect to any digit pair.

This is a plain English description, which perhaps lacks mathematical rigour, but disbelievers are invited to produce a puzzle with a counter-example.

[Edit] item in bold added
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Postby eleven » Fri Nov 07, 2008 4:04 am

denis_berthier wrote:I never debated the standard UR, which you are always referring to.

In the case under discussion, UR1.1, 3 cells are decided, the fourth has two values (1 and 3) - which obviously supposes that none of them is yet known to be false (the 3 can be true, as you put it).

In case of UR1.1, there is no deadly pattern, there is nothing to exchange and there is no sensical conclusion.
Ok, so you again have answered before reading, what i said. I never spoke here about something other than this UR1.1, didn't you notice that ?
And what i proved and explained above definitely shows, that the 3 must be true, if you are able to see it or not.

Maybe you cant see, how it could be possible to get to such a situation in a solution process, because you dont use uniqueness methods. If you do, it will happen sometimes, that one uniqueness move "decides" a number in another uniqueness constellation.
How this knowledge about this pattern being deadly can be used for solving puzzles in practice, you e.g. can find in the neighbour thread A UR+4 Deduction. You just use the fact, that any assumption, that leads to such a pattern, must be false.
eleven
 
Posts: 1535
Joined: 10 February 2008

Postby denis_berthier » Fri Nov 07, 2008 5:51 am

David P Bird wrote:If an orthogonal rectangle of cells contained in two boxes is restricted to two candidates it is isolated (or decoupled according to Allan Barker) from the rest of the puzzle and would need one of the cells to be a given to be resolvable. This is because whatever deductions are made in the rest of the main puzzle, they won't achieve a reduction in either of the two digits in the isolated rectangle...
This theorem if you like, states that lacking a given, any orthogonal rectangle of cells contained in two boxes must contain a minimum of three digits to be resolvable.

At last, here is something that doesn't reduce straightforwardly to the previous incantations about UR1.1 and that might be really interesting.
But your formulation is very ambiguous.
What exactly did Allan prove? Do you have a reference?
In particular, what does "to be resolvable" mean? From a logical POV, it can mean three very different things:
- has at least one solution (there is a solution consistent with the entries and the sudoku axioms)
- has exactly one solution (there is a solution and it is the unique consequence of the entries plus the sudoku axioms).
- has exactly one solution (there is a solution and it is the unique consequence of the entries plus the sudoku axioms plus the axiom of uniqueness).

If we adopt the first or second interpretation, then standard UR itself doesn't depend on the assumption of uniqueness. Is this what you are claiming?
If we adopt the third interpretation, it anihilates the subsequent claim about independence on the assumption of uniqueness.

I've other questions, but in order to avoid useless hypotheses on my part, I'll first wait for your answer to the above.


This is just a side remark.
David P Bird wrote:disbelievers are invited to produce a puzzle with a counter-example.

Mathematical truth is not a matter of belief but of proof.
The absence of a known counter-example is not a proof of validity.
Supporters of this tentative rule are invited to produce a proof. But, even before a proof, what I'd like is a clear non ambiguous statement.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby eleven » Fri Nov 07, 2008 6:38 am

denis_berthier wrote:... previous incantations about UR1.1 ...

Now you are going to make me angry. You should not use those words, only because you are not willing or able to understand a proof. If something is wrong with it, so say it.

For your help:
Suppose there is a type 1 UR with one extra candidate and you can eliminate 3 candidates without using any uniqueness method to arrive at a UR1.1 (what of course is possible, though very rare). Then still the extra candidate must be true according to my proof above.

You said, since the candidates are already "decided", you cannot exchange them in the solution. But this is irrelevant. What the proof says is:
If you arrive at a solution with the deadly pattern, you could exchange them to get another solution.
Of course you will never arrive at such a "solution", if you dont make a mistake.

Got it now ?
eleven
 
Posts: 1535
Joined: 10 February 2008

Postby Mauricio » Fri Nov 07, 2008 7:29 am

My 2 cents
eleven wrote:Suppose there is a type 1 UR with one extra candidate and you can eliminate 3 candidates without using any uniqueness method to arrive at a UR1.1 (what of course is possible, though very rare).

I think that is impossible.

eleven wrote:What the proof says is:
If you arrive at a solution with the deadly pattern, you could exchange them to get another solution.
Which then proves that your solution path is flawed.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby Allan Barker » Fri Nov 07, 2008 7:49 am

denis_berthier wrote:What exactly did Allan prove? Do you have a reference?

I probably didn't prove, rather I observed that unique rectangles have a unique set/linkset structure that clears candidates from all row, column, box, and cell sets occupied by the solution candidates, for each solution. Kind of like a super nice loop. This makes the UR logically decoupled from the rest of the puzzle, just like a single.

From this, one might infer that such a puzzle has no logic that is capable of removing any of the 1s or 2s in this example. I assume this to be the case but never thought about a proof..

What I wonder about is the following. What if I took a puzzle that I know has 2 solutions, maybe one with this box:

Code: Select all
{1 2} --------- {1 2}
  :               :
{1 2} --------- {1 2 3}


Knowing the puzzle has 2 solutions, I choose one of the solutions, say 12/21, but the phone rings before I finish removing all the removable candidates, leaving just:

Code: Select all
{1} --------- {2}
 :               :
{2} --------- {1 3}


At which time, my wife comes home, finds the puzzle, and asks if this puzzle has a unique solution. I answer yes, knowing I had already forced one of the 2 solutions. She then assigns the 3, and I'm in trouble. Of course, this should not happen through any logical process. The question is, was I wrong to say what I said?
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby denis_berthier » Fri Nov 07, 2008 7:56 am

Sorry eleven, but if you don't change your tone, I'll no longer talk to you. If you think I'm unable to understand a proof, then why are you wasting your time talking to me?
The fact is, I can't see any proof of anything in any of your above posts.
If you want to submit a proof to me for inspection, please write it in detail with no irrelevant remarks and no reference to a supposed previous one, which itself didn't prove anything. And first state clearly what you want to prove.
eleven wrote:Suppose there is a type 1 UR with one extra candidate and you can eliminate 3 candidates without using any uniqueness method to arrive at a UR1.1 (what of course is possible, though very rare)

If such is the case, all the eliminations that you have done are valid with no restriction, the 3 candidates decided in the resulting UR1.1 are valid with no restriction and nothing can be changed to the UR1.1 pattern thus obtained. So there's nothing you could exchange.

eleven wrote:You said, since the candidates are already "decided", you cannot exchange them in the solution. But this is irrelevant.

Unfortunately for you, nothing can be more relevant.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby ronk » Fri Nov 07, 2008 8:00 am

Mauricio wrote:My 2 cents
eleven wrote:Suppose there is a type 1 UR with one extra candidate and you can eliminate 3 candidates without using any uniqueness method to arrive at a UR1.1 (what of course is possible, though very rare).

I think that is impossible.

I misread hobiwan's solution paths here; statement withdrawn.
Last edited by ronk on Fri Nov 07, 2008 4:22 am, edited 2 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby denis_berthier » Fri Nov 07, 2008 8:08 am

Allan Barker wrote:
denis_berthier wrote:What exactly did Allan prove? Do you have a reference?

I probably didn't prove, rather I observed that unique rectangles have a unique set/linkset structure that clears candidates from all row, column, box, and cell sets occupied by the solution candidates, for each solution. Kind of like a super nice loop. This makes the UR logically decoupled from the rest of the puzzle, just like a single.
From this, one might infer that such a puzzle has no logic that is capable of removing any of the 1s or 2s in this example. I assume this to be the case but never thought about a proof..

Hi Allan, thanks for your answer. That makes things clear. There's not yet any proof. I think a proof would be very difficult, because one would have to consider all the possibilities of interactions between this pattern and the rest of the puzzle.


Allan Barker wrote:What I wonder about is the following. What if I took a puzzle that I know has 2 solutions, maybe one with this box:
Code: Select all
{1 2} --------- {1 2}
  :               :
{1 2} --------- {1 2 3}

At this point, why 2 solutions and not the following 4?
Code: Select all
12    21    12    21
21    12    23    13


Allan Barker wrote:Knowing the puzzle has 2 solutions, I choose one of the solutions, say 12/21, but the phone rings before I finish removing all the removable candidates, leaving just:
Code: Select all
{1} --------- {2}
 :               :
{2} --------- {1 3}

At which time, my wife comes home, finds the puzzle, and asks if this puzzle has a unique solution. I answer yes, knowing I had already forced one of the 2 solutions. She then assigns the 3, and I'm in trouble. Of course, this should not happen through any logical process. The question is, was I wrong to say what I said?

I think my previous remark answers this.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby David P Bird » Fri Nov 07, 2008 9:08 am

When I say that a rectangle of four cells is resolvable with respect to a digit pair I mean that it can only be filled in one way just using those two digits.

If a qualifying rectangle reduces to the same pair of digits in each cell then there are clearly two solutions and it is not resolvable.

In such a case, no deduction made in the balance of the puzzle will affect this duality because the rectangle has become an isolated sub-puzzle. (Not being a mathematician I look on this as plain common sense.) It would need one of the cells to be a given to provide a unique solution.

So for any qualifying rectangle, we can see whether it is resolvable for any particular digit pair, and if so we know that one of the four cells in the rectangle must contain a third digit - otherwise the rectangle would have been isolated from the rest of the puzzle, and the elimination that reduced it to a single two-digit solution would not have been possible.

Say we have:
abc ac
abc bc

This rectangle can filled just one way using any selected pair of candidates because external inferences have eliminated a & b from different cells.
From the resolvable rectangle logic, it therefore is not an isolated sub-puzzle and so must contain a minimum of three digits.
Hence if any digit is eliminated from one side, it must be true on the opposite side.

I believe isolated sub-puzzles can exist which are much larger than four cells, I but I leave it to the mathematicians to sort out the qualifying conditions to be met. For a simple rectangle, the cells must be orthogonal and confined to two boxes and not include a given, otherwise box restraints would allow clues to be provided which will produce a single two digit solution for the four cells.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Postby denis_berthier » Fri Nov 07, 2008 9:37 am

David,
What you are defending here is the standard UR - based on the axiom of uniqueness.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby David P Bird » Fri Nov 07, 2008 10:41 am

denis_berthier wrote:David,
What you are defending here is the standard UR - based on the axiom of uniqueness.

No I'm saying it's 1) impossible to eliminate one digit in an un-resolvable rectangle and that 2) its impossible for a two-digit rectangle to be resolvable unless one of the digits is a given.

These are observations based on the relationships between givens and the deductions they provide and have nothing to do with uniqueness of the puzzle being assumed.

We check if a particular two digit solution for a rectangle is only achievable in one way, we don’t assume it. Furthermore we make no assumptions about the uniqueness of the rest of the puzzle.

How do you then make out that this logic (which isn't new) uses the uniqueness axiom?
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Postby denis_berthier » Fri Nov 07, 2008 11:15 am

David P Bird wrote:We check if a particular two digit solution for a rectangle is only achievable in one way, we don’t assume it.

Well, so how do you check this?

The whole problem is: how could any logical or mathematical proof (of the solution) make a difference between an axiom (a given) and a consequence of an axiom?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Advanced solving techniques