JExocet Pattern Definition

Advanced methods and approaches for solving Sudoku puzzles

Re: Frequencies

Postby denis_berthier » Tue May 21, 2013 10:47 am

blue wrote:
denis_berthier wrote:If my interpretation of all your results is correct, considering JExocets (types A B C D) on the one hand and all Exocets (types A B C D G H K O) on the other hand, something strange appears with the percentages JExocets/Exocets:
(...)

One note: I don't think that David will like calling them all JExocets. (Maybe with the "types", it's OK ?)

OK

denis_berthier wrote:You have slight error in your calculations: (43479+2960+25+825) is 47289
It's a correct interpretation of the results, though.

I'll correct the error. Thanks.

blue wrote:
denis_berthier wrote:I wonder how much multiple Exocets/JExocets in a puzzle overlap. This is only part of the question but (if this is not too much work) it would be interesting to have a similar table for the number of different eliminations.

I'm not exactly sure what you're asking, but I'm sure it wouldn't be too much work.
Counting candidates eliminated by "some" type (A B C D) exocet, and only counting them once, then extending the count to include eliminations from the remaining exocets ?
Can you suggest a table layout (or layouts) ?


I was thinking of a layout similar to that for Exocets, but the last column may not be the sum of the other ones and rows X (resp. Y, Z) may not be the sums of rows ABCD (resp. GHKO ABCDGHKO) (I keep the JExocet data only for formatting purposes):

Code: Select all
       size                           Eliminations
      +------------+-------------------------+
      |  3       4 |     5      6     7    8 |
  +---+------------+-------------------------+
t | A |  6   52869 |     7      -     -    - |  52882
y | B |  -    2066 |  1655   3937   452   45 |   8155
p | C |  1   47413 |    20      -     -    - |  47434
e | D |  2    5335 | 14987   1177     -    - |  21501
  | X |  xx    xxx | xxxxx   xxxx     -    - |  xxxxx
  +---+------------+-------------------------+
  | G |  -     185 |  9811   5574   164    - |  15734
  | H |  -     135 |    29      -     -    - |    164
  | K |  1    4905 |  4587   6642   135    1 |  16271
  | O | 27      40 |    69      1     -    - |    137
  | Y | yy     yyy | yyyyy   yyyy     -    - |  yyyyyy
  +---+------------+-------------------------+
    Z   zz  zzzzzz   zzzzz  zzzzz   zzz   zz   zzzzzz

In each cell of the table, an elimination is counted only once.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: JExocet Pattern Defintion

Postby David P Bird » Tue May 21, 2013 12:18 pm

Hi Blue, and thanks for your comprehensive response.
Blue wrote:On the other hand, if you include the "box extensions", then the JExocet pattern can be "broken" for a digit that uses the box extension ... leaving a situation that doesn't fit the 'utilising the JE inferences when a pattern is found' characterization.

There was an example in the other exocet thread. Here's another(?) one from in champagne's list:
Code: Select all
#3049 1.34............36.8..2.4............7..4.5.....6.1..8..2.9...4.9.....5.8....79..

+------------------------+---------------------+-----------------------+
| 1       256     3      | 4      5678   5689  | 278     2789    2579  |
| 24579   245     4579   | 15789  1578   589   | 1278    3       6     |
| 5679    8       5679   | 13579  2      3569  | 4       179     1579  |
+------------------------+---------------------+-----------------------+
| 234569  123456  145689 | 35789  3578   23589 | 12367   124679  12379 |
| 2369    7       1689   | 389    4      2389  | 5       1269    1239  |
| 23459   2345    459    | 6      357    1     | 237     2479    8     |
+------------------------+---------------------+-----------------------+
| 3567    1356*    2     | 1358   9      3568  | 13678   1678    4     |
| 367     9       167    | 123-8  136-8  4     | 123678  5       1237  |
| 8       13456   1456   | 1235   1356   7     | 9       126(B)  123(B)|
+------------------------+---------------------+-----------------------+
          S                       S              S

base: r9c89, targets: r8c45, * cell: r7c2

