The New Sudoku Players' Forum

[David P Bird]

The purpose of this thread is to avoid taking either the "Exocet Pattern in Hardest Sudokus" or the "Pattern Based Classification of (hard) Puzzles" too far off-course, although our findings here may be pertinent to both.

The starting point is a repeat of the definition posted in < July 2012 >as the subject of (welcome) critique.

Denis (and possibly Blue) may I suggest that you re-post your queries and observations here for me to respond to.

----------------------------------------------------------------------


Junior Exocet Definition

An Exocet exists when it can be shown that a base cell pair and two target cells must reduce to holding the same two digits out of a set of 3 or 4 base cell candidates. This then allows any non-base candidates to be eliminated from the target cells.

As defined by champagne, the way this base-target cell equivalence is demonstrated is unrestricted and may for example use multiple templates. However analysis has shown that in most cases there are identifiable pattern elements that exist.

The Junior Exocet (JE) pattern restricts the base and target cells to a single band of boxes and the digits to those in the base cells.
The Junior Exocet Plus (JE+) extends this by also checking for other candidates that are locked in the cells of interest.

Pattern Element Map

Code: Select all

  *-------*-------*-------*
  | B B . | . . . | . . . |  B = Base Cells 
  | . . . | Q . . | R . . |   
  | . . . | Q . . | R . . |  Q = 1st Object Pair
  *-------*-------*-------*  R = 2nd Object Pair
  | . . S | S . . | S . . |       
  | . . S | S . . | S . . |  S = Cross-line Cells     
  | . . S | S . . | S . . |   
  *-------*-------*-------*  . = Any candidates
  | . . S | S . . | S . . | 
  | . . S | S . . | S . . |     
  | . . S | S . . | S . . |   
  *-------*-------*-------*

The different cell pairs occur in different boxes in the same band (the JE band).
In each object pair one cell will be a target cell and the other will be a companion cell that will reduce to a non-base candidate.
The three cross-lines intersect this band as shown, passing through the object cell pairs but not the base cell pair.

Requirements

1) The base cells must be restricted to a set of three or four digits (the base candidates)

2) Each object cell pair must only be capable of accommodating one base digit. This requires that they
a) have one cell that contains at least one base candidate (the target cell) and the other that contains none of them (the companion cell)
or
b) (JE+) must overlap an Almost Hidden Set that restricts the object cells to holding one base digit.
The simplest and most frequent situation will be when the AHS is an Almost Hidden Pair with a single extra digit locked in the object cells.

3) The two target cells must be forced to reduce to different base digits. This is satisfied when all occurrences of a digit (solved or not) in the "S", cross-line, cells are contained by two houses. A way to check this is to consider how many lines would be needed to cover all of them.

These diagrams show examples of the maximum number of occurrences of a digit in the "S" cells that can be contained by different combinations of two houses.

Code: Select all

                                    v           v                         v   
r4   . . \ | \ . . | \ . .      . . O | \ . . | O . .     . . \ | \ . . | O . .   
r5   . . O | O . . | O . . <    . . O | \ . . | O . .     . . O | O . . | O . . <   
r6   . . \ | \ . . | \ . .      . . O | \ . . | O . .     . . \ | \ . . | O . .   
r7   . . \ | \ . . | \ . .      . . O | \ . . | O . .     . . \ | \ . . | O . .   
r8   . . O | O . . | O . . <    . . O | \ . . | O . .     . . \ | \ . . | O . .   
r9   . . \ | \ . . | \ . .      . . O | \ . . | O . .     . . \ | \ . . | O . .
      2 Parallel Lines(I)        2 Parallel Lines(II)      2 Orthogonal Lines
         rows 5 & 8                 columns 3 & 7             row 5 & column 7

Eliminations

In JE patterns any non-base candidates can be eliminated from the target cells
In JE+ patterns (relying on condition 2b) the identity of the target cell won't be known. One object cell must eventually hold a base digit, and the other a candidate locked in the AHS, so any candidates that aren't in either set can be eliminated from both the object cells.

After a JE has been found

When the givens in the JE band are suitably placed, the inference that the two target cells must contain different base digits will often allow eliminations to be made in the target cell mini-lines.

When a base digit is known it will often form one of two Swordfish patterns and it will be possible to eliminate it from the fin cells common to both.

Short Proof

The columns of interest are c347 in the pattern map.

In the JE band the digits that are true in the base cells will be excluded from c3r123, c4r1 and c7r1.

From condition 2, the objects cells are limited to holding 2 truths at most for this digit pair. With no other openings in the JE band there therefore must be at least 4 truths in the 'S' cells to satisfy the three columns.

But condition 3 limits the number of truths that can be held in these cells to 4 at most, (2 for each digit).

