The New Sudoku Players' Forum

[Lummox JR]

A few months ago I posted about constraint subsets, the great granddaddy of the lesser techniques of singles, subsets, and X-fish. Going back to that now to implement an algorithm, I've finally found an elusive type of constraint subset that uses the "cell must be filled" constraints. Consider this example from advanced coloring:

Code: Select all

ab . . | . Bc .
.  . . | . .  .
.  . . | . .  .
---------------
.  . . | . .  .
AD . . | . Cd .
.  . . | . .  .

Now in a constraint subset, there are the A constraints which have no overlapping values and exist entirely within the B constraints. In this example the A's are these columns and rows, each for a particular digit. In this case, advanced coloring tells us we can eliminate all other choices in each of those 4 cells, the B constraints. We could also look at this situation, where the cells are the A constraints and the columns and rows are the B's: Here, the same 4 digits are in those cells as the only candidates, but other candidates exist in the columns and rows in question.

Code: Select all

aA . . | . bB .
.  . . | . .  .
.  . . | . .  .
---------------
.  . . | . .  .
cC . . | . dD .
.  . . | . .  .

If the digits involved are such that they line up into these two columns and these two rows, then other choices for each digit can be eliminated from the respective column or row they share.

This is sort of a forcing chain and the same logic can be extended to larger chains. This invalidates my initial assumption that a 9x9 grid can have constraint subsets no bigger than 9. In fact, I don't know the upper bound for such a subset, except of course for 2N^2. As I mentioned on the programmer's forum, there's also an interesting twist on this that covers situations advanced coloring doesn't, where a 3x3 set of cells might happen to converge with 9 digit-in-house constraints.

[Jeff]

If the digits involved are such that they line up into these two columns and these two rows, then other choices for each digit can be eliminated from the respective column or row they share.

Hi LJ, Isn't this an xy-ring; a continuous xy-chain of length 4?

[Lummox JR]

Hi LJ, Isn't this an xy-ring; a continuous xy-chain of length 4?

Indeed. But this is one of the less simple techniques, and it's interesting to see that it's expandable to other cases that the xy-ring can't handle (not that those are easy to construct). Up to now the only constraint subsets I knew of that used cell constraints all devolved to simple naked/hidden subsets or singles.

[Jeff]

......it's interesting to see that it's expandable to other cases that the xy-ring can't handle (not that those are easy to construct).

xy-ring can’t handle Strong-ring and x-wing (x-ring could be a better name)?

xy-ring
Continuous
Length 4
All links have weak inferences

Strong-ring
Continuous
Length 4
All links have strong inferences

x-wing
Continuous
Length 4
All links have alternate strong and weak inferences

Or, am I barking at the wrong tree?