Universal Elimination Pattern for hard puzzles

Everything about Sudoku that doesn't fit in one of the other sections

Re: Universal Elimination Pattern for hard puzzles

Postby denis_berthier » Tue Apr 23, 2013 9:26 am

I'll wait logel's answers before making more comments or any conjectures about what he means.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Universal Elimination Pattern for hard puzzles

Postby logel » Wed Apr 24, 2013 11:44 am

Coming back after some days I am bit of overwhelmed with so many comments and questions.
Anwers will come one after another. I try to be careful avoiding more unneccesary misunderstandings.

eleven wrote:logel,
please give us a better example.
E.g. can you show your first step to solve "Champagne dry" and explain pattern, lines etc. there ?
Code: Select all
98.7.....7.....6....6.5.....4...5.3...79..5......2...1..85..9......1...4.....3.2.


OK, this is the top of the "hardest" list.

A previous example request from champagne was also misunderstood. My reply was only meant as an illustration of the pattern definition not of a solution.

I said my initial post that the implementation of the reduction procedure of level-one sequences is not completed. So what I can show for this particular puzzle is limited, because all information is contained in a large logfile together with other technical details. I will come back with more details, but need some time to work out.

Preliminary results:
I used only plane pairs or triples of equal type, that is 2 or 3 combined number planes, full rows, columns or boxes.
No direct eliminations found scanning all those planes. Hard puzzle.
No level-one eliminations found, assuming any candidate, applying all possible eliminations derived from single number planes, single rows, colums or boxes. Really hard puzzle.

Applying eliminations derived from plane pairs can solve this puzzle completely.
But no contradiction path after assuming any candidate is found, if the size of the level-one elimination is restricted to size 6.
Allowing elimination of size up to 7 a very long contradiction path appeares. The first is at 9r9c3, then 4r9c5 and 6r9c5 in the first pass. The second pass based on these three elimination produces some more and after completing a third pass with a total of 28 eliminated candidates the level-one stage is done. A solution is reached with direct elimations only beyond this point, all based on plane pairs at most.
The number of candidates until only direct elimations are needed, drops to 21 with no size restrictions.

The picture looks completely different if all triples of number planes are used additionally.
The number of possible eliminations gets large and the sequences can be very different to those from plane pairs. The result depends on the order of elimations after the first pass.
With restriction to size 6 on plane triple pattern a solution is completed, but with may step, usually > 20.
Relaxing this restriction to size 7, the result is interesting. Only 8 eliminations on level one are needed: 2r1c3, 4r1c5, 24r1c6, 134r1c7, 1r1c8. The maximal size of the subsequent direct eliminations is 11.
A close look at the result from adding triple planes of rows, columns and boxes and also no size restriction shows little improvement.

Note that there is no check if all level-one elimations are neccessary. Currently my aim was only to prove solvability with enough power to solve all known puzzles and at the same time with enough restrictions to keep it computable. A lot of things more to investigate.

I also like your statement:
eleven wrote:[Added:] "No problem" might be misleading. As you know, i "love" those XSudo pictures with 40 marked cells, 25 base and 21 cover sets, and the "conclusion": xy<>z without any further explanation. But as i see it, the goal here is to find well defined "minimal" solutions rather than reader friendly ones.

So you will have a lot of fun when I present some of the elimations of the above in detail later. Of course we all look for "simple" or "reader friendly" solutions.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Universal Definition of an Elimination Pattern

Postby logel » Wed Apr 24, 2013 4:02 pm

Hi Denis
denis_berthier wrote:About vocabulary: any of your patterns is a very specific structure. So, the real topic of the thread is not "Universal Elimination Pattern" but "Universal Definition of an Elimination Pattern".

Yes, of course its a definition. I anyone read between the lines "Universal Elimination Solver", I must frustrate such hopes. There is no "ultimate" solver, never will.

denis_berthier wrote:One can now wonder why you don't include from the start the core (the base set) in the definition instead of using such a convoluted path to reach the same effect (hopefully - because I'm not convinced that your statement, even in its modified form, is true).
In any case, I think your current definition makes it too difficult to check if something is an elimination pattern.