Consequently each digit must be true twice in the 'S' cells and once in the object cells.

Additional Available from JE Patterns

Once a JE pattern has been found, additional follow-on inferences may also be available as listed here: < Additional JE Inferences >.

[edit] Link to additional inferences added.

[denis_berthier]

Hi David,

Very good idea to make a separate thread. Here is a copy of my post in the "Pattern Based Classification of (hard) Puzzles" thread.

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.

I've had a look at your definition of a JExocet.
At the level of the pattern of cells, all is OK for me. It perfectly specifies it, modulo any Sudoku grid isomorphism.
Probably because I didn't follow the topic, I'm less happy with the rest of your definition.

When I read

In each object pair one cell will be a target cell and the other will be a companion cell that will reduce to a non-base candidate.

I'm lost: one cell in the pair is the target cell BUT eliminations (reductions) are not done in the target, they are done in the companion ???? Usually, the target is what is eliminated.
Reading further on, I understand that you mean the following condition is satisfied:
In each object pair, one cell is considered as a target cell and the other as a companion cell; the companion cell DOES NOT contain any base candidate.
Right ?

When I read

2) Each object cell pair must only be capable of accommodating one base digit. This requires that they
a) have one cell that contains at least one base candidate (the target cell) and the other that contains none of them (the companion cell)

I'm lost again.
Again reading further on, I understand that you mean the following condition is satisfied:
Each target cell contains at least one base candidate (this does not exclude non-base candidates) and each companion cell contains no base candidate.
Right?


If you can confirm these two interpretations before I read further on, these two problems will have been only superficial - but it'd be worth to modify your definition so that such ambiguities are eliminated.

3) The two target cells must be forced to reduce to different base digits. This is satisfied when all occurrences of a digit (solved or not) in the "S", cross-line, cells are contained by two houses. A way to check this is to consider how many lines would be needed to cover all of them.

It's harder here. As I understand it, there may be different kinds of JEcocets, depending on how the target cells are "forced to reduce to different base digits". And you give only a particular case of how this can be done. Therefore I can't know the real extent of your definition.

[daj95376]

FWIW: This is from my notes. It includes examples of the JExocet chute in [band 1].

Code: Select all

    JExocet chute in [band 1]
    *-------*-------*-------*
    | B B . | . . . | . . . |  B = Base Cells
    | . . . | Q . . | R . . |
    | . . . | Q . . | R . . |  Q = 1st Target Pair
    *-------*-------*-------*  R = 2nd Target Pair
    | . . S | S . . | S . . |
    | . . S | S . . | S . . |  S = Cross-line Cells (outside JExocet chute)
    | . . S | S . . | S . . |
    *-------*-------*-------*  . = Any candidates
    | . . S | S . . | S . . |
    | . . S | S . . | S . . |
    | . . S | S . . | S . . |
    *-------*-------*-------*


The different cell pairs occur in different boxes in the same chute (the JExocet chute). The three cross-lines intercept this chute as shown, passing through the target cell pairs but not the base cell pair.

Conditions:

1) The base cells must be restricted to a set of three or four digits (the base candidates).

2) Target pairs must have one cell that contains at least one base candidate (the target cell), and the other cell contains none of the base candidates (the empty companion cell -- "T /" in the examples).

3) Outside the JExocet chute, no base digit should be capable of simultaneously occupying more than two of the cross-line cells.

This is satisfied when all occurrences of a digit in the cross-line cells can be covered by no more than two lines. (given/solved included ???)

An Exocet pattern satisfies conditions (1&2), and is used to identify base candidate values to analyze further.

A JExocet pattern satisfies all 3 conditions and proves that the two target cells will hold the same digits as the base pair. This allows any non-member candidates to be eliminated from the target cells.

Secondary eliminations are possible if additional non-candidate cells (/) are present.

Code: Select all

  JExocet w/aligned  target cells and no eliminations
 |-------------------+-------------------+-------------------|
 |  B1234  .  B1234  |    .    .    .    |    .    .    .    |
 |    .    .    .    |  T /    .    .    |  T /    .    .    |
 |    .    .    .    |  T1234  .    .    |  T1234  .    .    |
 |-------------------+-------------------+-------------------|


Code: Select all

  JExocet w/diagonal target cells and no eliminations
 |-------------------+-------------------+-------------------|
 |  B1234  .  B1234  |    .    .    .    |    .    .    .    |
 |    .    .    .    |  T1234  .    .    |  T /    .    .    |
 |    .    .    .    |  T /    .    .    |  T1234  .    .    |
 |-------------------+-------------------+-------------------|