That's great! However it's a real fly in my ointment as the search method I use excludes givens in the JE band! This means I would only consider a base digit set of (136) for tier 3 in this puzzle and wouldn't find your pattern.
you wrote:
I'll leave your frequency analysis post for later study, but my knee-jerk reaction is to wonder if patterns with more than 4 base digits are within the scope of a manual solver to find.

My opinion would be biased -- I don't think the size 4 cases are "within the scope".

I manage it by limiting the base digit sets I investigate that way and using conditional cell colouring on a helper spreadsheet.

However, it would be possible to find by inspecting the partial fish patterns for (136) in tiers 1 & 2 where columns 457 produce a hit. I think that would be too laborious for a player to run through 27 possible column combinations, but it would be quick on a computer. This might also possibly find other exotic elimination patterns using partial fish.

This will need some pondering time on my part.

Thank you very much for your other examples too which I'll look at later today.

David

[Edit - corrected an oversight regarding the number of column combinations to check]
Last edited by David P Bird on Tue May 21, 2013 9:51 pm, edited 1 time in total.
David P Bird
2010 Supporter
 
Posts: 1043
Joined: 16 September 2008
Location: Middle England

Re: JExocet Pattern Defintion

Postby logel » Tue May 21, 2013 3:11 pm

Hi David
David P Bird wrote:I have tried but failed to produce a precise definition of a Sudoku pattern. At every attempt, wherever I tried to draw a boundary line, I found I was either excluding acceptable patterns or including unacceptable ones. Consequently now I just resort to the spirit of the intention.


David P Bird wrote:However you and I have different goals, for you it's an efficient computer solver and for me it's logical constructs that can be applied by someone with sufficient patience to look for them in favour of guessing or using brute force. What defeats me on practical grounds, may be possible for you given a large amount of memory to hold a catalogue of pre-analysed patterns.

Our goal are not so different, only the methods are. We are looking for efficient solution paths. Large pre-analysed patterns are clearly not possible without computer support. The type of pre-analysed tables I use have the nice property that they remain valid with local updates from subsequent eliminations. So I have a test bed framework for various elimination sequences. Nevertheless any result should be presented in a human readable form.
David P Bird wrote:Note I use the term 'guessing' where you have used the phrase "assuming the potential targets true and performing a limited number of eliminations". Trial and Error, like assuming a unique solution, is something that you're either prepared to employ or not. For me it's equivalent to cheating at patience. But it's a wide church and there's room for both of us.

I got the impression that the term guessing usually appears in discussions about distinguishing guessing from no-guessing, where the latter is regarded as superior. But its just two sides of the same coin with no substantial difference. Any result of guessing + T&E can be transposed into a direct form and vice versa.

This is my comment to your fundamental remarks, the following returns to the topic of this thread. Btw these comments have very little connection to pattern permutations (my other thread).

After analysing a couple of Exocet patterns, I identified a common kernel structure. As I did not follow all Exocet discussions, I can't say if its something really new. The kernel structure is maybe part of a larger class than JExocet.
Code: Select all
     A1==========A2==========A3
     |           |           |
     B1==========B2==========B3
     |           |           |
     |           |           |
 R1==R2==RX  S1==S2==SX  T1==T2==TX
 |           |           |
 |___________|___________|
             |
            TGT

RX NAND SX, RX NAND TX, SX NAND TX

My view on patterns is generally more abstract and similar to Denis view. So I do not refer to cells etc, but rather to lines containing the remaining candidates related to a constraint. So A,B,R,S,T can be lines of any type (cell, row, col, box). Exocet seem to consider A,B of cell type and R,S,T of row/col type only, but the above structure works with any types. The index numbers on the lines do not refer to symbol numbers but to line members. RX,SX,TX denotes one or more candidates.
The pattern kernel consists of 5 base lines. The lines A,B must be of the same type, A must contain 3 candidates, the other 3 or 2. The lines R,S,T must have at least 3 candidates, where one is connected to the target and another one connected to A,B in the way shown in the diagram. The target(s) are false if the X-candidates are indirectly linked pairwise (NAND).
This is what I called rule fragment in a previous post, because the details of the indirect links are left open. So you may have a number of sub-rules.
The elimination is easy to prove. Assuming TGT = true kills R1+S1+T1. The secondary assumption of RX = true kills SX+TX by NAND, activates S2+T2 and creates a contradiction in A+B. The inverse assumption of RX = false activates R2 and killing A1+B1. A23+B23 are killing S2+T2 with the pair rule, activating SX+TX and contradicting the indirect link. This is sufficient because of the pattern symmetry.
So all patterns containing this kernel delete the target. The JExocet seems to be more special with a second set of base lines X,Y,Z connected to A+B.

