Universal Elimination Pattern for hard puzzles

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

Universal Elimination Pattern for hard puzzles

Postby logel » Fri Apr 19, 2013 2:21 pm

This thread is intended to throw some light on aspects of sudoku that I had not found somewhere else. If you look for tips or methods for manual solving, this thread is not for you. It is purely theoretical. Nevertheless I can show some interesting experimental results especially for solving very hard sudoku problems.

Introduction: (skip if boring)

The term “solution” denotes a full set of numbers (symbols) complying with all base constraints of sudoku. Each particular sudoku problem can be unsolvable, or has one to many solutions. Sudoku is NP-complete (proof elsewhere). That translates to: The only way to solve a sudoku problem completely is to explore all possible cases. This is done by backtracking, possibly enhanced by cutting off assured dead branches. The procedure is quick and efficient and solves all sudoku with all multiple solutions if existing. So there are no remaining unsolved sudoku problems. Or in other words: Solving sudoku is trivial.

So what about all the solvers based on methods and rules discussed in this forum are doing other than solving already solved problems?
Answer (intentionally provocative): Any attempt to build a solver from a limited number of methods and rules is futile. Such solvers will either not solve all sudoku, or if one is meant to solve all, the proof is another and very large NP-complete problem.

The value of methods and rules is not solving but analysis. Unfortunately mostly the possible goals of this analysis is not clearly defined. That results frequently in misunderstanding and unproductive discussions. I do not intend to diminish the value of rules and traditional methods, but at least for me it is important to put them in the right place. In spite of everything I continue to use the term solver like anyone else.

If you have a solution for a particular sudoku, its correctness can be verified by itself. There is absolutely no need to present how the solution was found. This is different from the statement, that the sudoku can be solved e.g. with singles, pairs and triples. You have to show up with an appropriate elimination sequence to prove this statement.

There are two completely different directions of analysis goals.
- You can analyze properties of a particular sudoku and compare these with other sudoku.
Any scalable property defines a specific aspect of rating. (I come back to this important point later).
Additionally you have classes of problems with the same shared properties.
- You can analyze the scope of rules and rule sets.
This results in classes of sudoku solvable by such rule/method sets.
How to compare such classes is not obvious generally.

Sorry for the long introduction. Two more posts to come.

1) definition of universal elimination pattern independent from rules
along with an explanation why this is necessary
some general properties and resulting consequences for rating
2) experimental solving results on a large set of very hard sudoku with
application of universal eliminations at level 1 ( one candidate assumption )
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Cont: Universal Elimination Pattern

Postby logel » Fri Apr 19, 2013 2:46 pm

Universal Elimination Pattern:

It seems that rules/methods are commonly seen as the primary objects for sudoku solving. And patterns are regarded as instances of these rules when the rule conditions are met.There are very good reasons to see patterns as the primary objects. This is the main point of this post. As rules work fine on easy and medium severe sudoku. They automate manual solving techniques. Hard and very hard ones require mostly individual procedures for solving by constraint propagation.
Also trying to put rules into a definite order is questionable and not convincing for me.
See the thread: ordering-the-rules
The only systematic approach is done by Denis Berthier with his braid definition. But unfortunately a generalisation to universal patterns is not obvious.

Systems of rules/methods constitute a bottom-up approach for solving. When constructing patterns top-down from larger structures rules are not helpful any more.

I ran into this problem when implementing a solver based on permutations.

Example: Consider the number planes of all candidates with numbers 2 or 5. Now we build all permutations of true and false candidate states that comply with all relevant constraints. This way we get all multiple solutions of this partial sudoku. The number of such permutations is some thousand - large but not unmanageable. Every elimination that affects these two numbers will cancel some of the permutations. Now we observe the number of still valid permutations, where a particular candidate of the planes has the value true. If this number drops to zero, the candidate is always false in the combined planes 2 plus 5 and therefore false globally. On the other hand if all candidates of the plane pair have a true value with at least one of the permutations, its impossible to find eliminations inside that planes with whatever methods, provided that only row/col/box constraints of the two planes and cell constraints connecting the planes are used.

