Pattern-based classification of (hard) puzzles

Advanced methods and approaches for solving Sudoku puzzles

Re: Pattern-based classification of (hard) puzzles

Postby logel » Fri Apr 19, 2013 4:25 pm

denis_berthier wrote:
logel wrote:From some manual case studies I know that k is at least 5.

I bet you'll find a larger k on a larger collection.


It took really much more time than expected. The reduction of planes is a severe problem. Chasing bugs too.

The answer is 6. (not 42!)

So T&E(S6) solves all known sudoku represented by 817681 puzzles of the current hardest list, all SER 10.3 or more.
S6 stands for pattern with max 6 base lines, i.e. with max 6 true nodes in the pattern.
The S6-pattern used are additionally restricted to max three planes, so its in fact < S6.
If the restriction is on two planes, only 169 are left unsolved.

But I have absolutely no clue how you might compare this to T&E(B7). Looks like apples and oranges.

Re-reading your statements in this thread, I still don't understand why you object to a universal pattern definition.
I put up a new thread proposing such a definition: universal-elimination-pattern
There you also find more details of my results.

I appreciate very much your work on nrczt-chains and braids, but these pattern don't loose their value when embedded in a larger scope.
Any comparison of size or complexity needs a common basis.

Another mystery is how you justify that T&E(Bx) build a strict hierarchy for x=2,3,4,... in whatever sense of simplicity.
The size/complexity of pattern on T&E level one does not limit the size/complexity of the primary elimination.

Some observation (more to do) rather show that smaller patterns on level one increase the complexity of the primary pattern in some cases.
I mistrust the simplest-first strategy to be valid globally.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Pattern-based classification of (hard) puzzles

Postby denis_berthier » Fri Apr 19, 2013 6:12 pm

logel wrote:T&E(S6) solves all known sudoku represented by 817681 puzzles of the current hardest list, all SER 10.3 or more.
S6 stands for pattern with max 6 base lines, i.e. with max 6 true nodes in the pattern.
The S6-pattern used are additionally restricted to max three planes, so its in fact < S6.
If the restriction is on two planes, only 169 are left unsolved.
But I have absolutely no clue how you might compare this to T&E(B7). Looks like apples and oranges.

The only direct comparison I can see without much thought: you have a slightly smaller n with much more complex patterns.


logel wrote:I still don't understand why you object to a universal pattern definition. I put up a new thread proposing such a definition: universal-elimination-pattern

I'll discuss it in more detail there later. In a few words, the main problem I see is the necessity of trying all the truth value assignments (what you call permutations) for all the candidates in the pattern (this is a hidden aspect of complexity). In braids or B-braids, once the pattern is written, checking the validity of the elimination in a given resolution state (PM) is obvious (these patterns are indeed a full description of their proof).


logel wrote:I appreciate very much your work on nrczt-chains and braids, but these pattern don't loose their value when embedded in a larger scope. Any comparison of size or complexity needs a common basis.

It needs a common conceptual framework but not necessarily a common super-pattern. I can compare whips (or braids) and Subsets of same size - two a priori very different patterns - via the subsumption theorems.


logel wrote:Another mystery is how you justify that T&E(Bx) build a strict hierarchy for x=2,3,4,... in whatever sense of simplicity.The size/complexity of pattern on T&E level one does not limit the size/complexity of the primary elimination.
Some observation (more to do) rather show that smaller patterns on level one increase the complexity of the primary pattern in some cases.

There are two different things:
- the B?B classification. It's clear it doesn't allow a direct comparison of all the puzzles, even though one has, obviously:
B7B(P) <= B6B(P) .... <= B1B(P)=gB(P) <= B(P) for any puzzle (with equality in most cases);
- the universal B7B rating (or B8B if some day a B8B puzzle is found). It takes into account the global length of the B7B braid together with its inner braids.
You can even go beyond B7B (even if there are no puzzles out of it) and use BB as a universal rating (B-braids with a priori unrestricted inner braids). Here also, the global length takes into account the length of the inner braids.
Moreover, for puzzles in T&E(2), there are many more resolution paradigms (see chapter 12 on the "patterns of proof").


