The New Sudoku Players' Forum

[champagne]

- whether what is being talked about is the pattern or the rule, i.e. whether the impact of the mere presence of the pattern on the rating of a puzzle is taken into account (e.g. is the puzzle still considered as "having the pattern" if applying the associated rule has no impact or no significant impact?)

I shall not discuss whether a manual player would have solved that puzzle using the exocet property.
In case of a positive response, the exocet would likely have been found in that position

Code: Select all

A     B     C     |D     E    F     |G     H     I     
5     69    127   |1278  1389 12789 |248   34678 247   
127   37    4     |6     1358 12578 |9     378   257   
69    8     237   |257   4    2579  |256   1     23567 
-------------------------------------------------------
13478 2     13578 |9     158  6     |1458  478   1457   
1489  459   6     |12458 7    12458 |3     489   1459   
14789 4579  1578  |3     158  1458  |14568 2     145679
-------------------------------------------------------
34678 1     378   |478   2    4789  |46    5     39     
248   456   9     |1458  1568 3     |7     46    12     
247   34567 257   |1457  1569 14579 |12    39    8     


but in that case, the manual player would have used the "abi loop" pattern (refused by denis because it uses uniqueness properties) and immediately concluded that the soulution for the base is 58.
(this is a very common status in exocets with 3 digits)
with now found 58 in the base and the target, we have still easy (an well known) eliminations linked to the exocet, but still with the uniqueness property.

IMO if we use exocets, we must do it in the appropriate way.

[denis_berthier]

but in that case, the manual player would have used the "abi loop" pattern [...] and immediately concluded that the soulution for the base is 58.

This argument is totally irrelevant to the topic under discussion.
The topic was evaluating the impact of JExocet, not JExocet+"abi loop", or JExocet+ any other convenient rule.
This is also totally unrelated to whether one accepts rules based on the assumption of uniqueness.

IMO if we use Exocets, we must do it in the appropriate way.

As JExocet (not Exocet, which is not a pattern) is totally independent of the assumption of uniqueness, nothing allows to say that the appropriate way of using it requires to add this assumption.

[champagne]

