The concept of a RESOLUTION RULE and its applications

Advanced methods and approaches for solving Sudoku puzzles

Postby aran » Fri Nov 14, 2008 2:03 am

Denis
As a first approximation, it is not false, But mentally eliminating all the candidates nrc-linked to z may unduly eliminate potential left-linking candidates and you may miss some xyzt-chains.

I don't see that removing z candidates as described could hinder chain progession:?:
Let C be such a cell : it's structure is llc z t.. rlc
For the case you describe, we have llc=z, so the structure is : z t.. rlc
If z is removed under my approach, it is reduced to t.. rlc
which in the chain reduces to rlc=>chain progression.

Before I can answer, I need to know what is reversed.
If it is only a and b, then the resulting sequence of candidates may not even be a chain.
If it is the whole chain then it may not be an xyt-chain. (If it is, it is probably a mere xy-chain.)

The source bivalue is reversed.
There will be situations (not infrequent) where there is a resulting xyt chain.
We know that any right link in either chain is strongly linked to any right link in the other chain.
Therefore when any right link in the one is nrc-linked to any right link in the other, there is elimination potential of two orders:
i) when the respective right-links are on the same digit => potential elim
ii) when any non llr-digit in either cell is also a right-link in the other cell => actual elim.
This is something easily checkable by a program.
What I am saying is that after application of your sudorules to xyt chains examined, if only to be rejected, there is at hand a source of potential eliminations ie the confrontation of the xyt and yxt chains.
The Paradox is that a potential source of elimination at hand via sudorules is ignored under sudorules because it doesn't have a name in sudorules.

