exocet pattern in hardest puzzles

Advanced methods and approaches for solving Sudoku puzzles

Re: bi bi pattern in hardest puzzles

Postby daj95376 » Tue Apr 10, 2012 12:38 am

ronk wrote:My too terse statement assumes r9c89=9, just as you did in your single-digit PMs. IOW while there are swordfish for the other digits, the digit 9 case degenerates to a hidden single.

Okay, I now understand that you are using an Exocet pattern -- r9c89, r78c24 -- instead of David's pattern -- r9c89, r78c26.

You derived r8c2=9 when r9c89=9. FWIW, here's r7c4=3 when r9c89=3.

Code: Select all
r7c4<>3, X-Wing r23\c47, r23c2<>3, r8c2=3, r7c3<>3, r7c4=3
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: bi bi pattern in hardest puzzles

Postby champagne » Tue Apr 10, 2012 7:47 am

ronk wrote:My suspicion is that your revised program is now missing another degenerate case.


____Image




Agreed, that strong link

9r8c56 = 9r8c3 = 9r9c3 = 9r9c89

can be applied to both exocets and the rest complies with the "simplified rules".

BTW, David did not recognise it as correct.

Not to hard to adjust the process, but more than one line of code.

champagne

EDIT finally, it was just one line of code.
he four double exocets are now recognised
champagne
2017 Supporter
 
Posts: 5610
Joined: 02 August 2007
Location: France Brittany

Re: bi bi pattern in hardest puzzles

Postby David P Bird » Tue Apr 10, 2012 10:03 am

Some quick comments to keep you going*:

1) Working Name

For now I'll call the Exocets that comply with all 3 conditions "Junior Exocets" or "JExocets"

2) The third condition

The point finally got home. I accept the current treatment is incomplete and using the Swordfish concept is potentially confusing.

It must be impossible for the 3 cross lines to hold 3 instances of a member digit in the non-JExocet bands. This will be true when
a) A member digit is restricted to any 2 lines in these bands
b) A member digit is restricted to 2 of the 3 cross lines in these bands

3) Twin JExocets
Code: Select all
 *-------------------------*-------------------------*-------------------------*
 | 9       8       2345    | 7       123     1235    | 6       124     124     | -
 | 7       134     234     | 6       12389   12389   | 5       1248    12489   | -
 | 25      156     256     | 289     4       12589   | 278     3       12789   | 2
 *-------------------------*-------------------------*-------------------------*
 | 6       347     8       | 5       1237    1234    | 9       1247    12347   | -
 | 345     2       34579   | 3489    136789  134689  | 3478    145678  134578  | 34
 | 345     34579   1       | 23489   236789  234689  | 23478   245678  234578  | 234
 *-------------------------*-------------------------*-------------------------*
 | 1       3479    23479   | 23489 t 23689   234689  | 23478 t 24578   234578  |
 | 23458 t 3457    23457   | 1       238 b   2348 b  | 23478   9       6       |
 | 2348 t  3469    23469   | 23489   5       7       | 1       248 b   2348 b  |
 *-------------------------*-------------------------*-------------------------*
    ^                         ^ 8                        ^ 8

(2348)TwinJExocet:b=r8c56,r9c89,t=r7c47,r89c1

When Twin JExocets exist the following eliminations can be made immediately without needing SLG confirmation:
1) Non-member digits can be eliminated from the target cells as usual.
. . r7c4 <> 9, r7c7 <> 7, r8c1 <> 5
2) As each member will occur once in the 4 base cells**, they can all be eliminated from cells seeing every base cell.
. . r8c7,r9c6 <>2348
3) The target cells will also hold all the member digits eliminating them from cells that see all 4 of them
. . r7c2 <> 34 r7c3 <> 234

4) The three cross lines must hold 3 instances of all 4 member digits so
. . a) those restricted to 2 internal lines in the non-JExocet bands can be excluded elsewhere in these lines.
. . . . r3c5639,r6c5689 <> 2, r5c3569,r6c2569 <> 3, r5c3689,r6c2689 <> 4
. . b) any restricted to 2 cross lines can be eliminated in the cells they cover in the JExocet band
. . . . r79c4,r78c7 <> 8 (two of these eliminations repeat earlier ones)


** Each base pair will either see the other pair directly or see the two target cells that hold the same digit pair. They therefore must each contain different digits.

4) Reported results