To verify such pattern in a PM pracitically, I would
    Set the target neighbors R1+R2+R3 = false
    Set RX = true and TX = true, subsequent steps must create a contradiction, confirming RX NAND TX.
    The same with RX+SX and SX+TX.
A kernel with four (or five) candidates in A,B can be constructed in the same way, adding C (or D). Any sub-rules need only to assure the NAND terms for verification.
Its obvious that all patterns based on such kernel are "exotic" in the sense prohibiting a classification with Denis rule hierarchy. The pattern kernel contains inevitable branches that you cannot bypass by braids, g-braids, not even by S2-braids.
User avatar
logel
 
Posts: 57
Joined: 29 April 2012
Location: Germany

Re: Frequencies

Postby champagne » Tue May 21, 2013 4:00 pm

Hi Blue,

May be one more comment on that point

champagne wrote:For me the worst we are doing with computers is to produce these long, boring and indigestible paths using chains nets.
for a manual player, such paths are just not acceptable;
generally speaking, the uniqueness brings much shorter paths. with exocets and the "abi loop", the contrast is still bigger.


for sure uniqueness makes it easier (and somehow evident usually with 3 digits), but in many cases you can find the contradiction applying a more classical net chain to each of the potential 6 or 12 scenarios (depending on the number of digits) it is just harder and longer.

It remains easier to analyse scenarios with the exocet implications than to look for chains nets
champagne
2017 Supporter
 
Posts: 7334
Joined: 02 August 2007
Location: France Brittany

Re: JExocet Pattern Defintion

Postby David P Bird » Tue May 21, 2013 11:38 pm

Hi again Blue,

I've now looked at your two 5-digit JExocets and find that, unlike your other example, my search method will locate them as none of the 5 digits appear as givens in the JE band. This stirred memories – which are rather dangerous to rely on, as recent experience has shown, – that when I've explored bands with no givens for 5 digits in the past I have found 4-digit JE patterns on occasion.

For manual solving, restricting the search to 'absent givens' in a band is a huge saving in comparison to checking all digit sets in two cells in a mini-line. This is what IMO just about brings JE patterns into the realm of what can be considered to be a 'recognisable pattern'. However what you've shown is that this will miss a small(?) number of patterns where a base digit appears as a given in the band. What's more, you've also shown that in those circumstances the existing acceptance criteria will reject the cases covered by your 'box-extension' sub-pattern.

Personally I'm happy with a method that finds > 95% of all instances of the pattern for a manageable amount of effort, when to catch 100% of them would increase that effort enormously. I accept though that this view won’t necessarily be shared by those coding a solving program. I've therefore come to think the best way to handle this is to start by writing up the simpler approach, and then to follow this up by describing the circumstances when some patterns may be missed and the measures needed to overcome the problem.

It also occurs to me that the more digits that are included in the digit sets to explore, the fewer eliminations there will be, and all that will remain is the inference that the target cells must contain different digits. If then ABI loops are considered unacceptable for whatever reason, it could be a lot of work for a few weak inferences.

David
David P Bird
2010 Supporter
 
Posts: 1043
Joined: 16 September 2008
Location: Middle England

Re: JExocet Pattern Defintion

Postby blue » Wed May 22, 2013 2:14 am

Hi David,

David P Bird wrote:For manual solving, restricting the search to 'absent givens' in a band is a huge saving in comparison to checking all digit sets in two cells in a mini-line. This is what IMO just about brings JE patterns into the realm of what can be considered to be a 'recognisable pattern'. However what you've shown is that this will miss a small(?) number of patterns where a base digit appears as a given in the band. What's more, you've also shown that in those circumstances the existing acceptance criteria will reject the cases covered by your 'box-extension' sub-pattern.

