The concept of a RESOLUTION RULE and its applications

Advanced methods and approaches for solving Sudoku puzzles

Postby denis_berthier » Wed Sep 24, 2008 3:52 am

Myth Jellies wrote:If you wish to define your UR1 as the condition pattern
Code: Select all
{1 2} --------- {1 2}
  :               :
{1 2} --------- {1 2 3}

I don't "wish". This is the standard definition.

Myth Jellies wrote:Thus the generalized missing pattern (call it UR1.1) defined in terms of what candidates are present is
Code: Select all
{1} --------- {2}
 :               :
{2} --------- {1 3}
with the added proviso that the "solved" cells here were not among the original givens.


The application of a resolution rule is based on what is present or absent in the grid at the time it is applied. It has no memory of past states.
In my appraoch, a cell is decided or not, no matter how it came to be so; similarly, a candidate is present or not, no matter how it came to be so.

For me, the above pseudo-pattern allows no conclusion.

What you are describing here is merely not a pattern in my sense.
So that I don't know what you are discussing, but it is certainly not resolution rules and resolution theories.

As a result, your objections don't apply in any reasonable sense to my approach.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby Myth Jellies » Thu Sep 25, 2008 12:06 am

The standard UR+1 or type 1 UR definition should at least allow for an unknown number of extra digits in the target cell. It should also be removing 12 from the target cell instead of placing a digit.

As for your approach, I saw nothing in your rules which prohibits you from using both solved values as well as candidates in your patterns. I also didn't see anything which prevents you from devising or using a simple originally_solved(r, c) function.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby denis_berthier » Thu Sep 25, 2008 1:12 am

Myth Jellies wrote:The standard UR+1 or type 1 UR definition should at least allow for an unknown number of extra digits in the target cell. It should also be removing 12 from the target cell instead of placing a digit.

I don't know what the standard definition SHOULD ALLOW, I only know what this definition currently IS and this is enough to illustrate my point about the non confluence of a resolution theory containing this rule.
You may be right about what the definition of UR1 SHOULD ALLOW, I don't know and I don't want to spend time on this: uniqueness really doesn't interest me. Uniqueness in itself is not in the topics of this thread. After scanning quickly the thread you recently opened on this topic, a better place to discuss your ideas on uniqueness, I'm not convinced by anything said there and I don't plan participating in these discussions.

Myth Jellies wrote:As for your approach, I saw nothing in your rules which prohibits you from using both solved values as well as candidates in your patterns.

True. Nothing prevents it a priori in my general concept of a resolution rule. But all the specific resolution rules I've defined, in particular all the types of chains, from the most basic and classical xy to the most elaborated nrczt-whips, don't allow this. Just check my definitions: they specify only candidates, all of which can have one and only one of 3 and only 3 statuses:
- must be present (left- and right- linking ones),
- must be absent (all those that are not specified to be present or optional),
- is optional (z- and t- candidates).
The reason for this choice is that considering decided values is useless in practice in such chains. Moreover, from a computational POV, it would lead to examining astronomically more useless partial chains.
Decided values are taken care of by elementary constraints propagation. This seems to be enough.
AFAIK, other approaches, e.g. based on graph theory, also work only on candidates. GSF or Red Ed, if you read this, can you confirm?

Myth Jellies wrote:I also didn't see anything which prevents you from devising or using a simple originally_solved(r, c) function.

Literally right: you didn't see it. You can't see it. It is not there. There is no such predicate (not "function") in my framework. Not only is it not there, it is not allowed.
In my framework, the (very short) list of basic predicates is closed. It is tailored to represent all and only the most elementary and direct facts one can observe on a PM. No new basic predicate is allowed.
Auxiliary predicates definable from this list may be introduced, such as the predicate describing an xy-chain[6], but from a pure logic POV, they are only shorthands for longer formulæ.
The reason is that something as "originally_solved" would be useless for all the rules I've defined (and all those I can imagine). Not only useless, but also a nuisance: it would introduce unnecessary complications.
(Indeed, before I published the 1st edition of my book, I had this predicate; I noticed I never used it; and, after analysing why, I concluded that it was useless and I eliminated it).

Using my framework, a player doesn't have to remember all his previous knowledge states (the formal logic model of PMs); he works only on the current one.
Moreover, from a player's POV, I can't see how having failed to see some UR1 at some point in time, he could remember that some UR1 was valid at that time.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby RW » Thu Sep 25, 2008 2:20 am

denis_berthier wrote:Moreover, from a player's POV, I can't see how having failed to see some UR1 at some point in time, he could remember that some UR1 was valid at that time.

From a player's POV, I usually remember which cells were given (that would be those printed in black, usually all using the same font) and which are solved cells (those filled in in my own handwriting using a pen). That's all you need to know.

