Pattern-based classification of (hard) puzzles

Advanced methods and approaches for solving Sudoku puzzles

Can a JExocet be seen as a Subset? - classification

Postby denis_berthier » Sun May 12, 2013 5:26 am



Can a JExocet be seen as a Subset or a gSubset? - classification of JExocet




blue wrote:I would be curious if you can place the JExocet patterns in the "chains" or "subset" category.

Now that the JExocet definition is clear, I can try to tackle this question.

I'll use the definition and notations here http://forum.enjoysudoku.com/jexocet-pattern-defintion-t31133-12.html. There may appear extensions of this core pattern, but that shouldn't change the following remarks.

Let p (= 3 or 4) be the number of base digits.


1) Can a JExocet be considered as a Subset (or a gSubset)?

Suppose we try to see the JExocet as a Subset or as a gSubset (according to my general definitions in "Pattern-Based Constraint Satisfaction - PBCS").

Then it is somehow obvious that the following 2+3p [= 11 or 14] CSP-variables/2D-cells must be part of the pattern:
- the two B rc-cells
- the 3p cn-cells: for each of the 3 S columns ci and for each of the p base digits nj, the cn-cell cinj
At this point, the situation is rather simple, as these 2+3p CSP-variables are pairwise disjoint.

It is also obvious that the following must be part of the transversal sets:
- for each of the base digits nj, the rn constraint r1nj (r1 is the row holding the B cells)
- for each of the base digits ni and for each of the two rows ri and r'i in which it can be present in the S cells, the rn constraint rini / r'ini.
This makes up 3p transversal sets.

We also have to deal with the Q and R pairs. As long as we are concerned only with base digits, we can discard the companion cells. There remains only one possibility, i.e. taking two more transversal sets: the two rc constraints defined by the two target cells. As the complement of the intersections of these constraints with the base CSP-variables is exactly the set of non-base digits in the target cells, it would be OK for the targets of a Subset or gSubset.
We now have 2+3p transversal sets and they are pairwise disjoint.

Is therefore everything OK for a Subset[2+3p]?

Nope. The base candidates that, by the general JExocet definition, are allowed in the intersection of block b1 and column c3 are not yet covered by these transversal sets.
Note: in a first version of this post, I had forgotten that there may be base digits in the intersection of block b1 and column 3. But Blue (many thanks to him) pointed it out in a PM.

If this was the only problem, we could consider a special case and try to conclude that
- any JExocet with 3 or 4 base digits and no base digit in the intersection of the base block and the S column intersecting it can be considered as a Subset[11 or 14].
By replacing the p rn-constraints r1nj by p bn-constraints b1nj, we would get similarly:
- any JExocet with 3 or 4 base digits and no base digit in the intersection of the base row and the two S columns not intersecting the base block can be considered as a Subset[11 or 14].
(I don't know if such special cases have already been considered.)

But even this doesn't work. Indeed, if it worked, the Subset rule would also eliminate (in the first case) all the base digits in the first row non-S columns outside the B cells, which is obviously incorrect.


At this point, we must also notice that the condition of having no base digit in the companion cells has not yet been taken into account. We should therefore introduce two more CSP-variables corresponding to these cells. But then, we would also have to introduce (9-p) or 2(9-p) rn transversal sets [depending on whether they are in the same row or nor] to cover them. Finally, we would get many more transversal sets than CSP-variables.



I'm fully aware that this is not a full proof that a JExocet cannot be seen as a Subset or as a gSubset, but if there is some smarter way of proving it, it still eludes me. As I'm a little lazy about exotic patterns on Sundays, it's enough to deter me from looking longer for a proof that a JExocet can be considered as a Subset or as a gSubset.

To answer the second part of Blue's question, trying to see a JExocet as some kind of chain doesn't seem much more promising.



2) Classification of the JExocet

The above analysis isn't completely negative and that's why I posted it. Even though I couldn't prove that a JExocet is a Subset or a gSubset, the analysis shows that this pattern involves (at least) 13 or 16 CSP-variables.

As a result, in a systematic search for patterns of increasing size, JExocets would appear very late.
As the complexity of a systematic search for Subsets (and a fortiori for general patterns) increases very fast with their size (much faster than for whips or braids), it is probably out of reach of ordinary computers and JExocets can only be found if patterns with special properties (instead of all patterns) are looked for.


Finally, I wonder:
1) what's the easiest known puzzle (say, with smallest SER) having a JExocet? Did anyone already investigate this?
2) has anyone tried to express JExocet in Allan's formalism? What's the base set? Can any fixed "rank" be assigned to it?
3) how would it appear in logel's approach?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can a JExocet be seen as a Subset? - classification

Postby champagne » Sun May 12, 2013 9:39 am

denis_berthier wrote:

Can a JExocet be seen as a Subset or a gSubset? - classification of JExocet
...


2) Classification of the JExocet

The above analysis isn't completely negative and that's why I posted it. Even though I couldn't prove that a JExocet is a Subset or a gSubset, the analysis shows that this pattern involves (at least) 13 or 16 CSP-variables.

As a result, in a systematic search for patterns of increasing size, JExocets would appear very late.
As the complexity of a systematic search for Subsets (and a fortiori for general patterns) increases very fast with their size (much faster than for whips or braids), it is probably out of reach of ordinary computers and JExocets can only be found if patterns with special properties (instead of all patterns) are looked for.