Two things are important:
- Usually not all objects of the planes are necessary to produce the elimination.
This calls for a reduction until a minimal configuration is reached that still works.
There a many possible minimal pattern generally.

- A relationship to one of the traditional rules/methods does not exist in the general case, although in some cases a reverse engineering may find a rule that fits.

Any reduction can always be done by stripping off candidates one by one and checking the remaining permutations. This is of course not practical but nevertheless possible.

It motivates the following definition:

An Universal Elimination Pattern is a set of candidates along with a set of links connecting the candidates according to basic sudoku constraints, where
(1) exactly one designated candidate is the elimination target ( single target )
(2) the target value is false for all valid permutations of candidate values ( elimination )
(3) all candidates and all links in the set are absolutely necessary for (2) ( minimal set )
(4) there exists no subset of the defining candidate set that is a separate universal elimination pattern ( no cascading )
corrected

The attribute universal is meant programmatic of course. If anyone has a more universal definition of eliminations, I would like to hear. The definition covers all traditional elimination methods and rules – afaik, so there is no conflict.

Note that there is intentionally only one target candidate and no elimination pattern without target. The term link stands for a logical constraint equations restricted to the candidates in the set. The term pattern core will be used for the set of candidates without the target.

Another little definition:
A line is the set of all still undecided candidates belonging to a single constraint.
This is also called unit elsewhere, but I am not sure if it means the same thing. A line can be a row, column, box of the same number or a cell - reduced to the unknown candidates.

Universal elimination pattern have some nice general properties:

From the definition follows immediately:
- None of the candidates of the pattern core has a fixed value.
- The candidates build a connected graph, where each candidate – including the target - has at least two neighbours.
- Assuming the target to be true creates inevitably a contradiction inside the pattern.

Most important is the following statement:
The pattern core of a universal elimination pattern is equal to the union of all lines of the pattern core. (discarded)
The pattern core of a universal elimination pattern is equal to the union of all those lines, where all line candidates are also members of the pattern core.corrected
That says that all candidates of the pattern core must be also be member of some line that is fully covered by the pattern core.edited
Consequently the pattern core can be relabelled as a set of lines. This is easy to prove.
In many cases where lines in the set do overlap some of the lines (not their candidates) are dispensable.
So a subsequent reduction of lines is possible and applied. The remaining minimal set of lines is called base set (in appreciation of Allen Barkers ideas).

This implies: Any (universal) elimination pattern is fully determined by enumerating its base set.
This implies also that the link structure (net or queue) and other properties depend on the base set.
In other words: The base set is defining the elimination, but stop … wait …

This requires the base set to be unique for a particular elimination pattern. That would be really great. But a proof seems not so easy. Ideas welcome.

So I put the uniqueness of the base set of an elimination pattern as a conjecture here.
The conjecture is true for all practical cases, but I have some doubts.

Now is the time to introduce size for universal elimination pattern. Any size function is an aspect of complexity of the pattern and relies solely on properties of the pattern itself. This is often confused with the severity of a pattern depending on properties of the solver and quantifies the difficulty to find it. The severity therefore is always relative to a solver only.

As complexity is like beauty - only in the eye of the beholder - there are many size functions.

For the next chapter I will use the number of lines in the base set as pattern size. Its also equal to the maximal number of true candidates in the pattern core. This is not my favourite size function because it has some disadvantages. But it is easy computable and easy comparable with other results. Discussion of alternatives would overload this post and is saved for later.
Last edited by logel on Sat Apr 20, 2013 10:09 am, edited 1 time in total.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Cont: Permutation based Solving

Postby logel » Fri Apr 19, 2013 3:10 pm

Results with permutation based solving.

A huge amount of very hard sudoku – all SER rated 10.3 or higher – is published in thread the-hardest-sudokus. The current collection contains 817681 soduku, much more than last year. So thanks to all who spent time on that project.

My solver works with permutation of planes in the manner described in the previous post. Using a single number plane is not new and known as template method. But you can do more and use plane pairs and plane triples.
There are 9 number planes and 9 each with rows, columns and boxes. Then we have 36 plane pairs of number planes and the same number each with row/col/box. I use also plane triples with non-overlapping planes. Together with the 84 number plane triples its 264 plane sets already. There are more details to explain, but this post can only sketch the procedure.
The computation of all permutations of all planes sets can be done in reasonable time.

