exocet pattern in hardest puzzles

Advanced methods and approaches for solving Sudoku puzzles

Re: bi bi pattern in hardest puzzles

Postby champagne » Sun Mar 18, 2012 9:07 am

Hi,

Up to now, all analysed exocets took place in a band.
A possible conjecture raised that it would be a rule.

For a player, looking in band is a normal way to identify an exocet,
So I prepared in my new code a quick way to extract Exocets with that limitation.

Running the code toward my data base of hardest, I found that exocet which does not comply with the limited rule
(one in a file containing thousands of puzzles)




...4....94....923..8..2...4..6..3...8..59...2.......7.3..9....5..8..21...1...5...;1952;elev;1806

Code: Select all
A     B     C      |D    E      F     |G      H     I   
12567 23567 12357  |4    135678 1678* |5678   1568  9   
4     567   157    |1678 15678  9     |2      3     1678*
15679 8     13579  |1367 2      167*  |567    156   4   
--------------------------------------------------------
12579 24579 6      |1278 1478   3     |4589   14589 18   
8     347   1347   |5    9      1467  |346    146   2   
1259  23459 123459 |1268 1468   1468  |345689 7     1368
--------------------------------------------------------
3     2467  247    |9    14678* 14678 |4678   2468  5   
5679  45679 8      |367  3467   2     |1      469   367 
2679  1     2479   |3678 34678  5     |346789 24689 3678


Here we have a valid exocet based on r13c6
the target is r2c9 r7c5

champagne
Last edited by champagne on Tue Mar 20, 2012 8:24 am, edited 1 time in total.
champagne
2017 Supporter
 
Posts: 6712
Joined: 02 August 2007
Location: France Brittany

Postby ronk » Sun Mar 18, 2012 11:31 am

champagne wrote:Here we have a valid exocet based on r13c6
the target is r2c9 r7c5

It will be interesting to see the deductive logic found for this one. BTW the targets are in the two chutes of the "exocet."
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: bi bi pattern in hardest puzzles

Postby David P Bird » Sun Mar 18, 2012 11:44 am

Champagne, the analysis done <here> certainly confined your four cells to a single tier. This way the conflict between the candidates in the target cells could be simplified to considering the Swordfish patterns in three columns that would be made by the Exocet digits as the grid is solved.

This approach works for all one-tier Exocet signature patterns provided an extra condition in met: that the Exocet digits in these three columns are each confined to 2 rows in the parallel tiers. This then promotes the pattern to one covered by a theorem which can be used by manual solvers. When this extra condition is not met, the Exocet eliminations may still be valid but must be proved using deeper analysis.

Clearly when the target cells are split, as in your example, this approach can't be used but another one might be possible – I don't know. What I notice is that in your example there are no givens for (1567) in tier 1 and (1678) in stack 2, which may make it possible to consider the Deadly Patterns that must be avoided.
David P Bird
2010 Supporter
 
Posts: 1040
Joined: 16 September 2008
Location: Middle England

Re: bi bi pattern in hardest puzzles

Postby champagne » Sun Mar 18, 2012 3:30 pm

David P Bird wrote:Champagne, the analysis done <here> certainly confined your four cells to a single tier. This way the conflict between the candidates in the target cells could be simplified to considering the Swordfish patterns in three columns that would be made by the Exocet digits as the grid is solved.

This approach works for all one-tier Exocet signature patterns provided an extra condition in met: that the Exocet digits in these three columns are each confined to 2 rows in the parallel tiers. This then promotes the pattern to one covered by a theorem which can be used by manual solvers. When this extra condition is not met, the Exocet eliminations may still be valid but must be proved using deeper analysis.

Clearly when the target cells are split, as in your example, this approach can't be used but another one might be possible – I don't know. What I notice is that in your example there are no givens for (1567) in tier 1 and (1678) in stack 2, which may make it possible to consider the Deadly Patterns that must be avoided.



I went again through that thread, but the theorem you mention is somehow spread in several posts and I don't see (but my English is poor) a clear synthesis.

Anyway, at that point, I am not in a solving view, this will come later, but in an identification process. If I see clearly the rule you apply, I'll try to put it in the new version of my solver.

