The New Sudoku Players' Forum

[denis_berthier]

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

[David P Bird]

I'd now say that there is a curse of Sudoku: every constraint arises from a CSP-variable (from the extended set), whence the confusion (and all the inconsistent writings about weak and strong links). That's one of the reasons why I started to be interested in other logic games. One can easily find examples in which there are constraints that do not arise from CSP-variables, e.g. N-Queens - or Kakuro, if anyone also reads the discussions on this topic.

My interpretation what you are saying is that it's wrong to make use of the properties of Sudoku that aren't common to the wider family of puzzles to which it belongs. IMO however, that doesn't follow, and if you discarded the corset you've made for yourself over this and also refusing to utilise uniqueness, you would be able to refine a much better method.

I believe that the rules could be expressed as "The objective is to satisfy the requirement that each house contains one of each of the digits 1 to 9 subject to the constraint that no cell can contain more than one digit". This would then fit the terms Blue used.

[tarek]

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

[denis_berthier]

I'd now say that there is a curse of Sudoku: every constraint arises from a CSP-variable (from the extended set), whence the confusion (and all the inconsistent writings about weak and strong links). That's one of the reasons why I started to be interested in other logic games. One can easily find examples in which there are constraints that do not arise from CSP-variables, e.g. N-Queens - or Kakuro, if anyone also reads the discussions on this topic.

My interpretation what you are saying is that it's wrong to make use of the properties of Sudoku that aren't common to the wider family of puzzles to which it belongs.

Absolutely not.
But many rules that are believed to be Sudoku-specific can indeed be written in a much more general context. Being aware of this broader context sheds additional light on Sudoku. The case of whips[1] is particularly instructive, because they appear under very different guises in the various games I considered. Nevertheless, the underlying logic is the same.
General rules do not preclude the existence of Sudoku-specific ones (e.g. sk-loops) or of Sudoku-specific formulations of the generic rules (in PBCS, I show in detail how my general definition of Subsets for any CSP translates into the usual ones in Sudoku).

if you discarded the corset you've made for yourself

What you call a "corset" I call a consistent conceptual framework. But the requirement of consistency is probably too much for these forums.

refusing to utilise uniqueness

May I suggest you take courses in reading and understanding English?

[David P Bird]

refusing to utilise uniqueness

May I suggest you take courses in reading and understanding English?

Ignoring the slight, which wasn't unexpected, have you ever explored "Avoidable" pattern deductions that make use of the fact that a particular elimination has proved a sub-puzzle has a unique solution (ie it doesn't need to be assumed)?

I still hold that, although it is a matter of convenience for you to convert a "one of each" requirement into a series of 9 binary constraints, that doesn't make it mandatory for everyone else to stop thinking in terms of weak and strong links and expressing themselves accordingly.

[eleven]

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

Denis, you are repeating an argument, which already has been answered:

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.

I do not agree. Even if the definition relies on permutations, you don't have to check all value assignments. You prove instead that the inverse is false, means that once the target has a value true no valid permutation can exist, because you run into a contradiction. This is of almost similar complexity as checking validity of what you call a g-Subset. The validation effort depends mainly on the number of inevitable branches, the rest grows linear with the number of candidates.

The order of the chain is helpful for a reader, but not needed to prove the elimination.

[blue]

Hi Denis,

I think you raise a good question, but it must be taken the other way round: start from the problem and, only after that, see what kinds of logical relations it involves.

Interesting. I didn't think I was raising a queston. But "good".

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

First, a clarification: what I meant by an "at most one of" statement, was something like the conjunction of the NAND staetments associated with one of the "constraints" that you list in (2).

Next, it's nice that you included the 81/324 breakdown above, since it a good illustration of something that can leave me confused. The first thing that popped into my head, was "wait, isn't it really 81 of first type, and only 243 of the 2nd type ?" -- thinking that with (1), the 'rc' constraints from (2) are unnecessary. The answer would depend on whether, in (1), you're considering the possiblity that two or more digits could be placed in the same cell. In the 2nd bit that I quoted, where you say that the type 1 items are "exactly one of" formulae, I think that confirms my "isn't it only 243 ?" suspicion.

