The New Sudoku Players' Forum

[Allan Barker]

Hello to all,

I am starting this thread to share some ideas on Sudoku logic and perhaps get feedback from the experience in this forum. Although I'm a computational junkie, my experience with the Sudoku world is limited. Everything is presented on my (non-commercial) website dedicated to the purpose along with numerous examples and many 3D images:

http://sudokuone.com

The approach is like a local area set theory. It focuses on global and regional properties of sets rather than candidates and implications. It does this using cover sets from set theory and a logical rank that defines regions. Regions and boundaries are then related to multiple linked logic. This, combined with 3D symmetry, produces a few simple rules that are not restricted by geometry, set type, or number of candidates. Unlike this quick description, the rules themselves are simple and easy to apply. I have been using them for over a year and I cannot find anything they do not account for, not to mention what they can explain or predict.

Some concepts are not new. Cover sets are used with fish and in fact, are fish. Cover sets are also the basis for the Subset Constraint Theory that I have seen here and in part the two approaches are the same. Cover sets in turn can be derived from other principles including permutations. Sudoku's 3D symmetry is also well known but not widely used. This approach is developed in 3D from the start without reliance on single-digit logic or bi-value sets.

I hope some of this is useful or at least interesting. I'm also interested to hear how it might be refined, made more useful. Thanks.

Allan Barker

[8-6-08]
Uploaded major revision of SudokuOne Web Site. Main differences are:
. Much shorter, the entire set theory derivation and explanation is now on one page.
. A new section with many simple examples of set theory principles.
. Full attention to previously sketchy areas, i.e., triplets, rank zones, summing of rank effects.

As usual, all feedback is welcome. rab.

[denis_berthier]

Hi Allan,

Welcome on this forum.

I've just had time for a quick browsing of your website and I want to find more time for a deeper look at it.

As you can see from my book or my threads here, I've been using 3D symmetry in a systematic way since I first met Sudoku (december 2005). I therefore greatly appreciate your approach. (Congratulations also for the gorgeous 3D graphics).

From a logical POV, I'd say the difference between our approaches is I keep to first order logic while you use second order logic (cover sets) from the start. For a fast computer, this may be innocuous; for human players, I wonder about a priori exponential complexity (exponential number of subsets).

AFAIK, no complete first order set of resolution rules is known.
From your website it is unclear whether you have a complete second order set of rules. You suggest that yes, but do you have a proof of completeness?
(Your rules are described under the section: "basic principles of generalised logic", right?)

I may have further questions later on, but that's my last one for now: could you give the full solution path output by your solver for a hard puzzle (e.g. for Easter Monster)?

[Allan Barker]

Dear Denis,

..... I've been using 3D symmetry in a systematic way since I first met Sudoku (december 2005).

I don't go back that far but I fully agree about 3D and symmetry being useful. Some things are very hard to recognize in 2D using digits.

I'd say the difference between our approaches is I keep to first order logic while you use second order logic (cover sets) from the start.

I am still reading your posts with great interest. I assume your first order logic uses only candidates whereas my second order logic includes but is not restricted to sets, although I prefer sets. This is a very good characterization. Of course, comparing the two is like comparing an apple to a fruit basket, but this is the apple.

For a fast computer, this may be innocuous; for human players, I wonder about a priori exponential complexity (exponential number of subsets).

Humans are best at pattern recognition (500,000,000 year design cycle) and we do it in parallel. The serial computer is probably at maximum disadvantage on these combinatorial, exponential problems.

However, the complexity issue is real. If I wanted to calculate all bi-value chains, I think first or second order (candidate vs. set) must consider the same number of combinations. It is when sets contain 3, 4, even 5 candidates, then the lights begin to dim! However, wouldn't a first order approach face the same thing? Have I interpreted order correctly?

I address the rest in the next post.

Allan

[Allan Barker]

The goal is only to find a common logic that relates eliminations to their environment. To me, this is not exactly the same as a technique designed for finding eliminations, nor is it a methodology. A good example is coloring. Both approaches find eliminations but the coloring techniques may often be easier and more elegant for this task.

(Your rules are described under the section: "basic principles of generalised logic", right?)

They are summarized there, stated symbolically in "mathematical description", and explained in the five sections of "principles by example".

AFAIK, no complete first order set of resolution rules is known.
From your website it is unclear whether you have a complete second order set of rules. You suggest that yes, but do you have a proof of completeness?

This is good feedback. I think the approach already works as a common logic because its covers a wide and diverse range of methods, but I do not claim completeness in any formal sense. I do not even know of a definition for completeness, without such a definition a proof is not useful. Thanks, I will clarify that if needed.