It is no surprise that direct eliminations even from triple planes achieve little to nothing when applied to any puzzle in the list. The problems in the collection are really hard.
So we have to switch to level one, that is assuming a candidate to be true and applying a series of eliminations until a contradiction occurs confirming the candidate to be false.

Results: There are many and I selected the most interesting parts.

Applying singles at level one finds no elimination for all sudoku in the collection. This comfirms the 10+ rating.
With a sequence of patterns with two base lines (pairs, 2-string-kite, etc) - braid(2) by DB terminology - many elimination candidates are identified. In ~50% of all cases its enough to resolve the sudoku completely by repeating the procedure.

My first goal was to find a limit of level-one eliminations that are sufficient to build a contradiction for an assumed candidate.
So consequently the next step is to use all eliminations of a single plain, that is all fish pattern of a single number, row, column or box. Only 307 sudoku of the collection can resist this powerful attack and almost all of them live in the upper 3000 of the collection.
The remaining problems need eliminations of plane triples of number planes on level one.
That is enough.

Although some limit is found, the result is not really satisfying because nothing is known about the size of the level-one eliminations let alone the size of the resulting base elimination.

Only after reducing level-one eliminations to their minimal configuration, that is reducing to universal elimination pattern (see above), any size function makes sense. What is difficult with reductions is not finding one but finding the smallest result of the many possible ones. This problem is also NP-complete, but smaller than bottom-up construction.
With pattern from plane pairs we find sizes (counting base lines) up to 12-14, from plane triples up to 20 base lines.

It seems almost evident that pattern with large sizes are not necessary to assure solving. This is confirmed by discarding all patterns larger than 10 base lines in the procedure. We can still solve all with eliminations from plane triples of numbers in the worst case. Now we reduce the limit step by step.
The critical pattern size is found at six base lines for level-one eliminations. Solutions are still possible, but besides the plain triples of number plains, plane sets from three rows/columns/boxes need to be scanned additionally, in some cases even more mixed ones.

Conclusion, or what can we learn:
Mainly it shows that even the most severe sudoku can be solved by a constraint propagation sequence that is computable with reasonable effort.
Even if the used elimination patterns are very complex on the base level, they can be assembled from pieces of limited size.

Next steps to do:
The level-one sequences need to be reduced to universal elimination patterns on the base level. They contain lots of redundant stuff usually. Only reduced patterns can be sized properly.
More research is needed to understand the relation between level-one and base level pattern size.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Cont: Universal Elimination Pattern

Postby eleven » Fri Apr 19, 2013 11:12 pm

logel wrote:The definition covers all traditional elimination methods and rules – afaik, so there is no conflict.

Uniqueness methods too ? Can't be sure, this is a bit too high for me:
logel wrote:The term pattern core will be used for the set of candidates without the target. (...)
A line is a set of all still undecided candidates belonging to a single constraint. (...)
The pattern core of a universal elimination pattern is equal to the union of all lines of the pattern core.

So i have:
The set of candidates without the target of a universal elimination pattern is equal to the union of all sets of all still undecided candidates belonging to a single constraint of the set of candidates without the target.
eleven
 
Posts: 1582
Joined: 10 February 2008

Re: Cont: Universal Elimination Pattern

Postby denis_berthier » Sat Apr 20, 2013 2:35 am

eleven wrote:
logel wrote:The definition covers all traditional elimination methods and rules – afaik, so there is no conflict.
Uniqueness methods too ?

No.

eleven wrote:
logel wrote:The term pattern core will be used for the set of candidates without the target. (...)
A line is a set of all still undecided candidates belonging to a single constraint. (...)
The pattern core of a universal elimination pattern is equal to the union of all lines of the pattern core.

So i have:
The set of candidates without the target of a universal elimination pattern is equal to the union of all sets of all still undecided candidates belonging to a single constraint of the set of candidates without the target.


