The New Sudoku Players' Forum

[Pep]

I'm the guy who posted that puzzle, and thank you for bringing this forum to my attention. I thought the x-constraints were all about the intersections between sets, not the contents of individual elements of the sets. Or have I got this wrong?

<OT comment>
I'm late coming into this business, and so the implementation of the constraints is far as I've got so far, but all the work to date in my solver has been my own ideas. It was only very recently that I discovered the present terminology.

You can find my program at http://www.pepperdine.eclipse.co.uk. It is in Java and can run as an applet from that site. It is not designed either to be fast or complete, but as an experiment in logical deductions. A description of the rules are also there.
</OT comment>

[ronk]

I thought the x-constraints were all about the intersections between sets, not the contents of individual elements of the sets. Or have I got this wrong?

I just yesterday ran across the definition by Glenn Fowler of x-constraint, so I don't know the answer to your question. However, I suspect the usage of constraint in this forum may be quite different.

Constraint here is being used in the sense of x-wing, swordfish, and jellyfish patterns. For example: for the swordfish, if candidates (for the same digit) are located in three rows (constrained by three rows) such that every candidate is also constrained by exactly three intersecting columns, then other candidates in those columns may be elimnated.

The discussion was then extended to mixed sets where the first set of constraints was not all rows (or columns) and the second set was not all columns (or rows), but rather a mix of row/column/box. Your puzzle was the first we've seen that had a mix in both of the intersecting sets.

[Pep]