Denis, I will not bother to enter an argument like this one, but perhaps you can clarify your views by answering the three following statements. A simple "true" or "false" is enough for each one:

1. You are designing your own framework.
2. You have decided that your framework only examines the candidates in unsolved cells.
3. You do not wish your framework to be able to find all available eliminations at any point of solving a puzzle.

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

Postby denis_berthier » Thu Sep 25, 2008 2:46 am

RW wrote:
denis_berthier wrote:Moreover, from a player's POV, I can't see how having failed to see some UR1 at some point in time, he could remember that some UR1 was valid at that time.

From a player's POV, I usually remember which cells were given (that would be those printed in black, usually all using the same font) and which are solved cells (those filled in in my own handwriting using a pen). That's all you need to know.

OK, but did you ever use in practice the information that a value was given rather than being obtained during the resolution process?

RW wrote:Denis, I will not bother to enter an argument like this one, but perhaps you can clarify your views by answering the three following statements. A simple "true" or "false" is enough for each one:
1. You are designing your own framework.

True. But it is not arbitrary, if that's what you had in mind. I've designed it by modelling the resolution process as a sequential process in which each step is based on (possibly complex) combinations of elementary FACTS directly present in the current PM. (To be specific, I'm not using the notions of an inference level or of a weak or a strong link - these are not factual. Of course, I have their purely factual counterparts).

RW wrote:2. You have decided that your framework only examines the candidates in unsolved cells.

False. As explained in my previous post, I'ven't DECIDED this a priori. But I've decided this for all my chains, for good reasons, also explained in my previous post.
If some day, there appears a rule that requires considering decided cells, it will be possible to integrate it into my framework without any need of changing it. As of today, I know no rule of this sort.

RW wrote:3. You do not wish your framework to be able to find all available eliminations at any point of solving a puzzle.

Meaningless. "Available" according to which criteria?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Fri Sep 26, 2008 2:05 am

As this may concern both this thread and the thread on fully supersymmetric chains, I've hesitated about where to put it and I've finally put it in the other thread: http://forum.enjoysudoku.com/viewtopic.php?t=5591&start=150.

Just after defining nrczt-braids, I've shown that they can solve exactly the same puzzles as T&E(ECP+NS+HS).
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby RW » Fri Sep 26, 2008 2:17 am

denis_berthier wrote:
RW wrote:
denis_berthier wrote:Moreover, from a player's POV, I can't see how having failed to see some UR1 at some point in time, he could remember that some UR1 was valid at that time.

From a player's POV, I usually remember which cells were given (that would be those printed in black, usually all using the same font) and which are solved cells (those filled in in my own handwriting using a pen). That's all you need to know.

OK, but did you ever use in practice the information that a value was given rather than being obtained during the resolution process?

I've used in practise the information that a solved cell was not a given value, when solving patterns like the one described by MJ.

denis_berthier wrote:
RW wrote:3. You do not wish your framework to be able to find all available eliminations at any point of solving a puzzle.

Meaningless. "Available" according to which criteria?

"Available" as in "logically deducable from the facts directly present in the current PM."

I guess this is the biggest difference between us. I look for available possibilities, using all the knowledge I have about sudoku, it's internal inferences and possible invalid states. You look for rules. To me a rule is meaningless, because it does nothing more than restricts me from using my own creativity. Statements like "this can't be done, because it isn't defined by the rules" are as pointless as trying to tell an athlete not to run as fast because that fast running isn't defined in your book "hidden logic of running fast".

If your attitude towards new techniques would be more like "interesting, I haven't thought about that, I shall see how it could be incorporated in my system when I have time, until then I'm open for suggestions", then I'd probably have some respect for it. But at the moment you are dismissing powerful solving techniques by saying that "I don't want to spend time on this: this really doesn't interest me." Such thinking has no place in sudoku solving and can only lead to an incomplete solving system that restricts the solver from using his own brain.

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

Postby denis_berthier » Fri Sep 26, 2008 2:40 am

RW wrote:I've used in practise the information that a solved cell was not a given value, when solving patterns like the one described by MJ.

Where? How? What's this pattern?

denis_berthier wrote:I guess this is the biggest difference between us. I look for available possibilities, using all the knowledge I have about sudoku, it's internal inferences and possible invalid states. You look for rules. To me a rule is meaningless, because it does nothing more than restricts me from using my own creativity. Statements like "this can't be done, because it isn't defined by the rules" are as pointless as trying to tell an athlete not to run as fast because that fast running isn't defined in your book "hidden logic of running fast".

I do look for rules. But never said no new rule can appear. On the contrary, I'm constantly giving new ones - see the recent nrczt-braids.
I've never said anything like: "this can't be done, because it isn't defined by the rules". But if someone makes an elimination I don't understand according to the rules I know, yes, then I'll try to see if it can be justified by a new general rule.
You're a player. I'm more interested in modelling the rules used by players. That's the only difference.

denis_berthier wrote:If your attitude towards new techniques would be more like "interesting, I haven't thought about that, I shall see how it could be incorporated in my system when I have time, until then I'm open for suggestions", then I'd probably have some respect for it. But at the moment you are dismissing powerful solving techniques by saying that "I don't want to spend time on this: this really doesn't interest me." Such thinking has no place in sudoku solving and can only lead to a incomplete solving system that restricts the solver from using his own brain.

Firstly, this is not a communist world. I am free about what I'm interested in and what I'm not; and I have no justification to give anyone about this.
Secondly, you're misinterpreting my lack of interest. If I say "I'm not interested", it only means "I'm not interested" - it doesn't mean "it is not interesting"; you'll notice I've never written "it is not interesting".
Thirdly, about UR1, because this is what you are mentioning as a "powerful solving technique", the standard version of UR1 fits perfectly in my framework. I've programmed it long ago. I already mentioned it in the first edition of my book, together with other URs and with BUG. But I never use them.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Wed Nov 05, 2008 9:41 pm


FAMILIES OF RESOLUTION RULES REVISITED


Several times, I've mentioned that I'd been considering four large families of resolution rules:

1) the elementary constraints propagation rules or ECP: elimination of candidates via propagation of direct contradictions along rows, columns and blocks,
2) the basic interaction rules between rows and blocks and between columns and blocks, BI
3) the subset rules: Naked, Hidden and Super-Hidden (or fish) versions of Singles, Pairs, Triplets, Quads,
4) the xy-to-nrczt (xy, hxy, xyt, hxyt, xyz, hxyz, xyzt, hxyzt, nrc, nrct, nrcz, nrczt) family of chain rules (including chains, lassos and whips).