Code: Select all

  JExocet w/aligned  target cells and    eliminations
 |-------------------+-------------------+-------------------|
 | B1234   .  B1234  |    .    .    .    |    .    .    .    |
 |    .    .    .    |  T /    .    .    |  T /    .    .    |
 |    .    .    .    |  T12345 .    .    |  T12346 .    .    |
 |-------------------+-------------------+-------------------|
  r3c4<>5, r3c7<>6


Code: Select all

  JExocet w/diagonal target cells and    eliminations
 |-------------------+-------------------+-------------------|
 |  B1234  .  B1234  |    .    .    .    |    .    .    .    |
 |    .    .    .    |  T12345 .    .    |  T /    .    .    |
 |    .    .    .    |  T /    .    .    |  T12346 .    .    |
 |-------------------+-------------------+-------------------|
  r2c4<>5, r3c7<>6


Code: Select all

  JExocet w/diagonal target cells and 1x secondary dependency
 |-------------------+-------------------+-------------------|
 |  B1234  .  B1234  |    .    .    .    |    .    .    .    |
 |    .    .    .    |  T12345 /  S1237  |  T /    .    .    |
 |    .    .    .    |  T /    .    .    |  T12346 .    .    |
 |-------------------+-------------------+-------------------|
  r2c4<>5, r3c7<>6  ;  r2c6<>7, r3c7<>4


Code: Select all

  JExocet w/diagonal target cells and 2x secondary dependency
 |-------------------+-------------------+-------------------|
 |  B1234  .  B1234  |    .    .    .    |    .    .    .    |
 |    .    .    .    |  T12345 /  S1237  |  T /    .    .    |
 |    .    .    .    |  T /    .    .    |  T12346 /  S2348  |
 |-------------------+-------------------+-------------------|
  r2c4<>5, r3c7<>6  ;  r2c6<>7, r3c7<>4  ;  r2c4<>1, r3c9<>8


[David P Bird]

Denis, thanks for your feedback. It's always difficult to appreciate what problems others may face when reading ones work.

In each object pair one cell will be a target cell and the other will be a companion cell that will reduce to a non-base candidate.

I'm lost: one cell in the pair is the target cell BUT eliminations (reductions) are not done in the target, they are done in the companion ???? Usually, the target is what is eliminated.
Reading further on, I understand that you mean the following condition is satisfied:
In each object pair, one cell is considered as a target cell and the other as a companion cell; the companion cell DOES NOT contain any base candidate.
Right ?

The problems seem to arise because I've combined two scenarios:
1) A plain vanilla JE where the companion cells don’t hold any base candidates and any non-base candidates are eliminated from the target cells as you suppose. (The companion cells contain givens more often than not.)

2) The JE+ version where a pair of object cells is covered by an AHS with locked candidates that aren't members of the base set. In this case one cell must hold a base candidate and the other must hold one of the locked candidates, but which way round that will be is uncertain. However any candidates that aren't in the base set or locked in the AHS can be eliminated from both the cells in the pair.

Here the second pair of object cells could either be as in the vanilla pattern with the same eliminations or theoretically could be covered by a further AHS.

What's common to all these cases is that the intersections between the JE band and the cross lines can only hold a two instances of the true candidates in the base cells.

3) The two target cells must be forced to reduce to different base digits. This is satisfied when all occurrences of a digit (solved or not) in the "S", cross-line, cells are contained by two houses. A way to check this is to consider how many lines would be needed to cover all of them.

It's harder here. As I understand it, there may be different kinds of JEcocets, depending on how the target cells are "forced to reduce to different base digits". And you give only a particular case of how this can be done. Therefore I can't know the real extent of your definition.

The three cross-lines must hold 6 truths for the two true base candidates. When the S cells are restricted to holding four truths, two for each digit, the JE band must then hold one truth for each and the eliminations are proved. Effectively the S cells must hold 2/3 rds of a Swordfish for each digit (which may be degenerate).

Considering the problems you've had with my presentation it may be better to start by defining the basic JE pattern in full and providing it's proof before introducing the variations provided by the JE+ version. (There are also twin JExocets where the pattern occurs twice in a band which are very powerful.)

The "Exocet Pattern in Hardest Sudokus" thread has many (widely scattered) examples which could be brought into the presentation. I was in favour of splitting out the JExocet material but ronk as moderator wouldn’t agree.

Finally

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.

Hold onto that feeling and consider your readers too!

[blue]

Hi champagne,

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,
(...)

Yes, I've seen that definition.

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.

Maybe you understood this, but It was the part about the necessity to check permutations, that concerned me.
I guess my view is that if it's necessary to use a computer to check permutations, to validate a pattern, then you might just as well use a brute force solver to solve the entire puzzle, and just quote the solution, and list the puzzle itself as the justifying "pattern".
I know that's an extreme view, but ...

