JExocet Pattern Definition

Advanced methods and approaches for solving Sudoku puzzles

Re: JExocet Pattern Defintion

Postby champagne » Mon May 13, 2013 5:56 am

I made a quick test on a sample file of puzzles coming out of the pattern games 1_127 to see what happens in low ratings.

The lowest SER I got with a positive response, having first solved the singles, was a SER 1.7. This was a severely down graded form of JEXOCET, having no interest

Here is a list of puzzles in the range 7.7 to 9.6 (SER) with a more classical JEXOCET form. I checked the first (rating 7.7), it is a basic JEXOCET.
One appears with a double exocet (I did not check the PM)

The sample is highly biased (pattern game ...) but the ratio of puzzles having a JEXOCET is relatively low in that lot of a little more than 10 000 puzzles, far from the 80% seen for "potential hardest" puzzles


Code: Select all
5..........46..9...8..4..1..2.9.6.....6.7.3.....3...2..1..2..5...9..37..........8; ;1;1;r4c5 r6c5 r2c6 r8c4 158
1..........23..1...4..5..6..6.7.5.....8.6.9.....4...5..8..4..9...1..23..........7; ;1;0;r5c4 r5c6 r6c2 r4c8 123
4..........57..6...1..5..2..8.6.9.....3.7.9.....3...4..2..8..1...7..35..........2; ;1;0;r4c5 r6c5 r2c6 r8c4 124
4..........97..6...1..5..2..8.9.6.....3.7.9.....3...4..2..8..1...7..38..........5; ;1;0;r4c5 r6c5 r2c6 r8c4 124
8..........72..3...1..4..5..2.6.9.....3.7.6.....3...1..5..2..8...6..79..........4; ;1;0;r4c5 r6c5 r2c6 r8c4 158
..1.....2.3...4.5.6...7.8.......9....7..5..3....3.......2.4...1.4.5...9.8.....6..; ;1;5;r4c5 r6c5 r2c4 r8c6 1268
...1.2.....1.3.4...5.6....2..7....89....7....34....7..7....1.6...4.9.8.....5.8...;D;2;44;r4c1 r4c2 r6c5 r5c7 1256;r6c8 r6c9 r5c3 r4c5 1256
1..........23..4...5..6..7..6.1.4.....8.3.1.....8...9..9..2..5...3..82..........7; ;1;0;r4c5 r6c5 r2c6 r8c4 579
9..........47..3...1..2..5..8.9.6.....3.7.6.....3...1..2..4..8...6..74..........5; ;1;0;r4c5 r6c5 r2c6 r8c4 158
..1.....2.3...4.5.6...7.8.......3....7..5..9....9.......2.4...1.4.5...3.8.....6..; ;1;5;r4c5 r6c5 r2c4 r8c6 1268
..4.....7.9...8.1.6...1.2.......3....5..8..9....5.......2.9...4.8.3...5.7.....6..; ;1;5;r4c5 r6c5 r2c4 r8c6 2467
champagne
2017 Supporter
 
Posts: 7334
Joined: 02 August 2007
Location: France Brittany

Re: JExocet Pattern Defintion

Postby denis_berthier » Mon May 13, 2013 6:26 am

Champagne, thanks for this list.

I guess the 4 cells and the series of 3 or 4 digits represent respectively:
the 2 base cells
the 2 target cells (from which the companion cells can easily be deduced)
the 3/4 base digits

Don't you also need to specify the 3 S columns (or at least the 2 of them not cutting the base block) in order to fully define the pattern?

What are the two digits (0 to 5) appearing after the space or the D?
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: JExocet Pattern Defintion

Postby champagne » Mon May 13, 2013 6:59 am

denis_berthier wrote:I guess the 4 cells and the series of 3 or 4 digits represent respectively:
the 2 base cells
the 2 target cells (from which the companion cells can easily be deduced)
the 3/4 base digits


right
Note: in case of twin JEXOCETS, you have more cells in the target