I see -- about the realm accessable to a manual solver.
For the "type D pattern", not all of the "box-extension" instances will be missed. The the type B, maybe so.

Personally I'm happy with a method that finds > 95% of all instances of the pattern for a manageable amount of effort, when to catch 100% of them would increase that effort enormously. I accept though that this view won’t necessarily be shared by those coding a solving program. I've therefore come to think the best way to handle this is to start by writing up the simpler approach, and then to follow this up by describing the circumstances when some patterns may be missed and the measures needed to overcome the problem.

I don't have a problem with your search criteria missing some instances.
I wouldn't write up a description of the pattern(s), that includes heuristic search criteria as part of the pattern (if that's what you meant). I'ld describe the pattern first, and note the ways that the time spent in searching, can be greatly reduced by using various heuristic criteria (and that it may cause an small but acceptable percentage of the patterns to be missed).

It also occurs to me that the more digits that are included in the digit sets to explore, the fewer eliminations there will be, and all that will remain is the inference that the target cells must contain different digits. If then ABI loops are considered unacceptable for whatever reason, it could be a lot of work for a few weak inferences.

Right. I'm not advocating a search for instances with a large number of base digits.
I just included them for completeness, and to satisfy curiosities.
blue
 
Posts: 975
Joined: 11 March 2013

Re: Frequencies

Postby blue » Wed May 22, 2013 3:22 am

Hi champagne,

champagne wrote:
champagne wrote:For me the worst we are doing with computers is to produce these long, boring and indigestible paths using chains nets.
for a manual player, such paths are just not acceptable;
generally speaking, the uniqueness brings much shorter paths. with exocets and the "abi loop", the contrast is still bigger.


for sure uniqueness makes it easier (and somehow evident usually with 3 digits), but in many cases you can find the contradiction applying a more classical net chain to each of the potential 6 or 12 scenarios (depending on the number of digits) it is just harder and longer.

It remains easier to analyse scenarios with the exocet implications than to look for chains nets

To be honest (getting back to the "what to do after you've found an exocet" topic), I was hoping (but probably not expecting) to see something 1) more elegant than a case by case analysis of the different base scenarios, and in the end 2) not involving uniqueness.

For some background:

The sudoku (programming) problems that I've been interested in, have usually involved producing potentially valid puzzles, and checking them by brute force, for whether they have a unique solution (if any).

A case by case analysis (of anything), reminds me too much of brute force.
I don't like SE's "Aligned Pair/Triple Exclusion", for example.

About methods relying on uniqueness: When I see a solution path presented, I like to think of it as an "elegant proof" of the thing that the brute force solver has discovered -- that there is just one solution, and "this is it". Using techniques that rely on a uniqueness assumption, makes that impossible.

I do understand that "elegant", is a term that's difficult to use for a solution path that uses complex chains and nets.
Still it's a "proof", and it's more elegant than a simple trace of the brute force solver's actions.

I've probably said too much, and I don't want to get into a debate (with anyone).
To each his own. Live and let live. Etc., etc.

Regards,
Blue.
blue
 
Posts: 975
Joined: 11 March 2013

Re: Grey Zone

Postby blue » Wed May 22, 2013 4:21 am

champagne wrote:I started the generation of puzzles with no filter using the data base of potential hardest. It could be interesting to give the criteria for our "grey zone";

I don't have anything to suggest, unfortunately -- other than the obvious, that they shouldn't be solvable with singles, line-box, naked/hidden subsets, and basic fish.

Well, no ...

Including single digit template eliminations in the list, would cover "grouped candidate" and finned fish eliminations too.
I have template code, but nothing guaranteed to find all (complex, single digit) fish eliminations.
That may be going too far, though.

To avoid puzzles that are too complicated, it would be nice if they were solvable with SE techniques that exclude the "Dynamic (+)" class. Can you arrange for that with 'skfr' ?

Denis may have some ideas.

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

Re: JExocet Pattern Defintion