[
As JExocet (not Exocet, which is not a pattern) is totally independent of the assumption of uniqueness, nothing allows to say that the appropriate way of using it requires to add this assumption.

just years of experience from many players starting with "ttt" years ago

[denis_berthier]

[As JExocet (not Exocet, which is not a pattern) is totally independent of the assumption of uniqueness, nothing allows to say that the appropriate way of using it requires to add this assumption.

just years of experience from many players starting with "ttt" years ago

Observing that some rule B (say abi loop) can sometimes/often be applied after some rule A (say JExocet) doesn't mean that A must systematically be be stuck to B and to additional assumptions irrelevant to the validity of A.

[denis_berthier]

Classification and frequency of patterns/rules (continued)


This is a continuation of my previous post "Classification and frequency of patterns/rules"
http://forum.enjoysudoku.com/pattern-based-classification-of-hard-puzzles-t30493-74.html
where I showed in particular that the mere presence of a JExocet pattern may have little effect on the resolution path of a puzzle.
I didn't have much time to analyse many examples, but the first five in the list mentioned in that post lead to the following results:

Code: Select all

#1    SER = 7.7    W = 4     JE-W = 4
#2    SER = 8.8    W = 4     JE-W = 4
#3    SER = 9.0    W = 6     JE-W = 6
#4    SER = 9.2    B = 9     JE-B = 8
#5    SER = 9.3    W = 17    JE-W = 16


where:
- W (resp. B) is the W (resp. B) rating
- JE-W (resp. JE-B) is the W (resp. B) rating when all the target candidates of the JExocets have been artificially eliminated at the start. This is the most favourable situation for the JExocet - much too favourable considering its complexity.

In #4, the B instead of the W rating is used (it is one of the very rare cases in which they differ).


From such a small sample, no final conclusion can be drawn, but it nevertheless raises serious questions about the power of JExocets in the "grey zone" (http://forum.enjoysudoku.com/the-sudoku-grey-zone-t31143.html).

[logel]

Hi Denis
Your post contains some really fundamental stuff. Seems that we do not agree on important points.
So I try to argue as careful as possible.

What's a pattern?
The discussion here and in the other thread inspired me a few comments about the notion of a 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.

At first rules and patterns are in my view completely different categories. I regard a rule as a class definition for pattern objects and patterns as instances of rule classes. Of course all rule classes must comply to the basic sudoku rules. So patterns consists of candidates with their basic properties (e.g. linked to A) and other special properties releated to the corresponding rule.
Classed naturally can have sub-classes and super-classes, so patterns can relate to many rule classes. Your braid-class is a very large one and super-class of many traditional rule classes (you name it subsumption). This is nice for verifying solvability, but for a particular puzzle the relation to a sub-class has more benefits because its more specific. So here again its important what is your intention.
My intention to define universal patterns was simply to have a super-class covering as much as possible, but still containing enough information to define a useful size. I was really a bit surprised that the mimimality condition already ensures that all such patterns have a presentation as set of baselines (not unique as we now know). It seems that this property is very fundamental for sudoku puzzles.

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.

harsh words ... but I am very relaxed about the validation issue.
The main difference is that the rules you refer to require no extra steps of logical reasoning. That means the these rules carry the validation in the class definition. So the validation is on class level where the universal validation is on instance level. Although this is less desirable its correct. The possible complexity does not affect the correctness either. I do also not claim that a player has to perform the validation, I only state that its possible in principle. I could also resort to the cheap trick to define classes with one instance each, but with no gain. The universal validation is just a fallback version that always works.
I would rather say that one can determine rules from the bare candidate set by moderate reengineering. Especially chains are easy to detect. I do this quite often if I don't understand a complicated pattern logic. A hard job is somthing different.

So do you want to tell me that in case I forgot about the rule origin of the pattern candidates, the pattern is not a valid elimination any more? Be serious.

*: 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.

A have a draft of an alternative definition, which is slightly less general and moves the validation to class level. But I do not want to present a green banana again. The difference is tiny and will you not make more happy.

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.

The main issue is comparability, and comparison relies on common properties.

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?

Just a few remarks. An aspect of complexity of solving is always kept in the dark. You always stress the point that a braid definition is not a procedure. OK. But nevertheless a procedure is needed to produces a valid braid[14] pattern and you have to check thousands if not millions of queues without result and never shown. So in some way the final braid[14] contains this complexity. This is a more fair comparison to the effort of validation.
A computer cannot do anything else than I can, only faster. Saves my time.

Once more, we meet the idea that the goals of resolution must play a major role in defining our concepts.

Yes.

[logel]

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?'

I like this. One should be careful about everything.

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.

The inconvenience has a name: lost comparability.

I used plains and plain pairs/triple as predefined sub-puzzles. Unique states of these sub-puzzles appear quite frequently and the uniqueness is also proven at this point. But still each false candidate has a smaller elimation pattern inside the sub-puzzle, usually of different size. So the sub-puzzle itself has no useful size to compare with other eliminations.
If you accept unique sub-puzzles as elimination, you might also accept sub-puzzles with multiple solutions where some of the candidate have stable values. That was the leading idea when I used plains as sub-puzzles. If you dont care about size and comparison this justifies eliminations.
A more serious danger appears when you use larger sub-puzzles. The solutions gets more and more trivial because the complexity inside the sub-puzzle is no more visible.

[denis_berthier]

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.

At first rules and patterns are in my view completely different categories. I regard a rule as a class definition for pattern objects and patterns as instances of rule classes.

Changing the vocabulary can make a screen of smoke but doesn't make new ideas.

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.

The main difference is that the rules you refer to require no extra steps of logical reasoning.

Exactly: no extra step of logical reasoning and no hidden checking procedure. A resolution rule is self-contained; it is a complete description of its condition pattern and of the elimination it justifies; moreover the elimination can be proven on the basis of the condition pattern and the Sudoku axioms (without any reference to any specific instantiation). As you have read my books, you can see that the proofs of all the resolution rules are almost obvious once the condition pattern is clearly defined.

So do you want to tell me that in case I forgot about the rule origin of the pattern candidates, the pattern is not a valid elimination any more? Be serious.

The rule is proven once for all.
Seeing an instantiation of a rule in a PM is another matter. Of course, if you don't see it, you won't use it to do the elimination.

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.

The main issue is comparability, and comparison relies on common properties.

Wrong. I already answered this.
There are two types of comparisons:
- along a generalisation hierarchy: xy-chains < nrc-chains < nrct-chains < whips < braids < g-braids ...
- via subsumption theorems, bearing on eliminations: e.g. whips and Subsets can be compared, in spite of having no common super-rule.
You consider only the first type.

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?

Just a few remarks. An aspect of complexity of solving is always kept in the dark. You always stress the point that a braid definition is not a procedure. OK. But nevertheless a procedure is needed to produces a valid braid[14] pattern and you have to check thousands if not millions of queues without result and never shown. So in some way the final braid[14] contains this complexity. This is a more fair comparison to the effort of validation.

You make a total confusion between finding an instance of a pattern/rule in an actual PM and justifying the elimination once the instance is found.

I was really a bit surprised that the mimimality condition already ensures that all such patterns have a presentation as set of baselines (not unique as we now know). It seems that this property is very fundamental for sudoku puzzles.

*: 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.

A have a draft of an alternative definition, which is slightly less general and moves the validation to class level. But I do not want to present a green banana again. The difference is tiny and will you not make more happy.

As the difference is about a fundamental vice in your original definition, I wouldn't call it tiny. I think it should be your priority.

[logel]

Hi Denis

At first rules and patterns are in my view completely different categories. I regard a rule as a class definition for pattern objects and patterns as instances of rule classes.

Changing the vocabulary can make a screen of smoke but doesn't make new ideas.

On last try to clear the fog.

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.

The main issue is comparability, and comparison relies on common properties.

Wrong. I already answered this.
There are two types of comparisons:
- along a generalisation hierarchy: xy-chains < nrc-chains < nrct-chains < whips < braids < g-braids ...
- via subsumption theorems, bearing on eliminations: e.g. whips and Subsets can be compared, in spite of having no common super-rule.
You consider only the first type.

Comparing rules (class types) is one thing and comparing patterns (instances) is another. I am less interested in rule comparison.
= = =
As an illustration a take a very concrete pattern example related to an S2-braid example prior in the thread.

Code: Select all

98.7.....7.6...8...54......6..8..3......9..2......4..1.3.6..7......5..9......1..4 # 7658;GP;H1521

S2-braid[14]: b9n3{r9c8 r8c9} - b9n6{r8c9 r789c7} - b9n8{r8c9 r7c789} - {n8r7c5 NP: b8{r7c5 r8c4}{n2 n4}} - r7c6{n2 n9} - r9c4{n9 n3} - {n3r5c4 HP: b5{r5c6 r6c5}{n3 n6}} - b5n7{r5c6 r4c456} - r4c8{n7 n4} - r5c7{n4 n5} - r4c9{n5 n9} - r6c7{n9 .} ==> r9c8 <> 5

Consider this pattern object in form of a material list: ( boolean variables (candidates) in nrc notation )

Code: Select all

CORE={548,398,389,698,697,687,689,657,667,898,889,878,879,875,876,275,284,475,484,276,294,976,994,394,354,364,356,365,656,665,765,756,745,746,748,749,448,457,557,549,949,967} ( unordered set of candidates )
TARGET=598
LINKS={ Cx NAND Cy = true, where Cx,Cy are all pairings of candidates from CORE+TARGET } ( unordered set of equations )
BASE={ C1 OR C2 OR ... OR Cn = true, where Cx from CORE, all members of CORE occur in at least one equation } ( unordered set of equations )

This particular pattern is an elimination because it contains enough information to prove TARGET = false. This pattern notation is not meant to be human readable, to guard against any misunderstanding.
There are various ways to prove the elimination:
(1) Build all permuations of CORE+TARGET variables that comply to the equations LINKS+BASE. Assert that 598 = false with all permutations. This is also not human readable and not meant that any "player" should perform it. I am also well aware of the complexity of this procedure growing with the number of candidates. But of course the list of all cases is a valid proof.
The pattern matches the universal definition too. After removing any candidate variable along with the associated equations there exists a permutation with TARGET = true.
(2) Set TARGET = true and build an elimination sequence until a contradiction occurs. This T&E procedure needs secondary recursion levels if only single eliminations are applied. This procedure is also of some complexity in the general case, but is always computable. Using rules (BI+Pair) requires a prior proof of these rules. Its a matter of personal taste regarding such T&E sequence as human readable. Its a proof anyway.
The interpretation of an elimination pattern as contradiction sequence is rather inconvient because its not unique for components and order.
(3) What about S2-braids? My position is that the above pattern can also be interpreted as S2-braid. Therefore one needs a procedure(sic!) to check if the pattern is complying with any of the braid rules or not. And only after this check is positive and adds order information to the pattern, "no extra steps of logical reasoning" are necessary. The checking procedure is of non-trivial complexity too. This (hidden?) procedure nowhere appears in your pages and seems to be mixed into the finding process. Thats why I mentioned it.
(4) There are even more interpretations, Allans base-cover model, etc.

So any rules add type along with additional information to the pattern object.

.... moreover the elimination can be proven on the basis of the condition pattern and the Sudoku axioms (without any reference to any specific instantiation)

That is not much different from (1) or (2). So what we are discussing?
The motivation for a universal pattern definition was not a magic method for "new" or "better" eliminations, but to exclude obscure elimination constructions. So minimality is the key idea. Non-minimal patterns like plains or other partial puzzles would preclude comparison of patterns from the start, or can make the solution steps trivial with large "eliminations".

Two questions:
a) Do you regard the pattern example (CORE+TARGET+LINKS+BASE) as elimination? yes/no.
b) Do you regard the pattern example as S2-braid? yes/no (maybe why)

[denis_berthier]

Hi logel,

As an illustration a take a very concrete pattern example related to an S2-braid example prior in the thread.

Code: Select all

98.7.....7.6...8...54......6..8..3......9..2......4..1.3.6..7......5..9......1..4 # 7658;GP;H1521

S2-braid[14]: b9n3{r9c8 r8c9} - b9n6{r8c9 r789c7} - b9n8{r8c9 r7c789} - {n8r7c5 NP: b8{r7c5 r8c4}{n2 n4}} - r7c6{n2 n9} - r9c4{n9 n3} - {n3r5c4 HP: b5{r5c6 r6c5}{n3 n6}} - b5n7{r5c6 r4c456} - r4c8{n7 n4} - r5c7{n4 n5} - r4c9{n5 n9} - r6c7{n9 .} ==> r9c8 <> 5

Consider this pattern object in form of a material list: ( boolean variables (candidates) in nrc notation )

Code: Select all

CORE={548,398,389,698,697,687,689,657,667,898,889,878,879,875,876,275,284,475,484,276,294,976,994,394,354,364,356,365,656,665,765,756,745,746,748,749,448,457,557,549,949,967} ( unordered set of candidates )
TARGET=598
LINKS={ Cx NAND Cy = true, where Cx,Cy are all pairings of candidates from CORE+TARGET } ( unordered set of equations )
BASE={ C1 OR C2 OR ... OR Cn = true, where Cx from CORE, all members of CORE occur in at least one equation } ( unordered set of equations )

This particular pattern is an elimination because it contains enough information to prove TARGET = false.

To be clear, let me just recall that the discussion has never been about whether the elimination was correct or not.

There are various ways to prove the elimination: [...]
(3) What about S2-braids? My position is that the above pattern can also be interpreted as S2-braid. Therefore one needs a procedure(sic!) to check if the pattern is complying with any of the braid rules or not. And only after this check is positive and adds order information to the pattern, "no extra steps of logical reasoning" are necessary. The checking procedure is of non-trivial complexity too. This (hidden?) procedure nowhere appears in your pages and seems to be mixed into the finding process. Thats why I mentioned it.
So any rules add type along with additional information to the pattern object.

But what you are describing here is not at all my approach for S2-braids or for any resolution rule. I never look for "all the patterns (in your sense of pattern-instances)" before trying to interpret them as such and such.
Once I've chosen the resolution theory (the set of resolution rules) that I want to use to solve a puzzle, I (i.e. SudoRules) look only for pattern instances in this family. This is much more efficient than what you are describing (and probably "exponentially" more efficient as pattern size grows).
[BTW, SudoRules uses the pattern matching capabilities of an inference engine (CLIPS); it tries to match only the predefined patterns (indeed, it has no possibility of matching anything else or of doing anything else than pattern-matching; the "program" is the set of resolution rules).]
This remark is also totally independent of my own sets of rules. The same would apply even to SSTS. When one looks for Pairs, Triplets or Quads, they don't bother with other possible ad hoc structures you would call patterns.

.... moreover the elimination can be proven on the basis of the condition pattern and the Sudoku axioms (without any reference to any specific instantiation)

That is not much different from (1) or (2).

My approach is obviously completely different. What you propose is ad hoc eliminations justified by ad hoc proofs depending on specific PMs. If you want to present them as justified by rules, you must add an interpretation phase - much like in Allan's approach.
As you say:

This pattern notation is not meant to be human readable, to guard against any misunderstanding.

That's another major difference and it is directly related to the first. In my view, any line of a resolution path is a readable proof of an elimination.

a) Do you regard the pattern example (CORE+TARGET+LINKS+BASE) as elimination? yes/no.