denis_berthier wrote:Don't you also need to specify the 3 S columns (or at least the 2 of them not cutting the base block) in order to fully define the pattern?



"subject to a possible bug in the program", these are supposed to be a JEXOCET pattern. If I got your point the cross lines are then perfectly defined.



denis_berthier wrote:What are the two digits (0 to 5) appearing after the space or the D?


The first digit is the number of JEXOCETS seen
The second one qualify for my process the exocet(s) properties. (3/4 digits, twin/not twin, abi loop potential or not)
champagne
2017 Supporter
 
Posts: 7334
Joined: 02 August 2007
Location: France Brittany

Re: JExocet Pattern Defintion

Postby David P Bird » Mon May 13, 2013 7:05 am

denis_berthier wrote:Hi David,
As you've spent some time on JExocet, you may be able to answer the question I raised in the other thread:

what's the easiest (smallest SER) known puzzle with a JExocet? (or do you have a short list of "easy" or "moderate" ones?)

I'm afraid not. I've voiced my suspicions before that because Champagne has only been sampling the hardest puzzles, his frequencies are higher than would be expected from the general population.

If anyone feels inclined to check this using a fast batch solver approach, I'd be a lot more interested in determining the frequency of the rank-0 partial fish inference pattern which is a necessary component of JExocet. I'd like to see if there are any other inference patterns it can be combined with.

I'll make this observation too: Part of my solving approach is to determine which digits don't appear as givens in each stack and tier. Amongst other things this helps identify potential JE base digit sets as there must be 3 or 4 absent digits in a JE band. It's a convenient once-only check.
David P Bird
2010 Supporter
 
Posts: 1043
Joined: 16 September 2008
Location: Middle England

Re: JExocet Pattern Defintion

Postby denis_berthier » Mon May 13, 2013 7:13 am

champagne wrote:
denis_berthier wrote:Don't you also need to specify the 3 S columns (or at least the 2 of them not cutting the base block) in order to fully define the pattern?

"subject to a possible bug in the program", these are supposed to be a JEXOCET pattern. If I got your point the cross lines are then perfectly defined

I'm not questioning your program or the fact that there are indeed JExocets in the puzzles, with the base cells, target cells and base digits specified after the puzzle.
What I mean is that 2 of the S columns (and BTW also the 2 cross lines for each of the base digits) are not specified in your output. But that's OK. The given data are enough to deduce the eliminated candidates.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: JExocet Pattern Defintion

Postby denis_berthier » Wed May 15, 2013 3:37 am

David P Bird wrote:
denis_berthier wrote:Hi David,
As you've spent some time on JExocet, you may be able to answer the question I raised in the other thread:

what's the easiest (smallest SER) known puzzle with a JExocet? (or do you have a short list of "easy" or "moderate" ones?)

I'm afraid not. I've voiced my suspicions before that because Champagne has only been sampling the hardest puzzles, his frequencies are higher than would be expected from the general population.


champagne wrote:The sample is highly biased (pattern game ...) but the ratio of puzzles having a JEXOCET is relatively low in that lot of a little more than 10 000 puzzles, far from the 80% seen for "potential hardest" puzzles



Speaking of frequencies, is there an estimate of the ratio JExocet/Exocet (in the "potential hardest" list if there's nothing less biased)?
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: JExocet Pattern Defintion

Postby logel » Thu May 16, 2013 5:05 pm

Hi David
Yet another discussion rule vs pattern.

Inventing/finding new rules seem to be an endless story without any prospect to be completed.

If I summarize the discussion correctly, the JExocet fit to a precise rule definition now.

The JE+ looks like some hybrid, neither rule nor pattern. I would say its a pattern where some parts are determined by rules and some are not. So its some kind of rule fragment. This is an interesting idea and can maybe applied to other scenarios too. But without saying for what purpose it is intended, it will provoke controversy.

a) If you intend to include JE+ in the standard tool box of rules, all sub-rules for the variants have to be worked out the same way as for JE. Otherwise you cannot determine their solving strength. On top of that confusing discussions arise about what is real JE+ or only JE+ alike.