Instead of "... is equal to the union of ...", the second sentence should be "... is the set of ..."
But this supposes all the definitions are reformulated in terms of CSP variables before speaking of candidates.
What logel calls a "line" is the set of candidates remaining in what I've been calling a 2D cell (rc, rn, cn or bn) ever since I published "The Hidden Logic of Sudoku"; a "logel line" appear as the contents of an undecided cell of the extended Sudoku board; the latter is a kind of extended PM.
Allan Barker renamed this a Truth - a very confusing name.
In the general context of any finite CSP, as I have developed it more recently, a "logel line" is merely the set of remaining candidates for an undecided CSP variable.
We had a similar discussion in the "Pattern-based classification of (hard) puzzles" thread.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Universal Elimination Pattern for hard puzzles

Postby denis_berthier » Sat Apr 20, 2013 2:59 am

logel wrote:So what about all the solvers based on methods and rules discussed in this forum are doing other than solving already solved problems?


There may be various motivations for pattern-based solving and one may have various ideas about what a legitimate pattern is. What's common to all these motivations is, one is more interested in the resolution path (i.e. in the proof of the solution) than in the solution itself.


logel wrote:Answer (intentionally provocative): Any attempt to build a solver from a limited number of methods and rules is futile. Such solvers will either not solve all sudoku, or if one is meant to solve all, the proof is another and very large NP-complete problem.

For fixed size n=9, NP-completeness (at least, as currently formulated in terms of the size of the grid, but the same remark would apply if it was in terms of candidates) is irrelevant.
With a hierarchy of rules of increasing complexity, one can solve all the puzzles, activating the more complex rules only when necessary.
What appears is IMO an explanation of NP-completeness: in most cases the solution will involve simple rules, but there is a very broad spectrum of complexity for exceptional instances. Indeed, 99.9% of the minimal puzzles (unbiased stats) can be solved by whips of length <= 7 and fewer than one puzzle in 30,000,000 require more complex rules than braids.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Cont: Universal Elimination Pattern

Postby denis_berthier » Sat Apr 20, 2013 3:23 am

logel wrote:An Universal Elimination Pattern is a set of candidates along with a set of links connecting the candidates according to basic sudoku constraints, where
(1) exactly one designated candidate is the elimination target ( single target )
(2) the target value is false for all valid permutations of candidate values ( elimination )
(3) all candidates and all links in the set are absolutely necessary for (2) ( minimal set )
(4) there exists no subset that is a separate universal elimination pattern ( no cascading )

(4): subset of what? Of candidates, of links or (more properly) of CSP variables?
(3) and (4) are somehow redundant
(3): "all links" is impossible to guarantee (see the NP example below)


logel wrote:In many cases where lines in the set do overlap some of the lines (not their candidates) are dispensable.

This contradicts your point (3) above.


logel wrote:This implies: Any (universal) elimination pattern is fully determined by enumerating its base set.
This implies also that the link structure (net or queue) and other properties depend on the base set.
In other words: The base set is defining the elimination, but stop … wait …

This requires the base set to be unique for a particular elimination pattern. That would be really great. But a proof seems not so easy. Ideas welcome.
So I put the uniqueness of the base set of an elimination pattern as a conjecture here.
The conjecture is true for all practical cases, but I have some doubts.

The conjecture is trivially false. Take a Naked Pairs based on two cells in a mini-row. You can consider it both as a Pairs in a row or as Pairs in a block. In the 3rd cell in the mini-row, any NP elimination can be done by any of the two different patterns.


logel wrote:I will use the number of lines in the base set as pattern size. Its also equal to the maximal number of true candidates in the pattern core. This is not my favourite size function because it has some disadvantages. But it is easy computable and easy comparable with other results. Discussion of alternatives would overload this post and is saved for later.

See my suggestion for this definition of size in the "Pattern-based classification of (hard) puzzles" thread. This is the definition I use for all "my" patterns: whips, braids, extended whips or braids, Subsets, g-Subsets. So, at least, we have compatibility on this important point.


My overall conclusion: you should re-formulate your definition with the base set as the primary data.
Last edited by denis_berthier on Sat Apr 20, 2013 3:43 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Cont: Universal Elimination Pattern

Postby champagne » Sat Apr 20, 2013 3:37 am

