Pattern-based classification of (hard) puzzles

Advanced methods and approaches for solving Sudoku puzzles

Re: Pattern-based classification of (hard) puzzles

Postby logel » Sun Feb 10, 2013 2:24 pm

Hi Denis, thanks for the quick answer

denis_berthier wrote:So, let me first make a few remarks and ask a few questions to clarify some of your definitions.

First of all, the expression "all patterns" and its variants ("all patterns with 5 CSP variables", "all patterns restricted to a single plane [or number]") is not well defined. When you write:
logel wrote: P1 is defined by all patterns restricted to a single plane of the sudoku grid.
P1[N1] e.g. is the plane of numbers equal 1 containing all fish patterns with number 1
,
this is somehow contradictory. We don't know if we should read the first or the second line, i.e. whether P1[N] is the set of standard Fish (2nd line) or the set of g-fish [Franken and Mutant Fish] (first line).


OK, take the first line. The other was only meant as an explanation. I was not aware of the restricted use of the term "fish". Distinguishing "fish" and "g-fish" has not relevance in this context.

denis_berthier wrote:Secondly, the number of "CSP planes" (of types n, r, c, b) cannot be used to measure the size of a pattern (you don't say so, but it may be implicitly understood in some places). You must count the number of CSP variables (of types rc, rn, cn, bn). Thus, a fish on number 1 doesn't have size 1 but 2, 3 or 4.
This will be important when you need to measure the size of the patterns you use in T&E(X).


I never said that I intended to measure the size of patterns. My results just show solvability. Pattern size restrictions are not implemented, but may be an interesting extension. Even if you limit size of patterns in T&E(X) level 1, the size of the resulting level 0 pattern is unlimited.

denis_berthier wrote:
logel wrote:Class T&E(S+BI+Pair+T5): solving 17159, remaining 39289
T5 is defined as: all Patterns with exactly 5 CSP variables
Because of the basic construction of sudoku, T5 is always a single number pattern with two rows, two colums and a box link.

Allowing patterns with 1, 2 or 5 but not with 3 or 4 CSP variables seems quite arbitrary.
Moreover, I think "S+BI+Pair+T5" doesn't have the confluence property - and therefore this class is not well defined. When a pattern P built on 5 CSP variables is destroyed by some eliminations before being applied, what remains may have fewer variables; as it is not in your class, it doesn't allow the elimination allowed by P.
However, this doesn't have any impact on the sequel.


Ups, I think I misunderstood the term "CSP variable". BTW it would be nice to have a dictionary of sudoku terms.
Besides the typo "T5" should read "L5", I am using the term line for myself that I thought to be a synonym for CSP variable and is apparently not.

A line is the set of undecided candidates of one of the 324 constraints. So a line is a cell or row/col/box of a fix number.
A plane is the set of undecided candidates that share the same number or row/col/box.

I think the number planes are often called floor in sudoku discussions. They seem to be more important than the others, because of the extra box constraints.

BI pattern consist of two crossing lines and pairs of two by two crossing lines. L5 patterns are rings of five lines. So the above class is actually confluent. You are right that it does not really fit to the others, but I used it for more pragmatic reasons. I wanted to sort out the less hard puzzles quickly.

denis_berthier wrote:
logel wrote:Class T&E(S+BI+P1[NBRC]+P2[NBRC]) : remaining 317 unsolved puzzles, mainly residing in the top 3000 of the list
P2[1,2] e.g. contains all patterns restricted to the combined planes P[1] and P[2].
P2[N] denotes all multi-fish patterns in all the 36 pairings of two number planes.
That means patterns of this class all work in pairs of CSP planes, that do not overlap.

This seems to confirm my above reading: this should be written as T&E(P1[N]+P1[ B]+P1[R]+P1[C]+P2[N]+P2[ B]+P2[R]+P2[C]).
Can you confirm?

Yes. But for the P2 its even more clear to write P2[NN] etc. Plane sets P2[NB] or P[RB] are also possible, but are not in the above class.
denis_berthier wrote:This class should solve all the puzzles classified by Champagne as multi fish. Can you confirm?
Can you say more about the (new ???) multi-row, multi-column and multi-block patterns?
Can you say more about the maximum size of the patterns (e.g. multi-fish) needed to reach this result ("only 317 unsolved")?

I am now very careful about answering the "multi fish" question. I did not find a definition on Champagne's web pages. But the answer is probably yes.

Of course I expected the most eliminations in the number plane sets.
From figures of actually applied P2 eliminations in the above class I found:
50% in P2[NN]
25% in P2[BB]
10% in P2[RR]
10% in P2[CC]

The high value for box pairs was a bit of a surprise. Additionally many of P2[RR] and P2[CC] eliminations com from row/col pairs residing in the same box tower. So locality seems to be important.
Eliminations on plane connections are rather rare. These eliminations are the only ones with targets outside the members of the plane set.

All plane sets of used classes work with non-intersecting planes. With P3 there are lots of non-intersecting plane sets, especially P3[BBR] or P3[BBC), I did not yet investigate.
Experiments with two intersecting planes shows very little results.
One can understand this. Parallel planes like P2[NN] or P3[NNN] e.g. cut a 3D block out of the sudoku universe, the others don't.

denis_berthier wrote:It would be interesting to give these 5 puzzles explicitly.

Code: Select all
1.......9.5....2....87...4.2...3......48.5....8.6...7...6..4.5.........1....9.3..;11.80;11.80;7.90;elev;11;21;21
.....6..94...8.2.....7...1.2.9...8....4.3.9...6.....5.3.8.4.......5......7...1...;11.80;1.20;1.20;elev;4;31;21
....56.8...71.....6.....4.......85...3......29...4..6..1.7.......2.....38...9..5.;11.70;11.70;2.60;elev;30;55;21
98.........79..6......5....7..4..9....6.3..2......5..1.7.5..8....4.1..5......2..3;11.60;11.60;2.60;GP;H11;118;22
1......8..567..........3..6..7..5.......2.9...3.6....4....9..1..4.5....78.....2..;11.40;11.40;2.60;elev;246;415;21

denis_berthier wrote:One important point for me is the maximum size of the patterns involved in your results (i.e. the number of CSP variables they rely on)


Some more comments on pattern sizing and more definitions I use.

A general elimination is a set of candidates including the target(s) and a set of connecting lines forming a network where the targets are FALSE in all valid permutations.
That means, no specific structure, just a contradiction of the target to the rest of the set. Because of this there is no useful size property.

In a minimal elimination all of the candidates besides the targets are absolutely necessary. These ones are those we usually talking about and they have properties that allow counting size.

- A minimal elimination has a minimal set of lines where all candidates of those lines are members of the set. These active lines seem to correspond to CSP variables (Confirm ?) and give a basis for counting size.
- All other lines in the elimination network are passive lines.

Taking the number of active lines and ignoring the other properties is not my favorite size definition.

The framework producing the above result uses general eliminations. The basic idea is as simple as stupid. I construct all permutations of the plane sets I intend to use. Subsequent operations are performed on this data.
There is nothing really NEW of this approach, only the focus is on another point. I think Allan Barker used permutation sets of limited size to pragmatically support or speed-up search in his solver.
My intention was not directed to pragmatic solving but to completeness. Getting size information requires more effort.

Of course I can reduce any specific general elimination to a minimal one for each of the targets. These will be of different size and not unique usually.
The implemented process works with greedy progression. Each contradiction on T&E(1) will be immediately applied on level 0. Therefore one can miss easily eliminations of smaller size in terms of CSP variables.

The whole subject is still interesting and I hope to present more details soon.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Pattern-based classification of (hard) puzzles

Postby denis_berthier » Mon Feb 11, 2013 2:24 am

logel wrote:
denis_berthier wrote:First of all, the expression "all patterns" and its variants ("all patterns with 5 CSP variables", "all patterns restricted to a single plane [or number]") is not well defined. When you write:
logel wrote: P1 is defined by all patterns restricted to a single plane of the sudoku grid.
P1[N1] e.g. is the plane of numbers equal 1 containing all fish patterns with number 1
,
this is somehow contradictory. We don't know if we should read the first or the second line, i.e. whether P1[N] is the set of standard Fish (2nd line) or the set of g-fish [Franken and Mutant Fish] (first line).
OK, take the first line. The other was only meant as an explanation. I was not aware of the restricted use of the term "fish". Distinguishing "fish" and "g-fish" has not relevance in this context.


AFAIK, fish is generally used for "pure" fish, with no blocks (but I guess you will always find someone to say the contrary); the distinction is important if you consider the symmetry and super-symmetry relationships.
"g-fish" is not a standard term, it is my theoretical interpretation of the (more or less well defined) class of Franken and Mutant Fish. Indeed, I define g-Subsets in general as the natural generalisation of Subsets when you consider g-candidates instead of mere candidates. The resolution power of g-Subsets is much greater than that of Subsets.

For the understanding of your concrete results about T&E(X), it is therefore important to know precisely the patterns you use in your various X's.
Consider your claim about T&E(S+BI+P1[N]+P1[ B]+P1[R]+P1[C]): "Although this class is very powerful, it's clearly not enough".
If you consider only fish, there's nothing new; I have shown long ago that T&E(S)=T&E(S4) is not enough.
But it is an interesting new (although not really surprising) result if you consider g-fish, especially if you accept them to have unrestricted size. Indeed, I know no solver implementing g-fish of unrestricted sizes, let alone T&E(S4 + g-fish of all sizes).
So, what you're saying is, T&E(S4 + g-fish of all sizes) is not enough to solve all the puzzles. Can you confirm?
[Added: I made the remarks in this paragraph with the idea that BI=Basic Interactions. As it appears later it is not what you meant, they lose their purpose.]



logel wrote:
denis_berthier wrote:Secondly, the number of "CSP planes" (of types n, r, c, b) cannot be used to measure the size of a pattern (you don't say so, but it may be implicitly understood in some places). You must count the number of CSP variables (of types rc, rn, cn, bn). Thus, a fish on number 1 doesn't have size 1 but 2, 3 or 4.
This will be important when you need to measure the size of the patterns you use in T&E(X).

I never said that I intended to measure the size of patterns. My results just show solvability. Pattern size restrictions are not implemented, but may be an interesting extension. Even if you limit size of patterns in T&E(X) level 1, the size of the resulting level 0 pattern is unlimited.


Yes, but as your general question is "find a class X of patterns such that T&E(X) solves all the (known) puzzles", knowing exactly what you put in X is important.
The situation is similar to the BpB classification: there are puzzles that cannot be solved by T&E(B6), i.e. by B6-braids of any global length, but all the known puzzles can be solved by T&E(B7), i.e. by B7-braids of unrestricted global length.



logel wrote:I think I misunderstood the term "CSP variable". BTW it would be nice to have a dictionary of sudoku terms.

There used to be Sudopedia, but it has been lost after being vandalised. The partial copy present on this website includes no history (in particular, the initial vague definition of T&E by Ruud has been vandalised and the present one has been plagiarised from mine). The problem is, there are different views of Sudoku solving and forums (at the time when they were active) have mostly been fights about undefined words (such as T&E).

"CSP variable" is not a standard Sudoku term. Sudoku is (obviously) a CSP problem. When it is considered as such (which is rarely the case on Sudoku forum), it has 81 "natural" CSP variables, r1c1, r1c2, ..., r9c9: one is asked to find a value for each of them such that these values satisfy the four types of constraints. I also call them the rc CSP variables.
However, in CRT and PBCS, formalising the Extended Sudoku Board I introduced in HLS, I have introduced the additional rn, cn and bn CSP variables - for a total of 324. In the Sudoku jargon, which usually does not refer at all to the Constraint Satisfaction world [even though it uses (often incorrectly) the word "constraint"], these correspond to sis ("strong inference sets").



logel wrote: I am using the term line for myself that I thought to be a synonym for CSP variable and is apparently not.
A line is the set of undecided candidates of one of the 324 constraints. So a line is a cell or row/col/box of a fix number.


This sense of "line" does correspond to "CSP variable" - although in CSP one wouldn't confuse them with "constraints": constraints are relations that sets (or only pairs in binary CSPs like Sudoku) of CSP variables must satisfy.


logel wrote:I think the number planes are often called floor in sudoku discussions. They seem to be more important than the others, because of the extra box constraints.
A plane is the set of undecided candidates that share the same number or row/col/box.


"line" is often used as a synonym of "unit", i.e. row or column or block. You'd better avoid it.
"floor" is also used to mean a set of three rows cutting the same blocks. You'd better avoid it also.


logel wrote:BI pattern consist of two crossing lines and pairs of two by two crossing lines. L5 patterns are rings of five lines. So the above class is actually confluent. You are right that it does not really fit to the others, but I used it for more pragmatic reasons. I wanted to sort out the less hard puzzles quickly.

I thought you used "BI" for Basic Interactions. Indeed, if this is not the case, I don't understand your definitions: what does "two crossing lines and pairs of two by two crossing lines" mean? I'll wait a clarification for more comments.
rings ?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Pattern-based classification of (hard) puzzles

Postby logel » Tue Feb 12, 2013 3:42 pm

denis_berthier wrote:For the understanding of your concrete results about T&E(X), it is therefore important to know precisely the patterns you use in your various X's.
Consider your claim about T&E(S+BI+P1[N]+P1[ B]+P1[R]+P1[C]): "Although this class is very powerful, it's clearly not enough".
If you consider only fish, there's nothing new; I have shown long ago that T&E(S)=T&E(S4) is not enough.
But it is an interesting new (although not really surprising) result if you consider g-fish, especially if you accept them to have unrestricted size. Indeed, I know no solver implementing g-fish of unrestricted sizes, let alone T&E(S4 + g-fish of all sizes).
So, what you're saying is, T&E(S4 + g-fish of all sizes) is not enough to solve all the puzzles. Can you confirm?

Confirmed. I am surprised that this should be a new result.
Note that this is not done by constructing all kinds of g-fish (like the ultimate fish guide). How this is assured will get clear with the example below, I hope.
denis_berthier wrote:
logel wrote:I think I misunderstood the term "CSP variable". BTW it would be nice to have a dictionary of sudoku terms.

There used to be Sudopedia, but it has been lost after being vandalised. The partial copy present on this website includes no history (in particular, the initial vague definition of T&E by Ruud has been vandalised and the present one has been plagiarised from mine). The problem is, there are different views of Sudoku solving and forums (at the time when they were active) have mostly been fights about undefined words (such as T&E).

"CSP variable" is not a standard Sudoku term. Sudoku is (obviously) a CSP problem. When it is considered as such (which is rarely the case on Sudoku forum), it has 81 "natural" CSP variables, r1c1, r1c2, ..., r9c9: one is asked to find a value for each of them such that these values satisfy the four types of constraints. I also call them the rc CSP variables.
However, in CRT and PBCS, formalising the Extended Sudoku Board I introduced in HLS, I have introduced the additional rn, cn and bn CSP variables - for a total of 324. In the Sudoku jargon, which usually does not refer at all to the Constraint Satisfaction world [even though it uses (often incorrectly) the word "constraint"], these correspond to sis ("strong inference sets").

OK, the fog is disappearing. So finally the term CSP variable is the same as the term line I am using. I prefer the term line rather than unit that sounds too arbitrary to me.
Precise terms are necessary basis of useful communication. Sudopedia is dead. Fighting about undefined terms is wasted time and energy. What a mess.

denis_berthier wrote:
logel wrote:BI pattern consist of two crossing lines and pairs of two by two crossing lines. L5 patterns are rings of five lines. So the above class is actually confluent. You are right that it does not really fit to the others, but I used it for more pragmatic reasons. I wanted to sort out the less hard puzzles quickly.

I thought you used "BI" for Basic Interactions. Indeed, if this is not the case, I don't understand your definitions: what does "two crossing lines and pairs of two by two crossing lines" mean? I'll wait a clarification for more comments.
rings ?

This mystery is unraveled easily. Although only meant as a side note, its worth a detailed explanation. The picture below shows abstractly a box-row-interaction, an x-wing-pair and a L5-ring in a number plane before any targets can be assigned.
Code: Select all
... ... ...   ..c ... d..   0XX bbb Xbb
... ... ...   ..c ... d..   Xee ... c..
... ... ...   aaX aaa Xaa   Xee ... c..

aaa ... ...   ..c ... d..   a.. ... c..
XXX bbb bbb   ..c ... d..   a.. ... c..
aaa ... ...   ..c ... d..   a.. ... c..

... ... ...   bbX bbb Xbb   Xdd ddd Xdd
... ... ...   ..c ... d..   a.. ... c..
... ... ...   ..c ... d..   a.. ... c..

I did some analysis of how elimination patterns developed before and after producing targets. The pair e.g has two rows (a) and (b) and two columns (c) and (d), these are the four lines I mentioned. You can call my view on pairs pair candidate if you prefer. This structure becomes active when either both rows or both column lines become active (i.e. all candidates besides (X) are cleared). You seem to prefer to recognize a pair only in active states, resulting in two kinds, that is all the difference. The two possible active states are closely related, so I see them as one structure. After such a pair got active and the resulting targets are cleared, a ring of four candidates remains that is completely inert.
Even more interesting is the L5-ring on the right. The ring is a candidate for two-sting-kite, skyscraper and finned something. The ring gets active if any two lines not directly connected get active. The resulting target is the opposite corner, so the ring destructs itself and none of the other four potential states can ever occur. So the L5-ring groups five closely related elimination patterns together. Larger ring structures can contain sub-rings and show soon scary complexity. Any elimination pattern can be interpreted as active state of a candidate elimination pattern (I invented this term just right now) constructed of even and odd rings. The odd rings behave substantially different than the others.
A pair (candidate) may stem from other bigger structures. It could be a triple or something with a pair ALS, etc. The final container structure of all fish is of course the plane itself.

Back to the main topic:
The method finding plane (or plane set) related eliminations is simply to construct all valid permutations of true candidates and observe their number relative to candidates. If such number drops to zero, it follows that a pattern exists that creates a contradiction with this candidate if assumed TRUE. If no permutation contains the candidate, its clearly FALSE or more precisely "not part of any solution" if we do not assume uniqueness. This is conceptually simple, but needs implementation with reasonable performance.

Here a medium difficult puzzle as an example:
Code: Select all
900000001030007040006000200000023000040500070080704000100000600070400050000000009

Every solver will find the box pairs in box 1 and 9 and then some L7 ring for 4's or 7's (3 active lines, 4 passive lines == 3 CSP variables your count) continued by some singles clearing the remaining 4's and 7's.
Fine, but the fact that the permutation complexity of the plane set N4+N7 is zero from the beginning slips through unnoticed. There exists exactly one possible valid permutation. Furthermore my solver shows 44 different L7 eliminations for various 4's and 7's to choose from. But all are derived from a singular fact. Of course one can say that the max size of elimination pattern is 3 CSP vars, but that does not cover the fact that all decay sequences of the plane N4+N7 require at least two pairs and one L7. So what is the size of the decay sequence?

The next step is even more striking. After clearing N4+N7 the plane triple N3+N5+N8 becomes active and again the total permutation count is 1. That leads to 24 more elimination targets. There are hundreds of more ore less similar decay sequences of the plane set. Of course you can find a maximum size property of the decay sequences, but I personally would be more interested in something like a least effort sequence (unprecise).
The permutation count of a candidate relative to a plane set ensures only the possibility of elimination because a plane set is a non-minimal elimination. So the associated minimal eliminations of each target can be derived only by reduction of the plane set. Again you get a big number of alternative eliminations that go back to a singular fact.
In a number of subsequent steps (four with P3[NNN]) the puzzle is solved directly without T&E(1).
For a comparison with other solvers: xsudo finds some "complex logic T12,11,11,9" and sudoku explainer some "dynamic contradiction forcing chain" (rating 9.1). Both do not recognize the unique permutation of plane set N3+N5+N8.
In a way this plane set observations more reveal in which plane sets there are no possible eliminations. This is valuable information as most of the plane sets contain no active elimination patterns. Its like chasing bugs in computer programs by confining the bugs in larger blocks or modules and then reducing the scope.

I see that this all does not meet your expectation to directly compare the plane set figures with your results.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Pattern-based classification of (hard) puzzles

Postby denis_berthier » Wed Feb 13, 2013 3:34 am

Hi logel,

Instead of replying in detail to your last post, I'll make a few general remarks.

I suggest you fix your vocabulary before we continue this discussion. It becomes hard to follow you when each of your replies introduces new words that require new explanations.
I still don't understand what BI means for you. You confirm my question about T&E(S4 + g-fish of all sizes), but it appears later that you have a different definition of BI; so that your confirmation doesn't make much sense to me.

Why don't you take the time to re-start all from the beginning and to introduce your definitions step by step ? As you seem to have your own approach, it may be a good idea to start your own thread, where you'll be able to explain it in detail. It would be better to continue here only the discussion related to classifications or ratings.

I keep thinking that using the word "line" is a very bad idea. You should rely on some well established background; if you choose CSP, then you should use the CSP vocabulary.


In a sense, you remind me of Allan Barker (and you evoke his work); he had a very good starting idea (applying set covering techniques to Sudoku), but instead of referring to this background, he kept referring to a non-existing mathematical one ("set logic"), with his own vocabulary and notations (the latter were largely inconsistent, but it seems his priority was to make them different from mine) . He has developed great graphics in his xsudo program and he has shown that some known rules (e.g. Subsets, Mutant Fish, some reversible chains, sk-loops, ...) could be understood as particular cases of set covering techniques. But, due to a lack of theoretical analysis, he has never been able to deal properly with oriented chain rules such as whips or g-whips (he finally deleted from his website all that was related to them). Instead, he developed an abstruse "theory" of rank and "dark logic".
Moreover, as the complexity of his "set patterns" increases doubly exponentially with the size of the "base set", he has never been able to define a rating based on his approach, let alone to guarantee that xsudo solutions were the simplest wrt to it.
Unfortunately, he became inactive about two years ago and we can't have more explanations about his approach.
BTW, all his 0-rank cases are included in the g-Subset theory I developed in CRT and PBCS, with no need of "dark logic".


The main reason why I evoke this is, it seems that you are not yet referring to any clear technical domain. You seem to think that the general notion of a pattern doesn't have to be defined. After reading your posts, your (implicit) definition is close to that of Allan, i.e., in my terms: a set of CSP variables (his "base set") together with a set of links (binary constraints) between them. But then, you face the same complexity problem. The main difference is, you accept T&E(X), so that the patterns you need in X don't have to be as large as they had to be in Allan's approach (you may have seen some absurdly complex 3D graphics on some pages of this forum). Notice that this definition of a pattern is not as general as you may think, as it does NOT include chain patterns (it has no notion of order - a point Allan always refused to understand).


I continue to think there is something interesting in your approach, but it's difficult to see what's really new. E.g.: in your example, is there anything in what you say about N4+N7 or N3+N5+N8 that could be written in a way independent of the rest? Are there potential new underlying resolution rules?


As for having to compute all the "permutations" of a set of candidates related by various constraints (i.e. all the possible assignments of truth values compatible with the constraints), this is clearly a programmer's approach (moreover, a problem known to be NP-complete in general); I don't see how it can be used in a pattern-based solution [or in a T&E(X) solution, where X is a set of patterns]. However, as your goal is to find X s.t. T&E(X) solves all the puzzles, this doesn't matter much.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Pattern-based classification of (hard) puzzles

Postby logel » Thu Feb 14, 2013 9:10 pm

Hi Denis
denis_berthier wrote:I suggest you fix your vocabulary before we continue this discussion. It becomes hard to follow you when each of your replies introduces new words that require new explanations.
I still don't understand what BI means for you. You confirm my question about T&E(S4 + g-fish of all sizes), but it appears later that you have a different definition of BI; so that your confirmation doesn't make much sense to me.

I did not intend to annoy you by inventing new wording, but was trying to be explanatory, and BTW you missed my sense of humour.
I regret to mention BI in the first place, its just the trivial box-row or column-box intersections, and these a completely irrelevant for the subsequent results, just improving performance. So forget about.

So I confirm again, avoiding undefined terms:
All patterns restricted inside a single number plane or single row/col/box plane and without any other restriction are not sufficient to solve all (known) sudoku puzzles with T&E(1).
If this matches T&E(S4 + g-fish of all sizes) - fine, if not take the above statement. I deliberately did not mention the term size because your definition seems to differ from mine, but that is not relevant too.

Even stronger:
All patterns restricted inside two combined arbitrary single number planes or two combined arbitrary single row/col/box planes and without any other restriction are not sufficient to solve all (known) sudoku puzzles with T&E(1).
Its clear that this case covers the first one. If this matches two level multi fish or two level multi g-fish - fine, if not - ibd.

Even more stronger:
All patterns restricted inside three combined arbitrary single number planes or two combined arbitrary single row/col/box planes and without any other restriction are not sufficient to solve all (known) sudoku puzzles with T&E(1).
The five puzzles in a previous post are the counter-examples.

denis_berthier wrote:Why don't you take the time to re-start all from the beginning and to introduce your definitions step by step ? As you seem to have your own approach, it may be a good idea to start your own thread, where you'll be able to explain it in detail. It would be better to continue here only the discussion related to classifications or ratings.

I had in mind already to start a new thread and make the story more human readable.
denis_berthier wrote:In a sense, you remind me of Allan Barker (and you evoke his work); he had a very good starting idea (applying set covering techniques to Sudoku), but instead of referring to this background, he kept referring to a non-existing mathematical one ("set logic"), with his own vocabulary and notations (the latter were largely inconsistent, but it seems his priority was to make them different from mine) . He has developed great graphics in his xsudo program and he has shown that some known rules (e.g. Subsets, Mutant Fish, some reversible chains, sk-loops, ...) could be understood as particular cases of set covering techniques. But, due to a lack of theoretical analysis, he has never been able to deal properly with oriented chain rules such as whips or g-whips (he finally deleted from his website all that was related to them). Instead, he developed an abstruse "theory" of rank and "dark logic".
Moreover, as the complexity of his "set patterns" increases doubly exponentially with the size of the "base set", he has never been able to define a rating based on his approach, let alone to guarantee that xsudo solutions were the simplest wrt to it.
Unfortunately, he became inactive about two years ago and we can't have more explanations about his approach.
BTW, all his 0-rank cases are included in the g-Subset theory I developed in CRT and PBCS, with no need of "dark logic".

I share most of your view on xsudo and Allan never really revealed what he is doing behind the scenes. I suspect he used this and that with no real break-through, was lost in the sudoku jungle, and finally gave up.
But concerning rating I think his rating is based on pattern size defined by the max number of true candidates possible in a pattern, which is not that bad.
The "dark" logic is trying to construct contradictions with uniqueness like others do with "exotic" logic. I think using uniqueness is no good idea and moreover unnecessary.
denis_berthier wrote:The main reason why I evoke this is, it seems that you are not yet referring to any clear technical domain. You seem to think that the general notion of a pattern doesn't have to be defined. After reading your posts, your (implicit) definition is close to that of Allan, i.e., in my terms: a set of CSP variables (his "base set") together with a set of links (binary constraints) between them. But then, you face the same complexity problem. The main difference is, you accept T&E(X), so that the patterns you need in X don't have to be as large as they had to be in Allan's approach (you may have seen some absurdly complex 3D graphics on some pages of this forum). Notice that this definition of a pattern is not as general as you may think, as it does NOT include chain patterns (it has no notion of order - a point Allan always refused to understand).

Now you point to the really crucial point of the topic.
I dont understand what technical domain could designate other than basic sudoku constraints and logical correctness of implications.
Expicit pattern definitions are not superior to implicit ones unless verification of any specific pattern poses a problem or is impossible. This is not the case.

The following statements are puzzling and a bit mysterious, so it would be nice if you throw some light on them.
For comparison of different pattern - usually defined by pattern classes - you need a universal pattern definition covering all ever possible patterns as superset.
I admit that my definition is somewhat near to Allan's, but where is the complexity problem, and (most imortant) where is it not general enough? BTW: Do you have a more general one?
The most general representation of any particular elimination pattern is its connection graph, I am pretty sure. Chains - even branched ones - are clearly covered. Your definition of braids of any kind imply a notion of order, and because of their construction principle they can be progressively evaluated. But a graph generally has no inherent order, even if you relate a vertex to the elimination target. You may get a partial order relative to each target, but why?

denis_berthier wrote:As for having to compute all the "permutations" of a set of candidates related by various constraints (i.e. all the possible assignments of truth values compatible with the constraints), this is clearly a programmer's approach (moreover, a problem known to be NP-complete in general); I don't see how it can be used in a pattern-based solution [or in a T&E(X) solution, where X is a set of patterns]. However, as your goal is to find X s.t. T&E(X) solves all the puzzles, this doesn't matter much.

If I translate "programmer's approach" with "not conceptual" you clearly missing the point. You may not like the result, but the basic concept is to limit possible elimination patterns by scope but rather by size or by construction principle.
The implementaion with permutation is in no way mandatory, there may be smarter ones. I chose it only because I absolutely wanted to assure completeness of the result.
And of course it can be used for a pattern-based solution. The final result is always a series of explicit elimination patterns conforming to a set of predefined restrictions.

Next steps:
Your comments made me think of adding restrictions of size on top of the scope restriction by any given size function. I am pretty much relaxed about the definition of such function, provided its universal, i.e. can applied on any elimination pattern.
If you can desribe your notion of size in such way, I can present results accordingly, if you like. We need not to agree on the size function.

A major point is: eliminations induced by T&E(x) are usually dirty. In my terms: not minimal. The sequence on T&E(1) may include redundant or irrelevant branches and is of unlimited length. So a size limit on the T&E(1) sequence is desirable. Finding a useful function sizing any T&E(1) sequence is basically the same question as sizing (i.e. rating) the solution sequence of the whole puzzle. I still have no striking idea.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Pattern-based classification of (hard) puzzles

Postby denis_berthier » Fri Feb 15, 2013 5:40 am

logel wrote:I regret to mention BI in the first place, its just the trivial box-row or column-box intersections, and these a completely irrelevant for the subsequent results, just improving performance. So forget about.

So, your BI is the same as mine, OK. BI always plays a major role in all the solutions, so it's difficult to forget it. Moreover, without BI, no resolution theory (except BRT) has the confluence property. I can't imagine the sets X of patterns you consider do not contain BI.


logel wrote:For comparison of different pattern - usually defined by pattern classes - you need a universal pattern definition covering all ever possible patterns as superset.

I can compare whips and Subsets without having a definition that covers both. I have many such comparison results, both subsumption theorems and statistical results.


logel wrote:I admit that my definition is somewhat near to Allan's, but where is the complexity problem, and (most imortant) where is it not general enough? BTW: Do you have a more general one?

The question isn't that it should be more general (see previous point).
The problem is, it entails the same difficulties as Allan's - except that, as I said previously, you don't need so large patterns as him because you want to solve all the puzzles with T&E(X) instead of X.

logel wrote:Allan never really revealed what he is doing behind the scenes

This is intimately related to what I've told Allan at that time : sequence = set + order and this is in my POV the real deep reason of Allan's final failure.
Actually, he finally revealed partly "what he is doing behind the scenes" when he introduced "ribbons". As these were obviously deeply inspired by the Sp-braids that I had introduced two years earlier (under the name of braids(Subsets)) and of which he was aware (he had largely participated in their discussion), but he refused to admit it, our personal relations became harsh. But I've always appreciated him and his work. I think the reason why he withdrew ribbons and all that was related to non-reversible chains from his website is that he finally admitted that they were indeed a disguised form of Sp-braids.
Now, the technical point:
a pattern, according to Allan, but in my vocabulary,is given by:
1) a set of CSP variables (his "base set")
2) a set of constraints covering the base set (in practice, its size can only be > to the size of the base set).
This is where the complexity problem appears: just count the possible number of patterns with n CSP variables, as n grows (and for him n has to be left growing much more than for you).
This is also where what's behind the scenes in Allan's approach appears (at least in part): by introducing "ribbons", Allan tried to overcome the complexity problem and to deal with his patterns as if they were chains with simpler embedded patterns (which led him to look-ahead chains, an absurdity in my view). And then he said that this implementation technique had been in xsudo since the beginning.
Now closing the loop: by forgetting the "equation" sequence = set + order, he was led, for complexity reasons, to deal behind the scenes with sets as if they were sequences.