About my motivation:
After some more or less failed attempts to write a solver useful for hard puzzles, I decided to put aside bottom-up constructions, but cut the puzzle into larger pieces and examine properties of the pieces.
The most promising pieces are planes and pairs and triples of them.

First of all the above definition reflects the way the idea devellopped in my head. Second I regard the candidates as boolean variables as the primary objects. (more later).
When working with planes or pairs of them, its easy to detect that there is no room for some of the candidates. You simply pile up all valid variable permutations and look for candidates that do nat match any of them. This is not new and known as "template method". There are some related threads also. The templates seem to consider number planes only so far.
But I was not at all satisfied with this method, because
- the pattern consisting of all candidates of one, two or more planes contains redundant objects
- no further classification seems possible
- no size assignment possible

So a reduction to a minimal and still working configuration suggests itself. The restriction to a single target was made to keep things simple. The leading idea of the definition was to cover everthing one can get rather than having an easy evaluation.
But after doing such a reduction you don't have any clue what the remaining structure is like. So all properties of a pettern definition must rely on the basic constraints or the minimality. That its possible to describe any universal pattern as a set of base lines is a consequence of the minimality. If you start with the base set as a definition, it looks like been fallen from the sky. Addionally the are no operations on the lines, only operations on the candidates.
I cannot see how there is an elegant way to define which sets of some arbitrary lines work as base lines. Most of them do not eliminate anything. Any rule based bottom-up construction of elimination pattern faces the nasty characteristic, that the ratio between the number of all constructed pattern and number of pattern with target(s) gets worse and worse with growing pattern size.

So the definition wants to stress the point that Universal Pattern is the product of a reduction rather than the product of a construction.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: CSP variable vs constraint

Postby logel » Wed Apr 24, 2013 4:13 pm

blue wrote:Statements of the first type, are related to "base sets", or "strongly linked (candidate) sets", or "strong links" (for short).
Statements of the second type, are related to "cover sets", or "pairwise weakly linked (candidate) sets", or "weak links" (for short). In Alan Barker's vocabulary, they are just "links", or "link sets".
Statements of the third type, are related to either "CSP variables" (e.g. Denis Berthier's vocabulary), or "Truths" (Alan Barker's vocabulary).

If I try an interpretation: first and third type are identical.

denis_berthier wrote:The problem is naturally formulated in terms of:
1) 81 rc-cells and of values (digits) that must be assigned to them;
2) 324 constraints the values of these cells must satisfy; these can be classified into 4 constraint types (rc, rn, cn, bn).

Now, translated into logic formulae:
- type 1 is expressed in terms of EOO (exactly one of);
- type 2 is expressed in terms of NAND (not and).
The other type of logical relation you consider ("at most one of") never appears (neither in Sudoku nor in the general CSP).

One important aspect of these predicates:
- type 1 appears as non-binary (most of the time);
- type 2 always appears as binary.

At this point we have a different view what may explain other controversial issues.

A see the 324 basic constraints rather as equations of boolean variables called candidates carrying a value true or false.
What I call line is an equation L1 XOR L2 XOR ... XOR L9 = TRUE, where Lx are the candidates from a constraint. Btw XOR is a binary and associative operation.
This is first class blunder, forget about it. See comment of blue below. Sorry.


The XOR expression of each line trivially get shorter with every elimination.
The type2 NAND is not needed at this point, but Lx NAND Ly = TRUE (x<>y) is a consequence from the line equation.

Of course one could solve the resulting equation system in boolean algebra as any other equation system. I remember that someone did it already, forgot about the link.
For a unique puzzle all variables result in T of F. For multiple puzzles some variables are assigned T or F and for the others a smaller equation system remains, describing the conditions for all solutions.
The reason not to do this: Like full T&E you obtain just the solution but find out no other properties of the puzzle.