yes, but this is only labouring your point. Your question amounts to: "is my example an example of my definition?".

b) Do you regard the pattern example as S2-braid? yes/no (maybe why)

NO. As you write it yourself, it can be interpreted as an S2-braid (at best - I didn't check if the data correspond). That's quite different from being an S2-braid.


The way I see how your approach might be useful is not for solving puzzles, but for trying to find new rules. I you find pattern-instances that look similar in some sense, then you might reach a higher degree of generality. The whole problem is, your approach doesn't allow per se to define what "similar in some sense" means.

[denis_berthier]

On the classification of exotic patterns


As exotic patterns are not associated with families of rules of increasing size that could be used as a scale for any rating system, the question arises as to where one should classify them in my hierarchy.

Remember that this hierarchy is based on:
- chain length for patterns in the bivalue-chains, whips, g-whips, braids, g-braids,... family
- size of the base set for patterns in the Subsets, g-Subsets family
and that these two quantities are equal for patterns that can be considered from both points of view.



1) Classification versus priority

One of the problems with exotic patterns is, they are brittle: if other rules are applied before them, they may disappear and, depending on the other rules used, the eliminations they allowed may no longer be available.
Said otherwise, exotic patterns, when added to a resolution theory with the confluence property may destroy this property if they are used too late.
There is thus a dilemma between using an exotic pattern as soon as available and classifying it (and the puzzles) according to its real logical complexity.