logel wrote:Universal Elimination Pattern:

This requires the base set to be unique for a particular elimination pattern. That would be really great. But a proof seems not so easy. Ideas welcome.

So I put the uniqueness of the base set of an elimination pattern as a conjecture here.
The conjecture is true for all practical cases, but I have some doubts.


Generally speaking, this text could be improved by examples.

At the end, although I worked a lot on Allan Barker approach, I am not at all sure that my comments are in line with the text.

in the thread exotic-patterns-a-resume you can find long discussions about the big rank 0 logic.

This seems to be quite in line with your definition of a base set.

When a puzzle has a SK loop pattern, it has been shown that at least 4 different rank 0 logic lead to the same eliminations.
One has a row base, one a columns base, one a mixed base and one a cells base. Each of them could be said "minimal" in it's group.

For simpler cases, we all know that an elimination can often be achieved through different logic constructions. Each of theses construction has a corresponding "truths links" diagram in Allan Barker model.
champagne
2017 Supporter
 
Posts: 5745
Joined: 02 August 2007
Location: France Brittany

Re: Cont: Permutation based Solving

Postby denis_berthier » Sat Apr 20, 2013 3:57 am

logel wrote:Applying singles at level one finds no elimination for all sudoku in the collection.

What you call "level one" is T&E.
There's no puzzle in T&E(1) in this collection.


logel wrote:The critical pattern size is found at six base lines for level-one eliminations. Solutions are still possible, but besides the plain triples of number plains, plane sets from three rows/columns/boxes need to be scanned additionally, in some cases even more mixed ones.

So, T&E(P6) solves all the known puzzles, where P6 is the set of all patterns with a base set of size <= 6. Moreover, you can restric P6 to a subset as you described. This is the interesting result, in line with my old result that 97% of the top-down generated puzzles could be solved by patterns lying completely in one of the 4 2D spaces. Said otherwise, only limited interaction between the four kinds of CSP variables (rc, rn, cn, bn) is needed.


logel wrote:Next steps to do:
The level-one sequences need to be reduced to universal elimination patterns on the base level. They contain lots of redundant stuff usually. Only reduced patterns can be sized properly.
More research is needed to understand the relation between level-one and base level pattern size.

Theoretically, P6-braids and the simplest-first strategy will do the job. But P6-braids are very complex animals.

If you are consistent in your approach, you should apply your universal pattern without any T&E, just by increasing the size of the base set. Maybe, then, you'll meet the complexity problem.
Last edited by denis_berthier on Sat Apr 20, 2013 5:10 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Complexity of the Universal Elimination Pattern

Postby denis_berthier » Sat Apr 20, 2013 4:28 am

logel wrote:I will use the number of lines in the base set as pattern size. Its also equal to the maximal number of true candidates in the pattern core. This is not my favourite size function because it has some disadvantages. But it is easy computable and easy comparable with other results. Discussion of alternatives would overload this post and is saved for later.


Defining the size of a pattern is one thing. Analysing its relation with complexity is another one.

I know two main broad families of patterns where size can be defined and easily related to complexity:
- whips, braids, g-whips, g-braids, S-whips, ... B-braids: I defined their size as their total length (including the length of the inner patterns, if any);
- Subsets and g-Subsets: their size can trivially be defined as the number of CSP variables they rely on (the cardinal of their "base set").
In the many cases where a set of candidates can be seen as either of these patterns, the two definitions coincide.
The main point is, for both kinds of patterns, checking the validity of any instance in a particular resolution state (PM) is straightforward: they carry their own proof with their definition.
As a result, their complexity is easily related to their size.

In your approach, proving the validity of a pattern once you have written it requires that the reader tries all the truth value assignments for all the candidates in the pattern; this is exponential in the number of candidates. This is a degree of inner complexity that is added to that inherent in size.

Allan Barker had the same problem. For this reason, he could never define a rating associated with his rules and he never even claimed completeness of his program wrt his abstract definitions.
Instead, he introduced two things:
- some obscure considerations about dark logic, (when rank is <>0, i.e. in cases that are neither Subsets nor g-Subsets),
- a procedure (he called them ribbons) that was merely a partial implementation of the Sp-braids I had defined two years before; since then, he has withdrawn this from his website.