So instead of solving the equation system in one large block, we look for smaller equation systems that determine the value of dedicated variables (target candidates).
And only these equation systems need equations of the NAND type, because they use less variables. That is only another view on universal pattern. Any universal pattern (my definition) corresponds to an equation system in the following way:
There are equations related to base lines (chained XOR terms) and some binary NAND terms. All except one variable of the NAND terms are also operands of one of the XOR terms. The one exception is the target, only linked to some line candidates but is not member of any line.same. The relation to an equation system remains true.

denis_berthier wrote:I haven't forgotten the topic of this thread.
The fact that type 1 is (generally) not binary has concrete implications on complexity:
- Sudoku is not a 2-SAT problem and can't therefore be solved by the very efficient 2-SAT solvers.
- for the same reasons, logel means of checking validity of an "elimination pattern" is also not a 2-SAT problem (even if the target is fixed to True). The complexity of checking can't easily be computed in the general case, whereas it can for patterns such as Subsets, g-Subsets, whips and all the oriented chains fauna - which I express by saying that these special (but very general) patterns carry their own proof with them. In my view, a "pattern" that requires a non-obvious checking procedure (testing all the permutations - or all the remaining ones after the target has been fixed to True) does not really qualify as a pattern in any "pure logic" view of solving.

I never claimed that validation of universal patterns is 2-SAT. More comments on validation later.
Last edited by logel on Wed Apr 24, 2013 11:40 pm, edited 1 time in total.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Universal Elimination Pattern for hard puzzles

Postby champagne » Wed Apr 24, 2013 4:57 pm

I don't like that much to post "negative comments" but here, I would share my own experience.

I have been very found of Allan Barker process and it has been the source of huge improvements in the solving process for hardest puzzles, but...

1) It is very easy (but costly in terms of CPU consumption) to detect that combining several floors/planes some candidates can be discarded.
2) Alan Barker had a very efficient process to build a reduced "truths links" SLG to justify some of them.

3) Although he has be very open to describe the process he was applying, I never succeeded in copying it in a way I considered as reasonable as far as the CPU consumption was concerned.

BTW I had the chance to meet him in BANGKOK and we had a very pleasant day together with spouses.

4) The "multi floors/plane" process remains on my side a leading indicator to find where a deeper search can be made.
5) It appeared very fast that several different SLG's could explain the same elimination(s). Allan Barker process was basically producing one (to make it simple) so, another tool had to be designed;
6) As soon as you pass the rank 0 , it is extremely difficult to find the logic behind the SLG

At the end, we (many actors in that forum) made significant achieved or potential progress in the solution of puzzles working in specific directions

- all kinds of "EXOCETS" patterns
- all kinds of rank 0 logic
- non overlapping rank 1 logic

and alternative views of the same logic (see David's posts)

I have no doubt that a more general view can be implemented, but it is a huge task.
champagne
2017 Supporter
 
Posts: 5677
Joined: 02 August 2007
Location: France Brittany

Re: Universal Elimination Pattern for hard puzzles

Postby eleven » Wed Apr 24, 2013 7:21 pm

logel,
thanks for the elaborate response,
but what i wanted was just a single example, which is not so simple, that most other methods would have the same outcome. So i proposed the first step (elimination) for this puzzle only (which is not an extremely hard step, but which is different for different solvers). Then some definitions etc., which now are vague for me, could be better explained/discussed (also if it is not yet the optimal step you have in mind for the future).
[Edit:]Ah, forgive me, i now saw, that in this puzzle it is the hardest step for SE. I had remembered that wrong (probably because i had found an elimination with candidates from one box and 4 columns only, years ago).
Please choose any other puzzle grid/elimination you think would be good for an example.
eleven
 
Posts: 1561
Joined: 10 February 2008

Re: Universal Elimination Pattern for hard puzzles

Postby logel » Wed Apr 24, 2013 8:47 pm

Hi eleven
eleven wrote:The daily definition :)
:shock:

There are many comments related to uniqueness, yours and also others.
I going to state more precisely why using uniqueness is not desirable. I do not say that its bad or wrong. I see that the motivation is to find "better" or "simpler" solutions is a positive one.
From my point of view using uniquenes has simply too many disadvantages.
eleven wrote:
logel wrote:But because I see absolutely no reason to modify the problem statement, I reject using uniqueness methods in the solving sequence.