logel wrote:The most general representation of any particular elimination pattern is its connection graph, I am pretty sure. Chains - even branched ones - are clearly covered.

No, only their eliminations are covered. But if you have only the connection graph, you need some work to find (if any) a chain that will do the same elimination. This has been discussed several times on this forum, with Allan and with people that use xsudo and present some of its eliminations as if they were chains - hiding the fact that xsudo does not output chains: chains are the user's interpretation of some of xsudo outputs.

logel wrote:Your definition of braids of any kind imply a notion of order, and because of their construction principle they can be progressively evaluated.

That's why they are powerful and computationally tractable! The common property of all my patterns is, they require no look-ahead.

logel wrote:But a graph generally has no inherent order, even if you relate a vertex to the elimination target. You may get a partial order relative to each target, but why?

With Allan's patterns or yours, there's no reason, unless one wants to use chains. But xsudo is unable to find a solution with only chains.


logel wrote:If I translate "programmer's approach" with "not conceptual"

Although the translation may be correct in many cases, this is not what I had in mind.


logel wrote:If you can desribe your notion of size in such way, I can present results accordingly, if you like. We need not to agree on the size function.

The size of my patterns is inherent in their definition. I don't repeat them here, you can see them in many places.
For your patterns, I think you can define their size as the cardinal of their base set. If the size of the constraint set was always equal to that of the base set, there would be little discussion possible about this choice. As it can be larger, it opens up a few questions but I think they are of secondary importance.