Postby denis_berthier » Wed May 22, 2013 4:29 am

Hi logel,

logel wrote:After analysing a couple of Exocet patterns, I identified a common kernel structure. As I did not follow all Exocet discussions, I can't say if its something really new. The kernel structure is maybe part of a larger class than JExocet.
Code: Select all
     A1==========A2==========A3
     |           |           |
     B1==========B2==========B3
     |           |           |
     |           |           |
 R1==R2==RX  S1==S2==SX  T1==T2==TX
 |           |           |
 |___________|___________|
             |
            TGT

RX NAND SX, RX NAND TX, SX NAND TX

My view on patterns is generally more abstract and similar to Denis view. So I do not refer to cells etc, but rather to lines containing the remaining candidates related to a constraint. So A,B,R,S,T can be lines of any type (cell, row, col, box).

I and others had warned you against the use of the word "line". Here, it makes this paragraph totally illegible in the context of this thread.
What David calls a "line" is a row or a column; by contrast he calls "house" a row, a column or a block/box; "house" is also called "unit" by many people.
Moreover, what you call a line is indeed not at all what you are saying here "cell, row, col, box"; it is what I have always called a 2D-cell, i.e. an rc-, rn-, cn- or bn- cell in the Sudoku context; in the context of the general CSP, I call it a CSP-variable.


I won't comment your elimination structure (my fingers refuse to write "pattern") in detail, but the following seems to introduce arbitrary restrictions (A, B are the base cells):
logel wrote:The pattern kernel consists of 5 base lines. The lines A,B must be of the same type,

Why in your view of things should they be of the same type?
logel wrote:A must contain 3 candidates, the other 3 or 2.

I don't see why the case A={a, b} and B={b, c} should be excluded in a J3-Exocet, i.e. why the 3 base digits should have to be present in one of the base cells. Probably, David or Blue have counter-examples.



logel wrote:The target(s) are false if the X-candidates are indirectly linked pairwise (NAND).
This is what I called rule fragment in a previous post, because the details of the indirect links are left open. So you may have a number of sub-rules.