logel wrote:I mistrust the simplest-first strategy to be valid globally.

It is globally valid for any resolution theory with the confluence property - in particular for all the T-braid theories defined in my book, including all the BpB for any p.
But its meaning should be clear: it is simplest only for the chosen set of rules.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

What's a pattern ?

Postby denis_berthier » Mon May 06, 2013 8:51 am



What's a pattern?


The discussion here and in the other thread inspired me a few comments about the notion of a pattern.

Pattern vs elimination pattern
There are two kinds of resolution rules:
- Assertion rules: Pattern => candidate = True
- Elimination rules: Pattern => candidate = False

The basic assertion rules are Singles (Naked or Hidden).
A few other assertion rules are known, but I've shown long ago (see HLS1) that they can be considered as a combination of (simpler) elimination rules and Singles.

So, while trying to define what a pattern is, there is no real point in writing (as logel does) "elimination pattern" instead of "pattern".


Resolution rule vs pattern
Should one make a distinction between a resolution rule and a pattern ?

As (apart from the trivial Singles rule) a resolution rule can always be written as: Pattern => candidate = False, there's no deep point in distinguishing (as logel does) a pattern from a resolution rule. Said otherwise, trying to define the general concept of a pattern is basically the same thing as trying to define the general concept of a resolution rule.


Proof of an elimination
We now come to the heart of the question: how, considering an instance of a resolution rule / a pattern, can one known that it justifies an elimination?

In my view, this should be "obvious", i.e. it should require no extra steps of logical reasoning and no extra validation procedure.
This condition is satisfied by all the classical patterns (Subsets, reversible chains, Fish and their finned/mutant variants).
It is also satisfied by all the chains, whips, braids, Subsets, g-Subsets, generalized whips and braids I've introduced.
As I mentioned previously, all the known patterns can be classified into two broad families (Subsets vs chains), none of which can be reduced to the other.
Patterns I've called exotic, such as sk-loops, do not fall out of this classification: an sk-loop is a (very special) g-Subset.

Now, logel proposes a more general view of a pattern, in which an elimination may have to be justified by a complex procedure: try all the sets of truth value assignments to all the candidates of the pattern and show that all of them are incompatible with the target.
In case, the pattern belongs to either of the above two families, it is easy to find a simplified version of this procedure, based on the structure of the pattern. Maybe this would be easy also for a third family of patterns, still to be invented.
However, for any pattern not in these families, the only general way of doing so is setting to False all the candidates in the pattern linked to the target, and then for each CSP-variable of the base set* trying to set its value to each of the remaining candidates. As this is not a 2-SAT problem, there's no a priori bound on complexity. This means that, in spite of logel's unproved claims to the contrary, once the pattern (target included) is given to the player, he may still have a hard job in proving an elimination.
As for me, I would not accept this as a pattern-based solution.

*: supposing that logel finally admits the base set as part of his definition - otherwise one would first have to find it, thus requiring still more computations.


So, finally, what's a pattern?
I don't know (except that it has to be defined based on the basic concepts of Sudoku) and I don't care much about a general definition.
I know a few very powerful "chain patterns", "Subset patterns", I'm ready to accept any new "X pattern" provided that the associated elimination is obvious once an instance of it and a target are given (I don't even require that the target be easy to find - although this may be debatable). Perhaps, logel's overly general definition will eventually lead him to new patterns, but this is not yet the case.
In the meanwhile, I wonder:
- why should a player care about a general definition that he cannot use without a computer to check if an elimination is valid?
- why should a mere reader of a resolution path care about it if he cannot check every step without a computer?
Once more, we meet the idea that the goals of resolution must play a major role in defining our concepts.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Pattern-based classification of (hard) puzzles

Postby David P Bird » Mon May 06, 2013 11:50 am

Denis, some feed-back from the other side of the fence:

I agree that there is no need to call any pattern an assertion pattern, as to assert a digit is simply equivalent to eliminating all the others in the same cell. But I don't agree with dropping the 'elimination' qualifier, as for manual solvers there are also 'inference' patterns. For example with a finned fish pattern the inference is either a fin cell is true or the fish cells hold N truths.

