The New Sudoku Players' Forum

[eleven]

The moderators may cut it off to another thread, if you don't stop to spread pseudo-scientific nonsense.
Model, what you want, in fact there are only 2 ways to get you out of the dilemma:
- You restrict your rules to be applicable to unique puzzles by definition only.
- You allow guessing (and therefore can also handle multisolution puzzles)
You refuse both - so it remains to be a ridiculous approach.

[denis_berthier]

eleven, I have no time to waste with your insults, which can only prove that you have no rational arguments.

[logel]

Hi champagne

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

I wonder what you exactly call "negative". If you might mean that my ideas are already used in a similar way by others - namely Alan - this is not negative at all. My positions is always that useful ideas should be shared.

1) It is very easy (but costly in terms of CPU consumption) to detect that combining several floors/planes some candidates can be discarded.

Especially your side note in parenthesis is very interesting, because its just the other way around with my implementation. I am not sure if we speak of the same thing, because floor as defined in sudopedia is different from what i call plane. Seems you are interested in implementation issues, so I will give some figures. The construction of data structures holding plane information about all 126 plane pairs that do not overlap has CPU cost of ~ 4 sec. In case you want to use also the 84 tripel number planes ~ 6 sec more are needed. This computation is done only once at initialization phase and used thousands of times for elimation checks. All checks and updates for all elimations until complete solving is < 0.3 sec. All timings related to 2MHz CPU 64 bit single thread. Also these figure do not depend on any rating of the puzzle. Thime timings for reduction comes on top of that. I think these timings are fair for very hard puzzles.

2) Alan Barker had a very efficient process to build a reduced "truths links" SLG to justify some of them.

That is very interesting too. I always surprised about the xsudo speed of computation of difficult solutions. My implementations never get even near that speed. But its a very large difference if you reduce to "fair" reduction result or if you try to find the minimum related to some predefined metric. My implementation of reduction is currently the weaker part.

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.

Direct face to face communication has 100 times more value than typing posts in this forum.

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;

YES,YES,YES ( to 4 ). Whenever I scan through my trace logs I know why (especially large) eliminations usually have hundres of variants.

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.

After several years of doing very litte sudoku, I feel that some significant progress might be possible.

[eleven]

logel,
forget my wish for an example, i am not interested anymore. The more i read, the clearer it is, that you are so far from producing (new) results of worth, that my time is better invested in digging gold in my bathtub.
Sorry and good luck.

[denis_berthier]

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 [emphasised by DB].

Does this mean that:
- in practice, i.e. in xsudo (although not in his definition), all of his patterns relied only on the combinations of a restricted number of floors/planes ?
- for those not included in the above "some of them", he used a less efficient algorithm or he merely discarded them in his algorithm ?

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;

Once an elimination has been justified by some "pattern", why would you want a second justification for it ? Are you looking for a simpler pattern not dealt with by Allan ?


You'll understand that my questions revolve around the following fundamental one.
- AFAIK, Allan never claimed any form of completeness for his algorithm, i.e. he never claimed it dealt with all his theoretical "patterns" (even when restricted to rank 0);
- still AFAIK, he never claimed that he could produce the "simplest" elimination (in the sense of using the "smallest" of his theoretical patterns or even of the implemented ones).
I've always thought that his algorithm couldn't be complete - for reasons of complexity (even if restricted to rank 0) and from some posts indicating he used chains instead of sets in his implementation. But (still AFAIK) he never said it explicitly.
Do your remarks imply a negative answer to the question of completeness of his algorithm (in the above sense of completeness):
- wrt to all his theoretically possible patterns?
- wrt the rank 0 ones ?

How this relates to logel's goal is obvious, even if it remains very obscure whether logel's "universal patterns" are exactly the same thing as (or at least equivalent to) Allan's or only something very close.

[JasonLion]

For a computer solver that is displaying explanations to the user it is fairly common to use two unrelated techniques, one to find the eliminations quickly, and another one that produces justifications that are simpler for a person to understand. Saying that I used a three level implication net in my code doesn't help a person understand a particular elimination. It is much simpler to present the result as a chain in standard notation. Finding every possible chain explicitly would be slow, while implication nets can run much more quickly. Likewise it is common to use tabling to find eliminations and then explain them as mutant fish.

[champagne]

I wonder what you exactly call "negative".

1) It is very easy (but costly in terms of CPU consumption) to detect that combining several floors/planes some candidates can be discarded.