An easy way of turning the whole thing into a real pattern P is to require the existence of a bibraid for each pair of X-candidates. Bibraids are a pattern-based way of specifying the existence of a nand relation (of course, it doesn't cover all the nand cases).
You might then say that I have no choice but accepting this bibraided-JExocet. So, OK, at the cost of restricting it, I have turned your thing into a pattern, admittedly an ugly one but a pattern anyway. However, this is not the end of all.
In my approach, this pattern P would be assigned some length, at least 5 + the sum of the lengths of all these bibraids (5 for the already defined CSP variables). In the simplest first approach, I would have no reason for looking for such a pattern before any smaller one. Needless to say, I'd probably almost never look for it.


With this elimination structure, you seem to be in the same position as champagne with his exocet procedure about 3 years ago: you need to find useful special cases. But there's one more thing you need to show: it covers the already known JExocet cases.
It may be interesting if you find some real reasonable pattern with base cells that are not rc-cells.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: Grey Zone

Postby denis_berthier » Wed May 22, 2013 5:08 am

blue wrote:
champagne wrote:I started the generation of puzzles with no filter using the data base of potential hardest. It could be interesting to give the criteria for our "grey zone";
[...]
Denis may have some ideas.

I think this would better be discussed in the "grey zone" thread.
There I wrote SER between 9.0 and 10.5. Whether SER or skfr is used doesn't really matter; they are almost the same and they have the same fundamental theoretical vices; but we don't need any precise bounds. (skfr has another vice for me: I can't compile it on my Mac).

I also wrote that it is currently impossible to generate unbiased collections of puzzles in this zone - or even collections with known bias (as with the controlled-bias generator).
Any collection assembled from the Patterns Game or starting from the "potential hardest" would probably be extremely biased.
I think the best approach would be eleven's tamagotchi, but nobody (including me) seems to be interested in investing much (computer and brain) time in generating puzzles in this zone.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: JExocet Pattern Defintion

Postby daj95376 » Wed May 22, 2013 7:15 am

blue wrote:Before I do, I want to introduce a new kind of JExocet-like pattern.
The basic idea behind why they are exocets in the general sense, will be familiar to daj95376, from his posts that note "equivalences" between cell values that can be observed (and exploited), once a JExocet has been found.

The basic pattern/patterns, look like this:

Code: Select all
 B B . | .  . .  | . . .          B B . | .  . .  | . . .
 . . . | T1 \ T2 | \ . .          . . . | \  \ T2 | \ . .
 . . . | \  . .  | * . .          . . . | T1 . .  | * . .
-------+---------+-------        -------+---------+-------
 . . S | S  . .  | S . .          . . S | S  . .  | S . .
 . . S | S  . .  | S . .          . . S | S  . .  | S . .
 . . S | S  . .  | S . .          . . S | S  . .  | S . .
-------+---------+-------        -------+---------+-------
 . . S | S  . .  | S . .          . . S | S  . .  | S . .
 . . S | S  . .  | S . .          . . S | S  . .  | S . .
 . . S | S  . .  | S . .          . . S | S  . .  | S . .

The base cells and fish columns, are the same as for a normal JExocet.
The normal JExocet conditions are satisfied.
The T1 cell and the * cell, are normal exocet targets.
The \ cells, are supposed to be deviod of base digit candidates -- filled cells, usually.
It's the \ cell at r2c5 (in the diagrams), that's the essential ingredient.

It's possible for two patterns like this, to accompany a JExocet -- one for each target cell stack.

From the presence of the JExocet, we know that the T1 and * cells will contain the values that appear in the B cells.
From the \ at r2c5, we can see that the value in the * cell, will be forced into T2 (in box 2).
Danny would write (T2==*), as a "secondary equivalence", and note that there are bonus (base digit) eliminations in the T2 and * cells, when they don't have candidates for the same sets of base digits. Base digit candidates in T2, that don't occur in *, can be eliminated, and vica-versa.

Note: The * cell, can be filled, and the pattern is still valid. When that's the case, the * cell (must) contain a base digit, and we end up knowing what value to put in T2.

Like with JExocets, there is a possible extension, involving "box truths" in the box containing the target cells. If a base digit has candidates in box 2 (in this case), only in T1,T2, and the row containing the base cells, then if the digit appeared in a base cell, it would be forced into one of {T1,T2}, via the box constraint. When that's true, we can give that digit a "pass" on the usual requirement for the S cells/columns.

I don't have a problem if the digit is forced into T1. However, if the digit is forced into T2, then the digit must be a candidate in the (*) cell as well for an exocet to exist. That's the problem with the grid below. Neither T1 nor the (*) cell contain <2> as a candidate.

Code: Select all
#3049 1.34............36.8..2.4............7..4.5.....6.1..8..2.9...4.9.....5.8....79..

+------------------------+---------------------+-----------------------+
| 1       256     3      | 4      5678   5689  | 278     2789    2579  |
| 24579   245     4579   | 15789  1578   589   | 1278    3       6     |
| 5679    8       5679   | 13579  2      3569  | 4       179     1579  |
+------------------------+---------------------+-----------------------+
| 234569  123456  145689 | 35789  3578   23589 | 12367   124679  12379 |
| 2369    7       1689   | 389    4      2389  | 5       1269    1239  |
| 23459   2345    459    | 6      357    1     | 237     2479    8     |
+------------------------+---------------------+-----------------------+
| 3567    1356*    2     | 1358   9      3568  | 13678   1678    4     |
| 367     9       167    | 123-8  136-8  4     | 123678  5       1237  |
| 8       13456   1456   | 1235   1356   7     | 9       126(B)  123(B)|
+------------------------+---------------------+-----------------------+
          S                       S              S

base: r9c89, targets: r8c45, * cell: r7c2

Still, a very interesting grid with overlapping constraints!
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: JExocet Pattern Defintion

Postby blue » Wed May 22, 2013 7:57 am

Hi Danny,

Code: Select all
#3049 1.34............36.8..2.4............7..4.5.....6.1..8..2.9...4.9.....5.8....79..

+------------------------+---------------------+-----------------------+
| 1       256     3      | 4      5678   5689  | 278     2789    2579  |
| 24579   245     4579   | 15789  1578   589   | 1278    3       6     |
| 5679    8       5679   | 13579  2      3569  | 4       179     1579  |
+------------------------+---------------------+-----------------------+
| 234569  123456  145689 | 35789  3578   23589 | 12367   124679  12379 |
| 2369    7       1689   | 389    4      2389  | 5       1269    1239  |
| 23459   2345    459    | 6      357    1     | 237     2479    8     |
+------------------------+---------------------+-----------------------+
| 3567    1356*    2     | 1358   9      3568  | 13678   1678    4     |
| 367     9       167    | 123-8  136-8  4     | 123678  5       1237  |
| 8       13456   1456   | 1235   1356   7     | 9       126(B)  123(B)|
+------------------------+---------------------+-----------------------+
          S                       S              S

base: r9c89, targets: r8c45, * cell: r7c2

I saw an earlier version, too, of you last post, mentioning this puzzle.

This was meant to be an example where there is definitely not a JExocet present (with T1 and * as targets), but where with T1 and T2 as targets, there is an "exocet" in the more general sense. [ In fact, in the solution, T1 and *, both contain a 6, and the base cells contain 2 and 6. ]

For digits 136, there is usual JExocet argument (involving the S columns), that would force the digit to one of {T1,*}, if it appeared in a base cell. If it's in T1, that's fine, otherwise it isn't in T1, but it's in the * cell, and with the 4 present in r8c6, it would be forced to the T2 cell in box 8.

For the digit 2, the argument is different, and doesn't depend on the * cell or the S columns: if it was present in a base cell, then in box 8, it could only go in one of {T1,T2}. (For this puzzle, T1 isn't an option).

All in all, then, any value placed in a base cell, is forced to one of {T1,T2}, and we have an "exocet" in the general sense.
blue
 
Posts: 975
Joined: 11 March 2013

Re: JExocet Pattern Defintion

Postby denis_berthier » Wed May 22, 2013 9:20 am

denis_berthier wrote:
logel wrote:After analysing a couple of Exocet patterns, I identified a common kernel structure.
Code: Select all
     A1==========A2==========A3
     |           |           |
     B1==========B2==========B3
     |           |           |
     |           |           |
 R1==R2==RX  S1==S2==SX  T1==T2==TX
 |           |           |
 |___________|___________|
             |
            TGT

RX NAND SX, RX NAND TX, SX NAND TX

The target(s) are false if the X-candidates are indirectly linked pairwise (NAND).
This is what I called rule fragment in a previous post, because the details of the indirect links are left open. So you may have a number of sub-rules.

An easy way of turning the whole thing into a real pattern P is to require the existence of a bibraid for each pair of X-candidates. [...]
In my approach, this pattern P would be assigned some length, at least 5 + the sum of the lengths of all these bibraids (5 for the already defined CSP variables).


Things are still worse than what I wrote above:
1) you got confused by your "line" vocabulary and your elimination structure doesn't correctly represent the basic Exocet data: you don't need R, S and T "lines" (corresponding to the three columns in David's initial post). But, for each column ci = c1, c2, c3 and each base digit nj = n1, n2, n3, you need a cinj CSP-variable (2D-cell), as explained in my post here: http://forum.enjoysudoku.com/pattern-based-classification-of-hard-puzzles-t30493-69.html
2) As a result, you also need much more bibraids and the size of the "bibraided-J3-Exocet" would be 4 + 3p + the sum of the lengths of all these bibraids. (p=3 in the present case).
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: JExocet Pattern Defintion