If you like.
I know that other people have a different view, but I never heard a sound reasoning.

Here is my point of view:
Sudoku in first line is a game, which is played with the goal to solve it. The play is unfair, when the puzzle is not unique, because no solution can be found without guessing. When you had spent 5 hours trying to solve a multisolution puzzle, you know, why players insist on the uniqueness of puzzles as part of the "problem statement".
(On the other hand i had fun to solve some puzzles, which were declared to be multisolution puzzles, but this i a different game. )
Since your universal method seems to be non guessing, it is useless for non unique puzzles too, isn't it ?
For a player the goal is neither to analyze the puzzle nor to proof a solution (though both is required), but to find a solution, and in best case an elegant one. For this goal uniqueness methods can be the salt in the soup.

I do not regard sudoku as a game which is played against an ivisible partner, but as a logical problem statement.

When constructing a sudoku problem its important to check that the problem has a unique solution (!) AND is minimal. Here minimal means that there are no redundant givens.
Why is that important? Redundant givens that you can calculate from the other make the minimal problem simpler to solve. This is obvious because some of the complexity is removed. If there are many redundant givens, the problem may even become trivial and solvable by singles only. So sudoku problems with redundant givens a not desirable. This is also related to solving with backdoors and confusing some people.
Instead adding a redundant given we also can add a redundant clue. Such clues work like additional constraints. E.g. cell(a,b) different from cell(x,y) OR cell(x,y) has odd value. You would probably hesitate to use this clues or build methods using such clues even if the clue is confirmed by a "sudoku creator". Such clues have the same effect as redundant given, they make the problem easier to solve IF the clues match with the final solution. If they do not match the problems becomes unsolvable. This is the case even if the clues are not used when solving. The combined constraints create a contradiction.

Although the uniqueness statement is a bit special, because it cannot expressed by variables, it works like any other redundant clue. It is redundant because it can be calculated form the rest. And it makes the original problem simpler, not very much but simpler. So again: not desirable.
So you end up with the statement: I found a simpler solution of a sudoku problem because I made it simpler. :)

Besides the simplification effect there are more disadvantages. In case that the puzzle is unsolvable anyway, using uniqueness and finding a contradiction makes it impossible to distinguish between "really unsolvable" and "not unique". Not so important, also not desirable.
You wrote the nice phrase "to find a solution, and in best case an elegant one". Everybody seems to have a private feeling about, what is "elegant", "simple" or "less complex". Unfortunatlely private feelings are hardly shared. One of my long term goals is defining a function that gives "elegant" or "simple" a well defined value based on definite principles. Such function would allow to compare solutions by a "quality". Ideas are welcome.
Comparison of solutions sequences using redundant clues (or uniqueness) with normal solution sequences are obviously useless. Not desirable.

You wrote: The play is unfair, when the puzzle is not unique. Besides that I don't like the term play, my position: Its a big difference if you know uniqueness of if you use uniqueness. Knowing uniquenes avoids spending useless 5 hours. If you get stuck, you know that you have to try harder. That is the meaning of analysis in my initial post.

I clearly distinguish guessing from assuming a candidate value. Guessing is taking something for granted without verification. My mother use guessing and I have a hard time to explain that this is not correct even if the final solution is correct. Assuming is similar but after assuming the candidate true and detecting an inevitable contradiction as consequence, one can safely conclude that the assumtion is wrong and the inverse (candidate false) is true. If the assumption results in a solution, we can only conclude that we have found one of possibly many. Using only falsification of candidates says that candidates get true only by singles. This is my definition of constraint propagation.

Solving without uniqueness by constraint propagation proves the solution to be unique.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: CSP variable vs constraint

Postby blue » Wed Apr 24, 2013 9:56 pm

Hi logel,

blue wrote:1) There are statements like: "there must be at least one X in Y" (e.g. at least one 3 in box 4)
2) There are statements like: "there can be no more than one X in Y" (e.g. no more than one 3 in box 4)
3) There are statements like: "there must be exactly one X in Y" (e.g. exactly one 3 in box 4)

