JExocet Pattern Definition

Advanced methods and approaches for solving Sudoku puzzles

Re: JExocet Pattern Defintion

Postby David P Bird » Mon Aug 04, 2014 12:47 pm

For later arrivals see <Leren's post> on a puzzle thread which triggered this discussion.

Leren & Danny, I have now found the cause of my <false retraction> which came from my failure to realise that the posted grid that provided the assumed counter example contained an unsound JExocet.

I take a very simple truth counting approach which does away with having to consider degenerate cases - I don't care if any truth has already been proved or not, it still gets counted!

To walk through my proof:
Code: Select all
   CL1   CL2    CL3
. . S | . S  . | S  . .     . = Any digit
. . S | . S  . | S  . .   a,b = base digits
. . S | . S  . | S  . .     * = a & b eliminations in sight of base cells
------+--------+-------   
. . S | . S  . | S  . .     S = Crossline cells in the other bands 
. . S | . S  . | S  . .   
. . S | . S  . | S  . .     P = 2 Cells restricted to 1 truth for (ab)
------+--------+-------     Q = 2 Cells restricted to 1 truth for (ab)
a b * | * *  * | *  * *
* * * | . P  . | Q  . .     
* * * | . P  . | Q  . .

1. The base cells, must hold two of the base digits (ab) which will makes them false in JExocet band,crossline1 (b7c3)
2. By selection, crosslines 2 & 3 can each only hold one of the base digits in the JExocet band - in the target cells (r89c5 & r89c7)
3. This forces the parallel bands,crosslines123 to hold at least 4 truths for (a) & (b) (in the S cells, as the 3 cross lines must each hold one truth for each digit)
4. If these cells are restricted to a single truth for (a) they must therefore hold three truths for (b).
5. When no selection for (b) allows this, the base cells can't hold (a) and it can be eliminated from them.
( (a)would be true in b14c3 and in the two target cells, (b) could be true in two S cells but then couldn’t be assigned in the 3rd cross line)

I've been trying to re-absorb the various contributions made in this thread, some of which are very powerful but depend on specific extra conditions. This makes organising the material awkward to say the least. My thoughts at the moment are to create a hierarchy of JExocet patterns which reflects both the amount of effort it needs to confirm their different conditions exist, and how frequently they occur. Each level of the hierarchy will then need theorems to prove the inferences they provide. I'm afraid that will have to wait a while as I have other priorities as I hope you shall soon see.

DAJ wrote:Hopefully, I'm not covering old territory!

I'm afraid you are and have just discovered a gap in your coding.
David P Bird
2010 Supporter
 
Posts: 935
Joined: 16 September 2008
Location: Middle England

Re: JExocet Pattern Defintion

Postby Leren » Mon Aug 04, 2014 11:39 pm

Hi David, some comments on your proof.

It may simplify your argument to note that if a & b are in the base cells then there must be exactly 1 truth for a and 1 truth for b in the S cells of CL1.

Since a has only one truth in the S cells of CL1, CL2 and CL3 there are no truths for a in the S cells of CL2 and CL3. This means that a must occupy one of the P cells and one of the Q cells.

This proves that a JExocet or an Exocet in the more general sense, cannot exist if a is True in a base cell, however one may exist for fewer base cell digits (say b, c and possibly d) if a can be removed from the base cells.

The above also also shows that there are 2 truths for b in the S cells of CL2 and CL3.

You can thus prove that a can be removed from the base cells proving that no selection for any other base cell digit b, c (and possibly d) can allow 2 truths in the S cells of CL2 and CL3 whilst a occupies a base cell.

Leren
Leren
 
Posts: 2618
Joined: 03 June 2012

Re: JExocet Pattern Defintion

Postby Leren » Tue Aug 05, 2014 12:54 am

Code: Select all
                 v                v                v