logel wrote:A major point is: eliminations induced by T&E(x) are usually dirty. In my terms: not minimal. The sequence on T&E(1) may include redundant or irrelevant branches and is of unlimited length. So a size limit on the T&E(1) sequence is desirable. Finding a useful function sizing any T&E(1) sequence is basically the same question as sizing (i.e. rating) the solution sequence of the whole puzzle. I still have no striking idea.


Minimising T&E(X) amounts to introducing X-braids and using the simplest-first strategy !!!

But it seems you are confusing two questions. What we have been discussing is not the size of a T&E(X) solution, but the size of patterns in X such that T&E(X) solves all the known puzzles.
Your results show what types of patterns are not enough and what types X must contain, but they give no idea of the size of these patterns.

To compare with my approach, I have to types of results:
- all the (known) puzzles can be solved by T&E(braids) [equivalent to T&E(2) or to B-braids]
- all the (known) puzzles can be solved by T&E(B7) [equivalent to B7-braids]
The second is obviously much stronger than the first.

In your approach, you have shown until now that all the (known) puzzles can be solved by T&E(X); this is an interesting first step.
It'd be interesting to show that all the (known) puzzles can be solved by T&E(Xk), for some well defined k, where Xk are all the patterrns in X and of size <=k.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Pattern-based classification of (hard) puzzles