It seems the near 80% hit rate that is now being found is using only the first two conditions. When the third condition is added I believe it will fall considerably. Sampling the "Exocets Found" collection I find many of them don't comply with the third condition, but were obviously not excluded.

This makes me wonder what exactly has been changed in the search routine so far.

5) Optional Candidates

What is meant by this term needs clarification.

* PS they weren't such quick points by the time I'd finished though

[Edit] Extra eliminations: 3) thanks to champagne, 4b) spotted later. Wording revised, & justification for eliminations at 2), 4 eliminations for digit (2) missed - spotted by ronk.
Last edited by David P Bird on Thu Apr 12, 2012 9:55 am, edited 2 times in total.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Re: bi bi pattern in hardest puzzles

Postby ronk » Tue Apr 10, 2012 11:50 am

David P Bird wrote:2) As each member will occur once in the 4 base cells, they can all be eliminated from cells seeing every base cell.
r8c7,r9c6 <>2348

On what is the statement "each member will occur once in the 4 base cells" based? Knowing only that r9c89,[r7c7,r9c1] will ultimately contain a "remote pair" and ditto for r8c56,[r7c4,r8c1] is insufficient.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: bi bi pattern in hardest puzzles

Postby champagne » Tue Apr 10, 2012 11:57 am

David P Bird wrote:3) Twin JExocets
Code: Select all
 *-------------------------*-------------------------*-------------------------*
 | 9       8       2345    | 7       123     1235    | 6       124     124     | -
 | 7       134     234     | 6       12389   12389   | 5       1248    12489   | -
 | 25      156     256     | 289     4       12589   | 278     3       12789   | 2
 *-------------------------*-------------------------*-------------------------*
 | 6       347     8       | 5       1237    1234    | 9       1247    12347   | -
 | 345     2       34579   | 3489    136789  134689  | 3478    145678  134578  | 34
 | 345     34579   1       | 23489   236789  234689  | 23478   245678  234578  | 234
 *-------------------------*-------------------------*-------------------------*
 | 1       3479    23479   | 23489 t 23689   234689  | 23478 t 24578   234578  |
 | 23458 t 3457    23457   | 1       238 b   2348 b  | 23478   9       6       |
 | 2348 t  3469    23469   | 23489   5       7       | 1       248 b   2348 b  |
 *-------------------------*-------------------------*-------------------------*
    ^                         ^ 8                        ^ 8

(2348)TwinJExocet:b=r8c56,r9c89,t=r7c47,r89c1

When Twin JExocets exist the following eliminations can be made immediately without needing SLG confirmation:
1) Non-member digits can be eliminated from the target cells as usual.
r7c4 <> 9, r7c7 <> 7, r8c1 <> 5
2) As each member will occur once in the 4 base cells, they can all be eliminated from cells seeing every base cell.
r8c7,r9c6 <>2348
3) The three cross lines must hold 3 instances of all 4 member digits so those restricted to 2 lines in the non-JExocet bands can be excluded elsewhere in these lines.
r3c39,r6c89 <> 2, r5c3569,r6c2569 <> 3, r5c3689,r6c2689 <> 4



I feel not 100% comfortable with the wording in point 3)


is missing a point 2b) each candidate seeing every target cell can be eliminated. (234r8c23)


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

Re: bi bi pattern in hardest puzzles

Postby daj95376 » Wed Apr 11, 2012 8:39 am

[Withdrawn and replaced with a later post.]
Last edited by daj95376 on Wed Apr 11, 2012 4:41 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: bi bi pattern in hardest puzzles

Postby champagne » Wed Apr 11, 2012 9:28 am

ronk wrote:
David P Bird wrote:2) As each member will occur once in the 4 base cells, they can all be eliminated from cells seeing every base cell.
r8c7,r9c6 <>2348

On what is the statement "each member will occur once in the 4 base cells" based? Knowing only that r9c89,[r7c7,r9c1] will ultimately contain a "remote pair" and ditto for r8c56,[r7c4,r8c1] is insufficient.


In fact it's not possible in such a pattern to have the same digits in the 2 exocets
so the four targets contain the four digits.


My concern was more on point 3)

If you look at the XSUDO drawing of the double exocet, eliminations shown in that point are not there.
This is not a rank 0 area.

In addition, this is not valid for a simple exocet.

We have however one way to establish why this is valid in a double exocet pattern.

We can figure out a "pseudo row 7" in David's example collecting the 2 targets in column 2