In Sudoku Explainer, rating and order of rule application are confused.
But there's no reason to do the same in any resolution strategy.
When a pattern is brittle, one can decide to apply it as soon as available (or immediately after another set of rules, e.g. SSTS) and nevertheless assign it a high rating.

In this post, I won't discuss when an exotic pattern should be applied (this is a matter of personal taste), but only which rating it should be assigned.
For the hardest puzzles, whether it should be applied before or after some basic rules is somehow irrelevant as, usually, no basic rule can be applied at the start. But for puzzles with lower ratings, this may drastically change statistics for the pattern.

There are currently not so many exotic patterns.
For the sk-loop pattern, it is easy to see that it can be considered as a g-Subset of size 16. This immediately defines its classification.
So, I'll now concentrate on the J-Exocet cases. I first need precise definitions.



2) Standard Jk-Exocet

For definiteness, let me recall what I consider as a standard Jk-Exocet, k = 2, 3, 4, 5, ...
I have previously written "basic" Jk-Exocet but considering that we usually speak of "standard Fish" and not of "basic Fish" (vs e.g. Franken or Mutant ones), I think "standard" is better.
The following definition is a refinement of both David's initial definition: (http://forum.enjoysudoku.com/jexocet-pattern-defintion-t31133.html) and of my re-writing of it (http://forum.enjoysudoku.com/jexocet-pattern-defintion-t31133-12.html), with the S-conditions broadened as introduced here (http://forum.enjoysudoku.com/jexocet-pattern-defintion-t31133-145.html)
I'll also make a distinction between a Jk-Exocet-in-columns and a Jk-Exocet-in-rows, based on the quasi-fish part in the S-lines.