Inference patterns can endure for quite a time as a puzzle is reduced and can be re-used repeatedly in combination with other inference patterns as they emerge. I guess you would want to call these pattern components or sub-patterns, but I feel that doesn't do them justice.

Now, without wanting to resurrect the issue, your classification of patterns as either being a subsets or chains doesn't include avoidable or uniqueness patterns. As I've mentioned to you before, avoidable patterns apply to sub-puzzles that can be proved to have to a unique solution, and so don't depend on uniqueness. Even if you don't use either of these pattern types yourself, for whatever reason, you should recognise that they exist.

As a manual solver, albeit with a computer helper, I rely on spotting "recognisable patterns", but that's a term defies a precise description. All I can say is, that at its core, a recognisable pattern should contain a number of elements that match some locating criteria which justifies looking for other elements which may take a variety of forms.

We're all looking for efficient ways to solve puzzles that can be explained to others as elegantly and briefly as possible, (a conflicting set of goals). If you look at the way manual solutions are presented, many authors re-order their steps and prune out the insignificant ones. For example, if a continuous AIC loop can be found, it will provide multiple eliminations and so advancing it as early as possible in the sequence will shorten a solution considerably. I may be mistaken, but I don't think there is a solver program that attempts to do anything like this. However, from my limited understanding of logel's approach, it appears to focus on a single target at a time which is going in the opposite direction.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Re: Pattern-based classification of (hard) puzzles

Postby denis_berthier » Mon May 06, 2013 12:48 pm

David P Bird wrote: I don't agree with dropping the 'elimination' qualifier, as for manual solvers there are also 'inference' patterns. For example with a finned fish pattern the inference is either a fin cell is true or the fish cells hold N truths.
Inference patterns can endure for quite a time as a puzzle is reduced and can be re-used repeatedly in combination with other inference patterns as they emerge. I guess you would want to call these pattern components or sub-patterns, but I feel that doesn't do them justice.

Exactly. I wouldn't call them patterns until they are completed. But I have no problem with the idea that it is useful to consider partial patterns or sub-patterns or components - whichever name you give them. Even in whips, braids ..., it is useful to consider partial ones and to assemble them to make a full longer one that allows an elim.
BTW, for me, a finned Fish is a mere z-fish (fish with additional z-candidates) or a z-gFish in the mutant case.


David P Bird wrote: Now, without wanting to resurrect the issue, your classification of patterns as either being a subsets or chains doesn't include avoidable or uniqueness patterns.

I have no problem with considering uniqueness patterns or U-patterns (In HLS already, I spoke of U-rules). The only problem I have is with the ayatollahs of uniqueness who want to oblige everyone to use it. My position has always been clear: use it if you want to, don't use it if you don't want to (BTW, I have exactly the same position for ANY rule).


David P Bird wrote: As I've mentioned to you before, avoidable patterns apply to sub-puzzles that can be proved to have to a unique solution, and so don't depend on uniqueness. Even if you don't use either of these pattern types yourself, for whatever reason, you should recognise that they exist.

This is very unclear to me. Do you mean you can prove that a sub-puzzle has a unique solution without finding this sub-solution? Can you give an example of such a pattern?


David P Bird wrote: from my limited understanding of logel's approach, it appears to focus on a single target at a time which is going in the opposite direction.

logel said he has a long term goal of finding the simplest resolution path. But, like any of us, he has no idea of how to do it and he explicitly said that his current definition of a pattern doesn't tackle this question.


My main point in the previous post was about checking an elimination. You don't say anything about this, but I have no doubt that, as a player, you would agree with me: ONCE a pattern and a target are given in a particular situation, one shouldn't have to do complicated computations to check that the pattern justifies the elimination of the target.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Pattern-based classification of (hard) puzzles

Postby David P Bird » Mon May 06, 2013 4:15 pm

Denis Berthier wrote:This [avoidable pattern subject] is very unclear to me. Do you mean you can prove that a sub-puzzle has a unique solution without finding this sub-solution? Can you give an example of such a pattern?