*-----------------------------------------------------------------------*
| 23789  56     789-2   | 346789 789    3469    | 2789   45     1       |
| 1      56     789     | 46     789    2       | 789    3      45      |
| 23789  237    4       | 3789   5      1       | 6      29     2789    |
|-----------------------+-----------------------+-----------------------|
| 4      8      1       | 239    6      39      | 5      7      239     |
| 237    237    5       | 239    1      8       | 4      29     6       |
| 23     9      6       | 5      4      7       | 1      8      23      |
|-----------------------+-----------------------+-----------------------|
|B789-2 B7-2    3       | 1      2789   46      | 2789   456    45      |
| 5      1      2789    | 46789 T789-2  469     | 3      46     2789    |
| 6      4      2789    | 789    3      5       |T789-2  1      2789    |
*-----------------------------------------------------------------------*
                 ^               ^                 ^

FWIW I noticed an additional elimination in the Dobrichev Exocet puzzle - r1c3 <> 2. All 4 base digits occur in the cross lines in r12c357, so when 2 has been eliminated from the base cells r12c3 must eventually contain the two True base digits.

For this puzzle this followed trivially anyway, because r89c12 contained, no 2's. However, if they had contained 2's the elimination would still be valid and you could then also eliminate any 2's in r89c12.

Leren
Leren
 
Posts: 2618
Joined: 03 June 2012

Re: JExocet Pattern Defintion

Postby David P Bird » Tue Aug 05, 2014 7:21 am

Leren wrote:It may simplify your argument to note ...

Leren, yes, all your points are sound. However, a similar truth counting approach is used to prove that the two target cells must contain different base digits, and I was considering how the explanation of this situation could be tacked onto that.

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

Re: JExocet Pattern Defintion

Postby Leren » Tue Aug 05, 2014 11:50 am

Hi David, The following diagrams are an attempt at a proof of why, for 2 base digits that have 2 Truths in the S cells, exactly one of each such digit must end up in a Target cell.

Code: Select all
   CL1   CL2    CL3          CL1   CL2    CL3          CL1   CL2    CL3          CL1   CL2    CL3
. . A | . A  . | A  . .   . . A | . A  . | a  . .   . . A | . a  . | a  . .   . . A | . A  . | a  . .
. . \ | . \  . | \  . .   . . \ | . \  . | \  . .   . . \ | . \  . | \  . .   . . \ | . \  . | \  . .
. . B | . b  . | b  . .   . . B | . b  . | b  . .   . . B | . b  . | b  . .   . . B | . b  . | B  . .
------+--------+-------   ------+--------+-------   ------+--------+-------   ------+--------+-------
. . a | . A  . | A  . .   . . a | . A  . | A  . .   . . a | . A  . | A  . .   . . a | . A  . | A  . .
. . b | . B  . | B  . .   . . b | . B  . | B  . .   . . b | . B  . | B  . .   . . b | . B  . | B  . .
. . \ | . \  . | \  . .   . . \ | . \  . | \  . .   . . \ | . \  . | \  . .   . . \ | . \  . | \  . .
------+--------+-------   ------+--------+-------   ------+--------+-------   ------+--------+-------
a b . | . AB . | AB . .   a b . | . AB . | AB . .   a b . | . AB . | AB . .   a b . | . AB . | AB . .
. . . | . a  . | \  . .   . . . | . a  . | \  . .   . . . | . c  . | \  . .   . . . | . a  . | \  . . 
. . . | . \  . | a  . .   . . . | . \  . | c  . .   . . . | . \  . | c  . .   . . . | . \  . | b  . .


In the first diagram I've assumed that one digit, a, occupies both target cells. There are 2 contradictions here : 1. a is forced to only have 1 truth in the S cells - contradicting the assumption and 2. b can only be in r3c57 which forces at least one of CL2 or CL3 to be void of b. In the second and third diagrams I've assumed that a third digit c occupies one or both of the Target cells. In the second diagram b is void in CL2 and/or CL3 and in the third diagram both a and b are void in CL2 and/or CL3. The fourth diagram has a in one target cell and b in the other, and as far as I can tell there is no contradiction, although I think there is some restriction on how many of the a's and b's can be missing in the S cells.

So this is my version of the similar Truth counting approach for two 2 Truth digits you alluded to.

Since the first diagram effectively has no a's in Row 1 in the crosslines, it also shows that mixing a single truth digit with a 2 truth digit results in a contradiction, which can't be avoided.