The target in a first step is to see in a quick way puzzles with an exocet pattern.

I agree with ronk that that pattern of the Exocet has less solving potential that the classical one, but it's not null.

- we have <4>r7c5 as in any other exocet
- for any pair solution of r13c6, the same digits are solution of r2c9 r7c5 but here, we don't have the side elimination of candidates that we had the basic pattern.
(partly due to the fact that the cell r7c9 is assigned)

Just for information, I run a test on a file containing about 15000 puzzles having one or more exocets.
The code looking for an in band/stack exocet worked out the file in some seconds( less than 10).

champagne
champagne
2017 Supporter
 
Posts: 6712
Joined: 02 August 2007
Location: France Brittany

Re: bi bi pattern in hardest puzzles

Postby David P Bird » Sun Mar 18, 2012 6:34 pm

champagne wrote:I went again through that thread, but the theorem you mention is somehow spread in several posts and I don't see (but my English is poor) a clear synthesis.

I'm sorry about that, but I had the same problem reading your posts in this thread. From your writings I believe that once your solver has found a potential pattern, it must then check if it provides exclusions - that is, the pattern alone does not guarantee this. Taking a subset of the pattern – 'son of Exocet' if you like - was a way to try to overcome this.

champagne wrote:Anyway, at that point, I am not in a solving view, this will come later, but in an identification process. If I see clearly the rule you apply, I'll try to put it in the new version of my solver.

In which case I'll wait. In the interim it would be helpful if you could tell us what your solver reports for the analysis of the puzzle I used as a counter-example before:
..7..9....9......4.1..3..5...4..2....2.5.3.6....7..8...5..1..388......1....6..5.. Scanraid Weekly Unsolvable 34

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

Re: bi bi pattern in hardest puzzles

Postby champagne » Sun Mar 18, 2012 7:07 pm

David P Bird wrote:
From your writings I believe that once your solver has found a potential pattern, it must then check if it provides exclusions - that is, the pattern alone does not guarantee this. Taking a subset of the pattern – 'son of Exocet' if you like - was a way to try to overcome this.

DPB


Yes, but it's the same for many patterns. Once action on an XWing has been done, the XWing is still there, but does not lead to any elimination...

As far as I remember, all exocets I have analysed led to an action.
This does not allow the solver to consider that there is one. This is the best way to generate endless loops.


David P Bird wrote:
. In the interim it would be helpful if you could tell us what your solver reports for the analysis of the puzzle I used as a counter-example before:
..7..9....9......4.1..3..5...4..2....2.5.3.6....7..8...5..1..388......1....6..5.. Scanraid Weekly Unsolvable 34

DPB


my solver does not see any exocet in that puzzle (even not a partial one).