Postby David P Bird » Wed May 22, 2013 9:55 am

Hi Logel
you wrote:I got the impression that the term guessing usually appears in discussions about distinguishing guessing from no-guessing, where the latter is regarded as superior. But its just two sides of the same coin with no substantial difference. Any result of guessing + T&E can be transposed into a direct form and vice versa.

I don't want resurrect a further debate on this old topic again but there is a further aspect that I would like to present to you. For player a steam of consequences dependent on a single sided assumption (or 'guess') that a candidate is (say) true, is far less useful than one based on a double sided assumption (or 'observation') that stems from a candidate either being true or false. A sensible player will therefore start by only investigating possibilities where both outcomes can be followed.

Regarding your representation of the JExocet core structure, I'm a bit out of my depth. I can appreciate that methods that apply in one data space can also be used in another. But JExocet patterns can be viewed as combining two sub-patterns, one in the main band of boxes, and the other for the intersections of 3 rows or columns in the other two bands. I therefore have difficulty in seeing how that combination can be translated into other data spaces.

As Denis has already responded to you I'll leave this discussion to the two of you as I don't have the mathematical vocabulary to engage in the debate.

David
David P Bird
2010 Supporter
 
Posts: 1043
Joined: 16 September 2008
Location: Middle England

Re: JExocet Pattern Defintion