standard Jk-Exocet-in-columns, for k = 2, 3, 4 , 5, ...:

Conditions on the Pattern of Cells

Code: Select all

  *-------*-------*-------*
  | B B . | . . . | . . . |  B = Base Cell Pair
  | . . . | Q . . | R . . |   
  | . . . | Q . . | R . . |  Q = 1st Object Cell Pair
  *-------*-------*-------*  R = 2nd Object Cell Pair
  | . . S | S . . | S . . |       
  | . . S | S . . | S . . |  S = S-Cells, included in three S-columns   
  | . . S | S . . | S . . |   
  *-------*-------*-------*  . = Any candidates (including base digits)
  | . . S | S . . | S . . | 
  | . . S | S . . | S . . |     
  | . . S | S . . | S . . |   
  *-------*-------*-------*

The "Base Cell Pair" consists of two cells in the same "Base Row" and the same "Base Block"
Each of the two "Object Cell Pairs" (Q and R) is made of two cells in the same horizontal band as the Base Cell Pair (B) (the Base Band) but not in the same block/box as B; the two Object Cell Pairs may be in the same block.
The first "S-column" intersects the Base Block but doesn't contain any of the Base Cells.
The 2nd and 3rd "S-columns" intersect the Base Band by passing respectively through the Q and R Object Cell Pairs.

