The New Sudoku Players' Forum

[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.

[David P Bird]

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".

I missed this addition to your previous post. The embedded inferences in a JExocet pattern are something I'm trying to catalogue now, which I think should be described in the definition. I believe the pattern requirements are robust enough to identify a JE in whatever semi-resolved state it occurs, so that we can cite the pattern and then pull out the inference to be used in combination with a chain or pattern whenever we want.

Like a barrister, I also have a completely different line of argument, one I first used with Ruud probably in 2006. When we eliminate a candidate in a cell it becomes what he called a "Sudoku Truth", a fact that we've proved must be true once and which can be freely used without needing to be re-proved. We could therefore also recognise derived inferences from patterns as Sudoku Truths. If we did this however it would allow any net-based method to be used simply by logging the derived inferences available from each chain segment and progressively combining them into a linear stream. But, without malice, in my eyes you're already using a form of nets anyway!

This only goes to show that everything in respect to what is acceptable in Sudoku or not is arbitrary and reduces to a mattern of personal choice. We just have to live with the fact that others see things differently.

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?

This appeared as I was preparing this post. The simplest answer is that digit in question must be false in those cells seen by both targets, but the new strong link could also be used to link two chain segments to make a remote elimination.

[denis_berthier]

We could therefore also recognise derived inferences from patterns as Sudoku Truths.

If we accept this, every sudoku can be solved by whips[1].

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?

The simplest answer is that digit in question must be false in those cells seen by both targets, but the new strong link could also be used to link two chain segments to make a remote elimination.

But, apart from the first obvious case, this falls into the problem of uncontrolled inner patterns.

[eleven]

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

At this point you get a 1-digit pattern in 3 rows (or columns), which could be spotted also, when the "Exocet" was not yet born.

Step N+X+1: uses the newly revealed inference that that digit must occupy exactly one of the targets to make a further elimination.

So to remember an Exocet ist not needed to get the inference (though it is is nice, when you do).

[David P Bird]

Eleven OK so that wasn't a good example but there are others (similar to the one < here > ) where this type of simplification isn't possible.

What I was trying to do was simply understand Denis' viewpoint. But I'm afraid our meeting of minds failed miserably and it remains as much a mystery to me now as it was when I first responded.

[blue]

Maybe a better example of the kind of thing that Denis was talking about, would be if a JExocet existed, and then (somehow) you managed to fill one of the base or target cells.

[denis_berthier]

Blue is right, my answer didn't bear on David's specific example (which eleven has shown can be dealt with in simple ways). I was answering the general question I understood he was asking: what happens after we have applied the JE rule? Can we use it again later if part of its structure is altered?
In my view, there are four ways of doing this:

1) ad hoc: I have nothing to say about this;

2) using other independent resolution rules; as JE includes some quasi Fish part, it is likely that this part will sometimes appear to play some role in later eliminations; but it may be the case or not; as these rules exist independently of JE, the kind of information that may be useful about them is, how frequently they happen to be used after JE, based on the remaining JE part;

3) using specialised JE rules corresponding to different special cases allowing more eliminations (without going into details, I remember that daj had a list of such cases);

4) using follow-on rules with conditions including explicitly the JE pattern or part of it; it may be the case that such rules can be written; however, it may be a hard job to specify them; moreover, their complexity will be higher than JE; I can hardly imagine JE being included in some complex chain and David considering this as an "acceptable pattern".


After writing this, I wondered why this question appeared about JE.
For generic rules (whips, Subsets, ...), we have the feeling that the eliminations they specify exhaust their content.
For JE, what can be proven is apparently more than the elimination of the non-base digits: the two Target Cells must contain the same values as the two Base Cells; but the JE rule only says that the non-base digits can be eliminated. However, these eliminations do exhaust the content of the rule. To see this, consider what can happen to the Base Cells:
- if a digit is eliminated from one of them, either it is still present in the other and nothing is changed, or it disappears from both and we are left with a simpler JE that can eliminate it from the Target Cells (whether we have already used the original JE or not);*
- if a value is asserted for one of the Base Cells, this is the case just dealt with by eleven.**


(*) I wonder if this can happen in practice:
- apply JE4
- one of the digits is eliminated (by other rules) from both Base Cells
- apply J3 to eliminate this digit from the Target Cells

(**) this shows that when we accept JE, we must also accept Fish (but this was already obvious).

[denis_berthier]

everything in respect to what is acceptable in Sudoku or not is arbitrary and reduces to a mattern of personal choice.

I wouldn't equate "personal choice" with "arbitrary". A personal choice can be based on rational arguments. These may seem more or less convincing to other people, but this doesn't mean that the choice was arbitrary.

The "everything" also is too strong. To mention only the most obvious, I don't think anyone would consider that rules in SSTS are not acceptable.

We just have to live with the fact that others see things differently.

But, without malice, in my eyes you're already using a form of nets anyway!

Difficult to live with the fact?

I'm using "and branching" in braids (not in whips), which is a very natural thing; but I never use "or branching".