The concept of a RESOLUTION RULE and its applications

Advanced methods and approaches for solving Sudoku puzzles

Postby denis_berthier » Thu Oct 18, 2007 6:38 am

Mauricio wrote:
denis_berthier wrote:And you can come out with a sudoku resolution theory that will contain billions of billions of such rules.
I'll invite you for dinner when you've finished writing it ;)

My intention was not to do that, but instead to expose the dangers of using a subjective word (rationality) in an objective way.


I had written "As any real chain has a well defined length, choosing to look for chains with shorter lengths before longer ones is a perfectly rational strategy (although not the only one possible)"

I can't see what's your problem with this use of "rational". Or did I use it anywhere else?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby Mauricio » Thu Oct 18, 2007 7:05 am

denis_berthier wrote:I can't see what's your problem with this use of "rational". Or did I use it anywhere else?

It seems you forget things
denis_berthier wrote:It seems that some people consider stopping T&E at depth 1 as a possible technique. But, I'm like you, I can't see the rationality behind that.
Last edited by Mauricio on Sat Oct 20, 2007 2:14 am, edited 1 time in total.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby RW » Thu Oct 18, 2007 7:11 am

denis_berthier wrote:If there was no difference, can you explain why everybody is looking for new resolution rules (new kinds of fish, new chains,…)?
Why shouldn't we merely use T&E?

I don't think that anyone is saying that patterns should not be used. Patterns have many advantages over proposition chains, for example they may be able to eliminate several candidates. However, I don't see why a solver should be limited to a set of predefined rules. Here's what I disagree with the most:
denis_berthier wrote:One of the reasons for my introducing the notion of a resolution rule is that with them we are sure we are not using disguised forms of T&E. I consider that they are the proper formalisation for a "pure logic solution".

With this you clearly say that solving by the defined rules is "pure logic" while any other technique is not as it could be "disguised T&E". I wouldn't condemn the use of T&E like that, because it is as logical as any other technique. The rules of sudoku are very simple, I don't see the need for additional rules that restrict what techniques may or may not be used.

Not only is T&E required to solve the hardest puzzles, but it is also an essential tool in developing new techniques. Most of the new fish are found by finding eliminations using templates (T&E), then studying the situation to find the essential pattern which allows the elimination. If nobody ever did T&E, then most of the techniques we know of today would never have been discovered.

T&E also helps you understand the logic behind any pattern based elimination. We see people all the time here who have read about a pattern, but not understood the basic logic that allows the elimination, then they use the pattern in the wrong way. All that is required is to understand that if a pattern allows you to eliminate a candidate, it is because if the candidate was true, then there would be a contradiction in the pattern cells. This very simple rule explains all pattern based elimintaions, yet I hardly ever see it in a technique explanation because the word "if" is considered too T&E...

denis_berthier wrote:I don't know what a nested chain is.

Well, mostly when solvers have exhausted the possibilities using chains with singles, the next step is chains with locked candidates, followed by chains with subsets and so on. When the concept of "chain" is expanded enough in this way, we sooner or later arrive at "chains with chains" which solve all puzzles, just like T&E does.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby denis_berthier » Thu Oct 18, 2007 7:51 am

RW wrote:I don't think that anyone is saying that patterns should not be used. Patterns have many advantages over proposition chains

So, that's it.
You're not speaking of the same thing as me.
I never spoke of proposition chains (with all the stuff of weak and strong links).
My chains are not chains of inferences. They are patterns of well defined type and length.
With each chain type is associated a chain rule (which is a mathematical theorem) that allows some predefined eliminations in some predefined cells. You are not supposed to re-prove the chain rule each time you're using it.
The notions of weak links, strong links and chains of inferences are at the origin of a total confusion between chain patterns and chains of reasoning.
But, when you have found an xy-chain, this allows some eliminations, as a Hidden-Pairs would, and this supposes absolutely no hypothesis. You're just applying a theorem.


RW wrote:I don't see why a solver should be limited to a set of predefined rules.

Who said the set of rules should be limited? You can always devise new resolution rules.