I've already shown the unity of the subset rules through symmetry and super-symmetry.
I've also shown why all the rules in the xy-to-nrczt family can be considered as generalisations of the basic xy-chain rule. This includes nrc-chains, equivalent to the basic NLs or AICs (basic meaning "with no ALSs"). Although nrczt-chains subsume the whole family, the other chains are easier to find and should therefore not be forgotten. This family is thus organised in a pedagogical hierarchy.

The above rules are enough to solve almost any randomly generated puzzle (indeed, in several tens of thousands of randomly generated puzzles, I've met none that they couldn't solve).
From experiments with hundreds of puzzles taken from various forums, it appears that they are enough to solve puzzles upto SER=9.3. In particular, they are used daily by human players on the French sudoku-factory forum to solve puzzles at SER 9.1 to 9.3. They can probably solve any puzzle that any expert human player can solve and even much more.
It is important to recall this, because the sequel will discuss more complex patterns and I want to make it clear that such patterns, especially braids, are not necessary but for exceptionally hard puzzles.


Considering the current interest for such exceptional puzzles, I've recently extended my set of resolution rules in two directions.

Firstly, I've generalised my idea of additional z- and t- candidates and I've introduced a very general principle, zt-ing, that allows to define new patterns and associated new chain rules from any family FP of basic patterns: zt-whip(FP). zt-whipping is a general method (more general than the classical almost-ing) for including in chains/whips any pattern having an associated resolution rule.
In essence, the generalisation to nrczt-whip(FP) consists of allowing the right-linking candidates of a whip to be whole patterns instead of mere candidates.

If one takes FP=ECP+NS+HS, one gets the ordinary nrczt-whips.
If one takes FP=ECP+NS+HS+BI, one gets the grouped or hinged nrczt-whips.
If one takes FP = ECP+NS+HS+BI+SubsetRules, one gets a new family of chain patterns, whip(ECP+NS+HS+BI+SubsetRules), more general than nrczt-chains, AICs with ALSs and than their grouped or hinged counterparts. Indeed, these whips contain any AAAALS, AHHHHS and any AAAAAA-Fish, with as many A's or H's as one wants.
These patterns are chains, in exactly the same sense as any nrczt-chain or any AIC. They can be considered as defining a new set of levels in the hierarchy defined by family 4.
Such generalisations of nrczt-chains have also already been used in the sudoku-factory forum (see solutions by Caravail and Abi) - although in these cases ordinary nrczt-whips were enough.


Secondly, with the introduction of nrczt-braids, I have added a fifth family, composed of a (relatively mild) kind of nets.
The above two extensions can be combined, leading to zt-braids(FP) for any family of patterns with associated resolution rules.
I've also shown the close relationship between braids and Trial-and-Error (T&E) - the standard T&E procedure (which is not itself a resolution rule) with no guessing and no recursion:
for any family FP, any elimination that can be done by T&E(FP) can be done by some braid(FP).