What I mean is, one can indeed define very general types of patterns. The question is how one can use them.
This brings us back to your introduction.
You were right to start with a discussion of motivations.
But, if having an understandable proof of the solution is the motivation - as it is generally for Sudoku players -, one will not want to use patterns such that each step of the proof (each elimination) requires long additional computations (check all the "permutations") to be proven. This is the advantage of having a properly restricted set of patterns such that seeing one of them provides a direct proof of its eliminations.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Cont: Universal Elimination Pattern

Postby logel » Sat Apr 20, 2013 10:46 am

eleven wrote:
logel wrote:The definition covers all traditional elimination methods and rules – afaik, so there is no conflict.

Uniqueness methods too ?

The ALL is indeed questionable and overshoots.
My definition is intended to cover all eliminations that rely on the basic sudoku constraints.
What you call uniqueness methods are methods that construct a contradiction to some basic constraints AND uniqueness of the solution.

I see some problem because
- You use a property of the puzzle prior confirming it. Clearly incorrect logically.
OR You modify the original problem statement (why ???). That is not desirable and invites trouble.

I do not object to analyzing knowledge states of sudoku for uniqueness contradicting patterns. Yields some interesting results and may hint to candidates for further elimination.

But because I see absolutely no reason to modify the problem statement, I reject using uniqueness methods in the solving sequence.
I know that other people have a different view, but I never heard a sound reasoning.

eleven wrote:Can't be sure, this is a bit too high for me:
logel wrote:The term pattern core will be used for the set of candidates without the target. (...)
A line is a set of all still undecided candidates belonging to a single constraint. (...)
The pattern core of a universal elimination pattern is equal to the union of all lines of the pattern core.

So i have:
The set of candidates without the target of a universal elimination pattern is equal to the union of all sets of all still undecided candidates belonging to a single constraint of the set of candidates without the target.


Sounds really stupid. I corrected the statement to what was intended:

The pattern core of a universal elimination pattern is equal to the union of all those lines, where all line candidates are also members of the pattern core.

It finally says that one can designate all (universal) eliminations but enumerating some lines - the base lines.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Universal Elimination Pattern for hard puzzles

Postby dobrichev » Sat Apr 20, 2013 11:17 am

Hi logel,

I found much fresh ideas in your approach and wish you not to lose motivation. I did some elementary steps in the same direction long time ago, and lost interest due to the terminology, which for some of the active participants in this forum is evolved to religion, this successfully hiding their personal contributions.

Look positive on all remarks on your work and fire ahead.

logel wrote:But because I see absolutely no reason to modify the problem statement, I reject using uniqueness methods in the solving sequence.

One of the reasons is not to deal with The Ultimate Zero Givens Puzzle which most likely is far from your interests too.
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Cont: Universal Elimination Pattern

Postby logel » Sat Apr 20, 2013 11:21 am

champagne wrote:Generally speaking, this text could be improved by examples.

YES! here a (simple) example:
Code: Select all
+------+-------+------+
|      | T     | t    |
|      |       |      |
|    X |       | X    |
+------+-------+------+
|    X | X     | X    |
|      |       |      |
|      |       | t    |
+------+-------+------+
|      |       |      |
|    X | X     | X    |
|      |       |      |
+------+-------+------+


It shows a triple of some single number stripped to the essentials.
The universal elimination set consists of all 'X' and the 'T' as target. The 't' are other candidates of that number and everything else is clear.
The 't' do not belong to the elimination, although they are possible alternative targets.

So we have four lines that satisfy the conditions for base lines, as they are fully covered. These are row 3,4,8 and column 3.
The union of these lines is equal to the pattern core, but everyone can see that alone the union of row 3,4,5 does the same.
As further reduction of lines with that property is impossible, row 3,4,5 are the base lines.

For a rank-0 logic like this example it looks trivial, is well known and easy.
But what I say is that you can find base lines for all eliminations based on the basic sudoku constraints regardless how they are found or constructed.

champagne wrote:At the end, although I worked a lot on Allan Barker approach, I am not at all sure that my comments are in line with the text.