Then, in that "pseudo row 7"' all digits are in columns 2 4 7 (I know this is not globally possible, but we work digit per digit)

For each digit, we have now a pure swordfish with the digit seen in row 7. We can apply eliminations.

What happens with a single exocet is that the digit is not always there, so we have to consider the rest of the row and then to be very cautious.


Another problem I have with the wording in point 3 is that for degenerated forms, it could lead to errors.

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

Re: bi bi pattern in hardest puzzles

Postby ronk » Wed Apr 11, 2012 9:37 am

daj95376 wrote:
ronk wrote:
David P Bird wrote:2) As each member will occur once in the 4 base cells, they can all be eliminated from cells seeing every base cell.
r8c7,r9c4 <>2348
On what is the statement "each member will occur once in the 4 base cells" based? Knowing only that r9c89,[r7c7,r9c1] will ultimately contain a "remote pair" and ditto for r8c56,[r7c4,r8c1] is insufficient.

I finally understood champagne's comments in his Double Exocet example. Now for David's grid.
...
after forcing base cells [r8] r8c5=2 and r8c6=4 (their correct values)
target cells r7c4,r8c1=38 result for base cells [r9]

In a roundabout way, I am asking for the strong links required to reach that conclusion for every possible pair of digits in base cells r8c56. Remember we don't yet know the ultimate assignments. Base and cell locations, cell pairings, and potential placement values are the starting point.

[edit: added the below]
champagne wrote:In fact it's not possible in such a pattern to have the same digits in the 2 exocets
so the four targets contain the four digits.

That's an observation, not a proof.
Last edited by ronk on Wed Apr 11, 2012 9:44 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: bi bi pattern in hardest puzzles

Postby David P Bird » Wed Apr 11, 2012 9:40 am

I've edited my previous post.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Re: bi bi pattern in hardest puzzles

Postby ronk » Wed Apr 11, 2012 10:13 am

David P Bird wrote:Each base pair will either see the other pair directly or see the two target cells that hold the same digit pair. They therefore must each contain different digits.

Very good. We don't yet, and may never, have an example of a puzzle where the two base pairs see each other, but that works for me.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: bi bi pattern in hardest puzzles

Postby champagne » Wed Apr 11, 2012 11:39 am

David P Bird wrote:
4) Reported results

It seems the near 80% hit rate that is now being found is using only the first two conditions. When the third condition is added I believe it will fall considerably. Sampling the "Exocets Found" collection I find many of them don't comply with the third condition, but were obviously not excluded.

This makes me wonder what exactly has been changed in the search routine so far.



David

I skipped over that point in a first reading.

What do you mean exactly

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

Re: bi bi pattern in hardest puzzles

Postby daj95376 » Wed Apr 11, 2012 4:52 pm

It was late when I prepared my previous post. I already had David's puzzle open and examining it when I reread champagne's post on the Double Exocet. Instead of preparing a "proof", I was hoping that demonstrating what happens with a real puzzle would be sufficient. Apparently, that didn't come across. Here's the general analysis as I understand it.

First, A Double Exocet pattern that doesn't seem (to me) to provide any eliminations beyond those of the Exocets.

Double Exocet Type 1 ... (any Double Exocet variation other than Type 2)

Code: Select all
 r1c12 are base cells for the first  Exocet, target cells are r2c4,r3c7
 r2c89 are base cells for the second Exocet, target cells are r1c3,r2c6
 +-----------------------------------------------------------------------+
 | abcd   abcd   abcd+W  |     .      .      /   |     .      .      .   |
 |    .      .      /    |  abcd+X    .   abcd+V |     /      .      .   |
 |    .      .      .    |     /      .      .   |  abcd+Y abcd   abcd   |
 |-----------------------+-----------------------+-----------------------|
 Usable eliminations: -V, -W, -X, -Y

Now, a Double Exocet that (to me) seems to provide additional eliminations beyond those of the Exocets.

Double Exocet Type 2

Code: Select all
 r1c12 are base cells for the first  Exocet, target cells are r2c7,r3c4
 r2c89 are base cells for the second Exocet, target cells are r1c6,r2c3
 +-----------------------------------------------------------------------+
 | abcd   abcd      /    |     .      .   abcd+V |     .      .      .   |
 |    .      .   abcd+W  |     /      .      /   |  abcd+Y    .      .   |
 |    .      .      .    |  abcd+X    .      .   |     /   abcd   abcd   |
 |-----------------------+-----------------------+-----------------------|
 Usable eliminations: -V, -W, -X, -Y