Postby logel » Mon Feb 18, 2013 6:38 pm

Hi Denis
Although I have more comments on the relation between generalized chains and base sets, I want to focus on the size restriction an leave other interesting points for later.
denis_berthier wrote:But it seems you are confusing two questions. What we have been discussing is not the size of a T&E(X) solution, but the size of patterns in X such that T&E(X) solves all the known puzzles.

I am not confusing these two questions, but I am running ahead too far and too fast.
denis_berthier wrote:Your results show what types of patterns are not enough and what types X must contain, but they give no idea of the size of these patterns.

To compare with my approach, I have to types of results:
- all the (known) puzzles can be solved by T&E(braids) [equivalent to T&E(2) or to B-braids]
- all the (known) puzzles can be solved by T&E(B7) [equivalent to B7-braids]
The second is obviously much stronger than the first.

In your approach, you have shown until now that all the (known) puzzles can be solved by T&E(X); this is an interesting first step.
It'd be interesting to show that all the (known) puzzles can be solved by T&E(Xk), for some well defined k, where Xk are all the patterrns in X and of size <=k.

So I pick up the ball and come back with according results. It will probably take some time.
From some manual case studies I know that k is at least 5.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Pattern-based classification of (hard) puzzles

Postby denis_berthier » Tue Feb 19, 2013 6:55 am

