Can a JExocet be seen as a Subset or a gSubset? - classification of JExocet
blue wrote:I would be curious if you can place the JExocet patterns in the "chains" or "subset" category.
Now that the JExocet definition is clear, I can try to tackle this question.
I'll use the definition and notations here http://forum.enjoysudoku.com/jexocet-pattern-defintion-t31133-12.html. There may appear extensions of this core pattern, but that shouldn't change the following remarks.
Let p (= 3 or 4) be the number of base digits.
1) Can a JExocet be considered as a Subset (or a gSubset)?
Suppose we try to see the JExocet as a Subset or as a gSubset (according to my general definitions in "Pattern-Based Constraint Satisfaction - PBCS").
Then it is somehow obvious that the following 2+3p [= 11 or 14] CSP-variables/2D-cells must be part of the pattern:
- the two B rc-cells
- the 3p cn-cells: for each of the 3 S columns ci and for each of the p base digits nj, the cn-cell cinj
At this point, the situation is rather simple, as these 2+3p CSP-variables are pairwise disjoint.
It is also obvious that the following must be part of the transversal sets:
- for each of the base digits nj, the rn constraint r1nj (r1 is the row holding the B cells)
- for each of the base digits ni and for each of the two rows ri and r'i in which it can be present in the S cells, the rn constraint rini / r'ini.
This makes up 3p transversal sets.
We also have to deal with the Q and R pairs. As long as we are concerned only with base digits, we can discard the companion cells. There remains only one possibility, i.e. taking two more transversal sets: the two rc constraints defined by the two target cells. As the complement of the intersections of these constraints with the base CSP-variables is exactly the set of non-base digits in the target cells, it would be OK for the targets of a Subset or gSubset.
We now have 2+3p transversal sets and they are pairwise disjoint.
Is therefore everything OK for a Subset[2+3p]?
Nope. The base candidates that, by the general JExocet definition, are allowed in the intersection of block b1 and column c3 are not yet covered by these transversal sets.
Note: in a first version of this post, I had forgotten that there may be base digits in the intersection of block b1 and column 3. But Blue (many thanks to him) pointed it out in a PM.
If this was the only problem, we could consider a special case and try to conclude that
- any JExocet with 3 or 4 base digits and no base digit in the intersection of the base block and the S column intersecting it can be considered as a Subset[11 or 14].
By replacing the p rn-constraints r1nj by p bn-constraints b1nj, we would get similarly:
- any JExocet with 3 or 4 base digits and no base digit in the intersection of the base row and the two S columns not intersecting the base block can be considered as a Subset[11 or 14].
(I don't know if such special cases have already been considered.)
But even this doesn't work. Indeed, if it worked, the Subset rule would also eliminate (in the first case) all the base digits in the first row non-S columns outside the B cells, which is obviously incorrect.
At this point, we must also notice that the condition of having no base digit in the companion cells has not yet been taken into account. We should therefore introduce two more CSP-variables corresponding to these cells. But then, we would also have to introduce (9-p) or 2(9-p) rn transversal sets [depending on whether they are in the same row or nor] to cover them. Finally, we would get many more transversal sets than CSP-variables.
I'm fully aware that this is not a full proof that a JExocet cannot be seen as a Subset or as a gSubset, but if there is some smarter way of proving it, it still eludes me. As I'm a little lazy about exotic patterns on Sundays, it's enough to deter me from looking longer for a proof that a JExocet can be considered as a Subset or as a gSubset.
To answer the second part of Blue's question, trying to see a JExocet as some kind of chain doesn't seem much more promising.
2) Classification of the JExocet
The above analysis isn't completely negative and that's why I posted it. Even though I couldn't prove that a JExocet is a Subset or a gSubset, the analysis shows that this pattern involves (at least) 13 or 16 CSP-variables.
As a result, in a systematic search for patterns of increasing size, JExocets would appear very late.
As the complexity of a systematic search for Subsets (and a fortiori for general patterns) increases very fast with their size (much faster than for whips or braids), it is probably out of reach of ordinary computers and JExocets can only be found if patterns with special properties (instead of all patterns) are looked for.
Finally, I wonder:
1) what's the easiest known puzzle (say, with smallest SER) having a JExocet? Did anyone already investigate this?
2) has anyone tried to express JExocet in Allan's formalism? What's the base set? Can any fixed "rank" be assigned to it?
3) how would it appear in logel's approach?