Finally, I wonder:
1) what's the easiest known puzzle (say, with smallest SER) having a JExocet? Did anyone already investigate this?
2) has anyone tried to express JExocet in Allan's formalism? What's the base set? Can any fixed "rank" be assigned to it?
3) how would it appear in logel's approach?


I understand here that in the CSP view the JEXOCET is nearly impossible to produce.

However, on a practical view,
a) it is a very common pattern in what appear as the "potential hardest" puzzles using a chain oriented set of rules
b) it is easy to detect for a manual player.
c) Many of these puzzles collapses when that pattern is applied (with the associated "abi loop" pattern)

May-be this proves that the CSP analysis has some limits.

answering your point 1)
I did not explore low ratings, but some examples have been shown with rating around SER 10.0
I'll try to find a pattern game data base stored (out of the recent games) giving EXOCETS to try to cover lower ratings.

answering your point 2)
The first EXOCET is directly coming form Allan Barker analysis of the puzzle "fata morgana".here and here
In that Truths/Links analysis, we find 6 triple points (link mode) attached to 2 sets.
The rank 0 area is not so easy to describe.
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Re: Can a JExocet be seen as a Subset? - classification

Postby denis_berthier » Sun May 12, 2013 3:22 pm

champagne wrote:I understand here that in the CSP view the JEXOCET is nearly impossible to produce.
[...]May-be this proves that the CSP analysis has some limits.

Totally wrong interpretation of my last post:
- writing JExocet as a resolution rule is very easy (now that there is a clear definition); what I say is, it is (apparently) not feasible to write it as a special kind of resolution rule: chain or Subset; but there can be many other types of resolution rules;
- my analysis of complexity in the above post has nothing to do with a CSP view or any other specific view; it has to do with systematic search along patterns of increasing logical complexity; it would apply to Allan's or logel's approaches as well, if they ever cared about considering ALL the patterns they define;
- once written, the JExocet is easy to find provided that you are not looking for all the logically simpler patterns before it.



champagne wrote:However, on a practical view,
a) it is a very common pattern in what appear as the "potential hardest" puzzles using a chain oriented set of rules
b) it is easy to detect for a manual player.
c) Many of these puzzles collapses when that pattern is applied (with the associated "abi loop" pattern)