For 16x16 Sudoku, the number of permtuatations for a single digit on an empty grid, is (4!)^8 = 110,075,314,176 -- much larger than the (3!)^6 = 46,656 for 9x9 Sudoku. Already things have gotten out of hand, and even a verification by computer seems probematic -- finding the patterns in the first place, even more so. For JExocet (and its obvious extensions), things don't get that bad, that fast.

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.

Yes, I remember seeing the examples.
I was following the discussions in this forum.

Best Regards,
Blue.

[blue]

Hi David,

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.

These diagrams show examples of the maximum number of occurrences of a digit in the "S" cells that can be contained by different combinations of two houses.

Code: Select all

                                    v           v                         v   
r4   . . \ | \ . . | \ . .      . . O | \ . . | O . .     . . \ | \ . . | O . .   
r5   . . O | O . . | O . . <    . . O | \ . . | O . .     . . O | O . . | O . . <   
r6   . . \ | \ . . | \ . .      . . O | \ . . | O . .     . . \ | \ . . | O . .   
r7   . . \ | \ . . | \ . .      . . O | \ . . | O . .     . . \ | \ . . | O . .   
r8   . . O | O . . | O . . <    . . O | \ . . | O . .     . . \ | \ . . | O . .   
r9   . . \ | \ . . | \ . .      . . O | \ . . | O . .     . . \ | \ . . | O . .
      2 Parallel Lines(I)        2 Parallel Lines(II)      2 Orthogonal Lines
         rows 5 & 8                 columns 3 & 7             row 5 & column 7

For what it's worth, this is the part of the pattern spec, that I didn't especially favor.
The requirement that the candidates in the S cells can be covered by "2 lines", is consise.
It's somewhat obcure, though, about what needs to be argued next, to justify the eliminations.

Edit (added):

I'm probably being too critical here. I do understand the "truth counting" argument. I don't tend to think in those kinds of terms, though. I'm more at home with base\cover arguments. My point below, about the "extra" eliminations that are possible in some cases, is probably worth noting. You could get the same facts, using truth counting arguments, but you'ld need a different argument for each of the 3 cases, and it seems that in the arguments, you would ignore columns that have thier candidates covered by vertical lines, and focus on other the columns, and the horizontal lines (if any).

I would rather have seen something like this: (ronk too, I think).

For each base digit, one of these is true:
• The candidates in the S cells are restricted to two rows, across all columns -- swordfish related.
• In two of the columns, the candidates in the S cells are restricted to one row -- x-wing related.
• In one of the columns, none of the S cells contains a candidate -- singles related.

[ For the 3rd option, the column would be one of the target cell columns, since if were true about the remaining column, then a line-box elimination, would have eliminated the digit from the base cells. ]

Doing it like that, it's easy/easier to see that for base digits where only one or two of the columns are relevant, if the other column/columns contain a target cell, then that (base) digit can also be eliminated in that cell. A similar thing happens for the JE+ extension.

If I'm remembering right, daj95376 (or perhaps ronk) also noted a 4th option, similar to the "singles related" option above: if one of the base cells contained the digit, it would force a "box single" for the digit, in a particular target cell. There's an "extra" base digit elimination in the other target cell, in that case too.

My two cents.

Best Regards,
Blue.

[champagne]

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.

Maybe you understood this, but It was the part about the necessity to check permutations, that concerned me.
I guess my view is that if it's necessary to use a computer to check permutations, to validate a pattern, then you might just as well use a brute force solver to solve the entire puzzle, and just quote the solution, and list the puzzle itself as the justifying "pattern".
I know that's an extreme view, but ...

For 16x16 Sudoku, the number of permtuatations for a single digit on an empty grid, is (4!)^8 = 110,075,314,176 -- much larger than the (3!)^6 = 46,656 for 9x9 Sudoku. Already things have gotten out of hand, and even a verification by computer seems probematic -- finding the patterns in the first place, even more so. For JExocet (and its obvious extensions), things don't get that bad, that fast.

Hi Blue,
I am not sure I catch your point.

For me, the pattern is like a theorem. My code looks for the pattern and does not do any permutation (in that process).

I have seen your discussion with David. I must confess that I worked on my understanding of David's view, but not on David's diagrams. I added in the code upon request the identification of downgraded forms of the pattern, this seems to be the point currently discussed.

Regarding the permutations issue, looking for non JEXOCETS patterns some comments

1) I never worked on more than 9x9 cells.
2) With our experience, we can have a good result (9x9) working in a band/stack with the following restrictions
a) the base must be a mini row or mini column
b) the target is spread in the 2 other boxes
c) base + target cover all the rows/columns of the band/stack.
3) the digits of the base are not given in the band/stack
4) setting the base to true and the targets to false lead to a reasonable number of permutations

[denis_berthier]

