Explanation of "disjoint subsets"

Programs which generate, solve, and analyze Sudoku puzzles

Explanation of "disjoint subsets"

Postby Cec » Thu Jun 23, 2005 5:33 am

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

Postby simes » Thu Jun 23, 2005 6:26 am

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

Postby scrose » Thu Jun 23, 2005 1:27 pm

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

We start with the example simes provided.

{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

Postby Lardarse » Sun Jul 03, 2005 12:16 am

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

Postby normxxx » Sun Jul 17, 2005 3:49 am

Check out my posting under "The continuum of sudoku logic"
for an Algorithmic description of these solutions.:D
normxxx
 
Posts: 11
Joined: 12 July 2005

Postby chabo » Sat Jul 23, 2005 1:58 pm

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


Return to Software