logel wrote:From some manual case studies I know that k is at least 5.

I bet you'll find a larger k on a larger collection.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Pattern-based classification of (hard) puzzles

Postby logel » Fri Apr 19, 2013 4:25 pm

denis_berthier wrote:
logel wrote:From some manual case studies I know that k is at least 5.

I bet you'll find a larger k on a larger collection.


It took really much more time than expected. The reduction of planes is a severe problem. Chasing bugs too.

The answer is 6. (not 42!)

So T&E(S6) solves all known sudoku represented by 817681 puzzles of the current hardest list, all SER 10.3 or more.
S6 stands for pattern with max 6 base lines, i.e. with max 6 true nodes in the pattern.
The S6-pattern used are additionally restricted to max three planes, so its in fact < S6.
If the restriction is on two planes, only 169 are left unsolved.

But I have absolutely no clue how you might compare this to T&E(B7). Looks like apples and oranges.

Re-reading your statements in this thread, I still don't understand why you object to a universal pattern definition.
I put up a new thread proposing such a definition: universal-elimination-pattern
There you also find more details of my results.

I appreciate very much your work on nrczt-chains and braids, but these pattern don't loose their value when embedded in a larger scope.
Any comparison of size or complexity needs a common basis.

Another mystery is how you justify that T&E(Bx) build a strict hierarchy for x=2,3,4,... in whatever sense of simplicity.
The size/complexity of pattern on T&E level one does not limit the size/complexity of the primary elimination.