Conditions on candidates

1) No base cell is decided.
Each base cell may have up to k candidates, but together, they contain exactly k digits (called the "Base Digits").
2) Each Object Cell Pair is made of two cells: the "Target Cell" and the "Companion Cell"
Each Target Cell contains at least one Base Digit (plus possibly non-Base Bigits)
Companion Cells contain no Base Digit
3) For each Base Digit, there are two rows containing all its occurrences in the S cells (be it as a candidate or as a decided value).



3) Standard Advanced Jk-Exocet

The following definition is the extension of the above, proposed by Blue while I was preparing this post: (http://forum.enjoysudoku.com/jexocet-pattern-defintion-t31133-152.html). Blue's idea is, there's no reason to restrict the Target Cells to the Base Band.
I keep both definitions here, as I don't know which will prevail and it isn't at all the topic of this thread to discuss this, but it's clear for me that Blue's is more elegant.

Standard Advanced Jk-Exocet-in-columns, for k = 2, 3, 4 , 5, ...:

Conditions on the Pattern of Cells

Code: Select all

  *-------*-------*-------*
  | B B . | . . . | . . . |  B = Base Cell Pair
  | . . . | S . . | S . . |   
  | . . . | S . . | S . . |   
  *-------*-------*-------*   
  | . . S | S . . | S . . |       
  | . . S | S . . | S . . |  S = S-Cells, included in three S-columns   
  | . . S | S . . | S . . |   
  *-------*-------*-------*  . = Any candidates (including base digits)
  | . . S | S . . | S . . | 
  | . . S | S . . | S . . |     
  | . . S | S . . | S . . |   
  *-------*-------*-------*

The "Base Cell Pair" consists of two cells in the same "Base Row" and the same "Base Block".
The first "S-column" intersects the Base Block but doesn't contain any of the Base Cells.
The 2nd and 3rd "S-columns" do not intersect the Base Block (but they may be in the same tower).
In each of the two S-columns not crossing the Base Block, one of the S-cells is designated as a Target Cell.

Conditions on candidates

1) No Base Cell is decided.
Each Base Cell may have up to k candidates, but together, they contain exactly k digits (called the "Base Digits").
2) Each Target Cell contains at least one Base Digit (plus possibly non-Base Bigits)
3) For each Base Digit, there are two rows such that all the occurrences of this digit in the S cells (be it as a candidate or as a decided value) are either in the Target Cells or in these two rows.



4) Proof of the Standard and the Standard Advanced Jk-Exocet

The proof I gave for the standard Jk-Exocet works with almost no change for both versions.
Let a and b be the (unknown) true values of the two base cells. By the rules of Sudoku, each of a and b must be the value of a cell in each of the three S-columns.
But condition 3 entails that each of a and b can be the value of at most two S cells that are not Targets. Therefore (as neither a nor b can be in the Base Row or the Base Block anywhere outside the S Cells) each of a and b must also be the value of one of the Target Cells.
We have thus proven that the values of the two target cells are the same as those of the two base cells.
We don't know these values, but this is enough to exclude any non base digit from the target cells.



5) Classification of the standard Jk-Exocet

At first sight, formulating the whole set of conditions for the standard Jk-Exocet requires 6 + 3*k CSP-variables / 2D-cells, associated with:
- the 2 Base Cells,
- the 2 Target Cells,
- the 2 Companion Cells,
- the 3k cinj cells, one i for each S column and one k for each base digit
(see details here http://forum.enjoysudoku.com/pattern-based-classification-of-hard-puzzles-t30493-69.html)

However, contrary to the patterns in the main two families of rules mentioned at the start of this post, all these 2D-cells don't play similar roles.

In my view of the Jk-Exocet, the S-columns play the major role and, for each Base Digit, the covering conditions for the S-cells are Fish-like. The complexity of this part of the pattern is analogous to the complexity of k combined Swordfish, i.e. 3k.
Once this part of the pattern is found, the remaining Q, R and B cells are very easy to determine and the relevant conditions are very easy to check.
So, I think the standard Jk-Exocet should be classified at level 3k (taking only its Fish part into account).



6) Classification of the standard Advanced Jk-Exocet