RW wrote:Here's what I disagree with the most:
denis_berthier wrote:One of the reasons for my introducing the notion of a resolution rule is that with them we are sure we are not using disguised forms of T&E. I consider that they are the proper formalisation for a "pure logic solution".

With this you clearly say that solving by the defined rules is "pure logic" while any other technique is not as it could be "disguised T&E". I wouldn't condemn the use of T&E like that, because it is as logical as any other technique. The rules of sudoku are very simple, I don't see the need for additional rules that restrict what techniques may or may not be used.

The fact is most people don't accept T&E in a solution.


RW wrote:T&E also helps you understand the logic behind any pattern based elimination. We see people all the time here who have read about a pattern, but not understood the basic logic that allows the elimination, then they use the pattern in the wrong way. All that is required is to understand that if a pattern allows you to eliminate a candidate, it is because if the candidate was true, then there would be a contradiction in the pattern cells. This very simple rule explains all pattern based elimintaions, yet I hardly ever see it in a technique explanation because the word "if" is considered too T&E...

I can't see any relation between using "if" while you are proving a theorem and using T&E while you are solving a puzzle. These are two different activities.
But you're still thinking that you must re-prove a chain rule every time. Why then not re-prove also the rules for fish?
The origin of this confusion is the same as I indicated above.

RW wrote:
denis_berthier wrote:I don't know what a nested chain is.

Well, mostly when solvers have exhausted the possibilities using chains with singles, the next step is chains with locked candidates, followed by chains with subsets and so on. When the concept of "chain" is expanded enough in this way, we sooner or later arrive at "chains with chains" which solve all puzzles, just like T&E does.

As far as I know even these extended chains cannot solve Easter Monster.
Anyway, in my chains, there are neither ALS nor subsets of any kind and they solve "only" 99,99% of the minimal puzzles.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby ravel » Thu Oct 18, 2007 9:26 am

denis_berthier wrote:
ravel wrote:Theoretically i cant find a basic difference.

The theoretical difference is between finding a predefined pattern and applying the associated rule on one hand and making ad hoc reasoning on the other.

What i meant is, that theoretically they are the same in the sense, that these predefined patterns exactly work with the same logic than t&e chains, that lead to a contradiction. They only are limited to special cases.
If there was no difference, can you explain why everybody is looking for new resolution rules (new kinds of fish, new chains,...)?
Why shouldn't we merely use T&E?
Now this is a practical pov, lets try not to mix that for a moment. Patterns in the common sense are relations in a puzzle, which are more or (than) less easy to spot and allow eliminations or settings, based on the same logic. In the last year i only saw very few new patterns, indeed namings of patterns (that of course already had been used under the name t&e), that are really worth to directly look for. One example is the W-wing (remote naked pair). Maybe another one the simple patterns, that, as you found, appear, when you do the work of transforming the puzzle. Also ALS's for me are not really patterns to look for (if i find one, then always through chaining/t&e) and i never would call any chains of a given length > 7 a pattern. Also there are so much "chain patterns" with length less 8, that i dont find it practicable to memorize any of them, that dont have properties, that would jump into my eyes (like the pairs in the W-wing).

btw hese extended chains can solve Easter Monster, if you are patient, Sudoku Explainer will show you.
Last edited by ravel on Thu Oct 18, 2007 5:31 am, edited 1 time in total.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby RW » Thu Oct 18, 2007 9:30 am

denis_berthier wrote:So, that's it.
You're not speaking of the same thing as me.
I never spoke of proposition chains (with all the stuff of weak and strong links).

I know you didn't, and with proposition chains I did not mean your chains, but the chains that you would regard T&E.
denis_berthier wrote:The fact is most people don't accept T&E in a solution.

Around here most people accept step by step solutions for the hardest puzzles, with each step explained. It doesn't matter whether the steps have been found through T&E or some other predefined technique.
denis_berthier wrote:But you're still thinking that you must re-prove a chain rule every time.