in the thread exotic-patterns-a-resume you can find long discussions about the big rank 0 logic.

This seems to be quite in line with your definition of a base set.

When a puzzle has a SK loop pattern, it has been shown that at least 4 different rank 0 logic lead to the same eliminations.
One has a row base, one a columns base, one a mixed base and one a cells base. Each of them could be said "minimal" in it's group.

For simpler cases, we all know that an elimination can often be achieved through different logic constructions. Each of theses construction has a corresponding "truths links" diagram in Allan Barker model.


The symmetric rank-0 pattern always attract special attention, but I doubt that you can solve with rank-0 alone.
I will read again the thread you pointed at.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Cont: Universal Elimination Pattern

Postby champagne » Sat Apr 20, 2013 7:08 pm

logel wrote:YES! here a (simple) example:
Code: Select all
+------+-------+------+
|      | T     | t    |
|      |       |      |
|    X |       | X    |
+------+-------+------+
|    X | X     | X    |
|      |       |      |
|      |       | t    |
+------+-------+------+
|      |       |      |
|    X | X     | X    |
|      |       |      |
+------+-------+------+


It shows a triple of some single number stripped to the essentials.
The universal elimination set consists of all 'X' and the 'T' as target. The 't' are other candidates of that number and everything else is clear.
The 't' do not belong to the elimination, although they are possible alternative targets.

So we have four lines that satisfy the conditions for base lines, as they are fully covered. These are row 3,4,8 and column 3.
The union of these lines is equal to the pattern core, but everyone can see that alone the union of row 3,4,5 does the same.
As further reduction of lines with that property is impossible, row 3,4,5 are the base lines.

For a rank-0 logic like this example it looks trivial, is well known and easy.
But what I say is that you can find base lines for all eliminations based on the basic sudoku constraints regardless how they are found or constructed.


I usually take examples form existing puzzles, which prevent from "non realistic" pictures, but I can accept that one with the risk of a wrong analysis.
If I get it properly, this represents more or less a swordfish.
Showing 3 rows and a column as "potential core" is acceptable, but already highly challenging. That basis has 3 "double points". Not easy to work out to justify eliminations.
The "final picture" with 3 rows has no more overlaping sets. Here we have a clear logic.with the 3 links in column, we have a full rank 0 logic, and all 'T' and 't' are not valid.



logel wrote:The symmetric rank-0 pattern always attract special attention, but I doubt that you can solve with rank-0 alone.


symmetric or not, rank-0 patterns have a clear logic but as you say, it's not so often that you can use them.
It could be that we have still to learn a lot to find them. Two years ago, we knew nearly nothing about the rank 0 logic of multi fish patterns.

You took as example a swordfish. A finned swordfish is not a rank 0 logic.
In the field of hardest puzzles, the most common pattern is the "EXOCET" pattern. This is far from a rank 0 logic.
The classical pattern, in that case, has 3 or 4 triple points. Not so easy to handle as a set/linkset construction
champagne
2017 Supporter
 
Posts: 5745
Joined: 02 August 2007
Location: France Brittany

Re: Universal Elimination Pattern for hard puzzles

Postby Red Ed » Sat Apr 20, 2013 7:37 pm

As has been pointed out, this is a recurrent subject that many of us have dabbled in.

fwiw, my interest was in cataloguing all "fundamental patterns" that used a small number of truths/constraints. I mistakenly assumed the problem was simpler than it was, so my attempt failed. If I revisited the subject, I might be forced to use a more computationally-expensive definition:
  • A pattern is a set of holes (eliminated candidates) together with a target (candidate eliminated by those holes). Think of the elimination occurring as a result of the target being in contradiction with every possible way of solving some set of truths/constraints.
  • The "level" of the pattern is the smallest number of truths/constraints that eliminate the target.
  • The pattern is "fundamental" if all of the following hold:
    • Every hole is necessary for the target to be eliminated.
    • The target cannot be eliminated by the sequential application of any series of lower-level patterns.
With that definition, your Swordfish example would not be fundamental, as you have an unnecessary hole at r3c4.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Next

Return to General