2) Target pairs must have one cell that contains at least one base candidate (the target cell), and the other cell contains none of the base candidates (the empty companion cell -- "T /" in the examples).

Thanks, it confirms my interpretations and it answers my first two questions.

3) Outside the JExocet chute, no base digit should be capable of simultaneously occupying more than two of the cross-line cells.
This is satisfied when all occurrences of a digit in the cross-line cells can be covered by no more than two lines. (given/solved included ???)

I'm still not happy with this, as it remains open to many interpretations.

[daj95376]

3) Outside the JExocet chute, no base digit should be capable of simultaneously occupying more than two of the cross-line cells.
This is satisfied when all occurrences of a digit in the cross-line cells can be covered by no more than two lines. (given/solved included ???)

I'm still not happy with this, as it remains open to many interpretations.

Consider DPB's original grid and this wording:

Code: Select all

  *-------*-------*-------*
  | B B . | . . . | . . . |  B = Base Cells
  | . . . | Q . . | R . . |
  | . . . | Q . . | R . . |  Q = 1st Object Pair
  *-------*-------*-------*  R = 2nd Object Pair
  | . . S | S . . | S . . |
  | . . S | S . . | S . . |  S = Cross-line Cells
  | . . S | S . . | S . . |
  *-------*-------*-------*  . = Any candidates
  | . . S | S . . | S . . |
  | . . S | S . . | S . . |
  | . . S | S . . | S . . |
  *-------*-------*-------*


*) There is the row containing the base cells in a mini-unit
*) There are the columns containing the target-pair cells (separate stacks) -- QQ and RR
*) there is the column that does not intersect a base cell in [stack 1]

*) There is a maximum of two rows that cover all occupied S cells for the digit/value


There are additional scenarios that aren't covered by JExocet. Here's an example using a puzzle from champagne's list of hardest puzzles.

Code: Select all

98.7.....6..85......4..3...7...6.8...5.9.......6..8.3..6......2..1..24.........13

 +---------------------------------------------------------------------------------+
 |  9       8       235     |  7       124     146     |  12356   2456     1456    |
 |  6       1237    237     |  8       5       149     |  12379   2479     1479    |
 |  125     127     4       |  126     129     3       |  125679 R56789-2 R56789-1 |
 |--------------------------+--------------------------+---------------------------|
 |  7       12349   239     |  12345   6       145     |  8       2459     1459    |
 |  12348   5       238     |  9       12347   147     |  1267    2467     1467    |
 |  124     1249    6       |  1245    1247    8       |  12579  Q3       Q579-14  |
 |--------------------------+--------------------------+---------------------------|
 |  3458    6       35789   |  1345    134789  14579   | B579     5789     2       |
 |  358     379     1       |  356     3789    2       |  4       56789    56789   |
 |  2458    2479    25789   |  456     4789    45679   | B5679    1        3       |
 +---------------------------------------------------------------------------------+
 # 177 eliminations remain

 ### -5679- qExocet   Base = r79c7   Target = r6c9,(SL=8)r3c89


Both target-pair cells for RR contain <5679>. However, there is also a strong link on <8> that forces one of the cells to (eventually) not contain any of the base values. The eliminations are as shown.

[blue]

Hi champagne,

For me, the pattern is like a theorem. My code looks for the pattern and does not do any permutation (in that process).

(...)

Regarding the permutations issue, looking for non JEXOCETS patterns some comments

1) I never worked on more than 9x9 cells.
2) With our experience, we can have a good result (9x9) working in a band/stack with the following restrictions
a) the base must be a mini row or mini column
b) the target is spread in the 2 other boxes
c) base + target cover all the rows/columns of the band/stack.
3) the digits of the base are not given in the band/stack
4) setting the base to true and the targets to false lead to a reasonable number of permutations

For this part:

My code looks for the pattern and does not do any permutation (in that process).

I'm assuming that you mean it's looking for "prospective" base and target pairs, that satisfy the conditions in (2) and (3).
I also have some code that looks for base and target pairs that satisfy the "exocet property".
My code doesn't put any restrictions on the base or target cells, other that one target cell can't see both base cells.
I got a very nice speedup, by solving the puzzle beforehand, and looking only at cases where the base and target pairs, actually contain the same pair of (distinct) digits in the solution.
As you say, for the vast majority of the cases in you list of hardest puzzles, they can be explained as being associated with instances of the JExocet pattern. Most of them, I think, were not the actual base and target cells for a JExocet, but the puzzles did contain a JExocet, and they could be explained as follow on consequences of the existing JExocet.

4) setting the base to true and the targets to false lead to a reasonable number of permutations

This number is actually zero, is it not ?
Do you mean a reasonable number of "partially competed permutations, that are obviously impossible to complete" ?