No, I'm not. As I said, patterns have many advantages over proposition chains. I only listed one of the advantages, but the second would have been that you don't need to reinvent the wheel when you stumble upon the same situation. However, in order to use the wheel in the first place, you must understand how it works. I just said that proposition logic, commonly refered to as T&E, is a very simple way to explain and understand every single pattern or chain available. And if the solver is unsure if he has understood it, proposition logic may always be used to double check.
denis_berthier wrote:As far as I know even these extended chains cannot solve Easter Monster.

Sudoku Explainer can provide a step by step solution using extended forcing chains.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby denis_berthier » Thu Oct 18, 2007 12:32 pm

RW wrote:I just said that proposition logic, commonly refered to as T&E, is a very simple way to explain and understand every single pattern or chain available.

Logic = T&E ???
Of course, every rule for a chain of a well defined type (or for any pattern) is proven and can be explained by elementary logic. If you consider different types of chains, the proofs will always rely on logic, although they will be different.
When you use T&E, you also refer to logic to justify the eliminations you do when you backtrack. But this doesn't entail that T&E explains everything. The basis of all explanation is logic, not T&E.

RW wrote:
denis_berthier wrote:As far as I know even these extended chains cannot solve Easter Monster.

Sudoku Explainer can provide a step by step solution using extended forcing chains.

But forcing chains are not chains in my sense. They correspond to no predefined pattern.

Acceptability of a technique is a very subjective matter.
For me, being a resolution rule is only a minimum criterion of acceptability and it allows to discriminate T&E. For chains, I introduced additional (relative) criteria (such as length, homogeneity, non-anticipativeness, composability).
But this doesn't mean that if a technique is not known to be expressible as a resolution rule, it will never be. New types of chains may be discovered. If you discover one while you were using T&E, that's great; but it will pertain to the process of discovery, not to the proof of the rule.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Thu Oct 18, 2007 12:52 pm

ravel wrote:
denis_berthier wrote:
ravel wrote:Theoretically i cant find a basic difference.

The theoretical difference is between finding a predefined pattern and applying the associated rule on one hand and making ad hoc reasoning on the other.

What i meant is, that theoretically they are the same in the sense, that these predefined patterns exactly work with the same logic than t&e chains, that lead to a contradiction. They only are limited to special cases.

All depends on what you call the same logic.
FAPP, we can consider there is only one logic. Indeed, this is not even true: there is classical vs intuitionist, modal, epistemic, and so on. Anyway, at this level of generality, you can only be right.
I think what we are interested in is a limited number of predefined patterns (your special cases), as simple as possible, that allow us to solve (almost) all the puzzles. It may be a case of Occam's razor: don't accept anything unnecessarily complex.

ravel wrote:In the last year i only saw very few new patterns, indeed namings of patterns (that of course already had been used under the name t&e),

I'm not sure this is fair for the people who discovered these new patterns. Having an example where an elimination is done by some ad hoc reasoning as in T&E and formulating a general rule that justifies it are very different things.
From an example, lots of different justifications can generally be given. Finding the proper generalisation may be very hard and is much more than a matter of naming.

ravel wrote:i never would call any chains of a given length > 7 a pattern.

It may be a difficult to find pattern, but there is no logical ground for denying its being a pattern, in exactly the same logical sense as a Naked-Pairs.
What you mean, I think, is you wouldn't give it high acceptability from a practical POV.
Fortunately, as I showed, almost all the puzzles can be solved with chains of length <= 7.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby RW » Thu Oct 18, 2007 1:40 pm

denis_berthier wrote:
RW wrote:I just said that proposition logic, commonly refered to as T&E, is a very simple way to explain and understand every single pattern or chain available.

Logic = T&E ???
Of course, every rule for a chain of a well defined type (or for any pattern) is proven and can be explained by elementary logic. If you consider different types of chains, the proofs will always rely on logic, although they will be different.
When you use T&E, you also refer to logic to justify the eliminations you do when you backtrack. But this doesn't entail that T&E explains everything. The basis of all explanation is logic, not T&E.

Okay, right now I'm not quite sure what your definition of T&E is... To me trial and error means literally trial and error. Try a candidate and find the error. Every elimination by any pattern may be explained this way. For many people it is the easiest way to understand the techniques. When I tried to explain the concept of a naked pair to my old mother who was stuck in the daily newspaper puzzle, she couldn't understand the either/or logic in the pair itself, but understood the elimination when I pointed out that if that candidate was true, then both cells in the pair would have to hold the same digit.