However, the approach also uses triple points and regions. There is a nice example of proving loops in <another forum site> and it seems these PLs contain triple points. I also used a grouped turbot fish chain from Sudopedia as an example. It seemed that conventional chain and loop arguments were a bit strained explaining the eliminations while the triple point argument was more natural (to me of course!). Perhaps someone can give a better explaination, the GTFC is shown below. (maybe...)


Solid bars are strong links and hollow bars are weak links. The triple point (3 sets) in the middle of the left box makes the box fish-like and all candidates can be cleared from weak links. The rest of the logic is chain-like. See: http://www.sudokuone.com/sweb/princep/gturboc.htm
[/url]

[denis_berthier]

I assume your first order logic uses only candidates whereas my second order logic includes but is not restricted to sets, although I prefer sets. This is a very good characterization.

Indeed,for convenience purposes, I use multi-sorted first order logic (MS-FOL) which is an inessential extension of FOL (roughly speaking, variables have a type: number, row, column, block). As FOL allows any boolean combinations and quantifications on variables, conditions on many candidates can be written. In a restricted sense, some types of subsets are taken into account (e.g. all cells in a row with a 1) but not all types of subsets.

For a fast computer, this may be innocuous; for human players, I wonder about a priori exponential complexity (exponential number of subsets).

Humans are best at pattern recognition (500,000,000 year design cycle) and we do it in parallel. The serial computer is probably at maximum disadvantage on these combinatorial, exponential problems.

I agree on this in principle, but IMO this is valid only for patterns with some visual meaning. A subset that is the intersection of a row and a block has some visual meaning, but is it the case for a subset that is any subset of a row? What I mean is that I've seen solutions for hard puzzles based on subsets that no human is likely to ever discover. (Of course, when one is given the solution, one can see it).

However, the complexity issue is real. If I wanted to calculate all bi-value chains, I think first or second order (candidate vs. set) must consider the same number of combinations. It is when sets contain 3, 4, even 5 candidates, then the lights begin to dim! However, wouldn't a first order approach face the same thing? Have I interpreted order correctly?

Yes, you interpreted "order" correctly.
For bivalue chains (xy-chains or their 3D-counterparts: nrc-chains) the two views, chains of candidates and chains of bivalue cells are equivalent.
Complexity is an untractable matter. Even with such elementary chains, we don't know how to compute their complexity. There may be an priori complexity of the defining logical formula (even this is unclear), but the real complexity of finding instances is so context-dependent that I could give the example of an nrczt-chain of length 28 that was easier to spot than chains of length 7.
What I meant when I spoke of "a priori exponential complexity" is exactly what you say about sets of 3, 4 and more candidates. And, of course, FOL can't make miracles here.
What I'm trying to do is find rules with the proper degree of generality ("proper" may be partly subjective). I've shown that my set of first order rules can solve at least 99,9% of the minimal puzzles. With Mike (Barker also), we have shown that they have approximately the same coverage as rules based on chains with subsets (see my discussion with Mike in the "fully supersymmetric chains" thread). But we have also found rare examples for which each approach allowed eliminations not allowed by the other.
Concerning the introduction of subsets, my approach would ask: what simplest kind of subset do I need to solve the cases I can't solve yet?
A typical example of this is the way I interpret Steve's pattern as an x2y2-belt of crosses. From the basic FOL predicates for Sudoku, I can define a "cross" as a first order predicate. Of course, it has some second order flavour, but it is a very specific visual pattern, located in one block (where your parallel processing argument is fully effective).
In your approach, I think the same questions come naturally: what kinds of subsets and subset patterns should I consider first?

[denis_berthier]

AFAIK, no complete first order set of resolution rules is known.
From your website it is unclear whether you have a complete second order set of rules. You suggest that yes, but do you have a proof of completeness?

This is good feedback. I think the approach already works as a common logic because its covers a wide and diverse range of methods, but I do not claim completeness in any formal sense. I do not even know of a definition for completeness, without such a definition a proof is not useful. Thanks, I will clarify that if needed.