It's that number, that grows very quickly (I believe), as the size of the puzzle is increased.
It's the need to use "brute force" code, that is guaranteed to find a completion, when one exists, and that can run for a very long time before answering "no", when one doesn't exist ... that I object to.
For the JExocet patterns, there is no need to run such code, to verify that the exocet property is satisfied. The constraints that exist after forcing a base cell candidate to true and the candidate(s) in the target cells to false, are easily seen to be unsatisfiable, since they contain an embedded Nx(N-1) base/cover sub-problem, with N equal to 3,2 or 1.

Why should any of that be important ? If you were presenting me with a solution path for a puzzle, in an attempt to convince me that it only had one solution, and I was trying to verify its correctness, and at one point, you said "these cells satisfy the exocet property, and so these candidates can be eliminated", and I said: "OK, I buy that the candidates can be eliminated if the exocet property is satisfied -- prove to me that it's satisfied". At that point, the amount of text (or talk) that you would need to provide, could be quite large in the general case. On the other hand, if you knew that a JExocet pattern was associated with the cells, you could say: "Do you know about the unsatisfiability of Nx(N-1) base cover problems, and thier connection with the exocet property ? Yes ? OK, you can see the Nx(N-1) problems here, here and here" ... pointing out the instance for each base cell digit. I would be convinced, and we would move on.

Does what I said, really matter ? From the other side, you could say: "Look at this program that I wrote, to check for valid permutations. Do you belive that it functions correctly ? Yes ? When I run it against this PM state, for each digit, it answers back that there are no valid permutations after the relevant items have been forced. Run it yourself, if you don't believe me."

It's difficult to know what to say at that point. If I don't run the program, then I haven't really verified your solution path. If I do run it, then every execution step, somehow becomes part of the verification, and the number of execution steps, is on the order of the size of the "large amount of text (or talk)" that we would hope to avoid.

I'll leave it at that, I guess, with this addition:

Above, here, I wrote: "It's that number, that grows very quickly (I believe), as the size of the puzzle is increased." That number has some relation to the size of the "large amount of text" that I mentioned. If anyone could show that the number was bounded by a polynomial in the size of the puzzle, then I'm sure it would be of great interest to the mathemeticians that study the "(P = NP)" conjecture. It's one of the great unsolved problems in mathematics/logic. That's why I mentioned the 16x16 puzzles. The numbers (3!)^6 and (4!)^8, that I mentioned, are upper bounds for the number -- although not the best upper bounds. The general formula (n!)^(2*n), where 'n' is the (1D) box size for the puzzles, grows faster than any polynomial in N, the row size, or any polynomial in N*N.

Best Regards,
Blue.

[David P Bird]

Revisiting this work from 10 months ago in the light of my recent exchange with Denis, it strikes me that we can consider JExocet patterns as the combination of two inference patterns, one concerned with the JE band, and one concerned with "partial fish sets" in the other two bands. This may then suggest how a "partial fish" analysis can be combined with other inference patterns, perhaps with a different number of columns.

Now my prejudices will begin to show! I consider that counting the truths that are required to be much simpler than delving into complex base and cover sets. I also have no qualms about including givens and solved cells in the counts. It saves an awful lot of work itemising multiple possibilities. The concept of counting covering lines came from Ruud as a means of helping find fish patterns. However that doesn’t work when the houses can be boxes, so I've changed it to counting the containing houses, but basically the approach is still the same.

My mind isn't completely closed though and if someone is prepared to present this material in terms of base and cover sets it would make an interesting comparison.

Blue, I wasn't prepared to accept daj's extra case into the definition as it pushed the boundary of what constitutes a recognisable pattern too far IMO. However I don't dispute the logic.

So here is a cockshy description of "partial fish" for critique. I'm running out of terms to describe different pattern elements so any suggestions in that direction could be helpful.

Partial Fish Sets

Code: Select all

  *-------*-------*-------*
  | . . . | . . . | . . . |
  | . . . | . . . | . . . |
  | . . . | . . . | . . . |
  *-------*-------*-------*
  | . . 6 | 6 . . | / . . |
  | . . / | / . . | / . . |
  | . . / | / . . | / . . |
  *-------*-------*-------*
  | . . 6 | 6 . . | 6 . . |
  | . . / | / . . | / . . |
  | . . / | / . . | / . . |
  *-------*-------*-------*

A single partial fish consists of the instances of a subject digit (6) occurring in the intersections between with two parallel bands of boxes (tiers 2 & 3) and N orthogonal lines (columns 3, 4, & 7). The maximum number of truths these cells can hold will then determine the minimum number that must be held in the remaining cells in the third band (tier 1, columns 347).

Using the same set of cells for a set of different subject digits will then determine the minimum number of truths the third band must hold in order for each digit to be true in each if the N lines.