Looking at various combinations of 1 and 2 Truth digits I've come up with the following table

Code: Select all
                ------------------------------------------------------------------------------------------
                | Base Digit 1 | Base Digit 2 |  Target Cell Contents  |           Contradiction         |
----------------------------------------------------------------------------------------------------------
S Cells Truths  |       2      |      2       |        BD1 + BD2       |              None               |
S Cells Truths  |       2      |      1       |        BD2 + BD2       |    BD1 Void in CL2 &/or CL3     |
S Cells Truths  |       1      |      1       |      BD1&2 + BD1&2     | BD1 or BD2 Void in CL2 &/or CL3 |
----------------------------------------------------------------------------------------------------------

This is supposed to show that mixing 1 and 2 Truth digits in the base cells will result in an unavoidable contradiction, which can always be expressed in terms of CL2 and/or CL3 being void of a 2 Truth base digit.

Two 1 Truth digits in the base cells will result in an unavoidable contradiction, which can always be expressed in terms of CL2 and/or CL3 being void of either or both of the 1 Truth base digits.

Leren
Leren
 
Posts: 2618
Joined: 03 June 2012

Re: JExocet Pattern Defintion

Postby Leren » Tue Aug 05, 2014 10:22 pm

David P Bird wrote: I have now found the cause of my <false retraction> which came from my failure to realise that the posted grid that provided the assumed counter example contained an unsound JExocet.

The mystery deepens. My solver did actually find the JExocet you referred to. Here is the grid:

Code: Select all
  v                          v                          v
*--------------------------------------------------------------------------------*
| 9       8       124      | 7       125     1235     | 6       345     12345    |
| 7       3       124      | 8       1256    1256     | 9       45      1245     |
| 12      5       6        | 9       4       123      | 1278    378     12378    |
|--------------------------+--------------------------+--------------------------|
| 8       124     127      | 5       126     12467    | 3       9       1467     |
| 1234    6       1237     | 124     8       9        | 147     457     1457     |
| 14      9       5        | 14      3       67       | 78      2       678      |
|--------------------------+--------------------------+--------------------------|
|T2345    7       23-8     | 6       25      245      | 248     1       9        |
| 1246    124     9        | 1234    7       8        | 5      B346    B234      |
|T12456   124     128      |t23-14   9       1245     | 2478    34678   23478    |
*--------------------------------------------------------------------------------*
  ^                          ^                           ^

The JExocet is r8c8 r8c9 r7c1 r9c4 (2346). The cross columns are 1, 4 and 7 and the cross column S cell counts are 2 = 2, 3 = 2, 4 = 2 and 6 = 1 - a solved cell in r1c7.