Especially your side note in parenthesis is very interesting, because its just the other way around with my implementation.
I am not sure if we speak of the same thing, because floor as defined in sudopedia is different from what i call plane.
Seems you are interested in implementation issues, so I will give some figures.
The construction of data structures holding plane information about all 126 plane pairs that do not overlap has CPU cost of ~ 4 sec.
In case you want to use also the 84 tripel number planes ~ 6 sec more are needed.
This computation is done only once at initialization phase and used thousands of times for elimation checks.
All checks and updates for all elimations until complete solving is < 0.3 sec.
All timings related to 2MHz CPU 64 bit single thread. Also these figure do not depend on any rating of the puzzle.
Thime timings for reduction comes on top of that. I think these timings are fair for very hard puzzles.

May be I can answer in block to these points.
First of all, I checked your definition of a plane, my floor corresponds to you "number plane", but I also have functions working on the other "planes".
When you are processing millions of puzzles per day, you just don't consider any elementary process consuming more than some milli seconds.
In the last benchmark I made, the run lasted 20 hours for about 3 millions puzzles in the range serate ED 6.5 _ 9.3
In skfr, the hardest puzzles are solved in one or 2 seconds. My current code should run 3 to 4 times faster.
In addition, what we experienced is that you need 3 to 4 floors to have eliminations.

Finding every possible chain explicitly would be slow, while implication nets can run much more quickly.
Likewise it is common to use tabling to find eliminations and then explain them as mutant fish.

I put here Jasonlion before giving another experience.
As Jasonlion, I try to have leading indicators to know where to look for logic constructions leading to eliminations.


I made benchmarks runs using or not the leading indicators. My code goes faster looking directly for locked sets and basic fishes than doing a preliminary test using permutations.
As JasonLion, I still use the filter for more complex "fish patterns".
I tried also some band permutations, but so far, I have no clear result.
In that sense, I am not very positive on the potential results of that search.
One easy leading indicator is a "One number plane" permutation analysis, another one is the same for a "one row/column/block"

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 [emphasised by DB].

Does this mean that:
- in practice, i.e. in xsudo (although not in his definition), all of his patterns relied only on the combinations of a restricted number of floors/planes ?
- for those not included in the above "some of them", he used a less efficient algorithm or he merely discarded them in his algorithm ?