Classifying the Advanced version is only a little more subtle:
At first sight, there are only 2 + 3k CSP-variables / 2D-cells, associated with:
- the 2 Base Cells,
- the 3k cinj cells, one i for each S column and one k for each base digit, as in the standard case.
But listing all the constraints remains complex.
Writing the covering conditions of the S-cells require the choice of two target cells as in the standard case, so it can't be considered as simpler. Globally, it even looks a little more complex; but the difference may be small.

Finally, I think the standard Advanced Jk-Exocet should also be classified at level 3k.

[David P Bird]

Hi Denis

One of the problems with exotic patterns is, they are brittle: if other rules are applied before them, they may disappear and, depending on the other rules used, the eliminations they allowed may no longer be available.

I'm somewhat confused here. I believe that if only bi-directional inferences are used, the basis for every elimination will still be visible in the final solution grid. For example (a)cell 1 and (b)cell2 can't both be false will be seen to exist. At some intermediate solution stage the links between these cells may have become degenerate but the evidence is still there. In such cases the qualifying criteria for the exotic pattern should be set so that doesn't matter – this is reminiscent of my point about counting truths rather than links when recognising partial fish in an exchange with Blue.

Are you saying that this is can't be done if the pattern depends on following unidirectional inferences?

In the other thread I said that, before I modified my spreadsheet, I found it easier to find JExocets before applying simple eliminations because I could distinguish givens from solved cells more easily. I'm wondering if you misinterpreted my meaning?

Digesting the rest of your post will take me some time.

[denis_berthier]

Hi Denis

One of the problems with exotic patterns is, they are brittle: if other rules are applied before them, they may disappear and, depending on the other rules used, the eliminations they allowed may no longer be available.

I'm somewhat confused here. I believe that if only bi-directional inferences are used, the basis for every elimination will still be visible in the final solution grid. For example (a)cell 1 and (b)cell2 can't both be false will be seen to exist. At some intermediate solution stage the links between these cells may have become degenerate but the evidence is still there.

The only thing I mean is, you need to use other rules, simpler than JExocet, to take advantage of this remaining evidence (logically simpler, but not necessarily simpler from your POV).
As a result, it would be queer to use JExocet prior to such simpler rules.

One more point: the full list of rules into which a standard JExocet can degenerate is not obvious. You may consider that some of them are not acceptable from a player's POV, even if "reversible".

In the other thread I said that, before I modified my spreadsheet, I found it easier to find JExocets before applying simple eliminations because I could distinguish givens from solved cells more easily. I'm wondering if you misinterpreted my meaning?

No, my remarks were very general.

[David P Bird]

The only thing I mean is, you need to use other rules, simpler than JExocet, to take advantage of this remaining evidence.
As a result, it would be queer to use JExocet prior to such simpler rules.

As I understand that I don't feel that it's strictly true, so probably we have crossed wires. To use an example:
Step N: we locate a JExocet pattern and eliminate the non-base digits from the target cells if there are any.
Step N+X: determines that a digit is locked in the base cells
Step N+X+1: uses the newly revealed inference that that digit must occupy exactly one of the targets to make a further elimination.

How would describe your solver's handling of that? From my POV we're using the proof of the JExocet pattern to make the make the final elimination, not some simpler sub-pattern.

Another thing we haven't discussed here that you may wish to consider in your general theory, is the nightmarish prospect of Almost Exotic Patterns.

Regarding using higher rated methods before exhausting all the simpler ones, it's quite usual for manual solvers to head for the methods that will make multiple eliminations first, to keep their solutions short.

[denis_berthier]

Step N: we locate a JExocet pattern and eliminate the non-base digits from the target cells if there are any.
Step N+X: determines that a digit is locked in the base cells
Step N+X+1: uses the newly revealed inference that that digit must occupy exactly one of the targets to make a further elimination.

OK, you know that base digit a must be in one of the two target cells, but you don't know in which of the two. Which further elimination does this allow in general?

Another thing we haven't discussed here that you may wish to consider in your general theory, is the nightmarish prospect of Almost Exotic Patterns.

I'm only marginally interested in exotic patterns (when effectively defined as real patterns). I can leave this nightmare to others.