Degenerate partial fish occur when one of the fish cells is already a single either by being a given or having been solved. However, by treating these as being the same as any other candidates, a common approach can be taken whatever the circumstances. A way to determine the maximum number of truths that can be held for a partial fish is to check the minimum number of houses needed to contain the occupied cells.

Code: Select all

                                       
r4   . . / | / . . | / . .      . . / | / . . | 6 . .     . . / | / . . | 6 . .   
r5   . . 6 | 6 . . | / . .      . . / | / . . | 6 . .     . . 6 | 6 . . | 6 . .   
r6   . . / | / . . | / . .      . . / | / . . | 6 . .     . . / | / . . | 6 . .
     ------*-------*------      ------*-------*------     ------*-------*-------     
r7   . . / | / . . | / . .      . . / | / . . | / . .     . . / | / . . | / . .   
r8   . . / | 6 . . | 6 . .      . . 6 | / . . | 6 . .     . . / | / . . | / . .   
r9   . . / | / . . | / . .      . . 6 | / . . | / . .     . . / | / . . | / . .
Contained by:  rows 5 & 8           columns 3 & 7              row 5 & box 6

These three examples have the maximum truth counts of 2 as shown by their containing houses used. In the third band these three lines must therefore hold at least one truth for this digit.

Working with a set of partial fish, when the available cells in the third band matches the minimum number needed to satisfy the line constraints, an elimination pattern has been found. The eliminations will be:
1) Any non-member digits in the cells that must be occupied in the third band
2) External member digits occurring in one of the containing houses used for the digit concerned (fin cells).
3) Internal member digits contained by more than one of the houses concerned (endo-fin cells)

Code: Select all

    *-------*-------*--------*
r4  | * * 6 | 6 * / | * 6* * |   Three covering houses
r5  | . . / | / . / | . /  . |   r4, r7 & b9 
r6  | . . / | / . / | . /  . |
    *-------*-------*--------*   * = Potential Eliminations
r7  | * * 6 | 6 * 6 | * /  * |   (fin cells)
r8  | . . / | / . / | * /  * |
r9  | . . / | / . / | * 6  * |
    *-------*-------*--------*

This diagram gives an example of a 4-line partial fish that can hold 3 truths at most, and shows the eliminations that would result for this digit if it was necessary for these cells to hold that maximum. Note that if r4c8 were true then these cells could only hold one other truth in r7 – an endo-fin.

When several digits all provide the same individual maximum truth counts for the same set of partial fish cells, its possible to use any subset of them to balance the number of available cells in the third band. In a typical JExocet pattern there are two available cells in the JExocet band which can be filled using any pairing picked from four digits. In this case the fin eliminations won't be available until the precise pairing is known, and in the JExocet band only those digits that aren't one of the four possible ones can be eliminated from the available cells.

[daj95376]

[Edit: Withdrawn]

[denis_berthier]

This is a copy of (part of) David's introductory post, with the slight modifications I would bring to it in order to eliminate any ambiguity.
I deal only with JExocet, leaving the JE+ extension and daj's additional eliminations for later.
I hope we can agree on a final definition, at least for this core case.
Remark: I replaced "base candidate" by "base digit" because what we generally call a candidate is a <cell, digit> pair.


JEXOCET DEFINITION

Conditions on the Pattern of Cells

Code: Select all

  *-------*-------*-------*
  | B B . | . . . | . . . |  B = Base Cell Pair, in the Base Row and the Base Block/Box
  | . . . | Q . . | R . . |   
  | . . . | Q . . | R . . |  Q = 1st Object Cell Pair
  *-------*-------*-------*  R = 2nd Object Cell Pair
  | . . S | S . . | S . . |       
  | . . S | S . . | S . . |  S = Cross-line Cells     
  | . . S | S . . | S . . |   
  *-------*-------*-------*  . = Any candidates (including base digits)
  | . . S | S . . | S . . | 
  | . . S | S . . | S . . |     
  | . . S | S . . | S . . |   
  *-------*-------*-------*

The Base Cell Pair (B) and the two Object Cell Pairs (Q and R) occur in three different blocks/boxes in the same band (the JE band).
The three "cross-lines" intersect this band as shown, passing through the Object Cell Pairs but not through the Base Cells.


Conditions on candidates

1) No base cell is decided.
Each base cell may have up to 4 candidates, but together, they contain exactly 3 or 4 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 digits)
Companion cells contain no base digit

3) For each base digit, there are two units/houses containing/covering all its occurrences in the S cells (be it as a candidate or as a decided value).



JEXOCET RULE

Theorem: if a JExocet is present in some resolution state, then its non-base digits can be eliminated from its target cells.


