## Constraint subsets revisited

Advanced methods and approaches for solving Sudoku puzzles

### Constraint subsets revisited

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.
Lummox JR

Posts: 125
Joined: 22 September 2005

### Re: Constraint subsets revisited

Lummox JR wrote: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?
Jeff

Posts: 708
Joined: 01 August 2005

### Re: Constraint subsets revisited

Jeff wrote: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.
Lummox JR

Posts: 125
Joined: 22 September 2005

### Re: Constraint subsets revisited

Lummox JR wrote:......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

Strong-ring
Continuous
Length 4

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

Or, am I barking at the wrong tree?
Jeff

Posts: 708
Joined: 01 August 2005