When a puzzle has two solutions for some sub-puzzle no inference will be available to distinguish the difference between two candidates in any of its cells. Once the cells have been reduced to two candidates each, it becomes a 'Deadly Pattern' that's isolated from all the external cells .
Code: Select all
 
  12  .  .  | 124 .  .           12  .  .  | 24 .  .
  .   .  .  | .   .  .    =>     .   .  .  | .  .  .
  123 .  .  | 12  .  .           23  .  .  | 1  .  .

In the diagram on the left, if uniqueness is assumed there is an inference that (4)r1c4 and (3)r3c1 can't both be false otherwise a Deadly Pattern would remain.

Now if (2)r3c4 can be eliminated, the diagram on the right results (called an Avoidable Rectangle). The fact that this elimination has been possible shows that these cells don't have two alternative solutions. But if (4)r1c4 and (3)r3c1 were both false, the Deadly Pattern would have existed and (2)r3c4 could never have been eliminated!

This produces a theorem that if it has been possible to eliminate one of the two solutions for a potential DP, the other solution is also false. In the identifying cell it isn't necessary to assert one of the alternative DP candidates digits, but just to eliminate one of them.

I'm sure that you can tidy up my proof to make it more rigorous. I had a brief exchange with Blue < here > about the type of inference that is needed to produce an Avoidable Pattern. (Any further insights on this you may have on this are best posted there.)

Denis Berthier wrote:My main point in the previous post was about checking an elimination. You don't say anything about this, but I have no doubt that, as a player, you would agree with me: ONCE a pattern and a target are given in a particular situation, one shouldn't have to do complicated computations to check that the pattern justifies the elimination of the target.

My feeling on this is that a pattern that provides a theorem that has general utility can be invoked without needing a step-by-step proof of that theorem eg the Four Colour Mapping theorem. If no such theorem has been defined every link in the argument must be justified, but perhaps by combining defined inference pattern theorems (yes, I still want to hang onto that term because they provide theorems too). I'm therefore not prepared to accept a statement such as "running though all the permutations it transpires that ..." which is more or less my interpretation of logel's approach.

Champagne and I disagree over this. For me the way he defines and notates Exocet eliminations amounts to identifying a signature pattern, and then giving resulting eliminations that he's found in a back room. Blue analysed his original posts and found they nearly all relied combining multiple fish patterns. Later some of us expanded on this and came up with a pattern based version < Junior Exocet >, or JExocet which is just about on the limit of what I'd accept as a "recognisable pattern". To my knowledge this covers over 90% of all Exocet eliminations. Embedded in the pattern are a number of subsidiary inferences which can also be employed to make additional eliminations either when it's first discovered or later following further puzzle reductions.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Re: Pattern-based classification of (hard) puzzles

Postby denis_berthier » Mon May 06, 2013 5:53 pm

David,

for the DPs I'll have a look at the other thread and answer there if I have anything to say.

David P Bird wrote:
Denis Berthier wrote:My main point in the previous post was about checking an elimination. You don't say anything about this, but I have no doubt that, as a player, you would agree with me: ONCE a pattern and a target are given in a particular situation, one shouldn't have to do complicated computations to check that the pattern justifies the elimination of the target.

My feeling on this is that a pattern that provides a theorem that has general utility can be invoked without needing a step-by-step proof of that theorem

Yep, and this is the case for all the (g)Subsets, whips, braids, ...


David P Bird wrote:I'm therefore not prepared to accept a statement such as "running though all the permutations it transpires that ..." which is more or less my interpretation of logel's approach.

It is indeed his view.


David P Bird wrote:Champagne and I disagree over this. For me the way he defines and notates Exocet eliminations amounts to identifying a signature pattern, and then giving resulting eliminations that he's found in a back room. Blue analysed his original posts and found they nearly all relied combining multiple fish patterns. Later some of us expanded on this and came up with a pattern based version < Junior Exocet >, or JExocet which is just about on the limit of what I'd accept as a "recognisable pattern". To my knowledge this covers over 90% of all Exocet eliminations. Embedded in the pattern are a number of subsidiary inferences which can also be employed to make additional eliminations either when it's first discovered or later following further puzzle reductions.