In principle, it shouldn't come as a surprise that second order logic rules cover first order ones. Second order logic is much more poweful than first order (too powerful for most logicians because it more or less contains full set theory).
Of course, you had to write explicitly how this coverage is done in your approach and it's great you could do this in a uniform manner. But I'm not a specialist of using subsets (I'm even doing all I can to avoid using subsets, especially in chains) and I'm not sure what exactly is new in your approach. I hope subset users will give their opinion.


As for completeness, it is rather easy to define:
- take the Sudoku axioms (the completion constraint (completed grid) + the 3 constraints on rows, columns and blocks): they define a first order logic theory ST; the only problem of ST is that none of these axioms is directly useable by a player: it doesn't tell you what to do;
- therefore, let's define a resolution rule as a 1st order formula in the "condition => action" form, which is a logical consequence of ST - where "condition" describes a static (or factual) pattern on the grid and "action" is one of the two natural elementary actions a player can perform (addition of a value or deletion of a candidate) [in your framework, just replace "first order formula" by "second order formula"]; a resolution rule thus corresponds to a natural elementary step in the resolution process;
- define a resolution theory as a set of resolution rules;
- then you can say that a resolution theory T is complete if it is equivalent to ST, i.e. given any puzzle, any completed grid consistent with its entries satisfies ST if and only if it satisfies T.
Notice that this definition doesn't require any assumption of uniqueness for the puzzles (nor even of consistency).
If you have a complete resolution theory T, you have fully replaced a constraints satisfaction problem (ST) with an almost operational description of its solution.

[Allan Barker]

NRCT Chains and the Cover Set Approachs

I have seen discussions in another thread in this forum (by Milko) about the ability of cover set approaches to produce nrct chains, as nrct chains are more difficult than many other chains. The local area set theory approach presented here does cover nrct chains. Below I provide some examples to show that it is the integration of cover sets with other principles such as regions and sets/linkset overlaps (triple points) that explain nrct chains, and not the cover set approach itself. A better description of how this all works is derived on my website page http://www.sudokuone.com/sweb/princep/triple.htm, which has other, similar examples under the heading "Rank 2 Mixed Logic".

For clarity, the term rank refers to the difference in the number of sets (S) versus cover sets (L, for link) in a structure. Most fish are rank 0, where S = L, and linksets can be cleared of all extra candidates. Many chains are rank 1, where L = S + 1, and require 2 overlap linksets to eliminate candidates. Rank 2, where L = S + 2, then requires 3 overlap three linksets ... ,etc.

Although cover set approaches easily handle three dimensional chains, nrct chains are different because they allow feedback (internal loops) that can form triple points. These are covered by the following principles:

1: One logical structure can have regions of different rank where the regions are demarked by triple points.

2: When two linksets merge into one set, the rank on the merged side of the structure is 1 less than the rank on the other side.

I have redrawn the nrct chain with real sets using 3 sets and 5 cover sets. Extra test candidates are placed in the upper right to see which can be eliminated. The overall structure is rank 2, L = S + 2, thus it cannot eliminate the candidate in r1c8 with only 2 overlapping linksets. However, r2c5 is a triple point thus the region on the set side becomes rank 1. The linkset in row 1 is also in the rank 1 region and can therefore eliminate the candidate in r1c8 by overlapping with one other linkset.



To emphasize the point, a rank 1 structure is made by removing r5c8 and adding r1c1. This structure in rank 1 and again there is a triple point. The linkset in row 1 is rank=0 (fishy) and eliminates all extra candidates. Note: an almost identical linkset in row 2 cannot eliminate candidates because it is in the rank 1 region. These rules seem quite general and can account for many things.



[/url]

[ronk]

Allan Barker, without at least one candidate in r3c789, you have a hidden single in r3c2.

[milko]

Alan, I’d been through your website and read all the interesting stuff you have in there. I am very pleased to see that someone has the same approach to sudoku as I do, and even be a ‘casual’ sudoker as I am! I had difficulties understanding your mixed rank theory and still have, even though it became a bit clearer from your last post. Still can you explain how you would eliminate (Z) if the –t link of the nrct-chain is deeper in the chain like it is shown here:



Or how is your first example different from the structure below (the additional candidate (*) is linked to an odd and not an even candidate of the chain) that doesn’t produce any eliminations?



And a different issue:
Shouldn't you have minimum and maximum rank when overlapping (triplets) occurs and achieve contradiction only when maxRank(L) < minRank(S)?

The way I am thinking of it is that maxRank(L) < minRank(S) is the worst case scenario; if the inequality stands then elimination occurs but not necessarily vice-versa. On the other hand, when not even the best case scenario is true, i.e. minRank(L) >= maxRank(S), then there is no point searching for eliminations using these linksets.

What do you think?
alex

[ronk]

Or how is your first example different from the structure below (the additional candidate (*) is linked to an odd and not an even candidate of the chain) that doesn’t produce any eliminations?

While I don't know what is, the counter-example below implies that "odd or even candidate" is not the proper criteria.

[Allan Barker]

Allan Barker, without at least one candidate in r3c789, you have a hidden single in r3c2.

Ronk, Sorry, I have been getting other feedback about things I have not explained about my diagrams, so I will have work on this.

These diagrams are output from my software, which can also analyize logic. In this mode, the software assumes that anywhere in the grid that is not marked as a strong set (all candidates included in the set) may have additional candidates, thus it would not assume a single in r3. I was sloppy in placing only some "test candidates". Maybe I need something like a title bar that lists applied assumptions.

However, all possible eliminations are indicated by yellow squares (cubes in 3D) so this diagram states that r1c8 (cube r1c8n5) is the only possible elimination (zone). Some (not enough) of this is documented on the website in "Legends for 2d and 3d diagrams".

Thanks.

[Allan Barker]

Nrct chain links to odd node numbers?

>Milko. Yes, It is nice to meet others working along the same ideas.

Still can you explain [----] how is your first example different from the structure below (the additional candidate (*) is linked to an odd and not an even candidate of the chain) that doesn’t produce any eliminations?

I think Ronk points out that the first of your two new diagrams is not possible in a Sudoku grid (as set logic it is ok) and maybe the connection is to node number 3? I have made diagrams connecting to both nodes 1 and 3 and analyzed the set structure, which produces interesting results.

Connecting to node 1. When * is linked to node 1, the set in r1 is no longer needed as, and cannot be, a cover set. This means r1c8 can no longer be eliminated. Also, there is no longer a triplet. There are now 4 linksets (L) and three sets (S) so the logic is rank is 1 and should behave like a chain, meaning it will eliminate candidates anywhere two linksets (from the same cover group) overlap. This causes the elimination in r2c8.



Connecting to node 3 is more interesting. I had to rearrange the sets to get the logic right, but the diagram below is equivalent to your's if * is connected to node 3. Node 1 is now in r7c5. The logic here is like your very first diagram and the same arguments apply. The logic is again rank 2, has a triple point that causes the set in c2 to be a rank 1 linkset becasue the set side of the triplet now points left. The rank 1 linkset in c2 now overlaps with the end linkset in r7 to cause an elimination, which is the only elimination from this logic.



Now the question is, why is there an elimination connecting to an odd numbered node of the nrct chain? The elimination is real and is expected according to cover set rules ( with triple points). Can I count from either end, and if so is there any difference between even and odd for this type of chain? I am not much of an expert in this area.

[Allan Barker]

On the meaning of exact cover sets, cover sets, etc.

I would like to clarify how cover sets are used (in this thread) and also understand how everyone else is using similar terms.

In my approach, cover sets mean a group of sets that contains all the candidates of a problem or logic structure, and exact cover sets mean cover sets that do not overlap. The approach uses cover sets in part but is not strictly a cover set technique. The approach is based almost entirely on sets and emphases triple points and their effect on set structures. The use of cover sets is similar to several methods that use two groups of exact cover/cover sets to produce eliminations.

The approach uses a group of simple set based rules to determine which configurations of sets can cause eliminations and logically why. The aim is to find the simplest set of logical rules that are able to produce all possible eliminations, if not already found. The approach does not use backtracking, trial and error, or enumeration.

There are various ways to formulate Sudoku, or groups of candidates as exact cover problems which are then solved by other means, like the exact cover formulation often solved with Knuth's algorithm X using backtracking and T&E. These are not included in any comparison of pure logical methods that may employ cover sets in full or in part. Whew.

[Red Ed]

Well, while we're clarifying ...

• "The approach" = "Allan Barker's approach" ?
• "These are not included in any comparison ..." = "These 'other means' are outside of the scope of the present discussion" ?

[denis_berthier]

Nrct chain links to odd node numbers? [...]
Now the question is, why is there an elimination connecting to an odd numbered node of the nrct chain? The elimination is real and is expected according to cover set rules ( with triple points). Can I count from either end, and if so is there any difference between even and odd for this type of chain? I am not much of an expert in this area.

The logic of nrc(z)t chains allows to forget the presence of additional candidates that are nrc-connected to previous right-linking candidates (even candidates). The proof is almost obvious.

In no case does it allow to forget the presence of additional candidates that are nrc-connected to previous left-linking candidates (odd candidates). The reason is merely that the proof wouldn't work for these candidates.

Notice my careful formulation: there is no elimination of these additional candidates; only their presence can be forgotten when the chain is built from head to tail - or left to right, whatever you call it. These additional candidates are those that would cause an obstruction to the bivalue/bilocation relation and forgetting them amounts to allowing bivalue/bilocation modulo the previous right-linking candidates (and target in case the z-extension is used).

I don't know what your pattern is, but it is not an nrct-chain if it relies on such links to previous left-linking candidates.

This is not completely clear for me, but it seems all your chains are reversible (in my technical sense, i.e. you can start from any end). Indeed, it seems that you don't really have chains, in the sense that no order is defined on them. Can you confirm this?
As for nrc(z)t chains they are definitely not reversible. As a counterpart, their main positive characteristics are non-anticipativeness and composability. Being chains and being non-anticipative is what makes them tractable.

As they are not reversible, it is not clear for me whether and how nrczt-chains can be subsumed by your patterns of subsets.