Some observation (more to do) rather show that smaller patterns on level one increase the complexity of the primary pattern in some cases.
I mistrust the simplest-first strategy to be valid globally.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Pattern-based classification of (hard) puzzles

Postby denis_berthier » Fri Apr 19, 2013 6:12 pm

logel wrote:T&E(S6) solves all known sudoku represented by 817681 puzzles of the current hardest list, all SER 10.3 or more.
S6 stands for pattern with max 6 base lines, i.e. with max 6 true nodes in the pattern.
The S6-pattern used are additionally restricted to max three planes, so its in fact < S6.
If the restriction is on two planes, only 169 are left unsolved.
But I have absolutely no clue how you might compare this to T&E(B7). Looks like apples and oranges.

The only direct comparison I can see without much thought: you have a slightly smaller n with much more complex patterns.


logel wrote:I still don't understand why you object to a universal pattern definition. I put up a new thread proposing such a definition: universal-elimination-pattern

I'll discuss it in more detail there later. In a few words, the main problem I see is the necessity of trying all the truth value assignments (what you call permutations) for all the candidates in the pattern (this is a hidden aspect of complexity). In braids or B-braids, once the pattern is written, checking the validity of the elimination in a given resolution state (PM) is obvious (these patterns are indeed a full description of their proof).