b) If you instead intend to use JE+ in a pragmatic way to find some more eliminations you can't get otherwise, its completely OK. In this case I would rather start with assuming the potential targets TRUE and perform a limited number of local eliminations. If you find a contradiction there is a hit. Theoretical arguments about complexity are missing the point in this case.

I always like clear goals.
User avatar
logel
 
Posts: 57
Joined: 29 April 2012
Location: Germany

Re: JExocet Pattern Defintion

Postby David P Bird » Thu May 16, 2013 8:06 pm

Hi Logel

If you have followed the exchanges between Denis and I you will appreciate that I consider that there are two roles for patterns 1) to provide instant eliminations and 2) to provide inferences that can be assembled together Lego fashion into a more complex elimination patterns. JExocet falls into both those categories because once the basic eliminations have been made, it can be re-used later to show that the two target cells must hold different digits.

So regarding which option do I choose out of your two alternatives, the answer is both!

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.

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.

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.
David P Bird
2010 Supporter
 
Posts: 1043
Joined: 16 September 2008
Location: Middle England

Re: JExocet Pattern Defintion

Postby blue » Thu May 16, 2013 8:21 pm

Hi logel,

I'm (now) noting David's post, which has materialized while I've been editing this one.
FWIW, I agree with what he's saying.

logel wrote:Hi David
Yet another discussion rule vs pattern.

Inventing/finding new rules seem to be an endless story without any prospect to be completed.

If I summarize the discussion correctly, the JExocet fit to a precise rule definition now.

The JE+ looks like some hybrid, neither rule nor pattern.

This is very confusing.
JE and JE+ are both well defined patterns with associated elimination rules.

Maybe a better elucidation of the differences between JE+ and JE is called for (?). The basic idea is that one target cell, can be replaced by two, as long as there is a non-base digit that is forced to occupy one of the two cells, after considering where it can be placed in the "S" column, associated with the target pair. There's a possible variation where rather then considering where it can go in the column, one considers where it can go in the box containing the target pair. Whether that's supposed to be covered by the definition, I can't say.

This is the main thing I wanted say: (ignore the rest, if you like)

logel wrote:b) If you instead intend to use JE+ in a pragmatic way to find some more eliminations you can't get otherwise, its completely OK. In this case I would rather start with assuming the potential targets TRUE and perform a limited number of local eliminations. If you find a contradiction there is a hit.

I invite you to try this approach for a few JE (not JE+) instances, and report the findings (perhaps) in your "Universal Elimination Pattern" thread. (Maybe here will be fine as well).
Try to find a general pattern of logic.
I'm curious whether you might come up with something that differs fundamentally, from a particular "general pattern of logic" that I discussed in PMs with Denis.

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

Re: JExocet Pattern Defintion

Postby denis_berthier » Fri May 17, 2013 6:18 am

blue wrote:
logel wrote:Yet another discussion rule vs pattern.
[...]If I summarize the discussion correctly, the JExocet fit to a precise rule definition now.
The JE+ looks like some hybrid, neither rule nor pattern.

This is very confusing. JE and JE+ are both well defined patterns with associated elimination rules.


I fully agree with Blue.
I don't know if my re-writing of David's definition of JE and not that of JE+ played a part in the difference you make in your post, but you should know that the only reason for me was a matter of time. JE+ is a pattern and resolution rule in exactly the same sense JE is.
As for David, in spite of our different views on many topics, our ideas of a pattern are much closer than he thinks.