From here, we can deduce additional (usable) eliminations associated with the Double Exocet.

Code: Select all
 resulting grid
 +-----------------------------------------------------------------------+
 | abcd   abcd      /    |     .      .   abcd   |     .      .      .   |
 |    .      .   abcd    |     /      .      /   |  abcd      .      .   |
 |    .      .      .    |  abcd      .      .   |     /   abcd   abcd   |
 |-----------------------+-----------------------+-----------------------|

Code: Select all
 assume r1c12=ab, then they perform eliminations:
 r1c6,r2c3<>ab and r1c789,r3c123<>ab
 +-----------------------------------------------------------------------+
 |   ab     ab      /    |     .      .     cd   |   -ab    -ab    -ab   |
 |    .      .     cd    |     /      .      /   |  abcd      .      .   |
 |  -ab    -ab    -ab    |  abcd      .      .   |     /   abcd   abcd   |
 |-----------------------+-----------------------+-----------------------|

Code: Select all
 inverse Exocet logic on r1c6 & r2c3 forces r9c89=cd
 they perform eliminations:
 r2c7,r3c4<>cd and r1c789,r3c123<>cd
 +------------------------------------------------------------------------+
 |    ab     ab      /    |     .      .     cd   | -abcd  -abcd  -abcd   |
 |     .      .     cd    |     /      .      /   |    ab      .      .   |
 | -abcd  -abcd  -abcd    |    ab      .      .   |     /     cd     cd   |
 |------------------------+-----------------------+-----------------------|
 Usable eliminations: r1c789,r3c123<>abcd

What did I miss?
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: bi bi pattern in hardest puzzles

Postby champagne » Wed Apr 11, 2012 6:56 pm

daj95376 wrote:It was late when I prepared my previous post. I already had David's puzzle open and examining it when I reread champagne's post on the Double Exocet. Instead of preparing a "proof", I was hoping that demonstrating what happens with a real puzzle would be sufficient. Apparently, that didn't come across. Here's the general analysis as I understand it.

First, A Double Exocet pattern that doesn't seem (to me) to provide any eliminations beyond those of the Exocets.

Double Exocet Type 1 ... (any Double Exocet variation other than Type 2)

Code: Select all
 r1c12 are base cells for the first  Exocet, target cells are r2c4,r3c7
 r2c89 are base cells for the second Exocet, target cells are r1c3,r2c6
 +-----------------------------------------------------------------------+
 | abcd   abcd   abcd+W  |     .      .      /   |     .      .      .   |
 |    .      .      /    |  abcd+X    .   abcd+V |     /      .      .   |
 |    .      .      .    |     /      .      .   |  abcd+Y abcd   abcd   |
 |-----------------------+-----------------------+-----------------------|

Usable eliminations: -V, -W, -X, -Y

What did I miss?


did you find a way to have a solution with common digits in the 2 bases

if not, they have the same properties at least for eliminations within the band

(I did not)

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

Re: bi bi pattern in hardest puzzles

Postby David P Bird » Thu Apr 12, 2012 9:47 am

Here is a re-write of the revised pattern specifications:
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 JExcoet band). The three cross-lines intersect this band as shown, passing through the object 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) Object pairs must have one cell that contains at least one base candidate (the target cell) and the other that contains none of them (the empty companion cell)
3) Outside the JExocet band each base digit should not be capable of occupying more than two of the cross-line cells in the solution. This is satisfied when all the occurrences of a digit in these external cells, including any that are given or solved, can be covered by no more than two lines.

Code: Select all
Examples
                                v           v                         v   
 . . \ | \ . . | \ . .      . . O | \ . . | O . .     . . \ | \ . . | O . .   
 . . O | O . . | O . . <    . . O | \ . . | O . .     . . O | O . . | O . . <   
 . . \ | \ . . | \ . .      . . O | \ . . | O . .     . . \ | \ . . | O . .   
 . . \ | \ . . | \ . .      . . O | \ . . | O . .     . . \ | \ . . | O . .   
 . . O | O . . | O . . <    . . O | \ . . | O . .     . . \ | \ . . | O . .   
 . . \ | \ . . | \ . .      . . O | \ . . | O . .     . . \ | \ . . | O . .
2 Parallel lines (I)        2 Parallel Lines (II)     2 Orthogonal Lines