Statements of the first type, are related to "base sets", or "strongly linked (candidate) sets", or "strong links" (for short).
Statements of the second type, are related to "cover sets", or "pairwise weakly linked (candidate) sets", or "weak links" (for short). In Alan Barker's vocabulary, they are just "links", or "link sets".
Statements of the third type, are related to either "CSP variables" (e.g. Denis Berthier's vocabulary), or "Truths" (Alan Barker's vocabulary).

logel wrote:If I try an interpretation: first and third type are identical.

That is incorrect.

logel wrote:A see the 324 basic constraints rather as equations of boolean variables called candidates carrying a value true or false.
What I call line is an equation L1 XOR L2 XOR ... XOR L9 = TRUE, where Lx are the candidates from a constraint. Btw XOR is a binary and associative operation.
The XOR expression of each line trivially get shorter with every elimination.
The type2 NAND is not needed at this point, but Lx NAND Ly = TRUE (x<>y) is a consequence from the line equation.

Also, that is not the correct equation for a line, if you want it to be an "exactly one of" equation.

Take the example with only 3 candidates, A, B and C.
The equation (A XOR B XOR C), is satisfied when A,B and C are all true -- contrary to intent.
The proper equation is "(A OR B OR C) AND (A NAND B) AND (A NAND C) AND (B NAND C)".
It combines statements of the 1st and 2nd types, and the result is a statement of the 3rd type.

Note: In the world of "SAT probelms", expressed in "conjunctive normal form" (CNF), the equation would be "(A OR B OR C) AND (NOT(A) OR NOT(B)) AND (NOT(A) OR NOT(C)) AND (NOT(B) OR NOT(C))". It is an "AND" of 4 "OR"s. The first, expresses what I call the "strong link requirement", and rest express what I call "weak link constraints".

Regards,
Blue.
Last edited by blue on Wed Apr 24, 2013 9:58 pm, edited 1 time in total.
blue
 
Posts: 573
Joined: 11 March 2013

Re: Universal Elimination Pattern for hard puzzles

Postby eleven » Wed Apr 24, 2013 9:57 pm

logel,
my intent was to leave this topic, because we could agree, that it is a matter of taste.
But i can't accept your arguments here.
logel wrote:When constructing a sudoku problem its important to check that the problem has a unique solution (!) AND is minimal. Here minimal means that there are no redundant givens.
Why is that important? Redundant givens that you can calculate from the other make the minimal problem simpler to solve. This is obvious because some of the complexity is removed.

So what ? Sudoku problems have to be unique, but you don't allow to use this property ?? They have to be minimal ?? That means, i am not allowed to create a (unique) puzzle, which is easier to solve by adding clues ? And don't you know, that - when uniqueness methods are allowed - a puzzle also can become harder, when you add a clue, because with this clue you can't apply the technique anymore ?
Although the uniqueness statement is a bit special, because it cannot expressed by variables, it works like any other redundant clue. It is redundant because it can be calculated form the rest.

Not like a clue, it adds other constraints. It is redundant, but it is a difference, if you can solve a puzzle with a simple uniqueness move on paper or if you need long chains or whatever for it.
So you end up with the statement: I found a simpler solution of a sudoku problem because I made it simpler. :)

I don't make it simpler, i just use a property, it should have.
Besides the simplification effect there are more disadvantages. In case that the puzzle is unsolvable anyway, using uniqueness and finding a contradiction makes it impossible to distinguish between "really unsolvable" and "not unique". Not so important, also not desirable.

Yes, when a puzzle has multiple solutions, uniqueness techniques can give wrong results. And what does your method do with it ? Give up not knowing, if it does have a (unique) solution - or loop forever trying to find one ? Or do you cheat by first verifying, if it is unique - and then quickly forget that, because you don't want you use it ?
One of my long term goals is defining a function that gives "elegant" or "simple" a well defined value based on definite principles. Such function would allow to compare solutions by a "quality". Ideas are welcome.

Good luck.
Comparison of solutions sequences using redundant clues (or uniqueness) with normal solution sequences are obviously useless. Not desirable.