Finally, I would in no case use the word requirement here. Requirements appear at another level:
(...)

This surprised me.
I didn't intend a grand meaning in the term "requirement" -- just a preference to distinguish between the "must do", and "may not do" types of (low level) constraints.

For a more general audience ...

In any case, the reason I brought some of that up, has a bit to do with Alan Barker's XSudo program, and how what it does, is relates to "base/cover" concepts. It almost seems that his Truth sets equate to "bases" (sets of "base sectors"), and his link sets, to "covers" (sets of "cover sectors"). That isn't quite true though. In base/cover terms, the way his code is working, in that view, each "base sector" is also being treated as a "cover sector".

That's taking these "definitions" (if you like), into account

• a "base set" is a set of propositions/candidates where "at least one, must be true".
• a "cover set" is a set of propositions/candidates where "no more than one, may be true".
• "sector", rather than "set" is used ("base sector" or "base set"), when the set of candidates is the set of "live candidates" from one of the 324 "units"/"2D-cells".
• a "base", is a set of base sets (or base sectors), and a "cover" is a set of cover sets.

[ While it's true that the candidates in a base sector, satisfy an "exactly one is true" condition in an actual sudoku solution grid, that fact is never used in base/cover arguments. If it happened to be necessary to support an elimination claim (and I'm not saying that it ever is), then the sector would also be added as a cover sector as well. ]

I'm trying to put a plug in for clarity here. It seems that logel's definitions, after refinement, are going to revolve around either a "base/cover" setup, or a "truth/link" setup. I don't know what he'll have in mind for the "weak link" aspect of things -- that one should list individual "binary weak links", or that hings like "cover sectors"/"links", could be listed instead. It almost wouldn't mattern, but he's including a "minimality" condition, and maybe sometimes not every binary weak link associated with a cover sector, would be necessary to produce the target candidate elimination.

For logel,

I think you should heed Denis' advice, and include the "lines" (or whatever you'll call them) in the defintion, 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.

I would make one more plea. When you say "valid permutations of the candidates", I do understand what you mean, up to some point. It reminds me of the "Show candidate permutations" menu item in Alan Barker's XSudo. The silly side of me, though, looks at the diagrams above, and says: "what ... how am I going to get anything but a bunch of 1's in the same places they started at, if I 'permute the candidates' ?". I would appreciate it if you were more explicit about what you say in that regard. On the serious side, assuming that you include the "lines" idea in the definition, I'ld like to see an indication of whether a "valid permutation", could include a case where two candidates from the same "line" are true ("base sector" logic), or whether there's an implied assumption that only one may be true (Alan Barker's "truths" logic). I do realise, however, that the difference lies in what "links" are explicitly present, and that up to now, the number and nature of the links, hasn't been expecially relevant.

More about complexity of verifications, in another post ...

Regards,
Blue.

[denis_berthier]

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

Denis, you are repeating an argument, which already has been answered:

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.

I do not agree. Even if the definition relies on permutations, you don't have to check all value assignments. You prove instead that the inverse is false, means that once the target has a value true no valid permutation can exist, because you run into a contradiction. This is of almost similar complexity as checking validity of what you call a g-Subset. The validation effort depends mainly on the number of inevitable branches, the rest grows linear with the number of candidates.

The order of the chain is helpful for a reader, but not needed to prove the elimination.

You're confusing two arguments.
The first argument has not been answered and no one can seriously deny the conceptual difference: "[b]sequence = set + order relation on this set", if the word "pattern" is to mean anything at a conceptual level.
As for the second argument, involving complexity, I don't take "The validation effort depends mainly on the number of inevitable branches" as a proof of anything, especially in regard of the no 2-SAT property.

[denis_berthier]

