The New Sudoku Players' Forum

[milko]

Hello all,

I try to follow up with all the new solving techniques that come up by frequently visiting this forum. However, since I’ve first started solving sudoku puzzles I was always thinking that there should be a SINGLE solving technique that solves ALL puzzles without going into trial & error, since there is only one rule. Well, the method that I present here (http://files.filefront.com/General+method+for+solvinupdf/;9583658;/fileinfo.html - with many examples), although I cannot prove that it solves all puzzles, it ‘encloses’ all the methods that I am aware of, meaning that each of the known techniques is an individual case of the method. Only the techniques which assume that only one solution exists (uniqueness tests) are not covered, since that information is not used.
In practice however, the method is not very significant, because it is easier to apply the individual techniques which narrow significantly the research field of a valid ‘pattern’ where eliminations can exist. Anyway, I am posting it in case other people had the same ‘obsession’ of this one method for all cases. And maybe use its framework to find other, new techniques, since only part of the ‘capabilities’ of the method are used in the current techniques –but this may be due to the geometry of the standard sudoku, in other variations with more complex geometry (X-sudoku, Windoku, ..., and especially Sukaku) I have found cases that cannot be applied to standard sudoku-.
The method works like X-Wing, where N rows are trying to cover N columns but ‘rows’ and ‘columns’ are more abstract objects. It is all covered by naive set theory and therefore sudoku obtains a strong link with maths and a simple but elegant math framework.
Also, when number N becomes large (it can go theoretically till half of all the 324 candidate sets) it is human impossible to apply the method, but it can be applied by a computer solver, which is what I am working on (some months now...), hoping that the program will give me new techniques for solving sudokus, if not for the standard grid, at least for its variations.

alex

[jimbob]

Well you may not all understand but isn't it Milco now?

[Mike Barker]

We already have "The Ultimate Fishing Guide". I guess we'd have to title your article "The Uber Fishing Guide". Being a fisherman I like the idea that you can unify most techniques under the same ideas of constraint subsets and Obi-wans' finned fish finder. I was wondering how your approach deals with nrct-chains?

Of course the real payoff from your unification model is its use in developing new techniques or approaches for recognizing patterns defined by existing techniques. I look forward to seeing what comes of your ideas.

[milko]

Thank you Mike for your suggestions and encouragement. It seems that nrct-chains are not fully ‘enclosed’ by the method that I propose. It had worked out for some random cases that I had checked it but since you mentioned it and running over the theory, in the general case, the nrct-chains can achieve eliminations that the method that I propose can’t.

Applying the method for a size N nrc(t)(z)-chain is easy. It is very clear which sets to use for the driving subset and which for the excluding sets. For the driving set we use the N nrc-conjugates and we distinguish two cases:
a) the target cell and the endpoints (head and tail) of the chain belongs to the same candidate set A. In this case we use as excluding sets the N-1 candidate sets that form the nrc-links plus the set A. Eliminations occur in every candidate of set A not belonging in the driving subset.
b) the target cell is ‘seen’ by the head of the chain through candidate set A and by the tail of the chain through candidate set B. In this case we use as excluding sets the N-1 candidate sets that form the nrc-links plus sets A and B. Eliminations occur only at the intersection of A and B.

For the nrc-chains it is straight forward that the method works.
For the Z- extension one more excluding set is added for every additional candidate which links it with the target cell Z. However, the method can still be applied since there are multiple excluding sets intersecting at Z.
For the T- extension the additional candidates that appear in the driving subset are *expected* to be covered from the excluding sets. However that is not always the case. A typical application of a nrct-chain is demonstrated below:

nrct3 { 1 2 } – { 3 4 } – {5 6 *#2} => eliminate Z



Blue lines indicate nrc-links and red circles nrc-conjugates. The method I propose can only be applied here if candidates (2), (3) and (*) belong in the same candidate set, which is often the case, especially with small size chains. Otherwise, if there is a candidate where 3 or more of its 4 dimensions are used, an extra excluding set is needed to cover the driving subset and the balance between the number of excluding sets and the size of the driving subset is no longer kept. The nrct-chain method, on the other hand, doesn’t care at all nor does it distinguish the two cases and is always valid. Thus, I shall extend my method by investigating the intersection of excluding sets thoroughly. Perhaps merge intersecting excluding sets under certain circumstances.

[Red Ed]

Upon skim-reading, this seems to me analogous to -- if not the same as -- Stephen Kurzhals' use of matrices in sudoku.

Yet another way of looking at it is to consider the exact-cover formulation of sudoku. Consider, for example, the following snippet from a candidates/constraints table that shows all candidates (only four of them) that could possibly satisfy a particular set of three constraints:

Code: Select all

       +------+------+------+
       | 5@r5 | 5@c7 | 5@b6 |
+------+------+------+------+
|5@r2c7|      |  *   |      |
+------+------+------+------+
|5@r4c7|      |  *   |  *   |
+------+------+------+------+
|5@r5c6|  *   |      |      |
+------+------+------+------+
|5@r5c9|  *   |      |  *   |
+------+------+------+------+

The exact cover problem seeks non-overlapping rows of this table that completely cover the columns. In this case, there are just two covers ...

• cover #1: 5@r2c7, 5@r5c9
• cover #2: 5@r4c7, 5@r5c6

... and both of these are incompatible with the candidate 5@r2c6 (because the first hits 5@r2 and the second hits 5@c6), so that candidate can be eliminated. Thus we have justified the elimination shown in Sudopedia's 2-string kite example.

The great drawback of this general strategy is that it can be extremely computationally expensive to find appropriate constraint sets -- especially as the larger ones generate a lot of covers. Steve K used the term depth (IIRC) for the number of constraints. His hidden pair loop in the Easter Monster has depth 16, for example. Is there any lower-depth opening for EM? No-one knows; and I can't see a computer settling the question one way or the other any time soon.

Assuming that Alex's strategy has at least some relation to the exact cover approach sketched above, I take a pessimistic view of the comment near the end of his paper that says "it is easy to create an algorithm for a computer solver to systematically search for driving subsets and excluding sets that meet the criteria". While coding the algorithm may be easy, its probability of success on puzzles such as EM would seem to be rather low.

[Allan Barker]

Nrct Chains and Cover Set Approaches

Hi Milko,

Nrct type chains are covered by the local area set theory that I introduced in the thread http://forum.enjoysudoku.com/viewtopic.php?t=5912, where I show some examples including the nrct chain presented here in the thread.

These examples try to point out that it is the integration of cover sets with other principles that explain nrct chains, and not the cover set approach itself. If you want a full description of on how these points work, you can also look at my website page http://www.sudokuone.com/sweb/princep/triple.htm, which has other similar examples under the heading "Rank 2 Mixed Logic".

[Red Ed]

Really, Allan? Can you demonstrate an nrct chain that's not explicable by exact-cover methods?

Let's look at your artful redrawing of Alex's nrct3 chain:


Now turn to the exact-cover candidates/constraints table. We'll show all candidates (seven in this case) that are incident with a particular set of three ("STRONG") constraints. Of course those candidates are incident with other constraints as well, but I'll just show the relevant ones ("WEAK") in the diagram below:

Code: Select all

       +------+------+------+     +------+------+------+
       | STRONG CONSTRAINTS |     |  WEAK CONSTRAINTS  |
       | 5@b1 | 5@b2 | 5@r5 | ... | 5@r2 | 5@c2 | 5@c5 | ...
+------+------+------+------+     +------+------+------+
|5@r1c6|      |  *   |      |     |      |      |      |
+------+------+------+------+     +------+------+------+
|5@r2c3|  *   |      |      |     |  *   |      |      |
+------+------+------+------+     +------+------+------+
|5@r2c5|      |  *   |      |     |  *   |      |  *   |
+------+------+------+------+     +------+------+------+
|5@r3c2|  *   |      |      |     |      |  *   |      |
+------+------+------+------+     +------+------+------+
|5@r5c2|      |      |  *   |     |      |  *   |      |
+------+------+------+------+     +------+------+------+
|5@r5c5|      |      |  *   |     |      |      |  *   |
+------+------+------+------+     +------+------+------+
|5@r5c8|      |      |  *   |     |      |      |      |
+------+------+------+------+     +------+------+------+
  ...           ...           ...          ...

It's a straightforward job for a computer (or, in this small example, a human) to enumerate all ways of satisfying the "STRONG" constraints. They are:

• 5@r1c6, 5@r2c3, 5@r5c2
• 5@r1c6, 5@r2c3, 5@r5c5
• 5@r1c6, 5@r2c3, 5@r5c8
• 5@r1c6, 5@r3c2, 5@r5c5
• 5@r1c6, 5@r3c2, 5@r5c8
• 5@r2c5, 5@r3c2, 5@r5c8

Finally, since every one of these solutions is incident with r1 or c8, we can eliminate the candidate 5@r1c8.

Sure, that wasn't a very pretty way of achieving the elimination, but it uses fully generic methods. The difficult part is in picking the right set of "STRONG" constraints from which everything else follows. In this case, with only three such constraints (depth = 3), a computer could find the strong constraint set by brute force.

Allan, when you said, "these examples try to point out that it is the integration of cover sets with other principles that explain nrct chains, and not the cover set approach itself", were you referring to Alex's method or to exact-cover techniques? I couldn't tell.

[milko]

I believe Red Ed that it can be explicable by cover set methods as well besides the exact cover method as you prooved, but i don't know if it is 'logic' or not...:

If we assume (Z) to be true and ‘re-adjust’ the constrain sets to that information (in the above case {(1) (2)} becomes {(2)} and {(5) (6)} becomes {5}) the chain immediately breaks into pieces if a cover set method is applied: {(2)} is now a subset of the constrain set that includes (2) and (*) and of the constrain set that contains (2) and (3). Thus (*) and (3) are eliminated and we end up having as true nodes BOTH (4) and (5) which is a contradiction.

I think Alan’s point was that there is no need to recursively apply a cover set method to crack the chain which someone may accuse for being trial & error, but he is able to eliminate (Z) using his mixed rank theory, which is very promising but I still don’t completely get it, i.e. how is this case different with the case the additional candidate (*) is linked with (1) instead of (2) in which case no elimination can occur (I posed the question to his thread).

I believe recursively applying the cover set method is powerful even if it doesn’t lead to direct contradiction. In the case we study here, the information that candidate (2) is always true when (Z) is true is enough to eliminate (Z), since the two link sets (2)-(3) and (2)-(*) merge to just one and that makes equal the number of linksets with the number of the primary sets, thus (Z) can be eliminated.

Therefore in more complex structures than nrct-chains, applying cover set methods to the ‘re-adjusted’ constrain sets might overcome the obstacle of internal overlapping even when no direct contradiction is discovered:

-In the case of overlapping linking sets, if the overlapping subset is always TRUE when a candidate outside the driving subset is assumed to be TRUE then the number of linking sets decreases by one.
-In the case of overlapping primary sets, if the overlapping subset is always FALSE when a candidate outside the driving subset is assumed to be TRUE then this also helps to even out the number of primary sets – linking sets.

alex

[Red Ed]

OK, I think I understand the Alex/Allan conversation now.

Alex> recursively apply a cover set method to crack the chain which someone may accuse for being trial & error
You could also accuse exact-cover (EC) methods of being trial-and-error solutions, since they require brute-force enumeration of covers for a given strong constraint set (even if leaving aside the extremely difficult job of finding an appropriate strong constraint set in the first instance).

In this context, EC is more a descriptive framework than it is a viable solution technique. I rather like the compactness with which it can describe an elimination by simply listing the strong constraints. For the case in question, the nrct3 chain can be described as "EC of 5@b1, 5@b2, 5@r5". All non-uniqueness solutions can be written as a sequence of EC eliminations in this way.

[Allan Barker]

Allan, when you said, "these examples try to point out that it is the integration of cover sets with other principles that explain nrct chains, and not the cover set approach itself", were you referring to Alex's method or to exact-cover techniques? I couldn't tell.

Red Ed. You are perfectly correct to say that I was referring to more generic applications of cover sets that do not have rules or reasons to eliminate the candidate in r1c8. That includes exact-cover techniques, which as I understand do not allow overlap of sets.

I think, your main point is the table and analysis that eliminates r1c8.

The candidate in r1c8 is guaranteed to be eliminated by the rules of Sudoku, without consideration of specific solving methods. It is already a goner, we only seek logical reasoning that helps find this and other eliminations. Sorry to back up this far, but there is a point.

The table itself lists the membership of candidates in various sets based on the input from the logic diagram. The candidate is then eliminated by enumerating all possible permutations of these candidates inside these sets. While permutations make powerful proofing methods (my absolute favorite), I do not consider them part of a generic set approach. Also, it is the set cover considerations that provide the logic for the permutations to test.

On the other hand, r1c8 can be eliminated considering only permutations and the rules of Sudoku, I do not need to ever consider set cover. Personally, I love permutations and wonder why they don't get more attention, perhaps they are associated with brute force, which is not strictly true. Anyway, I think all points here are correct and the only differences come from the interpretation of definitions.

BTW: I take no credit for the pretty drawings, they are the output from my software, as are any logical conclusions in the diagrams.

[denis_berthier]

Milko,

In practice however, the method is not very significant, because it is easier to apply the individual techniques which narrow significantly the research field of a valid ‘pattern’ where eliminations can exist

Complexity problem related to the exponential number of subsets to be considered.
Practical necessity of ordering the rules according to some complexity measure. In your framework, I think length of the chains and maximal size of the subsets may be parameters. But, considering how complex the transposition of an nrct chain becomes, I'm not sure the size of the subsets will be relevant. Did you try to put any ordering in your solver?

The method [...] is all covered by naive set theory and therefore sudoku obtains a strong link with maths and a simple but elegant math framework.

Sudoku has always had obvious strong links with different branches of maths, the most obvious one being with FOL.
As Allan, you have a method that subsumes all known first order rules in a uniform second order framework (call it set theory) and this is interesting.
More precisely, the framework can be made existential second order - which, according to Fagin's theorem, corresponds to NP-complete problems (the case of Sudoku).

We may therefore expect some claim of completeness. But, instead of this, you only say (in section 4 of your paper):

Although not proven here, each sudoku-like game with a unique solution is expected to be solved using logical steps in order to narrow the 324 initial candidate sets of size 9 to 81 sets of size 1,

which is very ambiguous.
What do you mean by "is expected to be"? Can you prove that using your set cover algorithm you can solve any valid puzzle? Or are you just conjecturing this?
The same question is still asked to Allan (see his thread).
gsf, Red Ed? As Sudoku can be translated into a graph colouring problem, can't set cover techniques be aplied to graph colouring to prove completeness?

If you can prove completeness, then this is an interesting theoretical result. If not, we hope with you

that the program will give me new techniques for solving sudokus

[Red Ed]

As Sudoku can be translated into a graph colouring problem, can't set cover techniques be aplied to graph colouring to prove completeness?

Which set cover techniques are you referring to: Allan's, Alex's or my description of Exact Cover? Completeness (if that's the word) of the latter is obvious: simply take as the "strong constraints" the complete set of 324. I think you were referring to Alex's, in which case I would need to read his paper much more carefully if I had any chance of being able to help on the completeness question.

[denis_berthier]

As Sudoku can be translated into a graph colouring problem, can't set cover techniques be aplied to graph colouring to prove completeness?

Which set cover techniques are you referring to: Allan's, Alex's or my description of Exact Cover? Completeness (if that's the word) of the latter is obvious: simply take as the "strong constraints" the complete set of 324. I think you were referring to Alex's, in which case I would need to read his paper much more carefully if I had any chance of being able to help on the completeness question.

I think the question is interesting for each of these three techniques.
Moreover, it'd be interesting for specialisations of them to particular subsets.

Finally, it's not very clear for me how these 3 techniques are related.


Could you give the best reference to your description of exact cover? I couldn't find it in this forum.

[Red Ed]

Could you give the best reference to your description of exact cover? I couldn't find it in this forum.

Sure, here: <wikipedia>.

Allan's use of "exact cover", to talk about covering candidates rather than constraints, is a little non-standard. Maybe that gives rise to some confusion. (Nevertheless, I find his web pages rather an enjoyable read.)