However there is a SIS digit 5 in r79c1 so there is really a combined target cell r79c1 (I've forgotten the terminology - is this a twin JExocet ?). There is also a secondary equivalence relation r7c3==r9c4.

The eliminations were r7c3 <> 8 and r9c4 <> 14 after which the puzzle solved by singles.

The solution had r8c8 = 6, r8c9 = 3, r7c1 = 5, r9c1 = 6 and r9c4 = 3.

This would suggest that you can't remove a single S cell Truth digit from the base and target cells where a twin JExocet situation (or whatever the correct terminology is ) applies, but you can when this does not apply.

Leren
Leren
 
Posts: 2618
Joined: 03 June 2012

Re: JExocet Pattern Defintion

Postby David P Bird » Tue Aug 05, 2014 11:20 pm

Hi Leren,

I haven't had time to look properly at your earlier post but it looks as if it goes into cases which are unnecessary if truth counting is used.

Your second post is easier – look at the companion cell to the r9c4 target!

David (on the way to my bed!)
David P Bird
2010 Supporter
 
Posts: 935
Joined: 16 September 2008
Location: Middle England

Re: JExocet Pattern Defintion

Postby daj95376 » Wed Aug 06, 2014 4:56 am

[Withdrawn: existence of the <2346> Exocet is now in question.]

_
Last edited by daj95376 on Wed Aug 06, 2014 11:40 am, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: JExocet Pattern Defintion

Postby Leren » Wed Aug 06, 2014 6:36 am

daj95376 wrote: I find your final paragraph confusing

Actually what I'm now confused about is why both our solvers saw the 2346 base r8c89 Exocet when the companion cell to r9c4 is 6 - a base digit. It's either a bug or some obscure bit of logic I've forgotten about. Perhaps you can enlighten me.

I also saw the 1248 base r9c23 Exocet and also a 245 Base r7c56 Exocet.

Leren
Leren
 
Posts: 2618
Joined: 03 June 2012

Re: JExocet Pattern Defintion

Postby daj95376 » Wed Aug 06, 2014 11:39 am

[Withdrawn: Thanks blue for catching the error in my logic. That seems to happen a lot anymore. _ :( _]

_
Last edited by daj95376 on Wed Aug 06, 2014 10:29 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: JExocet Pattern Defintion

Postby blue » Wed Aug 06, 2014 7:53 pm

(withdrawn)
Last edited by blue on Thu Aug 07, 2014 12:59 am, edited 1 time in total.
blue
 
Posts: 572
Joined: 11 March 2013

Re: JExocet Pattern Defintion

Postby JC Van Hay » Wed Aug 06, 2014 8:03 pm

FWIW and independently of any terminology and any formalisation, here are some analysis of the puzzle posted by Leren here :

1. AALS(2346)r8c89 :
Code: Select all
+---------------------+----------------------+----------------------+
| 9         8    124  | 7        125   1235  | 6       345    12345 |
| 7         3    124  | 8        1256  1256  | 9       45     1245  |
| 1(2)      5    6    | 9        4     123   | 178(2)  378    12378 |
+---------------------+----------------------+----------------------+
| 8         124  127  | 5        126   12467 | 3       9      1467  |
| 13(24)    6    1237 | 1(24)    8     9     | 17(4)   457    1457  |
| 1(4)      9    5    | 1(4)     3     67    | 78      2      678   |
+---------------------+----------------------+----------------------+
| -3(245)   7    238  | 6        25    245   | 8(24)   1      9     |
| 1(246)    124  9    | 1(234)   7     8     | 5       (346)  (234) |
| -1(2456)  124  128  | -1(234)  9     1245  | 78(24)  34678  23478 |
+---------------------+----------------------+----------------------+
{2456C1 234C4 24C7 8N89} :=> r9c14<>1, r7c1<>3

Details :

r8c89=2 -> r3c7=2, FXW(2C14) :=> 2r9c4==52r79c1
r8c89=3 -> r9c4=3
r8c89=4 -> r5c7=4, FXW(4C14) :=> 4r9c4==54r79c1
r8c89=6 -> r79c1=56
|
V
r8c89=3a -> r9c4=3, r79c1=5a
r8c89<>3 -> r9c4=a, r79c1=5b
||
VV
r9c14<>1, r7c1<>3; singles to the end.

2. AALS(1248)r9c23 :
Code: Select all
+------------------------+----------------------+----------------------+
| 9         8      124   | 7        125   1235  | 6       345    12345 |
| 7         3      124   | 8        1256  1256  | 9       45     1245  |
| 1(2)      5      6     | 9        4     123   | 178(2)  378    12378 |
+------------------------+----------------------+----------------------+
| 8         124    127   | 5        126   12467 | 3       9      1467  |
| 13(24)    6      1237  | 1(24)    8     9     | 17(4)   457    1457  |
| 1(4)      9      5     | 1(4)     3     67    | 78      2      678   |
+------------------------+----------------------+----------------------+
| 35(24)    7      23(8) | 6        25    245   | (248)   1      9     |
| 6(124)    24(1)  9     | -3(124)  7     8     | 5       346    234   |
| 56-1(24)  (124)  (128) | 13(24)   9     1245  | 78(24)  34678  23478 |
+------------------------+----------------------+----------------------+
{1R8 8R7 2C147 4C147 9N23} :=> r8c4<>3, r9c1<>1

Details :

r9c23=1 -> r8c4=1
r9c23=2 -> SSF(2C147) : (2)[r8c4=r5c4-r5c1=r3c1-r3c7=r7c7] :=> 2r8c4==2r7c7
r9c23=4 -> SSF(4C147) : (4)[r8c4=XW(r56c14)-r5c7=r7c7] :=> 4r8c4==4r7c7
r9c23=8 -> r7c7=8
|
V
r9c23=1a -> r8c4=1, r7c7=a
r9c23<>1 -> r8c1=a, r7c7=b
||
VV
r8c4<>3, r9c1<>1

3. ALS(245)r7c56 :
Code: Select all
+--------------------+---------------------+-----------------------+
| 9        8    124  | 7       125   1235  | 6        345    12345 |
| 7        3    124  | 8       1256  1256  | 9        45     1245  |
| 1(2)     5    6    | 9       4     123   | 178(2)   378    12378 |
+--------------------+---------------------+-----------------------+
| 8        124  127  | 5       126   12467 | 3        9      1467  |
| 13(24)   6    1237 | 1(24)   8     9     | 17(4)    457    1457  |
| 1(4)     9    5    | 1(4)    3     67    | 78       2      678   |
+--------------------+---------------------+-----------------------+
| 3(245)   7    238  | 6       (25)  (245) | 8(24)    1      9     |
| -1(246)  124  9    | 1(24)   7     8     | 5        346    234   |
| (2456)   124  128  | 13(24)  9     1245  | -78(24)  34678  23478 |
+--------------------+---------------------+-----------------------+
{2456C1 24C4 24C7 7N56} :=> r9c7<>78, r8c1<>1

r7c56=2 -> r5c4=2, FXW(2C17) :=> 2r9c7==26r89c1
r7c56=4 -> SSF(4C147) : (4)[r9c7=XW(r56c47)-r56c1=r89c1] :=> 4r9c7==46r89c1
r7c56=5 -> r89c1=56
||
VV
r9c7<>78, r8c1<>1

4. Basics :
Code: Select all
+------------------------+----------------------+----------------------+
| 9       8      4(12)   | 7       125   1235   | 6       345    12345 |
| 7       3      4(12)   | 8       1256  1256   | 9       45     1245  |
| (12)    5      6       | 9       4     123    | 78(12)  378    12378 |
+------------------------+----------------------+----------------------+
| 8       24(1)  127     | 5       126   12467  | 3       9      1467  |
| 134(2)  6      37-1(2) | 14(2)   8     9      | 47(1)   457    1457  |
| 4(1)    9      5       | 4(1)    3     67     | 78      2      678   |
+------------------------+----------------------+----------------------+
| 2345    7      38-2    | 6       25    245    | 48(2)   1      9     |
| 146(2)  4(12)  9       | 34(12)  7     8      | 5       346    34(2) |
| 2456-1  24(1)  8-12    | 234(1)  9     245(1) | 478(2)  34678  23478 |
+------------------------+----------------------+----------------------+
ER(1C7B1)-1r5c3 [Optional]
SF(1C2R6B8)-1r9c13 AND JF(2R58C7B1)-2r79c3 :=> r9c3=8; singles to the end.

Details :

(1)[r5c7=r3c7-r3c1=r12c3]-1r5c3
(1)[r89c2=r4c2-r6c1=r6c4-r89c4=r9c6]-1r9c13

2r5c4=*[r5c3=*r5c1-r3c1=r12c3]
|
2r8c4=*[r8c12=*r8c9-r79c7=r3c7-r3c1=r12c3] :=> (2)[r5c3==r12c3==r8c12]-2r79c3
JC Van Hay
 
Posts: 618
Joined: 22 May 2010

Re: JExocet Pattern Defintion

Postby David P Bird » Thu Aug 07, 2014 10:42 am

Leren, ploughing through cases is rather a brute force method of developing a proof, although I accept that it can be useful way to confirm a proof is properly stated.

Your efforts therefore tell me that that the way I've stated my proof is unconvincing, so let me try again, this time combining it with the need to show that the target cells will hold different base digits (which actually makes it simpler).

Code: Select all
   CL1   CL2    CL3
. . S | . S  . | S  . .     . = Any digit
. . S | . S  . | S  . .   a,b = base digits
. . S | . S  . | S  . .     * = a & b eliminations in sight of base cells
------+--------+-------   
. . S | . S  . | S  . .     S = Crossline cells in the other bands 
. . S | . S  . | S  . .   
. . S | . S  . | S  . .     P = 2 Cells restricted to 1 truth for (ab)
------+--------+-------     Q = 2 Cells restricted to 1 truth for (ab)
a b * | * *  * | *  * *
* * * | . P  . | Q  . .     
* * * | . P  . | Q  . .

To confirm a JExocet pattern is valid it's necessary to confirm that the two target cells will be forced to hold different base digits.
  1. A base digit must be true in each of the cross-lines and so requires three cells.
  2. To force at least one these cells to be a target cell, each base digit candidate must be restricted to being true together in two S cells at most, otherwise the JExocet is not proven.
  3. With 2 base digits each of which must be true in at least one target cell, the two target cells must therefore contain one of each.
  4. Each true base digit must therefore be true in exactly two S cells, which eliminates any base cell candidate that can only be true in one.
The wording of step 2 allows for almost JExocets which depend on eliminations in the S cells to make them true.

This proves the simple case where the resultant theorems are well known, but the discussions have shown that more elaborate cases exist, such as where the target cells are in the same box or one of two in a mini-line along the JE band. These will have more complex conditions and will produce a different set of theorems so must be given different names.

I'm far from sure if any of these either a) occur often enough or b) are simple enough for a manual player to identify, to make them worth including.

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

Re: JExocet Pattern Defintion

Postby David P Bird » Thu Aug 07, 2014 10:49 am

JC Van Hay wrote:FWIW and independently of any terminology and any formalisation, here are some analysis of the puzzle posted by Leren ...

Is there any connection between your proof and the JExocet pattern, the subject of this thread?
David P Bird
2010 Supporter
 
Posts: 935
Joined: 16 September 2008
Location: Middle England

Re: JExocet Pattern Defintion

Postby Leren » Thu Aug 07, 2014 12:18 pm

David P Bird wrote :

To confirm a JExocet pattern is valid it's necessary to confirm that the two target cells will be forced to hold different base digits.
1.A base digit must be true in each of the cross-lines and so requires three cells.
2.To force at least one these cells to be a target cell, each base digit candidate must be restricted to being true together in two S cells at most, otherwise the JExocet is not proven.
3.With 2 base digits each of which must be true in at least one target cell, the two target cells must therefore contain one of each.
4.Each true base digit must therefore be true in exactly two S cells, which eliminates any base cell candidate that can only be true in one.


Hi David, I don't like this wording because it seems to me to be a circular argument ie you can eliminate a digit that has only one truth in the S cells because a digit that has 2 truths in the S cells is "forced" to be in at least one of the target cells. This simply is not true. In order to justify this statement you have to consider what would happen for all possible parings of base digits. If you pair a 2 Truth digit with a 1 Truth digit the 2 Truth digit cannot be shown to occupy at least one Target cell. Let's see if I can re-word your argument that seems sequentially logical, at least to me.

To confirm a JExocet pattern is valid it's necessary to confirm that the two target cells will be forced to hold different base digits - the same 2 digits that occupy the base cells.

1.A base digit must be true in each of the cross-lines and so requires three cells.
2.If any base digit is not restricted to being true together in two S cells at most, the JExocet cannot be proven.
3. If a base digit that is restricted to 1 Truth in the S cells at most, is paired with a base digit that is restricted to 1 Truth or 2 Truths in the S cells at most, a valid solution to the puzzle cannot be found. Therefore such a base digit cannot occupy the base cells.
4. If a base digit that is restricted to 2 Truths in the S cells at most, is paired with another base digit that is restricted to 2 Truths in the S cells at most, then it can be shown that each such digit must occupy at least one target cell. Consequently the two target cells must contain one of each. If at least 2 such base digits exist, the JExocet can be proven.

Again it's late at night so I'll review this wording tomorrow.

Leren
Leren
 
Posts: 2618
Joined: 03 June 2012

PreviousNext

Return to Advanced solving techniques