The last time I looked at exocet, the only "definition" I could find contained some set of conditions that could be called a partial pattern P and another condition that said "C1 and C2 are contradictory", where C1 and C2 are candidates appearing in P.*
For me, this is totally meaningless unless it is clearly specified HOW C1 and C2 are supposed to be proven contradictory: from an abstract logic POV, any candidate that is not the real value for a cell is contradictory with the givens and a fortiori contradictory with any other candidate.
The best way of interpreting this is to consider Exocet only as a heuristic for looking for potential eliminations (find P and then try to find some pattern relating C1 and C2 and proving that they are contradictory - e.g. find a bibraid based on C1 and C2). As we've never been able to state such heuristics, this may be a first step. The question then is, what's its value in real solving (without a computer)?

As for JExocet, I don't remember reading about this. I'll have a look.

(*: I also saw on the programmer's forum an alternative more formal definition proposed by Blue, but he received no answer).
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Pattern-based classification of (hard) puzzles

Postby blue » Mon May 06, 2013 11:36 pm

Hi Denis,

denis_berthier wrote:As for JExocet, I don't remember reading about this. I'll have a look.

(*: I also saw on the programmer's forum an alternative more formal definition proposed by Blue, but he received no answer).

I think the culmination of my ideas, was D.P. Bird's specification for the JExocet pattern. It extended them a little, to include some "easily recognized" cases that were not entirely describable in terms of "Finned Swordfish". I'll have to say (apologies to David), that like ronk, I was unsatisfied with David's specification, and would have preferred one that was more oriented towards sub-patterns that are strictly base/cover problems.

I would be curious if you can place the JExocet patterns in the "chains" or "subset" category.
My gut says no, but I'm open minded.

Like you (I'm sure), and David, I was not satisfied with champagne's definitions. It wasn't that there was a problem with the logic, but that, like with logel's definition, the valid instances of the "pattern", are not easily verified.
Note: I put quotes around 'pattern', to emphasize the fact that I wouldn't put it in the same class any of the "usual" patterns. I don't especially like calling it a pattern, but for lack of a better term, I'm using anyway (along with the quotation marks).

Best Regards,
Blue.
blue
 
Posts: 573
Joined: 11 March 2013

Re: Pattern-based classification of (hard) puzzles

Postby champagne » Tue May 07, 2013 5:46 am

blue wrote:Like you (I'm sure), and David, I was not satisfied with champagne's definitions. It wasn't that there was a problem with the logic, but that, like with logel's definition, the valid instances of the "pattern", are not easily verified.



Hi blue,

May be an historical comment on that.

The Exocet general definition (and I am sure you are here thinking of a more restrictive one) is an attempt to define the wider specification to cover all patterns having the implicit logic shown by Allan BARKER in the puzzle "fata morgana" in a multi floor analysis.

At the start, I applied it to all AAHS, but,

1) I got a lot of redundancy,
2) It appeared that using only 2 cells belonging to a mini row, mini column the redundancy vanished and nearly nothing was lost
3) When, later, the twin Jexocet has been added, it appeared that nearly all EXOCET+ twin were located in a band (I have only one exception so far).

David, as manual player made a very good job focusing on the JEXOCET. It is by far the most common form of EXOCET when the base is a mini row/column and it is there in more than 50% of the potential hardest file.

The JEXOCET is "easy" to see for a manual player, it is also very fast to look directly for it with a computer (thousands times faster than using permutations). As in any pattern analysis, it is just requiring more code.

Last but not least, seen on the solving angle, but using the uniqueness property, the JEXOCET pattern finds its best efficiency when using the "abi loop" pattern.

It remains that the solving power of an EXOCET is highly variable form one puzzle to another one.

For sure, to-day one can think that the field has been deeply explored and the wider definition can be ignored.

Nevertheless, exploring all possibilities within a band has shown interesting situations and these are not JEXOCETS

regards

champagne
champagne
2017 Supporter
 
Posts: 5675
Joined: 02 August 2007
Location: France Brittany

Re: Pattern-based classification of (hard) puzzles

Postby denis_berthier » Tue May 07, 2013 6:36 am

blue wrote:I think the culmination of my ideas, was D.P. Bird's specification for the JExocet pattern.

I wasn't aware your ideas had been further developed by David on this forum.
In general, I can't read more than the first few posts of a thread before getting a headache, not being able to tell what is being spoken of; so I can't even imagine reading the 27 pages of the Exocet thread.


blue wrote:I was unsatisfied with David's specification, and would have preferred one that was more oriented towards sub-patterns that are strictly base/cover problems.
I would be curious if you can place the JExocet patterns in the "chains" or "subset" category.
My gut says no, but I'm open minded.

I'm not yet able to understand David's definition (due to a few ambiguities), let alone to answer these questions.
Considering only the pattern of cells, some kind of chain definition is not obvious. There might be a gSubset definition but I can't confirm this right now.

My rough classification of patterns into two broad categories may not be exhaustive. The fact is, all the known patterns fall into either of them (and sometimes in both, depending on one's POV) - except maybe a few exotic ones*. My main point in speaking of this rough classification was, and still is, the structures of these patterns carry the proofs of their eliminations. I'm completely open to any other pattern not falling in either of these two categories, provided that it also carries the proofs of its eliminations.
(* sk-loops can easily be considered as g-Subsets, although I don't think this is in the spirit of Steve's definition as a generalised chain pattern).

A remark about the base/cover vocabulary. Even if "base" is convenient and I also use it to mean a set of CSP-variables in the general CSP context, i.e. a set of 2D-cells in the Sudoku context, I don't like "cover" because it supposes that one is dealing with a base-cover problem - which is not the case.
As you and everyone here know, it is not enough to cover the candidates in the base set - one must cover them with constraint sets (where a constraint set is a set of candidates with pairwise constraints between any two candidates in this set); due to additional conditions, I call them transversal sets or transversal constraint sets.
I think my general definition of a g-Subset - a straightforward extension of the most standard Subsets and of the Mutant Fish - covers (if I dare use this word in this context) all the clean part of Allan's definition. And it has the advantage of clearly showing that there is both a close relationship and an essential difference between Subset or g-Subset patterns and chain patterns (e.g. whips, braids, g-whips or g-braids) - see PBCS for details.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

JExocet

Postby denis_berthier » Fri May 10, 2013 9:35 am

Definition and discussion of the JExocet pattern has been moved to a new thread where it will fit better than here: http://forum.enjoysudoku.com/post226661.html#p226661
Please post any new comments on this topic there.

I'll continue to discuss here topics related to its classification.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Exotic patterns

Postby denis_berthier » Sat May 11, 2013 8:38 am




Exotic patterns


When I first introduced the notion of an exotic pattern (http://forum.enjoysudoku.com/pattern-based-classification-of-hard-puzzles-t30493-2.html), I din't say what I meant. The expression must have hit something, as it was almost immediately taken for the name of a new thread - but without further analysis of its meaning.

Using the sk-loop example, I can be more precise.

As I said before, there are two and as of now only two large families of rules:
- the chain-like ones: whips, braids, g-whips, g-braids, ...
- those based on Subsets or g-Subsets.
The patterns in each of these families depend on a single parameter (length or size) and this naturally leads to a rating of puzzles (according to the hardest step philosophy and the simplest first strategy).
Moreover, these families and ratings are not specific to Sudoku, they are meaningful for any finite CSP - in particular for many logic puzzles (see Kakuro examples here: http://forum.enjoysudoku.com/can-you-solve-this-without-trial-and-error-t30960.html).
When both types of rules are included in a resolution theory, general subsumption theorems (valid for any CSP) don't leave any choice on how to define a combined rating: length of chains and size of Subsets must be equated.


What I had in mind when I introduced the expression of an exotic pattern is a pattern (defined in a factual/descriptive way independent of any procedure) that can only have one (or two or a few) length(s)/size(s) and that can, in and of itself, lead to no classification system.
Given an exotic pattern, the best we can therefore hope is to see how adding it to a set of rules can modify the corresponding rating/classification system. For the sk-loop, I have done this in chapter 13 of PBCS.


Now, one could ask: as you have shown that sk-loops are gSubsets[16], they are no longer exotic.
But my answer is: yes, they remain exotic nevertheless. When we speak of sk-loops, we don't consider them as having to be looked for at the same time as all the other gSubsets or Subsets of same or smaller size. We somehow give them higher priority.
Said otherwise, we don't consider them mainly as gSubsets[16].
Actually, that's why I didn't write "they are Subsets/gSubsets" but "they can be considered as ...".
Last edited by denis_berthier on Sat May 11, 2013 9:18 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Pattern-based classification of (hard) puzzles

Postby David P Bird » Sat May 11, 2013 8:55 am

Denis, in addition to the 2 classes of elimination patterns that I've already mentioned (JExcocet, and Avoidable Patterns) there are two more that I would describe in everyday terms as exotic.

Reverse BUGs: which are again are based on the 'a given per UA" derived constraint. For manual solvers these are only practical for 2-digit UAs. If a digit placement would cause the UAs containing all the givens for a set of digits to be identifiable, that placement must be false if these UAs don't cover every house. (I'm sure you'll dismiss this again but I include it for completeness.)

Overlapping Oddagons: This is another one of Steve Kurzhals' amazing finds. An oddagon is the threat of a single digit conjugate chain with an odd number of nodes (eg a kite pattern). These must be disrupted by the digit being true in a cell that sees two of the nodes. The method locates the possible disrupting cells for sets of oddagons for different digits. When the total number of disrupting cells equals the number of digits in the set, any non-member digit in these cells can be eliminated. The different oddagons concerned needn't completely coincide but must certainly overlap.

Although locating one of these sets is hard work, I think it still qualifies as being a pattern based method. Steve's example was lost in the Eureka forum crash but possibly Don will have a copy.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Re: Pattern-based classification of (hard) puzzles

Postby denis_berthier » Sat May 11, 2013 9:24 am

David P Bird wrote:I'm sure you'll dismiss this again but I include it for completeness.

I dismiss nothing.
Let's say there are:
- regular patterns (those belonging to the large families) and independent of the assumption of uniqueness
- exotic patterns, as defined above and independent of the assumption of uniqueness
- U-patterns, depending on the assumption of uniqueness
- exotic U-patterns, as defined above but depending on the assumption of uniqueness

Probably all the U-patterns are exotic U-patterns, but I'm not very aware of all the U-patterns, so I leave this open.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Pattern-based classification of (hard) puzzles

Postby David P Bird » Sat May 11, 2013 11:21 am

denis_berthier wrote:
David P Bird wrote:I'm sure you'll dismiss this again but I include it for completeness.

I dismiss nothing.
Let's say there are:
- regular patterns (those belonging to the large families) and independent of the assumption of uniqueness
- exotic patterns, as defined above and independent of the assumption of uniqueness
- U-patterns, depending on the assumption of uniqueness
- exotic U-patterns, as defined above but depending on the assumption of uniqueness

Probably all the U-patterns are exotic U-patterns, but I'm not very aware of all the U-patterns, so I leave this open.

Denis, sorry 'dismiss' was too strong a word.

However your categories don't make it clear which one includes Avoidable Patterns.

As you're aware I think intuitively rather than mathematically or in terms of formal logic al theory, but childlike questions can sometimes be great eye openers regarding our un-stated conditions and assumptions.

'Daddy, are you saying that everything's made up out of atoms?'
'Yes sweetie'
'What about shadows?'


Your justification for refusing to assume uniqueness, (because publishers never claim this), don't carry over to proven unique sub-puzzles. Your reasons there just appear to be that they're inconvenient to you. To my simple mind it appears that your constantly combing inferred constraints from mixed chain and subset classes of inference patterns to reach conclusions, and I still fail to see a solid reason for excluding 'proven uniqueness' as a further class.

Your arguments imply that you'd be prepared to use uniqueness if a trustworthy publisher claimed it, and therefore I just feel that the discussion your leading here is rather incomplete.

I should quickly add that I'm only considering Avoidable Patterns here, not Reverse BUGs because they do assume uniqueness.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

PreviousNext

Return to Advanced solving techniques