So you obviously have not understood the basics of uniqueness techniques.
And i really do not advise you to catch it up now. Just forget them for now, and try to make more concrete, for what you needed so much words, just leaving a cloud of mist so far.
eleven
 
Posts: 1561
Joined: 10 February 2008

Re: set vs sequence

Postby logel » Wed Apr 24, 2013 11:02 pm

Hi Denis
I needed to read this post three times to get what is baffling me at most.

denis_berthier wrote:Now, let me state an objection I have to logel's claim of universality.

It is very basic and it is the same objection I had to Allan's similar erroneous claim, years ago.

Most of the known patterns fall into two broad families:
- Subsets (Naked, Hidden or Super-Hidden), g-Subsets
- chains (reversible or oriented)
For both families, the proof that a target can be eliminated is obvious.
I've shown that oriented chains subsume most (but not all) cases of Subsets, in the sense that these Subsets can also be seen as oriented chains with the same targets. I've also shown that chains are much more powerful than Subsets of same size. However, I've never claimed that chains are a universal pattern - which would clearly be false, considering the (rare but real) cases of non-subsumption.

What I want to recall in the context of this thread is that any claim that the first family above is universal is clearly false. A chain cannot be considered as a mere set of CSP-variables (base set) and constraints. In such a view, something would be lost: the order of the chain. As a result, the proof of validity the chain carries with it would also be lost (and the complexity of proving validity increased).

The elementary mathematical basis for this is (symbolically) "sequence = set + order relation on this set".


You seem to see a contradiction where is absolutely none.

The (intended) universality of my definition just says that all elimations based on constraints only (explicitly excluding uniqueness) have some common properties.
And I state
- the base set property says that listing the base lines and a target is sufficient to declare the pattern
- in other words: two pattern with the same base lines and same target are identical (no order required, all links depend on the base lines) => this seems no problem for you
- validation of the target to be false is always possible using common properties alone (no order required, permutation check) => seem to cause alarm
- all Subsets, g-Subsets, chains, braids, etc are subclasses (any counter example?)

So if you construct patterns from your definitions, they do nor loose their special properties, only because they comply additionally to the universal definition.
And of course you can use their special chain properties to define a better, smarter or more efficient validation procedure, if you like.

But the conclusion that chains cannot comply to the universal defininition, because they can only be verified by a chain procedure, is incomprehensible.

I rather see an advantage to have a definition covering all. Now its possible to define size for the most general class. This is especially important for pattern derived from level-one contradiction pathes, their size is calculated from the steps.
If you use e.g. braid eliminations on level-one you mostly construct a non-braid elimation for the global level. So the size of such construction is "undefined" using your braid-size.
What now? Independant size definitions for different pattern classes? Not my road to go.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Universal Elimination Pattern for hard puzzles

Postby logel » Wed Apr 24, 2013 11:14 pm

Hi tarek
I appreciate your long term project "ultimate fish guide". From my point of view its a dictionary of all possible elimination pattern of a single number plane. right?
Did you ever prove the completeness? That would make it very valuable.

tarek wrote:The idea of universal solving technique / pattern is an attractive one and is something that I would encourage forum members to work on even if there seems to no light at the end of the tunnel or if there is a déjà vu situation.

Most of the hard work in the Ultimate Fish Guide came from collective ideas/work by forum members. Because it was constructed on solid foundations, it allowed the extension of its concepts to what has been described before by Alan, Dennis and others. There is no harm in exploring ideas or methods that have been discussed before if the result would lead to a Fresh result. I guess that until we get the Fresh result, the process will look far from it.

The oversimplifying sarcastic thread can be found here at the The Ultimate Lizard Guide


I do not like the term "universal solving technique". This can easily misunderstood and rise unrealistic expectations. There is no magic sword for sudoku.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: CSP variable vs constraint

Postby logel » Thu Apr 25, 2013 12:40 am

Hi blue
embarrassing XOR blunder, but ...

blue wrote:For logel,

I think you should heed Denis' advice, and include the "lines" (or whatever you'll call them) in the definition, from the start (along with the "links"). When you use the term "valid permutation of the candidates", it has little meaning without them. Your original definition, and 1st modification -- both in terms of candidates only, had this flaw:

Code: Select all
1 . . | 1 . .  | . . .          1 . . | 1 . .  | . . .
/ . . | / . .  | . . .          / . . | / . .  | . . .
/ . . | / . .  | . . .          / . . | / . .  | . . .
------+--------+------          ------+--------+------
1 . . | 1 . 1* | . . .          1 . . | 1 . 1* | . . .
/ . . | / . .  | . . .          / . . | / . .  | . . .
/ . . | / . .  | . . .          / . . | / . .  | . . .
------+--------+------          ------+--------+------
/ . . | / . .  | . . .          / . . | / . .  | . . .
/ . . | / . .  | . . .          / . . | / . .  | . . .
/ . . | / . .  | . . .          1 . . | / . .  | . . .


The '/'s mark cells where there is no '1' candidate.
The '*' marks a (possible) target candidate.
The diagram on the left, shows a situation where an X-Wing elimination is possible.
The diagram on the right, shows the same thing with an extra '1' candidate in r9c1 -- where there is no X-Wing elimination.
For the 2nd diagram, I didn't see anything in your definition, that would block me from simply ignoring the 1r9c1 candidate, and focusing on the '1' candidates in the diagram on the left.
It's (slightly) possible that the bit about "valid permutations of the candidates", was meant to block that, but if that's the case, it wasn't made clear.

The expression "valid permutations of the candidates" means "valid permutations of the candidate values", if this make it more precise. It has the same meaning as in xsudo. Permutating the candidates itself make no sense.
You can of course focus on the five candidates at the top, but ignoring 1r9c1 does not mean that you can ignore the constraint relation to the other two candidates in the column.
So the right pattern has a permutation like this:
Code: Select all
F . . | T . .  | . . .
/ . . | / . .  | . . .
/ . . | / . .  | . . .
------+--------+------
F . . | F . T* | . . .
/ . . | / . .  | . . .
/ . . | / . .  | . . .
------+--------+------
/ . . | / . .  | . . .
/ . . | / . .  | . . .
+ . . | / . .  | . . .

Its a valid permutation because none of the basic constraints is violated. 1r9c1 is true if there are no other candidates in the column.
The definition says that all valid permutations of candidate (values) must assign F for a target. So the definition is not met.
I never expected that my definition rises so many questions.
Its just another view on well known things. The main purpose of the definition is that it should work for all patterns that may result from reduction of larger candidate sets.
That of course requires to cover existing pattern definitions (excluding uniqueness).
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: set vs sequence

Postby denis_berthier » Thu Apr 25, 2013 3:02 am

Hi logel,
I must say I'm rather disappointed with your answers.
As I said before, I don't mind about not using uniqueness. It's a pity that this topic, totally irrelevant to your approach, is discussed again, with always the same old flawed arguments.
But the problem is, your answers shed no light on your definitions.


logel wrote:
denis_berthier wrote:Now, let me state an objection I have to logel's claim of universality.
It is very basic and it is the same objection I had to Allan's similar erroneous claim, years ago.
[...]
The elementary mathematical basis for this is (symbolically) "sequence = set + order relation on this set".

You seem to see a contradiction where is absolutely none.
[...]
the conclusion that chains cannot comply to the universal defininition, because they can only be verified by a chain procedure, is incomprehensible.

Apparently, you have problems with logic.
If I say that a sequence is more than a set, it doesn't mean that a sequence is not a set.
Maybe, you didn't understand my "symbolic" writing. Let me write it more formally: Seq = {Set, <}, where < is an order relation, i.e. some subset of SxS with the relevant properties of an order. If you forget the <, there remains the Set.


logel wrote:I rather see an advantage to have a definition covering all. Now its possible to define size for the most general class. This is especially important for pattern derived from level-one contradiction pathes, their size is calculated from the steps.