I worked mainly on floors at that time, because I hoped it would be the place to find simpler logic (and because "fata morgana" example used a 3 floors construction.

Allan Barker model is open to any construction.

AFAIK, that model can be partly hand guided to go in a specific direction, but that process was not "public".

To make it short, Allan had some free time at one moment in his carreer and had in hand a software to show in 3 dimensions the sets linksets construction. He worked in that direction and came to an interesting point, but then, he had to stop it's Sudoku activity.

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;

Once an elimination has been justified by some "pattern", why would you want a second justification for it ? Are you looking for a simpler pattern not dealt with by Allan ?

Just take the easiest answer.
at the end of your permutaton process, you have an evident sets links group leading to the elimination (using all sets). Why should you try to find another one.

[denis_berthier]

OK, thanks.
I understand that Allan's implementation had no goal of completeness wrt to his patterns.

[logel]

Hi Denis, now I have some time to continue

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".

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.

Your statement as it stands is absolutely true and I never questioned this. Its just unrelated to what I said. Your braids carry an order property because they were defined using order. My universal pattern are defined without any notion of order, but can nevertheless be verified. This is not any "better" or so, only more general.

Back to where I started: If you compute all valid permutations of e.g. number plane 1+2 and find a candidate that is not member of any of these permutations. This candidate is clearly false and you have a perfect proof. Enumerating all possible cases for a finite problem is always a trivial proof. That was already clear in the discussion we had in another thread.
If we accept a permutation enumeration as "elimination", we are finished and move on with the next one. Even if the same elimination can be validated with less objects in a "simpler" way, its pointless to prove a fact that is already proven.
So moving into that direction needs another motivation in form of a secondary goal. Possible secondary goals must be clearly defined as comparison of results related to different goals make no sense. I think we also agree that any comparison is related to a well defined size function.
The motivation for "univeral pattern" is to define "acceptable elimations". The term elimination pattern seem self-evident but is not. The set of all permutations of one or more planes is regarded as "not acceptable". On the other hand I wanted the definition to be as general as possible. I did not mention uniqueness in my first post, because I was aware of the history of emotional discussions. Uniqueness undermines the comparabilty of results, that why I don't like it.

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.

Here is a key misunderstanding. All puzzles can be solved without T&E at the base level with universal pattern. Thats the way they are defined. This is obvious as all eliminations are a result of some reduction of the whole set of candidates. This justifies the attribute universal. Of course its another thing to show an "optimal" elimination sequence explicitly. I never claimed that I can do this with reasonable computing. And I never claimed to have a magic algorithm to find the simplest universal pattern for a situation.
Of course you don't get the "shortest path" on a level-one contradiction path, but that does not make the construction useless. Each elimation pattern at the base level has a corresponding contradiction sequence at level-one consisting of (smaller) eliminations itself. And a well defined size function should consistently relate to the values of the elimations of the inverted logic.
Moreover any contradiction path from level-one can be reduced to a universal elimination. This requires some additional computation stripping off all redundant parts, but is manageable for all pathes. The reduction result may not be "optimal", but we can compute its size. So with T&E as auxiliary vehicle I can get a at least some solution consisting of a series of explicit universal pattern, but these solutions are far from satisfactory (optimal size).

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 ?

I can surely solve moderate puzzles as test cases, but finally it does not help. Reduced T&E is the inverted form of the direct logic.
Yes, rating for the total resolution path is a long term goal. But this was not intended to address in this thread.

[denis_berthier]

I can surely solve moderate puzzles as test cases, but finally it does not help.

You should consider that we're now all waiting for a complete example. What's the output of your solver ?

Reduced T&E is the inverted form of the direct logic.

?????

[tarek]

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.

Interesting. Using POM to help in finding targeted eliminations, the fishermen in this forum have managed to find fish for every elimination. AFAIK we coudln't find a POM elimination that doesn't have a fish.

tarek

[blue]

Hi logel,

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.

Here is a counterexample to your conjecture.

[denis_berthier]

Hi Blue,

Unless I misunderstand it, your example doesn't really contradict logel's conjecture.
You have a Jellyfish for digit 1 in columns c1, c3, c7, c9 so that there is a "natural" "base set" made of the 4 CSP-variables / 2D-cells {c1n1, c3n1, c7n1, c9n1}.
You exhibit two different sets of constraints, allowing to conclude that there's no unique covering for it.
But how do you show that there's a second base set?

I think the following (Hidden Pairs) shows that logel's conjecture depends mainly on what he considers as a link.
Take a mini-row (intersection of row r with block b) such that there are two columns c and c' intersecting it and such that:
- in row r, numbers 1 and 2 appear only in columns c and c' (call C1, C2, C'1 and C'2 the associated candidates),
- in block b, numbers 1 and 2 appear only in cells rc and rc' (the same C1, C2, C'1 and C'2 are the associated candidates)
Suppose number 3 appears in cell rc. Call C'' the associated candidate.

Now consider all the links between C1, C2, C'1, C'2 and C'' and take a minimal set of links allowing to eliminate C'' (in the logel's sense that no truth value assignment to C1, C2, C'1 and C'2 can be compatible with value True for C''):
- If logel uses "named" links, a link along a row (rn link) and a link along a block (bn link) are two different things. In the minimising phase, he will choose one of the two, which amounts to choosing which types of CSP variables/ 2D-cells he is considering (rn or bn); which also amounts to deciding whether he uses a Hidden-Pairs-in-a-row (base set {rn1, rn2}) or a Hidden-Pairs-in-a-block (base set {bn1, bn2}) to eliminate C'';
- If he uses "unnamed" links (equivalent to "there exists a link, i.e. some direct contradiction of unspecified type - rc, rn, cn or bn"), then this example is a trivial counter-example to his conjecture.

All this doesn't change my previous conclusion: in any case, it is a very bad idea not to introduce from the start the CSP variables in his definition of an elimination pattern.

[blue]

Hi Denis,

You have a Jellyfish for digit 1 in columns c1, c3, c7, c9 so that there is a "natural" "base set" made of the 4 CSP-variables / 2D-cells {c1n1, c3n1, c7n1, c9n1}.
You exhibit two different sets of constraints, allowing to conclude that there's no unique covering for it.
But how do you show that there's a second base set?

The two base sets are shown in the left and right halfs of the diagram: { 1c2, 1c4, 1c6, 1c8 } and { 1c2, 1b2, 1b8, 1c8 }.
This was also meant to be an example that, unlike the hidden pairs one, couldn't be explained as a "naming" anomaly.
It's also a little interesting, since the set "valid permutations" is not the same for each case.

Blue.

[denis_berthier]

You have a Jellyfish for digit 1 in columns c1, c3, c7, c9 so that there is a "natural" "base set" made of the 4 CSP-variables / 2D-cells {c1n1, c3n1, c7n1, c9n1}.
You exhibit two different sets of constraints, allowing to conclude that there's no unique covering for it.
But how do you show that there's a second base set?

The two base sets are shown in the left and right halfs of the diagram: { 1c2, 1c4, 1c6, 1c8 } and { 1c2, 1b2, 1b8, 1c8 }.This was also meant to be an example that, unlike the hidden pairs one, couldn't be explained as a "naming" anomaly.
It's also a little interesting, since the set "valid permutations" is not the same for each case.

OK, very good. I was considering the wrong vertical lines (and I didn't look at the extra 1's).
Your example settles the case and it allows more remarks than mine.