it's nice that you included the 81/324 breakdown above, since it a good illustration of something that can leave me confused. The first thing that popped into my head, was "wait, isn't it really 81 of first type, and only 243 of the 2nd type ?" -- thinking that with (1), the 'rc' constraints from (2) are unnecessary. The answer would depend on whether, in (1), you're considering the possiblity that two or more digits could be placed in the same cell. In the 2nd bit that I quoted, where you say that the type 1 items are "exactly one of" formulae, I think that confirms my "isn't it only 243 ?" suspicion.

In each of the 81 rc-cells, there is the constraint that all the possible values are different. This is implicit when you consider that 1, 2, 3, ... are digits, in which case you include basic arithmetic knowledge, but not if you replace them by arbitrary symbols, e.g. n1, n2, ... - so it's better not to forget them).

[eleven]

Denis,
fortunately there is a conceptional difference to your chains, otherwise the thread would be boring.
I did not read the universality claim (did he say more than "The definition covers all traditional elimination methods and rules – afaik ..") as that it is mimicing all chains aspects, but that for any chain elimination there is an equivalent "Universal Elimination Pattern".
Concerning the validation effort i have my doubts too (and as it seems blue as well). That's one of the reasons, i wanted a better example, so far i don't really understand, how logel wants to calculate the patterns.

[denis_berthier]

fortunately there is a conceptional difference to your chains, otherwise the thread would be boring.

It's not only "my" chains. This applies also to any kind of chain: xy-chains, ALS, ...

I did not read the universality claim (did he say more than "The definition covers all traditional elimination methods and rules – afaik ..") as that it is mimicing all chains aspects, but that for any chain elimination there is an equivalent "Universal Elimination Pattern".

I would have no objection to the "equivalent elimination" formulation. BUT logel's explicit goal was to define a universal pattern in the sense that any pattern is an instance of it.

[eleven]

Ok, so we have to wait for logel - for "my" chains (without using uniqueness) i did not see a problem
[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.

[blue]

it's nice that you included the 81/324 breakdown above, since it a good illustration of something that can leave me confused. The first thing that popped into my head, was "wait, isn't it really 81 of first type, and only 243 of the 2nd type ?" -- thinking that with (1), the 'rc' constraints from (2) are unnecessary. The answer would depend on whether, in (1), you're considering the possiblity that two or more digits could be placed in the same cell. In the 2nd bit that I quoted, where you say that the type 1 items are "exactly one of" formulae, I think that confirms my "isn't it only 243 ?" suspicion.

In each of the 81 rc-cells, there is the constraint that all the possible values are different. This is implicit when you consider that 1, 2, 3, ... are digits, in which case you include basic arithmetic knowledge, but not if you replace them by arbitrary symbols, e.g. n1, n2, ... - so it's better not to forget them).

OK, I think I see what you're getting at. I won't belabor the point.

Regards,
Blue.

[denis_berthier]

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.

Yes, minimality of the patterns is one of the most interesting aspects - and a necessary one if the patterns are ever to be used to define a rating.
However, the requirement of minimality may involve complexity problems of its own, unless some form of priority is assigned to the rules, ensuring than "simpler" / non-minimal patterns are applied before more complex ones (in my approach, minimality is guaranteed by the "simplest-first" strategy). But:

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

It's not quite clear for me what logel means by this.
In any case, we'll need clarifications also on how he deals with minimality.

[David P Bird]

However, the requirement of minimality may involve complexity problems of its own, unless some form of priority is assigned to the rules, ensuring than "simpler" / non-minimal patterns are applied before more complex ones (in my approach, minimality is guaranteed by the "simplest-first" strategy). But:

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

It's not quite clear for me what logel means by this.

What may be behind his thinking is that a simplest first method will identify the highest rated step needed but not the shortest solution path.
1) Many of the early simple steps will make insignificant eliminations and can be removed.
2) Reordering steps to advance the highest rated step as far forward as possible will make other steps redundant.
3) Introducing other intermediate rated steps into the solution could similarly make several simpler steps redundant.

All this gets very complicated for a long solution path, and furthermore which of the possible paths is optimum will still be a matter of opinion.