Unfortunately, until now your "universal pattern" X can solve all the puzzles only if you use it in T&E(X). So, what does universality mean here ?
As for "deriving the size from the steps", we already talked of this in the "Pattern-based classification of (hard) puzzles" thread, but you had no idea of how to do this, even in the simplest case of a sequence of Singles.
Moreover, when you use T&E, you don't get the shortest path, so any size definition for a "pattern derived from level-one contradiction pathes", i.e. based on T&E, is totally meaningless.


logel wrote:If you use e.g. braid eliminations on level-one you mostly construct a non-braid elimation for the global level. So the size of such construction is "undefined" using your braid-size.

I've already answered this several times.
Braids are enough to solve and the B rating is enough to rate all the puzzles in T&E(1).
If you want to solve/rate all the puzzles (i.e. including those in T&E(2)), you need to use B7-braids and the B7B rating. In a restricted sense of "universal" (= they can do, without requiring any level of T&E, all the eliminations necessary to solve all the puzzles), B7-braids are a universal pattern and the B7B rating a universal rating.
But I've never said and will never say that any pattern has to be a B7-braid (or even a B-braid).


Finally, I'll raise a question of methodology.
Your goals are extremely ambitious: you want to define a universal pattern (in a sense of "universal" still undefined); you want to define a rating based on the global solution path instead of the hardest step; and you want to deal with the hardest puzzles.
BUT:
- it appears that your "universal pattern" X can solve all the puzzles only if applied in T&E(X); we already know that a relatively simple pattern can do this (e.g. braids[7]); so X also should be rather simple;
- your rating is not defined for puzzles not solvable by X, i.e. it is defined only for relatively easy puzzles;
- if, based on X only, you ever define a rating for the total resolution path, it will have to deal with paths of paths of X-eliminations.

In view of my above remark about paths of Singles, this is obviously not a sustainable research program.
Why don't you forget about the hardest puzzles and T&E and why don't you merely solve a moderate level puzzle using only X ?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: set vs sequence

Postby eleven » Thu Apr 25, 2013 8:51 am

denis_berthier wrote:...the same old flawed arguments.

Can't you stop it ? Your bombastic rules set cannot even solve a 77 clue puzzle with 2 solutions, but you refuse to accept uniqueness as part of the definition ? They are allowed, but you don't handle them ? That's ridiculous.
eleven
 
Posts: 1561
Joined: 10 February 2008

Re: set vs sequence

Postby denis_berthier » Thu Apr 25, 2013 10:03 am

eleven wrote:
leren wrote:...
And don't you know, that - when uniqueness methods are allowed - a puzzle also can become harder, when you add a clue, because with this clue you can't apply the technique anymore ?

eleven wrote:
denis_berthier wrote:...the same old flawed arguments.
Can't you stop it ?

You present as an evidence something that is only due to a logical flaw in some view of resolution (and in SER).
In a pure logic approach, adding an axiom (here the clue) can never lead to fewer conclusions.


eleven wrote:Your bombastic rules set cannot even solve a 77 clue puzzle with 2 solutions

No multi-sol puzzle can be solved with methods based only on logical inference. You should know (especially as this has been discussed years ago) that a logical theory can only prove properties that are common to all its models - this is really basic logic. Two solutions means two models with different values for at least 1 (and therefore more) cell(s).
If you want to go beyond the part common to the two models, you have to TRY the various possibilities remaining valid after all the rules have been applied, which is a form of delayed T&E. Of course, I can do this. This leads to a multi-solution of type P0(=the common part) AND (P1 OR P2 OR ...). (And I can also use the rules based on uniqueness that I have programmed in SudoRules, and I can even apply them before some of the other rules, but I usually choose not to use them)


eleven wrote:but you refuse to accept uniqueness as part of the definition ?

I don't refuse to accept using rules of uniqueness: I always said that it's a matter of personal taste. Mmmm, seems you said the same thing a few posts above.
What I refuse is to say that uniqueness is a constraint of Sudoku solving, because there's nothing the player can do to ensure uniqueness.


Now, if you want to discuss uniqueness again - which is IMO totally pointless, as there is no new argument - , I suggest you open another thread. logel's view on this point is totally clear, I don't think we should pollute his thread with this old debate. There are sufficiently many other points that need a clarification.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to General