An Exocet start pattern satisfies conditions 1) and 2) and is used to identify base candidate sets to analyse further.

A Junior Exocet 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 these two cells.

The pattern is described by identifying the candidates in the base cells and the location of the two target cells
eg (abcd)JExocet:r1c12,r2c4,r3c7

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

champagne firstly let me say how valuable your puzzle collections are as research material, so thank you very much.

Now that the number of patterns found has gone up, I would like to know how well your revised search routine implements each of these conditions.

Points of interest are target cells missing the full digit set and empty cells that aren't singles, as these changes would allow Exocet searches to be made at any time when solving a puzzle, not just at the start.

Do you intend to fully implement condition 3) ?

If you do, then it would be very useful if a representative sample of the hits found for conditions 1) and 2) could be extracted. The search could then be re-run with condition 3) also enabled to see what proportion of all Exocets are JExocets.

The same type of test could then be run to check what proportion of them have the two target cells in sight of each other.

Now finding an Exocet is one thing, but it is only successful when it proves that two cells must hold the same candidates as the base pair. So it would be interesting to discover the success rates achieved using different versions of these conditions.

DPB

[Edits]Specification revised according to various suggestions in later posts.
Last edited by David P Bird on Mon May 21, 2012 8:27 am, edited 7 times in total.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Re: bi bi pattern in hardest puzzles

Postby champagne » Thu Apr 12, 2012 11:56 am

David P Bird wrote:champagne firstly let me say how valuable your puzzle collections are as research material, so thank you very much.
DPB


Thanks to all people having worked to find such puzzles.


David P Bird wrote:Here is a re-write of the revised pattern specifications:
Code: Select all
*-------*-------*-------*
| 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     
| . . S | S . . | S . . |   
*-------*-------*-------*  . = Any candidates
| . . S | S . . | S . . | 
| . . S | S . . | S . . |     
| . . S | S . . | S . . |   
*-------*-------*-------*

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 that contains none of them (the empty companion cell)
3) In the array of 18 cross-line cells each base candidate must be restricted to two lines in at least one vertical or horizontal direction.

DPB


In my code, the targets can not share the same region (row or columns) , what is possible in your map.

Regarding point 3) here is the code checking the 18 'S' positions


Code: Select all
int okich=1;
for(int ich=0;ich<9;ich++) if(digits.On(ich)){
  BF16 wpo1=alt_index.tchbit.el[elp1].eld[ich].b& mask,
    wpo2=alt_index.tchbit.el[elp2].eld[ich].b& mask,
    wpo3=alt_index.tchbit.el[elp3].eld[ich].b& mask,
    wp12=wpo1|wpo2;
  if((!wpo1.f)|| (!wpo2.f)) continue; // one of the target assigned
  if((wp12.bitCount()==1) ) continue;// target is defined (xwing)
  if((wp12.bitCount()-2) ) {okich=0;break; }                       
  wpo3-=wp12;
  if(wpo3.f) {okich=0; break;} // must cover elp3
}
if(!okich) continue;
//now we have an exocet store it for final print


I don't see much room to be out of your constraints.




David P Bird wrote:Here is a re-write of the revised pattern specifications:


Now that the number of patterns found has gone up, I would like to know how well your revised search routine implements each of these conditions.

Points of interest are target cells missing the full digit set and empty cells that aren't singles, as these changes would allow Exocet searches to be made at any time when solving a puzzle, not just at the start.

Do you intend to fully implement condition 3) ?

If you do, then it would be very useful if a representative sample of the hits found for conditions 1) and 2) could be extracted. The search could then be re-run with condition 3) also enabled to see what proportion of all Exocets are JExocets.

The same type of test could then be run to check what proportion of them have the two target cells in sight of each other.

Now finding an Exocet is one thing, but it is only successful when it proves that two cells must hold the same candidates as the base pair. So it would be interesting to discover the success rates achieved using different versions of these conditions.

DPB


What I have in excess in my code is the exclusion of the possibility for the targets to share the same row or column.

When I run the test on the file of my database, where no restriction was applied except that the target must have the full set of digits, I find all exocets but 1.

This means that in my data base, no exocet with all digits in each target has both targets in the same row/column.

I don't say I am covering 100% of your points, but I am not far.

Looking for more does not seem a priority. It would require much more tests.
But I will erase the constraint for the target to be in different rows/columns.

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

PreviousNext

Return to Advanced solving techniques