PROOF OF THE JEXOCET RULE

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 "cross-lines" containing the S cells.
But condition 3 entails that each of a and b can be the value of at most two S cells. Therefore (as neither a nor b can be in the Base Row or the Base Block anywhere outside the B Cells) each of a and b must also be the value of one of the Q or one of the R cells.
By condition 2, each of a and b must therefore be the value of the Q or the R target cell.
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.



Remark: the cardinality of the set of base digits didn't play any role in the proof.

[denis_berthier]

If you were presenting me with a solution path for a puzzle, in an attempt to convince me that it only had one solution, and I was trying to verify its correctness, and at one point, you said "these cells satisfy the exocet property, and so these candidates can be eliminated", and I said: "OK, I buy that the candidates can be eliminated if the exocet property is satisfied -- prove to me that it's satisfied". At that point, the amount of text (or talk) that you would need to provide, could be quite large in the general case. On the other hand, if you knew that a JExocet pattern was associated with the cells, you could say: "Do you know about the unsatisfiability of Nx(N-1) base cover problems, and thier connection with the exocet property ? Yes ? OK, you can see the Nx(N-1) problems here, here and here" ... pointing out the instance for each base cell digit. I would be convinced, and we would move on.

Does what I said, really matter ? From the other side, you could say: "Look at this program that I wrote, to check for valid permutations. Do you belive that it functions correctly ? Yes ? When I run it against this PM state, for each digit, it answers back that there are no valid permutations after the relevant items have been forced. Run it yourself, if you don't believe me."
It's difficult to know what to say at that point. If I don't run the program, then I haven't really verified your solution path. If I do run it, then every execution step, somehow becomes part of the verification, and the number of execution steps, is on the order of the size of the "large amount of text (or talk)" that we would hope to avoid.

I think there's a fundamental difference between the two situations.

In the JExocet case (as for any resolution rule), you can refer to a "mathematical" theorem (the JExocet rule), proven once and for all. The JExocet pattern is defined in a purely factual, descriptive, non procedural, way - as in any resolution rule. You only have to exhibit it in the current PM and you get your eliminations for free.

In the Exocet case, you have to check all the relevant truth assignments in each particular situation. There's no generality, nothing that you can state once and for all (no elimination that would result only from the presence of this partial pattern). What there is is a partial pattern indicating the possibility that there might be something interesting to look for; elsewhere, I called this a heuristic. I don't mean that it cannot be useful (in addition to being the starting point for defining real full patterns), but it is certainly not what I would call a pattern, as long as, in addition to seeing it, you need some computer or some hard brain work to make complicated calculations.


By saying that the difference is fundamental, I mean in particular that it is not mainly one of complexity, as you seem to be suggesting (though it is not totally unrelated to it and I find your comments on complexity interesting).
When you refer to a theorem, it doesn't matter how hard its proof may have been. Whether the Fermat-Wiles theorem was really proven by Fermat in just a little more space than the margin of his Diophantus book (very unlikely) or whether it needed about three and a half centuries and a few thousand pages to be proven, it is no less true (provided that Wiles' proof is sound and you accept the Axiom of Choice).
Moreover, accepting it as true doesn't depend only on whether you are able to read the proof or not (only a few tens of people are currently able to read it). There is much more scientific "knowledge" that we accept as such (recalling that "knowledge" in science is always relative) on the basis of its global acceptance by the scientific community than we could ever check by ourselves. After all, I've never seen my DNA but I have little doubt about having some (it'd be harder for me to think that DNA is an invention of CIA for some obscure goal).
Of course, such questions don't arise for JExocet (or for any known resolution rule) - the proof is almost obvious, even without any knowledge of cover sets.


This discussion arose here, but it is also relevant to logel's tentative definition of a general "elimination pattern".

[champagne]

Hi blue,

Hi champagne,

For me, the pattern is like a theorem. My code looks for the pattern and does not do any permutation (in that process).

For this part:

My code looks for the pattern and does not do any permutation (in that process).

I have the feeling that you are mixing the 2 cases;
I don't use the permutations when looking for JEXOCETS. Reversely, I have a permutation process to detect non JEXOCETS patterns.

I got a very nice speedup, by solving the puzzle beforehand, and looking only at cases where the base and target pairs, actually contain the same pair of (distinct) digits in the solution.

very good idea.I keep it in mind and will do the same. My first reaction would be "what about twin exocets"

4) setting the base to true and the targets to false lead to a reasonable number of permutations

This number is actually zero, is it not ?
Do you mean a reasonable number of "partially competed permutations, that are obviously impossible to complete" ?

The correct wording would be

if it is not the searched pattern you can stop at the first valid permutation
and as you say , if it is the pattern you have a reasonable number of "partially competed permutations",

For the remaining part of the post, as I never entered (and don't plane to do in the near future) higher sizes I have no comment

regards

champagne