Randomly inserting digits until you eventually happen to find the final solution is in my opinion not T&E, because then your purpose of inserting the digits is not to find an error, but to find the solution. This technique I would rather call "random insertion of numbers".

denis_berthier wrote:But forcing chains are not chains in my sense. They correspond to no predefined pattern.

Then what are they? Are they logical or not? If I wrote a definition on the pattern in the Easter Monster where SE finds the 11,4 monster chain, would it then become a chain in your sense? (Don't worry, I will not write a definition, because it would most likely end up several pages long...)

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby ravel » Thu Oct 18, 2007 2:48 pm

denis_berthier wrote:But forcing chains are not chains in my sense. They correspond to no predefined pattern.
I really have a problem, when you come here and redefine all the basic terms, we use since years. So now i always have to distinguish between t&e or chains in your sense and in the sense of the rest of the forum members. If you have different definitions for similar things to those, which often have been used here, PLEASE take another term for it. We always have to think twice, what the hell this guy is saying, just because you MEAN another thing using the SAME terms. When i read back, i see a lot of misunderstandings based on this.
I think what we are interested in is a limited number of predefined patterns (your special cases), as simple as possible, that allow us to solve (almost) all the puzzles. It may be a case of Occam's razor: don't accept anything unnecessarily complex.
To repeat myself: I am NOT interested in chain patterns, that i have to memorize and that restrict me to just look for them. I probably will find most of them (and some more) by doing normal t&e, in my sense.
ravel wrote:In the last year i only saw very few new patterns, indeed namings of patterns (that of course already had been used under the name t&e),
You should not cut the citation here. I continued:
ravel wrote: that are really worth to directly look for.
I hope, it was clear, that this is my personal opinion.
I'm not sure this is fair for the people who discovered these new patterns.
Of course i appreciate a lot of work done in this area, but of course i solve puzzles my own way (and other authors dont misunderstand that, i am sure).
ravel wrote: i never would call any chains of a given length > 7 a pattern.
It may be a difficult to find pattern, but there is no logical ground for denying its being a pattern, in exactly the same logical sense as a Naked-Pairs.
What you mean, I think, is you wouldn't give it high acceptability from a practical POV.
What i mean is, that you are again misusing a term. I never had a problem with the word pattern in this forum before.
Fortunately, as I showed, almost all the puzzles can be solved with chains of length <= 7.
What should i say now ? Repeat me again ? I dont want to learn all these <=7 "chain patterns". I can find them anyway.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby denis_berthier » Thu Oct 18, 2007 4:36 pm

RW wrote:When I tried to explain the concept of a naked pair to my old mother who was stuck in the daily newspaper puzzle, she couldn't understand the either/or logic in the pair itself, but understood the elimination when I pointed out that if that candidate was true, then both cells in the pair would have to hold the same digit.

I think nobody would call this T&E. It is merely proof by contradiction.

RW wrote:Randomly inserting digits until you eventually happen to find the final solution is in my opinion not T&E, because then your purpose of inserting the digits is not to find an error, but to find the solution. This technique I would rather call "random insertion of numbers".

That's only a matter of names. When I speak of T&E, I speak of a precise procedure. If you don't like T&E, call it depth-first search.

denis_berthier wrote:But forcing chains are not chains in my sense. They correspond to no predefined pattern.

Then what are they? Are they logical or not? If I wrote a definition on the pattern in the Easter Monster where SE finds the 11,4 monster chain, would it then become a chain in your sense? (Don't worry, I will not write a definition, because it would most likely end up several pages long...)[/quote]
My problem is not "are they logical or not?" but "are they resolution rules or not?"
As you can't write them as such, difficult to answer the question.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby re'born » Thu Oct 18, 2007 4:56 pm

A quick off-topic post.

Denis, I've noticed in this thread and others your propensity for speaking on behalf of other people. Here is a sampling from this thread:
Denis Berthier wrote:As everybody is looking for solutions based on "pure logic"...
Most of the mathematicians are very specialised in their own field and they don't know much about other fields. Moreover, generally, they don't know anything about FOL.
FOL appears naturally as the proper formalism for Sudoku because everybody is looking for solutions using only "pure logic".
..."pure logic", as it is generally understood,
Usually, what we want in math is not only a proof but an illuminating proof.
No mathematician would deny it.
Few people would be satisfied with a T&E solution and they want what is often called a "pure logic solution".
The notions of weak links, strong links and chains of inferences are at the origin of a total confusion between chain patterns and chains of reasoning.
The fact is most people don't accept T&E in a solution.
I think nobody would call this T&E.

I'm sure you're not intentionally trying to speak with such authority as it would be arrogant and perhaps intimidating to those who might question the validity of your statements ("...boy, I must be wrong since Denis says that no mathematician would deny his point.") And I'm sure you'd be quick to clarify that when you use phrases like, "The fact is..." you don't mean 'fact' in the sense of what is true, but of what you'd like to think is true and if it isn't you'll change the definitions so that it is.

I only mention this so that in the future you let your (very important and substantial) arguments stand on their own, without the unnecessary accoutrement.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby denis_berthier » Thu Oct 18, 2007 4:58 pm

ravel wrote:I really have a problem, when you come here and redefine all the basic terms, we use since years. So now i always have to distinguish between t&e or chains in your sense and in the sense of the rest of the forum members. If you have different definitions for similar things to those, which often have been used here, PLEASE take another term for it. We always have to think twice, what the hell this guy is saying, just because you MEAN another thing using the SAME terms. When i read back, i see a lot of misunderstandings based on this.

I've defined a new global conceptual framework based on mathematical logic, in which some words have a different, generally more precise meaning.
In some respects, my definition of chains is different from others, e.g. a target doesn't belong to the chain. I've given precise reasons for this.
Also, my chains are defined as patterns of cells and links, not as chains of inferences, with all the confusion hidden behind this idea and all the false ideas it conveys.
This framework works, since it allowed me to discover poweful new types of chains that can solve almost all the puzzles with no subsets (hinges, ALSs, …) included in them.
When you find an xy-chain on a grid, it is a chain in your sense and a chain in mine. We insist on different views of it. But it is the same thing FAPP. As all my chains are generalisations of xy-chains, why shouldn't I call them chains?

For T&E, things may be different. Due to the unlimited confusion about this word, this name distracts us from speaking of the essential and it might be better for me to find another name for the procedure I'm speaking of. Each one will then decide if and how what he considers to be T&E is related to my procedure.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby gsf » Thu Oct 18, 2007 5:11 pm

denis_berthier wrote:Also, my chains are defined as patterns of cells and links, not as chains of inferences, with all the confusion hidden behind this idea and all the false ideas it conveys.

it would really help if you were as meticulous about tearing down other ideas as you are about building up your own

can you point out exactly what false ideas means?
otherwise it appears that you are claiming only my chains are true

and where do chains/loops composed of { strong weak conjugate } links fit in?
are they in the inference confusion?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby denis_berthier » Thu Oct 18, 2007 5:42 pm

gsf wrote:can you point out exactly what false ideas means?
otherwise it appears that you are claiming only my chains are true
and where do chains/loops composed of { strong weak conjugate } links fit in? are they in the inference confusion?

I have already answered this.
The notion of a strong link, e.g., leads to confusion because its definition has changed:
- initially it was associated to conjugacy
- then bivalue was added to it
- then ALS were added
- if we find another way of making "strong inferences", it will be extended again.
That's confusing an obvious step in a proof with a factual situation on a grid and that's cheating with complexity.

Chains are chains, i.e. particular patterns describing a factual situation on a grid, they can be neither true nor false.
Only chain rules can be true or false.

What I'm claiming is not that my chain rules are true (of course, they are) and the others are false (of course, they are not); what I'm claiming is that my conceptual framework is better (has better theoretical foundations) than the usual one.
This claim is clear. You may not agree, but then please provide precise arguments.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Advanced solving techniques