BTW, I don't consider I took any noticeable part in the definition of JE. My re-writing was merely cosmetic. So I think I can make a short history of JE. I think this is the ideal example for showing the difference between a real pattern/rule (JExocet) and something else (Exocet).
- years ago, Allan Barker found some common configuration of candidates allowing some elimination(s) in a few hard puzzles;
- Champagne dug into this; he defined the "Exocet", part of which is a partial pattern (not enough to justify any eliminations) and part of which is a verification procedure (much in the spirit of your approach); he spent much time popularising it and finding it in hard puzzles; he undoubtedly played a major role in this history;
- however, for many people, the Exocet definition was not satisfactory;
- on the Programmer's Forum, Blue proposed a logical description that could turn this procedure into a real pattern;
- after tweaking Blue's definition, David finally proposed the JE (and JE+) pattern(s).

JExocet is less general than Exocet (how much less remains an open question as we currently have no estimate of JE's presence neither in champagne's hardest list nor for easier puzzles).
But, contrary to Exocet, you can be shown a JE in a grid and you can immediately say "yes, I see it" and conclude "I can eliminate these candidates" - without checking thousands of possible truth value assignments (what you call permutations) to the relevant set of candidates. Well, I feel like paraphrasing something Blue said somewhere.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: JExocet Pattern Defintion

Postby David P Bird » Fri May 17, 2013 7:26 am

Blue wrote:Maybe a better elucidation of the differences between JE+ and JE is called for (?). The basic idea is that one target cell, can be replaced by two, as long as there is a non-base digit that is forced to occupy one of the two cells, after considering where it can be placed in the "S" column, associated with the target pair. There's a possible variation where rather then considering where it can go in the column, one considers where it can go in the box containing the target pair. Whether that's supposed to be covered by the definition, I can't say.

With the JE definition as it stands there are occasions where it's possible to have a choice of target cells on different cross lines in one particular box. This produces two candidate JE patterns to check, but an instance where both alternative cross lines comply with the partial fish requirements has never yet come to light. If additionally these two target options contain a locked candidate, I think we then get to the JE+ circumstances you're considering. However, then proof of the eliminations wouldn’t depend on the existence of the locked candidate.

Is that right? If not a diagram would help.

Denis Berthier wrote:JExocet is less general than Exocet (how much less remains an open question as we currently have no estimate of JE's presence neither in champagne's hardest list nor for easier puzzles).

In JE or JE+ if the partial fish requirement isn't met the case is closed, but for not for Exocet which continues to hunt for justification using templates and/or inference following. What would be interesting to me is how often this extra work is required, and how often it produces a hit.

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

Re: JExocet Pattern Defintion

Postby champagne » Fri May 17, 2013 8:15 am

David P Bird wrote:
If additionally these two target options contain a locked candidate, I think we then get to the JE+ circumstances you're considering. However, then proof of the eliminations wouldn’t depend on the existence of the locked candidate.

Is that right? If not a diagram would help.

Regards David


Hi David,

For me the logic of the exocet is requiring a locked candidate in that situation.
The basic for an Exocet are

if any of the base digit must be in the target, then
the target can only contain the base digits
the solution has the same couple of digits in the base and the target.


to extend that rule to a twin exocet, you need the locked candidate.

David P Bird wrote:
Denis Berthier wrote:JExocet is less general than Exocet (how much less remains an open question as we currently have no estimate of JE's presence neither in champagne's hardest list nor for easier puzzles).

In JE or JE+ if the partial fish requirement isn't met the case is closed, but for not for Exocet which continues to hunt for justification using templates and/or inference following. What would be interesting to me is how often this extra work is required, and how often it produces a hit.

Regards David


this is very easy to do, but requires cycles. The way things are going, I see no reason to change my priorities trying to answer to that question. I prefer to go ahead with investigations in the "potential hardest" area
champagne
2017 Supporter
 
Posts: 7334
Joined: 02 August 2007
Location: France Brittany

Re: JExocet Pattern Defintion

Postby denis_berthier » Fri May 17, 2013 9:16 am

champagne wrote:
David P Bird wrote:
Denis Berthier wrote:JExocet is less general than Exocet (how much less remains an open question as we currently have no estimate of JE's presence neither in champagne's hardest list nor for easier puzzles).