logel wrote:I appreciate very much your work on nrczt-chains and braids, but these pattern don't loose their value when embedded in a larger scope. Any comparison of size or complexity needs a common basis.

It needs a common conceptual framework but not necessarily a common super-pattern. I can compare whips (or braids) and Subsets of same size - two a priori very different patterns - via the subsumption theorems.


logel wrote:Another mystery is how you justify that T&E(Bx) build a strict hierarchy for x=2,3,4,... in whatever sense of simplicity.The size/complexity of pattern on T&E level one does not limit the size/complexity of the primary elimination.
Some observation (more to do) rather show that smaller patterns on level one increase the complexity of the primary pattern in some cases.

There are two different things:
- the B?B classification. It's clear it doesn't allow a direct comparison of all the puzzles, even though one has, obviously:
B7B(P) <= B6B(P) .... <= B1B(P)=gB(P) <= B(P) for any puzzle (with equality in most cases);
- the universal B7B rating (or B8B if some day a B8B puzzle is found). It takes into account the global length of the B7B braid together with its inner braids.
You can even go beyond B7B (even if there are no puzzles out of it) and use BB as a universal rating (B-braids with a priori unrestricted inner braids). Here also, the global length takes into account the length of the inner braids.
Moreover, for puzzles in T&E(2), there are many more resolution paradigms (see chapter 12 on the "patterns of proof").


logel wrote:I mistrust the simplest-first strategy to be valid globally.

It is globally valid for any resolution theory with the confluence property - in particular for all the T-braid theories defined in my book, including all the BpB for any p.
But its meaning should be clear: it is simplest only for the chosen set of rules.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

What's a pattern ?

Postby denis_berthier » Mon May 06, 2013 8:51 am



What's a pattern?


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

Pattern vs elimination pattern
There are two kinds of resolution rules:
- Assertion rules: Pattern => candidate = True
- Elimination rules: Pattern => candidate = False

The basic assertion rules are Singles (Naked or Hidden).
A few other assertion rules are known, but I've shown long ago (see HLS1) that they can be considered as a combination of (simpler) elimination rules and Singles.

So, while trying to define what a pattern is, there is no real point in writing (as logel does) "elimination pattern" instead of "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.


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.

*: 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.


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.
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?
Once more, we meet the idea that the goals of resolution must play a major role in defining our concepts.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Pattern-based classification of (hard) puzzles

Postby David P Bird » Mon May 06, 2013 11:50 am

Denis, some feed-back from the other side of the fence:

I agree that there is no need to call any pattern an assertion pattern, as to assert a digit is simply equivalent to eliminating all the others in the same cell. But I don't agree with dropping the 'elimination' qualifier, as for manual solvers there are also 'inference' patterns. For example with a finned fish pattern the inference is either a fin cell is true or the fish cells hold N truths.

Inference patterns can endure for quite a time as a puzzle is reduced and can be re-used repeatedly in combination with other inference patterns as they emerge. I guess you would want to call these pattern components or sub-patterns, but I feel that doesn't do them justice.

Now, without wanting to resurrect the issue, your classification of patterns as either being a subsets or chains doesn't include avoidable or uniqueness patterns. As I've mentioned to you before, avoidable patterns apply to sub-puzzles that can be proved to have to a unique solution, and so don't depend on uniqueness. Even if you don't use either of these pattern types yourself, for whatever reason, you should recognise that they exist.

As a manual solver, albeit with a computer helper, I rely on spotting "recognisable patterns", but that's a term defies a precise description. All I can say is, that at its core, a recognisable pattern should contain a number of elements that match some locating criteria which justifies looking for other elements which may take a variety of forms.

We're all looking for efficient ways to solve puzzles that can be explained to others as elegantly and briefly as possible, (a conflicting set of goals). If you look at the way manual solutions are presented, many authors re-order their steps and prune out the insignificant ones. For example, if a continuous AIC loop can be found, it will provide multiple eliminations and so advancing it as early as possible in the sequence will shorten a solution considerably. I may be mistaken, but I don't think there is a solver program that attempts to do anything like this. However, from my limited understanding of logel's approach, it appears to focus on a single target at a time which is going in the opposite direction.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Re: Pattern-based classification of (hard) puzzles

Postby denis_berthier » Mon May 06, 2013 12:48 pm

David P Bird wrote: I don't agree with dropping the 'elimination' qualifier, as for manual solvers there are also 'inference' patterns. For example with a finned fish pattern the inference is either a fin cell is true or the fish cells hold N truths.
Inference patterns can endure for quite a time as a puzzle is reduced and can be re-used repeatedly in combination with other inference patterns as they emerge. I guess you would want to call these pattern components or sub-patterns, but I feel that doesn't do them justice.

Exactly. I wouldn't call them patterns until they are completed. But I have no problem with the idea that it is useful to consider partial patterns or sub-patterns or components - whichever name you give them. Even in whips, braids ..., it is useful to consider partial ones and to assemble them to make a full longer one that allows an elim.
BTW, for me, a finned Fish is a mere z-fish (fish with additional z-candidates) or a z-gFish in the mutant case.


David P Bird wrote: Now, without wanting to resurrect the issue, your classification of patterns as either being a subsets or chains doesn't include avoidable or uniqueness patterns.