OK. That explains things a bit. In fact the full implementation of intersecting networks of sets is something I have still to complete. Currently, I handle only rows & columns, but I was aware that it should be a case of finding general non-self-intersecting sets. That puzzle falls to both techniques, (Glenn Fowler's x-constraints, and *-fish patterns) but I think my comment still holds that it is the intersections that matter.

Am I right in saying that for the 2-d case, there need to be two sets of equal size (A and B) in each of which the elements are pairwise non-intersecting, and each element in A intersects some element in B and vice versa, and in A, all the positions for a value are in the intersections between its elements and some element in B, then all places in B not at those intersections can be eliminated? Whether the elements of the sets are rows, columns or boxes is irrelevant.

I have not yet thought through the 3-d case (i.e. 3 sets of equal size, etc.). Can it ever occur in the usual r/c/b type of puzzle?

[stuartn]

Pep - nice solver - one (small) criticism is that it doesn't remove candidates as one progresses through the grid... or did I miss something?

stuartn

[Pep]

That is what the "Promote" button is for. The candidates are left in view so a right click on them can explain why it was done. Then you can promote them out of the way so that the next step can be seen.

Thanks for the comments. If you want to know more, please send me mail offline - the address is on my home page.

[Lummox JR]

Actually, ronk, just to clarify the terminology, as I posted in the beginning of this thread "constraint" means something a tad different in this context. The usage comes from the exact cover form of this problem (dancing links) and a constraint refers to one of the columns in the exact cover matrix. It means any of:

- The possible digits in a cell
- The possible positions for a digit in a box
- The possible positions for a digit in a column
- The possible positions for a digit in a row

Only the latter two of those are involved in X-fish patterns. In theory any mix of constraint types in sets A and/or B will work for this technique in any kind of exact cover problem, but in sudoku I don't think it's possible to use "digit in cell" without the whole thing simplifying to a basic naked or hidden subset.

One remaining question is whether you can mix different digits with the other constraints. (E.g., set A might be r1d2, r3d2, r2d9, r3d9, and set B might be b1d2, b2d2, b1d9, b2d9.) I suspect it's not possible without degenerating to something simpler.

[Ruud]

Of all the techniques "under construction", this looks to me the most promising.

As some of you know, I have a solver that uses templates to check the placements of each individual digit. This solver sometimes makes eliminations for a digit that cannot be explained by x-wing/swordfish or coloring, but only by small implication chains. In most of these cases, I noticed that a "narrowing" appeared in the candidates pattern.

Having read this topic, I see that many of the eliminations done by templates can be explained by the constraint subset theory. The "narrowing" is simply one of the A-constraints.

OK, so now I'm eager to implement this in Sudo Cue. Just to be sure, this is how I should do it?

1. Check all unsolved constraints.

At this point I will limit this to all constraints for a single digit, making the algorithm acceptable in speed.

2. Form an A-group of N constraints, where no candidate appears more than once.

Question: Should I look at the size of these constraints? e.g., to form a group of N=4, all the constraints should have a size <= 4.

3. Form a B-group of N constraints, not including any of the A-constraints, but including all the candidates in the A-group, and at least one more candidate to be effective.

Question: Does the B-group also require each candidate to appear in a single constraint, or is that irrelevant?

4. Eliminate from the B-group all excess candidates (not found in the A-group)

Any additions?

Ruud.

[ronk]

Question: Does the B-group also require each candidate to appear in a single constraint ...

No, but that will be the case after eliminations. The best example of that is a pattern first presented by Ocean AFAIK.

Code: Select all

 Example:               Reduces to:
 *-----------------*    *-----------------*
 |. . 1|1 . .|1 1 1|    |. . 1|1 . .|1 1 1|
 |. . 1|1 . .|1 1 1|    |. . 1|1 . .|1 1 1|
 |1 1 1|1 1 1|1 1 1|    |1 1 .|. 1 1|. . .|
 |-----+-----+-----|    |-----+-----+-----| 
 !1 1 1|1 1 1|1 1 1|    |1 1 .|. 1 1|. . .|
 |. . 1|1 . .|1 1 1|    |. . 1|1 . .|1 1 1|
 |. . 1|1 . .|1 1 1|    |. . 1|1 . .|1 1 1|
 |-----+-----+-----|    |-----+-----+-----|
 |1 1 1|1 1 1|1 1 1|    |1 1 .|. 1 1|1 1 1|
 |1 1 1|1 1 1|1 1 1|    |1 1 .|. 1 1|1 1 1|
 |1 1 1|1 1 1|1 1 1|    |1 1 .|. 1 1|1 1 1|
 *-----------------*    *-----------------*

The A set is boxes 1, 2, 4, and 5. The B set is rows 3 and 4, and cols 3 and 4. In the B set before eliminations, candidates exist at the intersections (overlaps) of the rows and columns. After eliminations, they do not.

[Lummox JR]

3. Form a B-group of N constraints, not including any of the A-constraints, but including all the candidates in the A-group, and at least one more candidate to be effective.

Question: Does the B-group also require each candidate to appear in a single constraint, or is that irrelevant?

It's not required, and in fact can give you more eliminations. Any intersection among the B constraints can be eliminated.

4. Eliminate from the B-group all excess candidates (not found in the A-group)

Any additions?

And all A candidates which satisfy 2 or more B constraints.

[ronk]

A puzzle originally posted here ..

Code: Select all

 . . . . 3 . . . .
 . 4 . . 7 . . 1 .
 . . 8 5 . 1 2 . .
 . . 3 . . . 4 . .
 7 9 . . . . . 8 1
 . . 1 . . . 9 . .
 . . 9 3 . 8 5 . .
 . 2 . . 4 . . 6 .
 . . . . 5 . . . . #SE=9.1, GSF=21368

... has two nice constraint subsets at the start.

Code: Select all

 . -7 *7  | .  .  .  |*7 -7 -7
 .  .  .  | .  .  .  | .  .  .
 . *7  .  | .  .  .  | . *7 *7
----------+----------+----------
 .  .  .  | 7  .  7  | .  7  7
 .  .  .  | .  .  .  | .  .  .
 .  .  .  | 7  .  7  | .  7  7
----------+----------+----------
 . *7  .  | .  .  .  | . *7 *7
 .  . *7  | 7  .  7  |*7  . -7
 . -7 *7  | 7  .  7  |*7 -7 -7

Constraint subsets:
Set A (base): r3, r7, c3, c7
Set B (cover): b1, b3, b7, b9
Exclusion(s): r1c289, r8c9, r9c289

This may also be viewed as a continuous grouped x-cycle.
-r3c2=7=r3c89-7-r1c7=7=r89c7-7-r7c89=7=r7c2-7-r89c3=7=r1c3-7-r3c2=

The second constraint subset has a couple of extra candidates ... like the fins of an x-wing, swordfish or jellyfish. This can be considered to be an Almost Constraint Subset.

Code: Select all

 
 -6 -6 *6  | 6  .  6  |*6  . -6
 -6  . *6  | 6  .  6  |*6  . -6
 *6 *6  .  | . *6  .  | .  . *6
 ----------+----------+----------
  6  6  .  | 6 -6  6  | .  .  6
  .  . #6  | 6 =6  6  |#6  .  .
  6  6  .  | 6 -6  6  | .  .  6
 ----------+----------+----------
 *6 *6  .  | . *6  .  | .  .  .
  .  .  .  | .  .  .  | .  .  .
 -6 -6 *6  | 6  .  6  | .  .  .

Almost constraint subsets:
Set A (base): r3, r7, c3, c7
Set B (cover): c5, b1, b3, b7
Fins: r5c3, r5c7
Exclusion(s): r5c5

Ultimately either fins r5c3 and r5c7 are both false ... or one of the fins is true. If both are false, the candidates in r3, c7, c3 and c7 are covered by c5, b1, b3 and b7 ... and all the candidates tagged '-' and '=' would be excluded. If one fin is true, exclusion r5c5<>6 (the '=') would still occur.