Many players use T&E and purists usually look down on them.
My results show that any elimination done by T&E (the very precise form of T&E I've defined) can always be recast (and moreover in a constructive way) as a pattern-based elimination. The practical consequence is that using such form of T&E, you can't go beyond what the logic of resolution rules allows.


Given your definition of T&E
Definition: Given a resolution theory T (i.e. a set of resolution rules) and a candidate z, T&E(T, z) is the following resolution technique:
- start an auxiliary grid by copying the current PM; in this auxiliary grid, delete z as a candidate and add it as a decided value; apply to this auxiliary PM all the rules in T until quiescence;
- if a contradiction is thus obtained in this auxiliary PM, then eliminate z from the original one; if no contradiction is obtained, then merely go back to the original PM.


I read that to mean : apply sudorules in any order to z, and if there is a resulting contradiction such that <z>, then this can be represented by a braid such that <z>.
But the braid incorporates all sudorules being the highest form of sudorules, so necessarily this will apply.
I don't see that you are saying anything more than A=>A.
aran
 
Posts: 334
Joined: 02 March 2007

Postby denis_berthier » Fri Nov 14, 2008 2:31 am

aran wrote:Denis
As a first approximation, it is not false, But mentally eliminating all the candidates nrc-linked to z may unduly eliminate potential left-linking candidates and you may miss some xyzt-chains.

I don't see that removing z candidates as described could hinder chain progession:?:
Let C be such a cell : it's structure is llc z t.. rlc
For the case you describe, we have llc=z, so the structure is : z t.. rlc
If z is removed under my approach, it is reduced to t.. rlc
which in the chain reduces to rlc=>chain progression.

You are confusing nrc-linked with =

aran wrote:
denis wrote:Before I can answer, I need to know what is reversed.
If it is only a and b, then the resulting sequence of candidates may not even be a chain.
If it is the whole chain then it may not be an xyt-chain. (If it is, it is probably a mere xy-chain.)

The source bivalue is reversed.
There will be situations (not infrequent) where there is a resulting xyt chain.

If the chain was {1 2} - {2 3 ###} ....
reversing 1 and 2 (your a and b) produces:
{2 1} - {2 3 ###} ....
which is not even a chain

aran wrote:I read that to mean : apply sudorules in any order to z, and if there is a resulting contradiction such that <z>, then this can be represented by a braid such that <z>.
But the braid incorporates all sudorules being the highest form of sudorules, so necessarily this will apply.
I don't see that you are saying anything more than A=>A.

Read what I write, not your erroneous transpositions.
T&E is not implemented in SudoRules
denis_berthier
2010 Supporter
 
Posts: 4234
Joined: 19 June 2007
Location: Paris

Postby aran » Fri Nov 14, 2008 3:51 am

Denis
aran wrote:
Denis
Quote:
As a first approximation, it is not false, But mentally eliminating all the candidates nrc-linked to z may unduly eliminate potential left-linking candidates and you may miss some xyzt-chains.

I don't see that removing z candidates as described could hinder chain progession Question
Let C be such a cell : it's structure is llc z t.. rlc
For the case you describe, we have llc=z, so the structure is : z t.. rlc
If z is removed under my approach, it is reduced to t.. rlc
which in the chain reduces to rlc=>chain progression.

You are confusing nrc-linked with =

I think you may be misunderstanding me. It would help if you could you write down some imagined xyzt whip to illustrate your point.

aran wrote:
denis wrote:
Before I can answer, I need to know what is reversed.
If it is only a and b, then the resulting sequence of candidates may not even be a chain.
If it is the whole chain then it may not be an xyt-chain. (If it is, it is probably a mere xy-chain.)

The source bivalue is reversed.
There will be situations (not infrequent) where there is a resulting xyt chain.

If the chain was {1 2} - {2 3 ###} ....
reversing 1 and 2 (your a and b) produces:
{2 1} - {2 3 ###} ....
which is not even a chain

Read what I write...
The second chain doesn't seek to retrace the first.
It is a an xyt independent of the first with the same source cell with llc rlc reversed.

Read what I write, not your erroneous transpositions.
T&E is not implemented in SudoRules

This statement of yours
T&E theorem: ANY ELIMINATION DONE BY T&E CAN BE DONE BY AN NRCZT-BRAID
misled me.
I see that T&E is
T&E(T, z)

The point remains.
THEOREM: ANY ELIMINATION THAT CAN BE DONE BY AN NRCZT-BRAID WITH TARGET Z CAN BE DONE BY T&E(ECP+NS+HS, z)
COROLLARY: ANY PUZZLE THAT CAN BE SOLVED WITH ONLY NRCZT-BRAIDS (+ of course ECP, NS and HS) CAN BE SOLVED BY T&E(ECP+NS+HS).

Proof: obvious.
What is interesting is that the converse is true:

THEOREM: ANY ELIMINATION THAT CAN BE DONE BY T&E(ECP+NS+HS, z) CAN BE DONE BY AN NRCZT-BRAID WITH TARGET z.


The converse looks just as obvious as the original.
Which is why I say
a) are you really saying anything other than A=>A ?
b) so what ?
aran
 
Posts: 334
Joined: 02 March 2007

Postby denis_berthier » Fri Nov 14, 2008 4:50 am

aran wrote:It would help if you could you write down some imagined xyzt whip to illustrate your point.

I have no point and no point to illustrate.
manu examples of nrczt-whips have already been provided.


aran wrote:
T&E theorem: ANY ELIMINATION DONE BY T&E CAN BE DONE BY AN NRCZT-BRAID
misled me.
I see that T&E is
T&E(T, z)

The point remains.
THEOREM: ANY ELIMINATION THAT CAN BE DONE BY AN NRCZT-BRAID WITH TARGET Z CAN BE DONE BY T&E(ECP+NS+HS, z)
COROLLARY: ANY PUZZLE THAT CAN BE SOLVED WITH ONLY NRCZT-BRAIDS (+ of course ECP, NS and HS) CAN BE SOLVED BY T&E(ECP+NS+HS).
Proof: obvious.
What is interesting is that the converse is true:
THEOREM: ANY ELIMINATION THAT CAN BE DONE BY T&E(ECP+NS+HS, z) CAN BE DONE BY AN NRCZT-BRAID WITH TARGET z.

The converse looks just as obvious as the original.
Which is why I say
a) are you really saying anything other than A=>A ?
b) so what ?

We had this discussion in the T&E thread. Read the definitions, read my answer there.
This is valid for all the rest. If you want to discuss something, try first to understand it.
What I'm stating is of the form A <=> B. If you don't know the difference with A <=> A, it's hopeless.
denis_berthier
2010 Supporter
 
Posts: 4234
Joined: 19 June 2007
Location: Paris

Postby aran » Fri Nov 14, 2008 4:56 am

Denis
I have never called you arrogant and never would.
I think you may be wrong on my first point
I know you are wrong on the second.
As to the third : good heavens this side of the coin is the opposite of the other, and wow, it works the other way round as well.
aran
 
Posts: 334
Joined: 02 March 2007

Postby denis_berthier » Fri Nov 14, 2008 6:10 am

aran wrote:I know you are wrong on the second.

If your second point is that there are resolution rules that are not programmed in SudoRules, such as using combinations of 2 different nrct-chains with the same target (which is the most favourable interpretation I can make of your "paradox") , you're right. I've tried this for short chains. It was very greedy for time and memory and it didn't lead to many productive results.
I know no solver that has all the known rules in it.
denis_berthier
2010 Supporter
 
Posts: 4234
Joined: 19 June 2007
Location: Paris

Postby aran » Fri Nov 14, 2008 9:30 am

Denis
If your second point is that there are resolution rules that are not programmed in SudoRules, such as using combinations of 2 different nrct-chains with the same target (which is the most favourable interpretation I can make of your "paradox") , you're right. I've tried this for short chains. It was very greedy for time and memory and it didn't lead to many productive results.
I know no solver that has all the known rules in it.


It is not that.
Let (a,b) be an ordered cell source cell for xyt chain A.
Then (b,a) is an ordered cell from which there may be an xyt chain B different from A.
Whatever the length of A, and whatever the length of B, each and every right hand link of A is strongly linked to each and every right hand link of B. So if A and B are of length 6 (including source) then there are 5*5=25 de facto strong links.

All I am saying is that since your programme must look at these chains, either to "reject" them or retain them in case of an elimination, then for very little extra work there is an opportunity to look for other eliminations, in the manner previously described.

Example :
Suppose that P and Q are nrc-linked cells in the respective chains.
Say the ordered cells are P (257) and Q (1345) (ie t candidates 5 and 34)
=>7P 5Q strongly linked
=>given the nrc-link : P <5>.
Thus whether or not there was a z elimination, there is a t elimination in this example.
aran
 
Posts: 334
Joined: 02 March 2007

Postby denis_berthier » Fri Nov 14, 2008 10:41 am

aran wrote:Let (a,b) be an ordered cell source cell for xyt chain A.
Then (b,a) is an ordered cell from which there may be an xyt chain B different from A.
Whatever the length of A, and whatever the length of B, each and every right hand link of A is strongly linked to each and every right hand link of B.

Completely absurd.
denis_berthier
2010 Supporter
 
Posts: 4234
Joined: 19 June 2007
Location: Paris

Postby re'born » Fri Nov 14, 2008 6:35 pm

denis_berthier wrote:
aran wrote:Let (a,b) be an ordered cell source cell for xyt chain A.
Then (b,a) is an ordered cell from which there may be an xyt chain B different from A.
Whatever the length of A, and whatever the length of B, each and every right hand link of A is strongly linked to each and every right hand link of B.

Completely absurd.

Would you elaborate, Denis?

If you have an xyt-chain (a b) - ... - (w x) (where (w x) might be modulo some t-candidates)
and if you have another xyt-chain (b a) - ... - (y z) (where, again, (y z) might be modulo some t-candidates),
then we can read the first chain as saying if a is not true, then x is true and the second as saying if b is not true then z is true. Since a or b is true, we conclude x or z is true, i.e., x is strongly linked to z.

Aran, is this what you are saying?
Denis, am I missing something?
re'born
 
Posts: 551
Joined: 31 May 2007

Postby denis_berthier » Fri Nov 14, 2008 7:30 pm

re'born wrote:Would you elaborate, Denis?
If you have an xyt-chain (a b) - ... - (w x) (where (w x) might be modulo some t-candidates)
and if you have another xyt-chain (b a) - ... - (y z) (where, again, (y z) might be modulo some t-candidates),
then we can read the first chain as saying if a is not true, then x is true and the second as saying if b is not true then z is true. Since a or b is true, we conclude x or z is true, i.e., x is strongly linked to z.
Aran, is this what you are saying?
Denis, am I missing something?

It's hard to know what Aran means. Does he know himself, when he confuses nrc-linked with =, links with candidates ("right links" instead of "right-linking candidates").

OK, you conclude "x is strongly linked to z". So what? Where's the paradox? How does it allow you to eliminate t-candidates?
denis_berthier
2010 Supporter
 
Posts: 4234
Joined: 19 June 2007
Location: Paris

Postby re'born » Fri Nov 14, 2008 8:41 pm

denis_berthier wrote:OK, you conclude "x is strongly linked to z". So what? Where's the paradox? How does it allow you to eliminate t-candidates?

Denis, do you talk to your colleague's like this?:(
I didn't mention anything about paradoxes or t-candidates. I was only pointing out that aran's argument, which you called "completely absurd" seemed reasonable to me and, apparently, you now agree that it is a reasonable argument.

As far as I can tell, aran was pointing out that you can use two xyt-chains with the same initial candidates, but swapped, to produce strong links that could lead to eliminations. His contention is that your rules do not find these eliminations and he is calling that a paradox. Of course, this is not a paradox (even if true) given the standard meaning of the word. But, who cares? Is aran correct? Will
aran wrote:your rules generates opportunities for eliminations which you cannot accept because they are not "formulated" within the rules.


As for t-eliminations, I don't understand what aran means, but I can't see how any of the above could eliminate any of the actual t-candidates except by coincidence.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby denis_berthier » Fri Nov 14, 2008 9:26 pm

re'born wrote:I didn't mention anything about paradoxes or t-candidates.

Aran did
re'born wrote:I was only pointing out that aran's argument, which you called "completely absurd" seemed reasonable to me and, apparently, you now agree that it is a reasonable argument.

Aran's "argument" was a full page that I didn't cite entirely.

The point is, and you agree with it, there's no paradox and there's no elimination.

re'born wrote:As far as I can tell, aran was pointing out that you can use two xyt-chains with the same initial candidates, but swapped, to produce strong links that could lead to eliminations. His contention is that your rules do not find these eliminations

These so-called "strong links" lead to no elimination and are therefore useless.

Resolution rules focus the search on useful patterns.
Looking for the millions of such potential indirect "strong links" (a concept absent from my framework because totally useless and misleading) can only be a waste of time. But if you want to do it, it's OK.
denis_berthier
2010 Supporter
 
Posts: 4234
Joined: 19 June 2007
Location: Paris

Postby re'born » Fri Nov 14, 2008 10:08 pm

denis_berthier wrote:
re'born wrote:I didn't mention anything about paradoxes or t-candidates.

Aran did

Yes, but you were addressing me, not him. This is not you against the world.
Denis wrote:
re'born wrote:I was only pointing out that aran's argument, which you called "completely absurd" seemed reasonable to me and, apparently, you now agree that it is a reasonable argument.

Aran's "argument" was a full page that I didn't cite entirely.

The point is, and you agree with it, there's no paradox and there's no elimination.

I agreed about there being no paradox, not about there being no eliminations.

Denis wrote:These so-called "strong links" lead to no elimination and are therefore useless.

Why can they not lead to an elimination? For instance, take the two xyt-chains in my post. If z = x (and here I really mean equals), then any other x seeing both of these candidates can be eliminated. It seems, a priori, that these strong inferences have as good a chance of producing an elimination as any xyt-chain. What am I missing?
re'born
 
Posts: 551
Joined: 31 May 2007

Postby denis_berthier » Fri Nov 14, 2008 11:03 pm

re'born wrote:
denis_berthier wrote:
re'born wrote:I didn't mention anything about paradoxes or t-candidates.
Aran did
Yes, but you were addressing me, not him. This is not you against the world.

Yes, but you were addressing me in the context of a conversation with Aran and in support of him.
This is a thread, this is not you with no context, especially if your post refers to another one.

re'born wrote:
Denis wrote:The point is, and you agree with it, there's no paradox and there's no elimination.
I agreed about there being no paradox, not about there being no eliminations.

I said no t-candidate is eliminated, contrary to what Aran claimed.

re'born wrote:
Denis wrote:These so-called "strong links" lead to no elimination and are therefore useless.
Why can they not lead to an elimination? For instance, take the two xyt-chains in my post. If z = x (and here I really mean equals), then any other x seeing both of these candidates can be eliminated. It seems, a priori, that these strong inferences have as good a chance of producing an elimination as any xyt-chain. What am I missing?


Dealing with pairs of chains is possible and the case you're mentioning doesn't rely on the misleading notion of a "strong link" used by Aran. It can be expressed directly in the purely factual framework.

I've mentioned other possibilities of using two nrczt-chains, here http://forum.enjoysudoku.com/viewtopic.php?t=5591&postdays=0&postorder=asc&start=120
It is very inefficient. I can't prove this formally but I've tried.
From the player's POV, it also means following two threads of reasoning instead of one.

Many other possibilities for elimination can be written if you combine several chains - not only two. This is fully compatible with the general framework. The basis for this is the partial nrczt-chain theorem.

But, if we speak of implementation (Aran spoke of SudoRules) the question becomes a practical one. As not all the rules can be implemented in a solver, and one must therefore ask: which rules have the best return on investement? Rules based on several chains have a low ROI.
denis_berthier
2010 Supporter
 
Posts: 4234
Joined: 19 June 2007
Location: Paris

Postby re'born » Fri Nov 14, 2008 11:23 pm

denis_berthier wrote:
re'born wrote:
denis_berthier wrote:
re'born wrote:I didn't mention anything about paradoxes or t-candidates.
Aran did
Yes, but you were addressing me, not him. This is not you against the world.

Yes, but you were addressing me in the context of a conversation with Aran and in support of him.

Imagine the following conversation:
imaginary aran wrote:1. Pigs can fly.
2. Sudoku is a fruit.
3. 1 + 1 = 2.

imaginary Denis wrote:Your claims are absurd.

imaginary re'born wrote:
imaginary aran wrote:3. 1 + 1 = 2.

imaginary Denis wrote:Your claims are absurd.

Denis, would you elaborate. I'm fairly certain that 1+1 = 2 is an accepted mathematical fact.

Denis wrote:Fine, 1+1 = 2. So what? How does that make a pig fly or sudoku a fruit?

Just because I support aran on one point does not mean I support him on all points.


Denis wrote:This is a thread, this is not you with no context, especially if your post refers to another one.

You are exactly right, Denis. The quote in my post was exactly the context. How else can I restrict the conversation to one point other than quoting that point and then responding to it?

Denis wrote:I've mentioned other possibilities of using two nrczt-chains, here http://forum.enjoysudoku.com/viewtopic.php?t=5591&postdays=0&postorder=asc&start=120
It is very inefficient. I can't prove this formally but I've tried.

Thank you, Denis. Until I see evidence to the contrary, I'll take your word for it.
re'born
 
Posts: 551
Joined: 31 May 2007

PreviousNext

Return to Advanced solving techniques