All the above patterns have two very important properties (defined in detail in the first posts of this thread), helpful for finding them:
- they are non-anticipative, i.e. the validity of a partial whip/braid depends only on the previous candidates (and it can therefore be checked on-the-fly)
- they are composable, i.e. partial whips/braids can be linkd together to make longer ones, with obvious compatibility conditions at the junction.



Finally, using the above T&E vs braids theorem and taking FP = the family of nrczt-braids, I've shown that all the known puzzles can be solved by zt-braids(nrczt-braids).
As zt-braids(nrczt-braids) are a complex kind of nets, I'm currently trying to find a simpler FP family with the same property.
Such work may seem very far from the normal player's topics of interest, but I'm not considering this as replacing anything of what I've done previously - just as a short excursion in the realm of exceptionally hard puzzles, most of which have never been solved by human players but have given rise to extremely complex net solutions.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby StrmCkr » Thu Nov 06, 2008 11:58 pm

removed
Last edited by StrmCkr on Sat Dec 24, 2016 3:28 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 624
Joined: 05 September 2006

Postby denis_berthier » Fri Nov 07, 2008 12:34 am

Hi StrmCkr, it's been so long.

You're referring to an old discussion, but you're missing its point.
The pattern you are mentioning is standard UR. I don't understand your problem with it.

StrmCkr wrote:so uniquess based solving patterns shouldnt be used in your point of view.

This is a gross distortion of my POV.
I always said that using rules based on uniqueness is a matter of personal choice.
And I also said I'm personally not interested in uniqueness - which doesn't prevent you or anyone else from using it if you like it.


The topic of the old discussion and what I consider not a matter of personal choice but of flawed logic is using incorrect versions of UR, such as the one proposed by Myth, which doesn't even define a pattern and, of course, has never been proven:
Myth wrote:Thus the generalized missing pattern (call it UR1.1) defined in terms of what candidates are present is
Code: Select all
{1} --------- {2}
 :               :
{2} --------- {1 3}
with the added proviso that the "solved" cells here were not among the original givens.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby eleven » Fri Nov 07, 2008 1:39 am

denis_berthier wrote:The topic of the old discussion and what I consider not a matter of personal choice but of flawed logic is using incorrect versions of UR, such as the one proposed by Myth, which doesn't even define a pattern and, of course, has never been proven ...
So you still didn't understand it ? It has been proven many times.
One more time for you:
If you know, that the puzzle is unique and that no number was a given in the 4 cells of Myth's pattern (which must be in 2 boxes), the 3 must be true.
Otherwise the puzzle would have a solution with the pattern
Code: Select all
 1  ---  2
 2  ---  1

With the premise, that none of the numbers was a given, you can exchange 1 and 2 there (in the 2 boxes of the solution) to get a second solution for the same sudoku. This is a contradiction to te uniqueness.
eleven
 
Posts: 1534
Joined: 10 February 2008

Postby denis_berthier » Fri Nov 07, 2008 1:57 am

eleven wrote:
denis_berthier wrote:The topic of the old discussion and what I consider not a matter of personal choice but of flawed logic is using incorrect versions of UR, such as the one proposed by Myth, which doesn't even define a pattern and, of course, has never been proven ...
So you still didn't understand it ? It has been proven many times.
One more time for you:
If you know, that the puzzle is unique and that no number was a given in the 4 cells of Myth's pattern, the 3 must be true.
Otherwise the puzzle would have a solution with the pattern
Code: Select all
 1  ---  2
 2  ---  1

With the premise, that none of the numbers was a given, you can exchange 1 and 2 there to get a second solution for the same sudoku. This is a contradiction to te uniqueness.

Incantation is not proof.
What's the problem with the solution with
Code: Select all
 1  ---  2
 2  ---  1

?????
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby eleven » Fri Nov 07, 2008 2:42 am

denis_berthier wrote:What's the problem with the solution with
Code: Select all
 1  ---  2
 2  ---  1

?????

Maybe you should first read and then answer:(
eleven wrote:With the premise, that none of the numbers was a given, you can exchange 1 and 2 there (in the 2 boxes of the solution) to get a second solution for the same sudoku. This is a contradiction to te uniqueness.
eleven
 
Posts: 1534
Joined: 10 February 2008

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

eleven wrote:Maybe you should first read and then answer:(
eleven wrote:With the premise, that none of the numbers was a given, you can exchange 1 and 2 there (in the 2 boxes of the solution) to get a second solution for the same sudoku. This is a contradiction to te uniqueness.

Maybe you should keep zen and decide first what you're speaking of.
In Myth "UR1.1", which is under discussion,
Code: Select all
{1} --------- {2}
 :               :
{2} --------- {1 3}
with the added proviso that the "solved" cells here were not among the original givens.

3 cells are already decided. So there's no 1 and 2 to exchange.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Advanced solving techniques