could you tell what assumed exocet you have in mind, I'll tell you why it's not correct (or I'll find a bug in the code :oops: )

champagne


EDIT

I was wrong when I said there were no partial result.
They just don't appear in the short print.

The solver found pieces of exocet (valid for part of the digits, but not all)
for the bases r7c6r8c6 and r7c6r9c6

but this is another story.
champagne
2017 Supporter
 
Posts: 6712
Joined: 02 August 2007
Location: France Brittany

Re: bi bi pattern in hardest puzzles

Postby ronk » Sun Mar 18, 2012 7:35 pm

David P Bird wrote:From your writings I believe that once your solver has found a potential pattern, it must then check if it provides exclusions - that is, the pattern alone does not guarantee this.

I generally see an AALS as a marker for a possible "exocet", but identifying the exact location of valid target cells without a lot of effort has eluded me. Whether exclusions are still possible in these target cells is a different issue, although a trivial one.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: bi bi pattern in hardest puzzles

Postby David P Bird » Sun Mar 18, 2012 11:29 pm

champagne wrote:The solver found pieces of exocet (valid for part of the digits, but not all) for the bases r7c6r8c6 and r7c6r9c6

Now you are really confusing me! This is the grid after singles and simple colouring deductions:
Code: Select all
 |-----------------------|-----------------------|----------------------|
 | 23456    3468  7      | 1248   2456    9      | 1236    28     1236  | 
 | 2356     9     23568  | 128    2567    1567   | 12367   278    4     | 
 | 246      1     268    | 248    3       4678   | 2679    5      2679  |
 |-----------------------|-----------------------|----------------------|
 | 135679   3678  4      | 189    689     2      | 1379    79     13579 | 
 | 179      2     189    | 5      489     3      | 1479    6      179   | 
 | 13569    36    13569  | 7      469     146    | 8       249    12359 | 
 |-----------------------|-----------------------|----------------------|
 | (24679)  5     269    | [249]  1       [47]   | 24679   3      8     |
 | 8        467   269    | 3      (24579) 457    | [24679] 1      2679  |
 | [123479] 347   1239   | 6      2789    478    | 5       (2479) (279) |
 |-----------------------|-----------------------|----------------------|

I considered the that there were two Exocet patterns:
(2479)Exocet:r7c46,r8c7,r9c1 => possible exclusions r8c7 <> 6, r9c1 <> 13
[2479]Exocet:r9c89,r7c1,r8c5 => possible exclusions r7c1 <> 6, r8c5 <> 5

But I can't validate these exclusions.

To help us to understand each other better please would you clarify what the difference is between a part Exocet pattern and a full Exocet pattern.

but this is another story.

Does this mean that you are still working on this area but aren't ready to report on it yet? If so I guess I'll just have to wait some more!
David P Bird
2010 Supporter
 
Posts: 1040
Joined: 16 September 2008
Location: Middle England

Re: bi bi pattern in hardest puzzles

Postby David P Bird » Sun Mar 18, 2012 11:32 pm

ronk wrote: I generally see an AALS as a marker for a possible "exocet", but identifying the exact location of valid target cells without a lot of effort has eluded me. Whether exclusions are still possible in these target cells is a different issue, although a trivial one.

My trick for spotting one-band Exocets is to examine which digits don't appear as givens anywhere in the band and look for cells composed only of those digits. If a pair of base cells is found, then look for target cells on different lines in the other two boxes in the band.

Obviously if a target cell only holds Exocet digits it will have no exclusions, but finding the four-cell pattern alone isn't sufficient to be sure that any non-Exocet digits are false in these cells AFAIAC.

BTW regarding my terminology: just as a line can either be a row or a column of cells, I consider a band to be either be a stack or tier of boxes and both these terms imply the direction they follow. This makes it easier to write about single-band patterns and allows me to use s1,s2,s3 and t1,t2,t3 as band identities whereas the abbreviations for chutes and bands can be confused with those for columns and boxes.

I'm not asking you to convert to my terms but just to understand that I've got good reasons for them and I'm not being awkward just for the sake of it.
David P Bird
2010 Supporter
 
Posts: 1040
Joined: 16 September 2008
Location: Middle England

Re: bi bi pattern in hardest puzzles

Postby champagne » Mon Mar 19, 2012 5:50 am

David P Bird wrote:
champagne wrote:The solver found pieces of exocet (valid for part of the digits, but not all) for the bases r7c6r8c6 and r7c6r9c6

Now you are really confusing me! This is the grid after singles and simple colouring deductions:
Code: Select all
 |-----------------------|-----------------------|----------------------|
 | 23456    3468  7      | 1248   2456    9      | 1236    28     1236  | 
 | 2356     9     23568  | 128    2567    1567   | 12367   278    4     | 
 | 246      1     268    | 248    3       4678   | 2679    5      2679  |
 |-----------------------|-----------------------|----------------------|
 | 135679   3678  4      | 189    689     2      | 1379    79     13579 | 
 | 179      2     189    | 5      489     3      | 1479    6      179   | 
 | 13569    36    13569  | 7      469     146    | 8       249    12359 | 
 |-----------------------|-----------------------|----------------------|
 | (24679)  5     269    | [249]  1       [47]   | 24679   3      8     |
 | 8        467   269    | 3      (24579) 457    | [24679] 1      2679  |
 | [123479] 347   1239   | 6      2789    478    | 5       (2479) (279) |
 |-----------------------|-----------------------|----------------------|

I considered the that there were two Exocet patterns:
(2479)Exocet:r7c46,r8c7,r9c1 => possible exclusions r8c7 <> 6, r9c1 <> 13
[2479]Exocet:r9c89,r7c1,r8c5 => possible exclusions r7c1 <> 6, r8c5 <> 5

But I can't validate these exclusions.

To help us to understand each other better please would you clarify what the difference is between a part Exocet pattern and a full Exocet pattern.

but this is another story.

Does this mean that you are still working on this area but aren't ready to report on it yet? If so I guess I'll just have to wait some more!


your example is not an exocet, and I'll tell why in a separate post with more details on how this can be shown easily.

two remarks before

================

My program looks for patterns after basic actions, but before having done any elimination through chains.

This could be a reason to give you a chance to find an exocet not seen by the current solver.

In that specific puzzle, the only elimination you made on the digits of the 2 "potential exocets" is <4>r9c5, so it can not explain a difference

==================

I'll comment the partial exocet after the post showing why your puzzle has no exocet.

I tried to use it in my solver, but I feel the pay-back is too low to keep them in the future, unless my other prospective changes don't show what I expect.

They are, in the way I do it, no so easy to detect for a player
Simplifications in the path are often poor.

May be I'll keep them for the typical pattern you study.

champagne
champagne
2017 Supporter
 
Posts: 6712
Joined: 02 August 2007
Location: France Brittany

Re: bi bi pattern in hardest puzzles

Postby champagne » Mon Mar 19, 2012 7:03 am

Code: Select all
|-----------------------|-----------------------|----------------------|
 | 23456    3468  7      | 1248   2456    9      | 1236    28     1236  |
 | 2356     9     23568  | 128    2567    1567   | 12367   278    4     |
 | 246      1     268    | 248    3       4678   | 2679    5      2679  |
 |-----------------------|-----------------------|----------------------|
 | 135679   3678  4      | 189    689     2      | 1379    79     13579 |
 | 179      2     189    | 5      489     3      | 1479    6      179   |
 | 13569    36    13569  | 7      469     146    | 8       249    12359 |
 |-----------------------|-----------------------|----------------------|
 | (24679)  5     269    | [249]  1       [47]   | 24679   3      8     |
 | 8        467   269    | 3      (24579) 457    | [24679] 1      2679  |
 | [123479] 347   1239   | 6      2789    478    | 5       (2479) (279) |
 |-----------------------|-----------------------|----------------------|


question:

Is r7c46 + r8c6 r9c1 an exocet
Is r9c89 + r7c1 r8c5 an exocet.

Answer: no at all for both.

The generic condition to have an exocet is that
a digit solving the base (say r7c46)
is also in one of the target cells (say r8c6 r9c1).

Let's see what happen for the digit 2.

The easiest way to check the generic condition is to consider the floor '2'
forcing r7c46 true (here r7c4 true)
forcing the target (r8c6 r9c1) false.
If the generic condition is true, that pattern has no solution

This is the resulting floor where 'g' shows the given in the PM
Code: Select all
2.. .2. 222
2.2 .2. 22.
2.2 ... 2.2

... ..g ...
.g. ... ...
... ... .22

... 2.. ...
..2 ... ..2
..2 ... .22


I let you check, but that PM has multiple solutions.

This is enough to say we have no exocet


The Floor 2 in the second potential exocet is the following

Code: Select all
2.. 22. 222
2.2 22. 22.
2.2 2.. 2.2

... ..g ...
.g. ... ...
... ... .22

..2 2.. ...
..2 ... ...
... ... .22

again, no problem to see that we have possible solutions.

So none of these 2 is an exocet.
In fact, we would come to the same conclusion using digits 9 (very similar floor)
and for digit 4 (I did not check digit 7, but with only one occurrence of that digit...).

================================

It could be that for some digits the check works and not for others.
As soon as the check works for 2 digits, we have a "partial exocet"
eg assume it works here for digits 4 and 7, we could say we have a partial exocet for the possble solution 47
This does not give direct eliminations, but we keep the side effect as here

if 47 was a partial exocet in r7c46 (this is false, but forget it)
then the reduced map in band 3 for assumption 47 would be

Code: Select all
 | (24679)  5     269    | 4      1       47     | 24679   3      8     |
 | 8        6     269    | 3      (259)   5      | 47      1      2679  |
 | 47       347   1239   | 6      289     8      | 5       29     29    |


just doing what comes directly from the exocet logic.
47r7c46 => 47 r8c7 ; 47 r9c1

This can make possible an easy elimination of the assumption 47 r7c46

champagne
champagne
2017 Supporter
 
Posts: 6712
Joined: 02 August 2007
Location: France Brittany

Re: bi bi pattern in hardest puzzles

Postby David P Bird » Mon Mar 19, 2012 10:56 am

champagne, thank you very much for your clarification.

So we agree, once a pair of base cells and two potential target cells have been found the job is not over and extra checks are required.

For 'son of Exocet' these checks are simplified to help manual solvers.

Taking a random puzzle from your list on page 2 of this thread:
.....1.....7.2.....9.6.8..5..1..7....6.9....42.9.........8...59.8....4....6.3...8 tarx0079,tarek 4.7 *3BB r9c78 r7c2 r8c4
Code: Select all
   
 *-------------------------*-------------------------*-------------------------*
 | 34568   2345    23458   | 3457    4579    1       | 236789  2346789 2367    | 27
 | 134568  1345    7       | 345     2       3459    | 13689   134689  136     | 1
 | 134     9       234     | 6       47      8       | 1237    12347   5       |
 *-------------------------*-------------------------*-------------------------*
 | 3458    345     1       | 2345    4568    7       | 235689  23689   236     | 2
 | 3578    6       358     | 9       158     235     | 123578  12378   4       |
 | 2       3457    9       | 1345    14568   3456    | 135678  13678   1367    | 17
 *-------------------------*-------------------------*-------------------------*
 | 1347    12347 # 234     | 8       1467    246     | 12367   5       9       |
 | 13579   8       235     | 1257 #  15679   2569    | 4       12367   12367   |
 | 14579   12457   6       | 12457   3       2459    | 127 #   127 #   8       |
 *-------------------------*-------------------------*-------------------------*
           *                 *                                         *

(127)Exocet:r9c78,r7c2,r8c4
The columns of interest are c2 & c4 which hold the target cells, and c9, the third column in the base pair box
Reducing the grid to the essentials:
Code: Select all
         
 *-------------*-------------*-------------*
 | .   2   .   | 7   .   .   | .   .   27  | 27
 | .   1   .   |     .   .   | .   .   1   | 1
 | .       .   |     .   .   | .   .       |
 *-------------*-------------*-------------*
 | .   .   .   | 2   .   .   | .   .   2   | 2
 | .   .   .   |     .   .   | .   .       |
 | .   7   .   | 1   .   .   | .   .   17  | 17
 *-------------*-------------*-------------*
 | 17  127 2   | .   17  2   | 127 .   .   |
 | 17  .   2   | 127 17  2   | .   127 127 |
 | 17  127 .   | 127 .   2   | 127 127 .   |
 *-------------*-------------*-------------*

The Exocet digits must occur in one cell in each of these columns, but tiers 1 and 2 can only hold 2 of each, so the third one must be in tier 3.
For the two digits in the base cells r9c78 these cells can only be r7c2 and r8c4 – the target cells, so these cells cannot hold a non-Exocet digit.

The simple test is therefore to check that only two rows in the other two tiers can contain each Exocet digit in these columns.

A manual solver will not look for Exocet patterns first, and it can be that one of the Exocet digits has been excluded from a target cell. This doesn't matter if we change the pattern we look for to two base cells + the 'empty' cells at r7c4 and r8c2 (which are usually givens).
David P Bird
2010 Supporter
 
Posts: 1040
Joined: 16 September 2008
Location: Middle England

Re: bi bi pattern in hardest puzzles

Postby champagne » Mon Mar 19, 2012 2:08 pm

Hi David,

For me, an exocet does not exist if it has not been proven, so talking of "additional checking" sounds strange in that situation.
But this is a detail.




For 'son of Exocet' I would say as "generic answer" that any pattern establishing that the generic condition is valid and can be used by a player.

In your example I would slightly change the presentation.

In that band, some cells will anyway play no role whatever is the rest of the PM

1347 12347 # 234 | 8 1467 246 | 12367 5 9 |
13579 8 235 | 1257 # 15679 2569 | 4 12367 12367|
14579 12457 6 | 12457 3 2459 | 127 # 127 # 8 |
* * *

I can reduce it to
Code: Select all
 Y  T  Y   | Z  Y  Y  | x  x  x |
 Y  Z  Y   | T  Y  Y  | x  x  x |
 x  x  x   | x  x  x  | B  B  x |
         

where

B is the base
T is the target
x can contain any value (in fact it will not, but it plays no role)
Y,Z can contain the digit of the base and play a role in the search of valid perms.


checking for an exocet, we assume 'B' true, so 'x' is false.


Your statement is that generally Z is empty and you just look at such puzzles.
I would agree on that
So, replacing all '*' and all 'Z' by a dot we come to that typical pattern
Code: Select all
 Y  T  Y   | .  Y  Y  | .  .  . |
 Y  .  Y   | T  Y  Y  | .  .  . |
 .  .  .   | .  .  .  | B  B  . |


then if I change slightly your wording, you say

if in each "column" containing a target we have still one and only one of the digits of the base
If in addition the last "column" contains that digit in the same "rows"
then this is an exocet (we have established that we have no valid perm in the last column)

Nothing to object to that specific pattern and I believe it is the most common one.

In general, any pattern that seem to have an interest should be ruled in a way proving that there are no valid perm for any digit.
I'll try to extract exocet fitting with that rule and others.

BTW, my database of hardest has surely to day more than 20 000 exocets if I account the ongoing run.

champagne
champagne
2017 Supporter
 
Posts: 6712
Joined: 02 August 2007
Location: France Brittany

Re: bi bi pattern in hardest puzzles

Postby ronk » Mon Mar 19, 2012 6:44 pm

champagne wrote:I found that exocet which does not comply with the limited rule (one among thousands)

...4....94....923..8..2...4..6..3...8..59...2.......7.3..9....5..8..21...1...5... ;1952;elev;1806

Code: Select all
A     B     C      |D    E      F     |G      H     I   
12567 23567 12357  |4    135678 1678* |5678   1568  9   
4     567   157    |1678 15678  9     |2      3     1678*
15679 8     13579  |1367 2      167*  |567    156   4   
--------------------------------------------------------
12579 24579 6      |1278 1478   3     |4589   14589 18   
8     347   1347   |5    9      1467  |346    146   2   
1259  23459 123459 |1268 1468   1468  |345689 7     1368
--------------------------------------------------------
3     2467  247    |9    14678* 14678 |4678   2468  5   
5679  45679 8      |367  3467   2     |1      469   367 
2679  1     2479   |3678 34678  5     |346789 24689 3678

Here we have a valid exocet based on r13c6
the target is r2c9 r7c5

So far, with Xsudo's help, the best I've been able to find is "a 4-digit mutant jellyfish with endo-fins" ... sorta. Note the appearance of digits <1> and <8> is very limited. I'll look a little harder for a logic set without endo-fins.

____Image

Code: Select all
12 Truths = {1R7 6R257 7R257 8R2 67C9 13N6}
17 Links = {1c6 6c26 7c236 2n29 5n3 7n56 6b269 7b29 8b2}
 6 Eliminations --> r17c5<>8, r56c6<>1, r2c9<>1, r7c5<>4
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: bi bi pattern in hardest puzzles

Postby David P Bird » Mon Mar 19, 2012 8:22 pm

Hi champagne, I'm pleased that I've now been able to explain the simplified pattern to you. I should stress that it wasn't me who found it but blue on the programmers forum. Since then I've been trying to present it in a form suitable for inclusion in a pattern book.

I accept that my presentation may not be the best, but before you decide on a final form I would suggest that you consider what other sub-patterns may need to be presented as well.

If you code it into your program, I would be interested to know how successful it is in finding the one-band Exocets in your data base.

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

PreviousNext

Return to Advanced solving techniques