This is a very biased personal view:
- the "potential hardest" represent less than 1 in 30,000,000 puzzles (unbiased stats); they will never appear in any newspaper; calling this "very common" is at least unexpected; but you have so much submerged yourself in the hardest topic that you've forgotten the "normal" puzzles;
- you invoke a "practical view" but you don't know if there are JExocets in moderate puzzles (say with SER < 9.3), the only ones that any normal player will ever see;
- only a handful of people ever heard of Exocet or JExocet;
- the puzzles "collapse" to less hard ones that remain nevertheless beyond reach of most players (I've shown this for the sk-loop and I have no doubt that it is not different for the JExocet).



champagne wrote:The first EXOCET is directly coming form Allan Barker analysis of the puzzle "fata morgana".here and here
In that Truths/Links analysis, we find 6 triple points (link mode) attached to 2 sets.
The rank 0 area is not so easy to describe.

OK, I understand that there's currently no description of JExocet in Allan's view.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can a JExocet be seen as a Subset? - classification

Postby champagne » Sun May 12, 2013 4:09 pm

denis_berthier wrote:
champagne wrote:The first EXOCET is directly coming form Allan Barker analysis of the puzzle "fata morgana".here and here
In that Truths/Links analysis, we find 6 triple points (link mode) attached to 2 sets.
The rank 0 area is not so easy to describe.

OK, I understand that there's currently no description of JExocet in Allan's view.



Once more the discussion is slipping in a dangerous slope, so I shall not comment your last post except on that point

If you read carefully the references, you will see that in "fata morgana" we have a JEXOCET. In that specific case, as in most of the JEXOCET with 3 digits, the puzzle really collapses applying the "abi loop" pattern;

For sure, Allan did not name that pattern, but found it in several puzzles including Golden Nugget.
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Re: Pattern-based classification of (hard) puzzles

Postby JasonLion-Admin » Tue May 14, 2013 11:35 am

A conversation about The Sudoku grey zone has been moved to a new topic.
User avatar
JasonLion-Admin
Site Admin
Site Admin
 
Posts: 72
Joined: 17 April 2010
Location: Silver Spring, MD, USA

Classification and frequency of patterns/rules

Postby denis_berthier » Wed May 15, 2013 5:58 am




Classification and frequency of patterns/rules


As an illustration of the importance of the classification of patterns when one tries to estimate their frequency, I'll take the following example, the simplest in the short list of JExocets provided by Champagne here: http://forum.enjoysudoku.com/jexocet-pattern-defintion-t31133-37.html
Here is the puzzle:
5..........46..9...8..4..1..2.9.6.....6.7.3.....3...2..1..2..5...9..37..........8
It is mentioned as having a "classical JExocet form" with:
- base cells r4c5 r6c5
- target cells r2c6 r8c4
- and 3 base digits 158
This JExocet can therefore (potentially) eliminate candidates (n2r2c6 n2r8c4 n3r2c6 n3r8c4 n4r2c6 n4r8c4 n6r2c6 n6r8c4 n7r2c6 n7r8c4 n9r2c6 n9r8c4). In practice, most of them are eliminated during initialisation, as being in direct contradiction with a given. There remain the following 3: n2r2c6 n4r8c4 n7r2c6.

If we don't take the JExocet into account, we get the following resolution path (in W4):

Hidden Text: Show
Code: Select all
*****  SudoRules 16.2 based on CSP-Rules 1.2, config: W-SFin   *****
naked-pairs-in-a-block: b9{r7c7 r8c8}{n4 n6} ==> r9c8 <> 6, r9c8 <> 4, r9c7 <> 6, r9c7 <> 4, r8c9 <> 6, r8c9 <> 4, r7c9 <> 6, r7c9 <> 4
hidden-pairs-in-a-block: b1{r1c2 r3c1}{n6 n9} ==> r3c1 <> 7, r3c1 <> 3, r3c1 <> 2, r1c2 <> 7, r1c2 <> 3
finned-x-wing-in-columns: n3{c2 c8}{r9 r2} ==> r2c9 <> 3, r8c1 <> 6
biv-chain[2]: b1n6{r1c2 r3c1} - r7n6{c1 c7} ==> r1c7 <> 6
biv-chain[2]: r3n3{c3 c9} - b9n3{r7c9 r9c8} ==> r9c3 <> 3
swordfish-in-columns: n3{c2 c5 c8}{r9 r2 r1} ==> r9c1 <> 3, r2c1 <> 3, r1c9 <> 3, r1c3 <> 3
swordfish-in-rows: n6{r3 r6 r7}{c1 c9 c7} ==> r9c1 <> 6, r1c9 <> 6
biv-chain[3]: c8n9{r5 r9} - r7n9{c9 c6} - r3n9{c6 c1} ==> r5c1 <> 9
biv-chain[3]: c5n9{r1 r9} - r9c8{n9 n3} - r1n3{c8 c5} ==> r1c5 <> 8, r1c5 <> 1
biv-chain[3]: b8n6{r8c5 r9c5} - c5n9{r9 r1} - r1c2{n9 n6} ==> r8c2 <> 6
biv-chain[3]: r9c8{n3 n9} - c5n9{r9 r1} - r1n3{c5 c8} ==> r2c8 <> 3
biv-chain[3]: c5n9{r1 r9} - r9n6{c5 c2} - r1c2{n6 n9} ==> r1c6 <> 9
hidden-triplets-in-a-row: r1{n3 n6 n9}{c5 c8 c2} ==> r1c8 <> 8, r1c8 <> 7
whip[2]: c8n7{r4 r2} - b1n7{r2c1 .} ==> r4c3 <> 7
hidden-triplets-in-a-row: r1{n3 n6 n9}{c5 c8 c2} ==> r1c8 <> 4
biv-chain[3]: r9n3{c2 c8} - r1c8{n3 n6} - c2n6{r1 r9} ==> r9c2 <> 7
finned-x-wing-in-columns: n7{c2 c8}{r2 r6} ==> r6c9 <> 7
whip[1]: b6n7{r4c8 .} ==> r4c1 <> 7
biv-chain[3]: r9n3{c2 c8} - r1c8{n3 n6} - c2n6{r1 r9} ==> r9c2 <> 5, r9c2 <> 4
whip[3]: b5n4{r5c6 r6c6} - c2n4{r6 r8} - c8n4{r8 .} ==> r5c9 <> 4
whip[3]: r4n4{c9 c1} - c8n4{r4 r8} - b7n4{r8c1 .} ==> r6c7 <> 4, r6c9 <> 4
whip[3]: c5n9{r9 r1} - r1c2{n9 n6} - r9n6{c2 .} ==> r9c5 <> 5, r9c5 <> 1, r9c6 <> 9
whip[4]: r4n4{c9 c1} - c1n3{r4 r7} - r7n6{c1 c7} - r8c8{n6 .} ==> r5c8 <> 4
whip[1]: b6n4{r4c7 .} ==> r4c1 <> 4
whip[4]: c8n7{r2 r4} - c8n4{r4 r8} - c8n6{r8 r1} - b3n3{r1c8 .} ==> r3c9 <> 7
whip[4]: r2c8{n7 n8} - r5c8{n8 n9} - r9c8{n9 n3} - c2n3{r9 .} ==> r2c2 <> 7
... easy end

Note that the finned-x-wing, swordfish, biv-chains, ... are special cases of whips[<= 3]

Considering the recent post in which I showed that a JExocet involves at least 13 or 16 CSP-variables (depending on whether it has 3 or 4 base digits), we could already conclude that it would never be found in this puzzle if, in the rules hierarchy, JExocet was classified at a place consistent with this high count.


However, one can still want to see what happens if we use it nevertheless. So, let's give it the highest priority and apply it right at the start. Do we get a simpler solution? NO. Here is the new resolution path.
As JExocet is currently not programmed in SudoRules, I use a special rule that allows me to make "simulated eliminations" of any list of candidates. Only the effective ones are displayed (here only 3 in the list of 12 potential ones).

Hidden Text: Show
Code: Select all
*****  SudoRules 16.2 based on CSP-Rules 1.2, config: W-SFin   *****
Simulated elimination of n4r8c4, n7r2c6, n2r2c6
naked-pairs-in-a-block: b9{r7c7 r8c8}{n4 n6} ==> r9c8 <> 6, r9c8 <> 4, r9c7 <> 6, r9c7 <> 4, r8c9 <> 6, r8c9 <> 4, r7c9 <> 6, r7c9 <> 4
hidden-pairs-in-a-block: b1{r1c2 r3c1}{n6 n9} ==> r3c1 <> 7, r3c1 <> 3, r3c1 <> 2, r1c2 <> 7, r1c2 <> 3
x-wing-in-rows: n2{r2 r8}{c1 c9} ==> r9c1 <> 2, r3c9 <> 2, r1c9 <> 2 ;;; <<<<<<<<<<<<<<
finned-x-wing-in-columns: n3{c2 c8}{r9 r2} ==> r2c9 <> 3, r8c1 <> 6
biv-chain[2]: b1n6{r1c2 r3c1} - r7n6{c1 c7} ==> r1c7 <> 6
biv-chain[2]: r3n3{c3 c9} - b9n3{r7c9 r9c8} ==> r9c3 <> 3
swordfish-in-columns: n3{c2 c5 c8}{r9 r2 r1} ==> r9c1 <> 3, r2c1 <> 3, r1c9 <> 3, r1c3 <> 3
swordfish-in-rows: n6{r3 r6 r7}{c1 c9 c7} ==> r9c1 <> 6, r1c9 <> 6
biv-chain[3]: c8n9{r5 r9} - r7n9{c9 c6} - r3n9{c6 c1} ==> r5c1 <> 9
biv-chain[3]: c5n9{r1 r9} - r9c8{n9 n3} - r1n3{c8 c5} ==> r1c5 <> 8, r1c5 <> 1
biv-chain[3]: b8n6{r8c5 r9c5} - c5n9{r9 r1} - r1c2{n9 n6} ==> r8c2 <> 6
biv-chain[3]: r9c8{n3 n9} - c5n9{r9 r1} - r1n3{c5 c8} ==> r2c8 <> 3
biv-chain[3]: c5n9{r1 r9} - r9n6{c5 c2} - r1c2{n6 n9} ==> r1c6 <> 9
hidden-triplets-in-a-row: r1{n3 n6 n9}{c5 c8 c2} ==> r1c8 <> 8, r1c8 <> 7
whip[2]: c8n7{r4 r2} - b1n7{r2c1 .} ==> r4c3 <> 7
hidden-triplets-in-a-row: r1{n3 n6 n9}{c5 c8 c2} ==> r1c8 <> 4
biv-chain[3]: r9n3{c2 c8} - r1c8{n3 n6} - c2n6{r1 r9} ==> r9c2 <> 7
finned-x-wing-in-columns: n7{c2 c8}{r2 r6} ==> r6c9 <> 7
whip[1]: b6n7{r4c8 .} ==> r4c1 <> 7
biv-chain[3]: r9n3{c2 c8} - r1c8{n3 n6} - c2n6{r1 r9} ==> r9c2 <> 5, r9c2 <> 4
whip[3]: b5n4{r5c6 r6c6} - c2n4{r6 r8} - c8n4{r8 .} ==> r5c9 <> 4
whip[3]: r4n4{c9 c1} - c8n4{r4 r8} - b7n4{r8c1 .} ==> r6c7 <> 4, r6c9 <> 4
whip[3]: c5n9{r9 r1} - r1c2{n9 n6} - r9n6{c2 .} ==> r9c5 <> 5, r9c5 <> 1
naked-triplets-in-a-row: r9{c2 c5 c8}{n3 n6 n9} ==> r9c6 <> 9  ;;; <<<<<<<<<<<<<<
whip[4]: r4n4{c9 c1} - c1n3{r4 r7} - r7n6{c1 c7} - r8c8{n6 .} ==> r5c8 <> 4
whip[1]: b6n4{r4c7 .} ==> r4c1 <> 4
whip[4]: c8n7{r2 r4} - c8n4{r4 r8} - c8n6{r8 r1} - b3n3{r1c8 .} ==> r3c9 <> 7
whip[4]: r2c8{n7 n8} - r5c8{n8 n9} - r9c8{n9 n3} - c2n3{r9 .} ==> r2c2 <> 7
... easy end

As you can see, there's almost no difference. Not only is the W rating unchanged, but the resolution path itself is almost unchanged (differences are shown by the ";;; <<<<<<<<<<<<<<" sign).


What can we conclude? When one tries to estimate the frequency of a pattern or a resolution rule, at least three conditions of the estimate should be clearly stated:
- on which collection of puzzles it is based
- how the pattern/rule is classified in some hierarchy of patterns/rules (i.e. which rules are applied before it)
- whether what is being talked about is the pattern or the rule, i.e. whether the impact of the mere presence of the pattern on the rating of a puzzle is taken into account (e.g. is the puzzle still considered as "having the pattern" if applying the associated rule has no impact or no significant impact?)

You think all this is obvious? I fully agree. Why then is it (almost) never applied?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Classification and frequency of patterns/rules

Postby champagne » Wed May 15, 2013 10:25 am

denis_berthier wrote:- whether what is being talked about is the pattern or the rule, i.e. whether the impact of the mere presence of the pattern on the rating of a puzzle is taken into account (e.g. is the puzzle still considered as "having the pattern" if applying the associated rule has no impact or no significant impact?)


I shall not discuss whether a manual player would have solved that puzzle using the exocet property.
In case of a positive response, the exocet would likely have been found in that position

Code: Select all
A     B     C     |D     E    F     |G     H     I     
5     69    127   |1278  1389 12789 |248   34678 247   
127   37    4     |6     1358 12578 |9     378   257   
69    8     237   |257   4    2579  |256   1     23567 
-------------------------------------------------------
13478 2     13578 |9     158  6     |1458  478   1457   
1489  459   6     |12458 7    12458 |3     489   1459   
14789 4579  1578  |3     158  1458  |14568 2     145679
-------------------------------------------------------
34678 1     378   |478   2    4789  |46    5     39     
248   456   9     |1458  1568 3     |7     46    12     
247   34567 257   |1457  1569 14579 |12    39    8     



but in that case, the manual player would have used the "abi loop" pattern (refused by denis because it uses uniqueness properties) and immediately concluded that the soulution for the base is 58.
(this is a very common status in exocets with 3 digits)
with now found 58 in the base and the target, we have still easy (an well known) eliminations linked to the exocet, but still with the uniqueness property.

IMO if we use exocets, we must do it in the appropriate way.
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Re: Classification and frequency of patterns/rules

Postby denis_berthier » Wed May 15, 2013 11:11 am

champagne wrote:but in that case, the manual player would have used the "abi loop" pattern [...] and immediately concluded that the soulution for the base is 58.

This argument is totally irrelevant to the topic under discussion.
The topic was evaluating the impact of JExocet, not JExocet+"abi loop", or JExocet+ any other convenient rule.
This is also totally unrelated to whether one accepts rules based on the assumption of uniqueness.


champagne wrote:IMO if we use Exocets, we must do it in the appropriate way.

As JExocet (not Exocet, which is not a pattern) is totally independent of the assumption of uniqueness, nothing allows to say that the appropriate way of using it requires to add this assumption.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Classification and frequency of patterns/rules

Postby champagne » Wed May 15, 2013 11:30 am

denis_berthier wrote:[
As JExocet (not Exocet, which is not a pattern) is totally independent of the assumption of uniqueness, nothing allows to say that the appropriate way of using it requires to add this assumption.


just years of experience from many players starting with "ttt" years ago
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Re: Classification and frequency of patterns/rules

Postby denis_berthier » Wed May 15, 2013 11:51 am

champagne wrote:
denis_berthier wrote:[As JExocet (not Exocet, which is not a pattern) is totally independent of the assumption of uniqueness, nothing allows to say that the appropriate way of using it requires to add this assumption.
just years of experience from many players starting with "ttt" years ago

Observing that some rule B (say abi loop) can sometimes/often be applied after some rule A (say JExocet) doesn't mean that A must systematically be be stuck to B and to additional assumptions irrelevant to the validity of A.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Classification and frequency of patterns/rules (continued)

Postby denis_berthier » Thu May 16, 2013 10:37 am



Classification and frequency of patterns/rules (continued)



This is a continuation of my previous post "Classification and frequency of patterns/rules"
http://forum.enjoysudoku.com/pattern-based-classification-of-hard-puzzles-t30493-74.html
where I showed in particular that the mere presence of a JExocet pattern may have little effect on the resolution path of a puzzle.
I didn't have much time to analyse many examples, but the first five in the list mentioned in that post lead to the following results:

Code: Select all
#1    SER = 7.7    W = 4     JE-W = 4
#2    SER = 8.8    W = 4     JE-W = 4
#3    SER = 9.0    W = 6     JE-W = 6
#4    SER = 9.2    B = 9     JE-B = 8
#5    SER = 9.3    W = 17    JE-W = 16

where:
- W (resp. B) is the W (resp. B) rating
- JE-W (resp. JE-B) is the W (resp. B) rating when all the target candidates of the JExocets have been artificially eliminated at the start. This is the most favourable situation for the JExocet - much too favourable considering its complexity.

In #4, the B instead of the W rating is used (it is one of the very rare cases in which they differ).


From such a small sample, no final conclusion can be drawn, but it nevertheless raises serious questions about the power of JExocets in the "grey zone" (http://forum.enjoysudoku.com/the-sudoku-grey-zone-t31143.html).
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: What's a pattern ?

Postby logel » Thu May 16, 2013 10:17 pm

Hi Denis
Your post contains some really fundamental stuff. Seems that we do not agree on important points.
So I try to argue as careful as possible.
denis_berthier wrote:
What's a pattern?

The discussion here and in the other thread inspired me a few comments about the notion of a pattern.

Resolution rule vs pattern
Should one make a distinction between a resolution rule and a pattern ?

As (apart from the trivial Singles rule) a resolution rule can always be written as: Pattern => candidate = False, there's no deep point in distinguishing (as logel does) a pattern from a resolution rule. Said otherwise, trying to define the general concept of a pattern is basically the same thing as trying to define the general concept of a resolution rule.

At first rules and patterns are in my view completely different categories. I regard a rule as a class definition for pattern objects and patterns as instances of rule classes. Of course all rule classes must comply to the basic sudoku rules. So patterns consists of candidates with their basic properties (e.g. linked to A) and other special properties releated to the corresponding rule.
Classed naturally can have sub-classes and super-classes, so patterns can relate to many rule classes. Your braid-class is a very large one and super-class of many traditional rule classes (you name it subsumption). This is nice for verifying solvability, but for a particular puzzle the relation to a sub-class has more benefits because its more specific. So here again its important what is your intention.
My intention to define universal patterns was simply to have a super-class covering as much as possible, but still containing enough information to define a useful size. I was really a bit surprised that the mimimality condition already ensures that all such patterns have a presentation as set of baselines (not unique as we now know). It seems that this property is very fundamental for sudoku puzzles.

denis_berthier wrote:Proof of an elimination
We now come to the heart of the question: how, considering an instance of a resolution rule / a pattern, can one known that it justifies an elimination?

In my view, this should be "obvious", i.e. it should require no extra steps of logical reasoning and no extra validation procedure.
This condition is satisfied by all the classical patterns (Subsets, reversible chains, Fish and their finned/mutant variants).
It is also satisfied by all the chains, whips, braids, Subsets, g-Subsets, generalized whips and braids I've introduced.
As I mentioned previously, all the known patterns can be classified into two broad families (Subsets vs chains), none of which can be reduced to the other.
Patterns I've called exotic, such as sk-loops, do not fall out of this classification: an sk-loop is a (very special) g-Subset.

Now, logel proposes a more general view of a pattern, in which an elimination may have to be justified by a complex procedure: try all the sets of truth value assignments to all the candidates of the pattern and show that all of them are incompatible with the target.
In case, the pattern belongs to either of the above two families, it is easy to find a simplified version of this procedure, based on the structure of the pattern. Maybe this would be easy also for a third family of patterns, still to be invented.
However, for any pattern not in these families, the only general way of doing so is setting to False all the candidates in the pattern linked to the target, and then for each CSP-variable of the base set* trying to set its value to each of the remaining candidates. As this is not a 2-SAT problem, there's no a priori bound on complexity. This means that, in spite of logel's unproved claims to the contrary, once the pattern (target included) is given to the player, he may still have a hard job in proving an elimination.
As for me, I would not accept this as a pattern-based solution.

harsh words ... but I am very relaxed about the validation issue.
The main difference is that the rules you refer to require no extra steps of logical reasoning. That means the these rules carry the validation in the class definition. So the validation is on class level where the universal validation is on instance level. Although this is less desirable its correct. The possible complexity does not affect the correctness either. I do also not claim that a player has to perform the validation, I only state that its possible in principle. I could also resort to the cheap trick to define classes with one instance each, but with no gain. The universal validation is just a fallback version that always works.
I would rather say that one can determine rules from the bare candidate set by moderate reengineering. Especially chains are easy to detect. I do this quite often if I don't understand a complicated pattern logic. A hard job is somthing different.

So do you want to tell me that in case I forgot about the rule origin of the pattern candidates, the pattern is not a valid elimination any more? Be serious.
denis_berthier wrote:*: supposing that logel finally admits the base set as part of his definition - otherwise one would first have to find it, thus requiring still more computations.

A have a draft of an alternative definition, which is slightly less general and moves the validation to class level. But I do not want to present a green banana again. The difference is tiny and will you not make more happy.
denis_berthier wrote:So, finally, what's a pattern?
I don't know (except that it has to be defined based on the basic concepts of Sudoku) and I don't care much about a general definition.
I know a few very powerful "chain patterns", "Subset patterns", I'm ready to accept any new "X pattern" provided that the associated elimination is obvious once an instance of it and a target are given (I don't even require that the target be easy to find - although this may be debatable). Perhaps, logel's overly general definition will eventually lead him to new patterns, but this is not yet the case.

The main issue is comparability, and comparison relies on common properties.
denis_berthier wrote:In the meanwhile, I wonder:
- why should a player care about a general definition that he cannot use without a computer to check if an elimination is valid?
- why should a mere reader of a resolution path care about it if he cannot check every step without a computer?

Just a few remarks. An aspect of complexity of solving is always kept in the dark. You always stress the point that a braid definition is not a procedure. OK. But nevertheless a procedure is needed to produces a valid braid[14] pattern and you have to check thousands if not millions of queues without result and never shown. So in some way the final braid[14] contains this complexity. This is a more fair comparison to the effort of validation.
A computer cannot do anything else than I can, only faster. Saves my time.
denis_berthier wrote:Once more, we meet the idea that the goals of resolution must play a major role in defining our concepts.

Yes.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Pattern-based classification of (hard) puzzles

Postby logel » Thu May 16, 2013 10:51 pm

David P Bird wrote:As you're aware I think intuitively rather than mathematically or in terms of formal logic al theory, but childlike questions can sometimes be great eye openers regarding our un-stated conditions and assumptions.

'Daddy, are you saying that everything's made up out of atoms?'
'Yes sweetie'
'What about shadows?'

I like this. One should be careful about everything.
David P Bird wrote:Your justification for refusing to assume uniqueness, (because publishers never claim this), don't carry over to proven unique sub-puzzles. Your reasons there just appear to be that they're inconvenient to you. To my simple mind it appears that your constantly combing inferred constraints from mixed chain and subset classes of inference patterns to reach conclusions, and I still fail to see a solid reason for excluding 'proven uniqueness' as a further class.

The inconvenience has a name: lost comparability.

I used plains and plain pairs/triple as predefined sub-puzzles. Unique states of these sub-puzzles appear quite frequently and the uniqueness is also proven at this point. But still each false candidate has a smaller elimation pattern inside the sub-puzzle, usually of different size. So the sub-puzzle itself has no useful size to compare with other eliminations.
If you accept unique sub-puzzles as elimination, you might also accept sub-puzzles with multiple solutions where some of the candidate have stable values. That was the leading idea when I used plains as sub-puzzles. If you dont care about size and comparison this justifies eliminations.
A more serious danger appears when you use larger sub-puzzles. The solutions gets more and more trivial because the complexity inside the sub-puzzle is no more visible.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Pattern-based classification of (hard) puzzles

Postby denis_berthier » Fri May 17, 2013 7:04 am

logel wrote:
denis_berthier wrote:As (apart from the trivial Singles rule) a resolution rule can always be written as: Pattern => candidate = False, there's no deep point in distinguishing (as logel does) a pattern from a resolution rule. Said otherwise, trying to define the general concept of a pattern is basically the same thing as trying to define the general concept of a resolution rule.

At first rules and patterns are in my view completely different categories. I regard a rule as a class definition for pattern objects and patterns as instances of rule classes.

Changing the vocabulary can make a screen of smoke but doesn't make new ideas.


logel wrote:
denis_berthier wrote:We now come to the heart of the question: how, considering an instance of a resolution rule / a pattern, can one known that it justifies an elimination?
In my view, this should be "obvious", i.e. it should require no extra steps of logical reasoning and no extra validation procedure.
This condition is satisfied by all the classical patterns (Subsets, reversible chains, Fish and their finned/mutant variants).
It is also satisfied by all the chains, whips, braids, Subsets, g-Subsets, generalized whips and braids I've introduced.
As I mentioned previously, all the known patterns can be classified into two broad families (Subsets vs chains), none of which can be reduced to the other.
Patterns I've called exotic, such as sk-loops, do not fall out of this classification: an sk-loop is a (very special) g-Subset.

Now, logel proposes a more general view of a pattern, in which an elimination may have to be justified by a complex procedure: try all the sets of truth value assignments to all the candidates of the pattern and show that all of them are incompatible with the target.
In case, the pattern belongs to either of the above two families, it is easy to find a simplified version of this procedure, based on the structure of the pattern. Maybe this would be easy also for a third family of patterns, still to be invented.
However, for any pattern not in these families, the only general way of doing so is setting to False all the candidates in the pattern linked to the target, and then for each CSP-variable of the base set* trying to set its value to each of the remaining candidates. As this is not a 2-SAT problem, there's no a priori bound on complexity. This means that, in spite of logel's unproved claims to the contrary, once the pattern (target included) is given to the player, he may still have a hard job in proving an elimination.
As for me, I would not accept this as a pattern-based solution.

The main difference is that the rules you refer to require no extra steps of logical reasoning.

Exactly: no extra step of logical reasoning and no hidden checking procedure. A resolution rule is self-contained; it is a complete description of its condition pattern and of the elimination it justifies; moreover the elimination can be proven on the basis of the condition pattern and the Sudoku axioms (without any reference to any specific instantiation). As you have read my books, you can see that the proofs of all the resolution rules are almost obvious once the condition pattern is clearly defined.


logel wrote:So do you want to tell me that in case I forgot about the rule origin of the pattern candidates, the pattern is not a valid elimination any more? Be serious.

The rule is proven once for all.
Seeing an instantiation of a rule in a PM is another matter. Of course, if you don't see it, you won't use it to do the elimination.


logel wrote:
denis_berthier wrote:So, finally, what's a pattern?I don't know (except that it has to be defined based on the basic concepts of Sudoku) and I don't care much about a general definition.
I know a few very powerful "chain patterns", "Subset patterns", I'm ready to accept any new "X pattern" provided that the associated elimination is obvious once an instance of it and a target are given (I don't even require that the target be easy to find - although this may be debatable). Perhaps, logel's overly general definition will eventually lead him to new patterns, but this is not yet the case.

The main issue is comparability, and comparison relies on common properties.

Wrong. I already answered this.
There are two types of comparisons:
- along a generalisation hierarchy: xy-chains < nrc-chains < nrct-chains < whips < braids < g-braids ...
- via subsumption theorems, bearing on eliminations: e.g. whips and Subsets can be compared, in spite of having no common super-rule.
You consider only the first type.


logel wrote:
denis_berthier wrote:In the meanwhile, I wonder:
- why should a player care about a general definition that he cannot use without a computer to check if an elimination is valid?
- why should a mere reader of a resolution path care about it if he cannot check every step without a computer?

Just a few remarks. An aspect of complexity of solving is always kept in the dark. You always stress the point that a braid definition is not a procedure. OK. But nevertheless a procedure is needed to produces a valid braid[14] pattern and you have to check thousands if not millions of queues without result and never shown. So in some way the final braid[14] contains this complexity. This is a more fair comparison to the effort of validation.

You make a total confusion between finding an instance of a pattern/rule in an actual PM and justifying the elimination once the instance is found.



logel wrote:I was really a bit surprised that the mimimality condition already ensures that all such patterns have a presentation as set of baselines (not unique as we now know). It seems that this property is very fundamental for sudoku puzzles.

logel wrote:
denis_berthier wrote:*: supposing that logel finally admits the base set as part of his definition - otherwise one would first have to find it, thus requiring still more computations.

A have a draft of an alternative definition, which is slightly less general and moves the validation to class level. But I do not want to present a green banana again. The difference is tiny and will you not make more happy.

As the difference is about a fundamental vice in your original definition, I wouldn't call it tiny. I think it should be your priority.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Pattern-based classification of (hard) puzzles

Postby logel » Mon May 20, 2013 10:48 pm

Hi Denis
denis_berthier wrote:
logel wrote:At first rules and patterns are in my view completely different categories. I regard a rule as a class definition for pattern objects and patterns as instances of rule classes.

Changing the vocabulary can make a screen of smoke but doesn't make new ideas.

On last try to clear the fog.
denis_berthier wrote:We now come to the heart of the question: how, considering an instance of a resolution rule / a pattern, can one known that it justifies an elimination?
In my view, this should be "obvious", i.e. it should require no extra steps of logical reasoning and no extra validation procedure.
logel wrote:The main issue is comparability, and comparison relies on common properties.

Wrong. I already answered this.
There are two types of comparisons:
- along a generalisation hierarchy: xy-chains < nrc-chains < nrct-chains < whips < braids < g-braids ...
- via subsumption theorems, bearing on eliminations: e.g. whips and Subsets can be compared, in spite of having no common super-rule.
You consider only the first type.

Comparing rules (class types) is one thing and comparing patterns (instances) is another. I am less interested in rule comparison.
= = =
As an illustration a take a very concrete pattern example related to an S2-braid example prior in the thread.
Code: Select all
98.7.....7.6...8...54......6..8..3......9..2......4..1.3.6..7......5..9......1..4 # 7658;GP;H1521

S2-braid[14]: b9n3{r9c8 r8c9} - b9n6{r8c9 r789c7} - b9n8{r8c9 r7c789} - {n8r7c5 NP: b8{r7c5 r8c4}{n2 n4}} - r7c6{n2 n9} - r9c4{n9 n3} - {n3r5c4 HP: b5{r5c6 r6c5}{n3 n6}} - b5n7{r5c6 r4c456} - r4c8{n7 n4} - r5c7{n4 n5} - r4c9{n5 n9} - r6c7{n9 .} ==> r9c8 <> 5

Consider this pattern object in form of a material list: ( boolean variables (candidates) in nrc notation )
Code: Select all
CORE={548,398,389,698,697,687,689,657,667,898,889,878,879,875,876,275,284,475,484,276,294,976,994,394,354,364,356,365,656,665,765,756,745,746,748,749,448,457,557,549,949,967} ( unordered set of candidates )
TARGET=598
LINKS={ Cx NAND Cy = true, where Cx,Cy are all pairings of candidates from CORE+TARGET } ( unordered set of equations )
BASE={ C1 OR C2 OR ... OR Cn = true, where Cx from CORE, all members of CORE occur in at least one equation } ( unordered set of equations )

This particular pattern is an elimination because it contains enough information to prove TARGET = false. This pattern notation is not meant to be human readable, to guard against any misunderstanding.
There are various ways to prove the elimination:
(1) Build all permuations of CORE+TARGET variables that comply to the equations LINKS+BASE. Assert that 598 = false with all permutations. This is also not human readable and not meant that any "player" should perform it. I am also well aware of the complexity of this procedure growing with the number of candidates. But of course the list of all cases is a valid proof.
The pattern matches the universal definition too. After removing any candidate variable along with the associated equations there exists a permutation with TARGET = true.
(2) Set TARGET = true and build an elimination sequence until a contradiction occurs. This T&E procedure needs secondary recursion levels if only single eliminations are applied. This procedure is also of some complexity in the general case, but is always computable. Using rules (BI+Pair) requires a prior proof of these rules. Its a matter of personal taste regarding such T&E sequence as human readable. Its a proof anyway.
The interpretation of an elimination pattern as contradiction sequence is rather inconvient because its not unique for components and order.
(3) What about S2-braids? My position is that the above pattern can also be interpreted as S2-braid. Therefore one needs a procedure(sic!) to check if the pattern is complying with any of the braid rules or not. And only after this check is positive and adds order information to the pattern, "no extra steps of logical reasoning" are necessary. The checking procedure is of non-trivial complexity too. This (hidden?) procedure nowhere appears in your pages and seems to be mixed into the finding process. Thats why I mentioned it.
(4) There are even more interpretations, Allans base-cover model, etc.

So any rules add type along with additional information to the pattern object.
denis_berthier wrote:.... moreover the elimination can be proven on the basis of the condition pattern and the Sudoku axioms (without any reference to any specific instantiation)

That is not much different from (1) or (2). So what we are discussing?
The motivation for a universal pattern definition was not a magic method for "new" or "better" eliminations, but to exclude obscure elimination constructions. So minimality is the key idea. Non-minimal patterns like plains or other partial puzzles would preclude comparison of patterns from the start, or can make the solution steps trivial with large "eliminations".

Two questions:
a) Do you regard the pattern example (CORE+TARGET+LINKS+BASE) as elimination? yes/no.
b) Do you regard the pattern example as S2-braid? yes/no (maybe why)
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

PreviousNext

Return to Advanced solving techniques