I have no problem with considering uniqueness patterns or U-patterns (In HLS already, I spoke of U-rules). The only problem I have is with the ayatollahs of uniqueness who want to oblige everyone to use it. My position has always been clear: use it if you want to, don't use it if you don't want to (BTW, I have exactly the same position for ANY rule).


David P Bird wrote: As I've mentioned to you before, avoidable patterns apply to sub-puzzles that can be proved to have to a unique solution, and so don't depend on uniqueness. Even if you don't use either of these pattern types yourself, for whatever reason, you should recognise that they exist.

This is very unclear to me. Do you mean you can prove that a sub-puzzle has a unique solution without finding this sub-solution? Can you give an example of such a pattern?


David P Bird wrote: from my limited understanding of logel's approach, it appears to focus on a single target at a time which is going in the opposite direction.

logel said he has a long term goal of finding the simplest resolution path. But, like any of us, he has no idea of how to do it and he explicitly said that his current definition of a pattern doesn't tackle this question.


My main point in the previous post was about checking an elimination. You don't say anything about this, but I have no doubt that, as a player, you would agree with me: ONCE a pattern and a target are given in a particular situation, one shouldn't have to do complicated computations to check that the pattern justifies the elimination of the target.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Pattern-based classification of (hard) puzzles

Postby David P Bird » Mon May 06, 2013 4:15 pm

Denis Berthier wrote:This [avoidable pattern subject] is very unclear to me. Do you mean you can prove that a sub-puzzle has a unique solution without finding this sub-solution? Can you give an example of such a pattern?

When a puzzle has two solutions for some sub-puzzle no inference will be available to distinguish the difference between two candidates in any of its cells. Once the cells have been reduced to two candidates each, it becomes a 'Deadly Pattern' that's isolated from all the external cells .
Code: Select all
 
  12  .  .  | 124 .  .           12  .  .  | 24 .  .
  .   .  .  | .   .  .    =>     .   .  .  | .  .  .
  123 .  .  | 12  .  .           23  .  .  | 1  .  .

In the diagram on the left, if uniqueness is assumed there is an inference that (4)r1c4 and (3)r3c1 can't both be false otherwise a Deadly Pattern would remain.

Now if (2)r3c4 can be eliminated, the diagram on the right results (called an Avoidable Rectangle). The fact that this elimination has been possible shows that these cells don't have two alternative solutions. But if (4)r1c4 and (3)r3c1 were both false, the Deadly Pattern would have existed and (2)r3c4 could never have been eliminated!

This produces a theorem that if it has been possible to eliminate one of the two solutions for a potential DP, the other solution is also false. In the identifying cell it isn't necessary to assert one of the alternative DP candidates digits, but just to eliminate one of them.

I'm sure that you can tidy up my proof to make it more rigorous. I had a brief exchange with Blue < here > about the type of inference that is needed to produce an Avoidable Pattern. (Any further insights on this you may have on this are best posted there.)

Denis Berthier wrote:My main point in the previous post was about checking an elimination. You don't say anything about this, but I have no doubt that, as a player, you would agree with me: ONCE a pattern and a target are given in a particular situation, one shouldn't have to do complicated computations to check that the pattern justifies the elimination of the target.

My feeling on this is that a pattern that provides a theorem that has general utility can be invoked without needing a step-by-step proof of that theorem eg the Four Colour Mapping theorem. If no such theorem has been defined every link in the argument must be justified, but perhaps by combining defined inference pattern theorems (yes, I still want to hang onto that term because they provide theorems too). I'm therefore not prepared to accept a statement such as "running though all the permutations it transpires that ..." which is more or less my interpretation of logel's approach.

Champagne and I disagree over this. For me the way he defines and notates Exocet eliminations amounts to identifying a signature pattern, and then giving resulting eliminations that he's found in a back room. Blue analysed his original posts and found they nearly all relied combining multiple fish patterns. Later some of us expanded on this and came up with a pattern based version < Junior Exocet >, or JExocet which is just about on the limit of what I'd accept as a "recognisable pattern". To my knowledge this covers over 90% of all Exocet eliminations. Embedded in the pattern are a number of subsidiary inferences which can also be employed to make additional eliminations either when it's first discovered or later following further puzzle reductions.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Re: Pattern-based classification of (hard) puzzles

Postby denis_berthier » Mon May 06, 2013 5:53 pm

David,

for the DPs I'll have a look at the other thread and answer there if I have anything to say.

David P Bird wrote:
Denis Berthier wrote:My main point in the previous post was about checking an elimination. You don't say anything about this, but I have no doubt that, as a player, you would agree with me: ONCE a pattern and a target are given in a particular situation, one shouldn't have to do complicated computations to check that the pattern justifies the elimination of the target.

My feeling on this is that a pattern that provides a theorem that has general utility can be invoked without needing a step-by-step proof of that theorem

Yep, and this is the case for all the (g)Subsets, whips, braids, ...


David P Bird wrote:I'm therefore not prepared to accept a statement such as "running though all the permutations it transpires that ..." which is more or less my interpretation of logel's approach.

It is indeed his view.


David P Bird wrote:Champagne and I disagree over this. For me the way he defines and notates Exocet eliminations amounts to identifying a signature pattern, and then giving resulting eliminations that he's found in a back room. Blue analysed his original posts and found they nearly all relied combining multiple fish patterns. Later some of us expanded on this and came up with a pattern based version < Junior Exocet >, or JExocet which is just about on the limit of what I'd accept as a "recognisable pattern". To my knowledge this covers over 90% of all Exocet eliminations. Embedded in the pattern are a number of subsidiary inferences which can also be employed to make additional eliminations either when it's first discovered or later following further puzzle reductions.

The last time I looked at exocet, the only "definition" I could find contained some set of conditions that could be called a partial pattern P and another condition that said "C1 and C2 are contradictory", where C1 and C2 are candidates appearing in P.*
For me, this is totally meaningless unless it is clearly specified HOW C1 and C2 are supposed to be proven contradictory: from an abstract logic POV, any candidate that is not the real value for a cell is contradictory with the givens and a fortiori contradictory with any other candidate.
The best way of interpreting this is to consider Exocet only as a heuristic for looking for potential eliminations (find P and then try to find some pattern relating C1 and C2 and proving that they are contradictory - e.g. find a bibraid based on C1 and C2). As we've never been able to state such heuristics, this may be a first step. The question then is, what's its value in real solving (without a computer)?

As for JExocet, I don't remember reading about this. I'll have a look.

(*: I also saw on the programmer's forum an alternative more formal definition proposed by Blue, but he received no answer).
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Advanced solving techniques