Postby blue » Wed May 22, 2013 8:57 pm

Here is a diagram showing how logel's "rule fragment" fits into a general 3-digit JExocet pattern.

Code: Select all
    n   r b    r  r      r b    r  r    r b    r  r   n

c   R1==R2=====Rx=Ry
    |   |      |  |
c   S1===================S2=====Sx=Sy
    |   |      |  |      |      |  |
c   T1==================================T2=====Tx=Ty
    :   |      |  |      |      |  |    |      |  |
    |   |      |  |      |      |  |    |      |  |
n   :   A1===============A2=============A3     |  |
    |   | \    |  |      | \    |  |    | \    |  |
c   :   D2=DZ==Dx=Dy     E2=EZ==Ex=Ey   F2=FZ==Fx=Fy
    |   | /    |  |      | /    |  |    | /    |  |
n   :   B1===============B2=============B3     |  |
    |   |      |  |      |      |  |    |      |  |
    :   |      |  |      |      |  |    |      |  |
c   |   U2=====Ux=Uy==================================U1
    :                    |      |  |    |      |  |   |
c   |                    V2=====Vx=Vy=================V1
    :                                   |      |  |   |
c   |                                   W2=====Wx=Wy==W1
    :                                                 :
    |                                                 |
    :                                                 :
   TGT1                                   (optional) TGT2


logel's RX,SX and TX, have been expanded to {Rx,Ry}, {Sx,Sy} and {Tx,Ty}.

Using Alan Barker's "truth" and "link" sets vocabulary ...

The letters, n,r,c,b along the top and on the left, show the type of "truth" or "link" set associated with the columns and rows,
for the JExocet orientation that we've been talking about (r,c and b for row, column and box, n for cell).
The top 3 rows, are column truths for one of the "target" S column.
The bottom 3 rows, are column truths for the other "target" S column.
The center row holds the 3 column truths for the S column that intersects the base cell box.
The rows on either side of that, are the base cell truths.
The left and right columns, are the cell links for the two target cells.
The columns connecting the x,y pairs, are the "covering rows" for candidates in the lower (S) section.

Note: in real instances of the pattern, it's typical for some of the candidates missing (e.g. an Rx present, but no Ry).
Also, the diagram shows some facts that are probably not necessary for the/an argument to succeed -- in particular, the fact that there are weak links between pairs in {R2,D2,U2}, {S2,E2,V2} and {T2,F2,W2}.

The missing "bit of detail", in his description, are how the rest of the diagram -- the D,E,F,U,V,W truths, and thier links into each other and the candidates in the A,B,R,S,T truths -- conspire to make it impossible to have any of these situations occuring in a solution:

  • TGT1 and one of {Rx,Ry} and one of {Sx,Sy} true
  • TGT1 and one of {Rx,Ry} and one of {Tx,Ty} true
  • TGT1 and one of {Sx,Sy} and one of {Tx,Ty} true
He leaves TGT1 out, above. I'm not sure whether he's assuming that its presence is implied, or saying that it doesn't need to be there.

Minor edit: to correct grammar, and add a "3" in the description what's in the center row in the diagram.
Last edited by blue on Thu May 23, 2013 7:21 pm, edited 1 time in total.
blue
 
Posts: 975
Joined: 11 March 2013

PreviousNext

Return to Advanced solving techniques