In JE or JE+ if the partial fish requirement isn't met the case is closed, but for not for Exocet which continues to hunt for justification using templates and/or inference following. What would be interesting to me is how often this extra work is required, and how often it produces a hit.
this is very easy to do, but requires cycles. The way things are going, I see no reason to change my priorities trying to answer to that question. I prefer to go ahead with investigations in the "potential hardest" area

There is a big expectation about the frequency of JExocet. The question is about how much the scope of a general non-pattern-based procedure has to be restricted when one wants to define a real pattern (or real patterns, JE and JE+) inspired by it.
You can continue to enlarge the list of puzzles having Exocets, but as we know that part of these do not correspond to real patterns, this seems rather pointless.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: JExocet Pattern Defintion

Postby David P Bird » Fri May 17, 2013 9:30 am

Hi Champagne,
Champagne wrote:
For me the logic of the exocet is requiring a locked candidate in that situation.
The basic for an Exocet are

if any of the base digit must be in the target, then
the target can only contain the base digits
the solution has the same couple of digits in the base and the target.


to extend that rule to a twin exocet, you need the locked candidate.

I'm confident that you and I will agree to the JE requirements in any particular case, and it is the choice of words that is the problem here. I was only considering the requirements for the basic eliminations of non-base digits from the target cells. As we know, the pattern in the primary band carries a number of extra inferences that can be used to advantage in combination with other circumstances.

When twin patterns arise (which have never been discussed here) it's a bonanza. For a start all the fin eliminations for four partial fish can be made, and then there are a bunch of others in the main band. However, the pattern elements needed to make the basic eliminations still remain the same, which together I believe, force the locked digits you mention.

You wrote:this is very easy to do, but requires cycles. The way things are going, I see no reason to change my priorities trying to answer to that question. I prefer to go ahead with investigations in the "potential hardest" area

I accept that, just as writing an illustrated guide to the pattern is low on my priorities (particularly regarding the attitudes towards my contributions in another section of this forum in recent times). I'll be very interested in anything you find.

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

Re: JExocet Pattern Defintion

Postby blue » Fri May 17, 2013 9:48 am

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


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

I don't look for twins, specifically. I only find both, when they exist.

I had forgotten that you use the "twin" to refer to the case with an AHS target pair.
I was thinking "double exocet" when I wrote that. Sorry for the confusion.
(It looks like David just made the same mistake that I did).
I wrote something to look for exocets with AHS targets too, but I made it too general (> 2 cells, allowed).
It took a long time to run, and it found a lot more than I had anticipated ... worthless cases with
no eliminations ... and very little in the 2-cell area.
I trashed the code, and I don't really remember what I tried in the way of "speedups".
I would guess that I looked for two target cells that contained the base cell digits, and then
looked at whether forcing one of them, would produce a hidden n-tuple that didn't exist before.
If that's the case, then the one target cell can be extended to a set that includes the 'n' cells from
the "would be" n-tuple. When the positions for the target cells are unrestricted, you'ld probably
also need to make sure that if you extended each cell to an AHS cell set, that the two cell sets
didn't overlap, and (whether it was two AHS or one) that neither set included a base cell.
(Does that sound right ?).

David P Bird wrote:If additionally these two target options contain a locked candidate, I think we then get to the JE+ circumstances you're considering. However, then proof of the eliminations wouldn’t depend on the existence of the locked candidate.

Is that right? If not a diagram would help.

The locked candidate is needed, in the proof.
It's important that after the cells that would contain the AHS digit(s) are counted, only two target cells remain -- one for each base cell value.
Is that enough ? ... I'm not really sure that a diagram would help.

Regards,
Blue.
Last edited by blue on Fri May 17, 2013 11:06 am, edited 1 time in total.
blue
 
Posts: 975
Joined: 11 March 2013

PreviousNext

Return to Advanced solving techniques