Explanation of "disjoint subsets"

Programs which generate, solve, and analyze Sudoku puzzles

Explanation of "disjoint subsets"

Thank you to simes and scrose for your clear explanation to me on "disjoint subsets" as to why candidates 1,5 and 7 can only occupy columns 2,3 and 6. Your clue which convinced me was your highlighting that "there are three cells (r2c2, r2c3 and r2c6) that have ONLY 1,5 and 7 as candidates between them.
You also asked if I had looked at pairs (group of 2 numbers) and if I understand them fully. I don't understand what you mean and would appreciate your explanation on this point.
Thank you again Bonsai Cec
Cec

Posts: 1039
Joined: 16 June 2005

A pair is simpler version of the previous example, where there are only two cells with two candidates.

For example, with the candidates:
{1, 7}, {6, 7, 9}, {1, 6, 7, 9}, {1, 7}, {1, 4, 7, 6}, {2, 3, 6, 7}, {3, 4, 6, 8, 9}, {2, 3, 4, 6, 8}, {5}
The 1 and 7 form a pair, and can be eliminated from the candidates for other cells.
Last edited by simes on Sun Dec 11, 2011 9:53 am, edited 1 time in total.
simes

Posts: 324
Joined: 11 March 2005
Location: UK

To complement simes' explanation, I will provide an example based on finding a contradiction.

{17} {679} {1679} {17} {1476} {2367} {34689} {23468} [5]

Ignoring the constraints of other columns and blocks, try putting a 7 in column 2, and thus remove the other 7's from the row.

{1} [7] {169} {1} {146} {236} {34689} {23468} [5]

We immediately arrive at the contradiction of 1 being the only candidate remaining in each of two columns.

You will reach similar contradictions if you attempt to place a 1 in columns 3 or 5, or a 7 in columns 3, 5, or 6.

Thus, columns 1 and 4 are the only columns in which the candidates 1 and 7 can be.
scrose

Posts: 322
Joined: 31 May 2005

Following on from the example given:

17 / 679 / 1679 / 17 / 1467 / 2367 / 34689 / 23468 / 5

After clearing out the 1's and 7's from other cells we are left with:

17 / 69 / 69 / 17 / 46 / 236 / 34689 / 23468 / 5

At this point there is another pair with the 6's and the 9's:

17 / 69 / 69 / 17 / 4 / 23 / 348 / 2348 / 5

There is an obvious 4 here, so using it leaves:

17 / 69 / 69 / 17 / 4 / 23 / 38 / 238 / 5

Leaving you to expand this idea into the boxes that they are a part of (or an X-Wing in the case of the 17)

LA
Lardarse

Posts: 106
Joined: 01 July 2005

Check out my posting under "The continuum of sudoku logic"
for an Algorithmic description of these solutions.
normxxx

Posts: 11
Joined: 12 July 2005

There are two ways to look at disjoint subsets see at:

http://users.pandora.be/vandenberghe.jef/sudoku/index.html?how2solve

Regards

http://daily-sudoku.tk
chabo

Posts: 5
Joined: 23 July 2005