Simple Colouring and Grouping of Candidates

Advanced methods and approaches for solving Sudoku puzzles

Simple Colouring and Grouping of Candidates

Postby ronk » Sat Jan 21, 2006 12:58 am

Grouping of candidates is a recent extension to Sudoku puzzle solving techniques, and it is certainly applicable to simple colouring. Consider the following example from a puzzle originally posted by Rod Hagglund here.

Image

Two [edit: non-intersecting] groups identically colored (amber) in the same unit (box 3) are a contradiction and, therefore, the candidates (the 2s) thusly colored may be eliminated from *all* cells bearing that color. Alternatively, placement of a candidate (2s) may be made in all groups of *single* cells that bear the complementary color (pink).

Code: Select all
Grouped implication chains are:

r12c9=2 => r6c9<>2 => r6c5=2 => r3c5<>2 => r3c78=2 (grouped turbot fish)
amber <--> pink <---> amber <--> pink <---> amber

OR

r12c9=2 => r6c9<>2 => r6c5=2 => r4c4<>2 => r12c4=2 => r3c5<>2 => r3c78=2 (grouped 7-sided x-cycle)
amber <--> pink <---> amber <--> pink <---> amber <--> pink <---> amber

Read r12c9=2 to mean "r1c9=2 OR r2c9=2"
and a (fictitious) r12c9<>2 to mean "r1c9<>2 AND r2c9<>2"

The puzzle in SS form:
Code: Select all
 *-----------*
 |...|.1.|...|
 |...|.7.|...|
 |61.|8.9|..3|
 |---+---+---|
 |4..|.3.|.19|
 |1..|96.|..7|
 |769|5.1|38.|
 |---+---+---|
 |..6|.9.|..5|
 |..2|.5.|19.|
 |951|482|736|
 *-----------*
Last edited by ronk on Sun Jan 22, 2006 2:37 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Simple Colouring and Grouping of Candidates

Postby flip » Sat Jan 21, 2006 9:04 am

ronk wrote:Grouping of candidates is a recent extension to Sudoku puzzle solving techniques, and it is certainly applicable to simple colouring.
.
Very nice, but this can also be solved using the classic technique of simple coloring with conjugates and closure of the exclusion matrix.
This is alternatively also explained using nice loops applied to x-cycles,
Before starting, there are two simplifications, cell r2c9 is a hidden 1 and cell r4c7 is a hidden 6, This leads to the following coloring in digit 2:
Code: Select all
   a.. e.. fgb
   A.. h.. ij.
   ... .B. km.
   .b. B.. ...
   .B. ... np.
   ... .b. ..B
   ... ... dD.
   ..2 ... ...
   ... ..2 ...

There are two conjugate sets in aA and bB.
Candidate e is at the intersection of r1c9b and r3c5B, it can be eliminated.
This is also an x-cycle
Code: Select all
  r1c4e-r3c5B=r6c5b-r6c9B=r1c9b-r1c4e  r1c4e<>2

The same argument applies to k and m being removed,
sharing intersection with r1c9b and r3c5B (also x-cycles)
Removing candidates e,k,m, leads to h being set to b and the coloring reduces to:
Code: Select all
   a.. ... fgb
   A.. b.. ij.
   ... .B. ...
   .b. B.. ...
   .B. ... np.
   ... .b. ..B
   ... ... dD.
   ..2 ... ...
   ... ..2 ...

(Edited)The rest of the exclusions are easy, with B single in row 3. Set the four B to 2, eliminate the four b, as well as n and p.
a.. ... fg.
A.. ... ij.
... .2. ...
... 2.. ...
.2. ... ...
... ... ..2
... ... dD.
..2 ... ...
... ..2 ...[/code]
As I said, the above conclusions can all be made using simple coloring with conjucates and following the closure of the exclusion matrix. This is what I get with my solver. I am still new to x-cycles and nice loops, but tried to add the explanation in terms of x-cycles. If I made any mistakes there, feel free to give the correct x-cycles.
Last edited by flip on Sun Jan 22, 2006 3:53 am, edited 1 time in total.
flip
 
Posts: 17
Joined: 08 January 2006

Re: Simple Colouring and Grouping of Candidates

Postby flip » Sat Jan 21, 2006 11:06 am

Oops(added): the candidates n and p are also eliminated, leaving:
Code: Select all
   a.. ... fg.
   A.. ... ij.
   ... .2. ...
   ... 2.. ...
   .2. ... ...
   ... ... ..2
   ... ... dD.
   ..2 ... ...
   ... ..2 ...
flip
 
Posts: 17
Joined: 08 January 2006

Re: Simple Colouring and Grouping of Candidates

Postby angusj » Sat Jan 21, 2006 11:30 am

ronk wrote:Grouping of candidates is a recent extension to Sudoku puzzle solving techniques

Actually, it's not that recent. See http://forum.enjoysudoku.com/viewtopic.php?p=7954#p7954
angusj
 
Posts: 306
Joined: 12 June 2005

Re: Simple Colouring and Grouping of Candidates

Postby ronk » Sat Jan 21, 2006 12:21 pm

angusj wrote:
ronk wrote:Grouping of candidates is a recent extension to Sudoku puzzle solving techniques

Actually, it's not that recent. See http://forum.enjoysudoku.com/viewtopic.php?p=7954#p7954

Instead of grouped simple coloring, I see Ocean's argument as an example of a (paraphrased) coloring rule you once illustrated on your site:

If any conjugate color representing true candidates would exclude all candidates in a unit (row, col, or 3x3 box), then that color must actually represent false candidates.

Ron

P.S. I take your removal of the illustration as indication you've decided not to implement the rule in Simple Sudoku.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Simple Colouring and Grouping of Candidates

Postby ronk » Sat Jan 21, 2006 1:05 pm

flip wrote:...this can also be solved using the classic technique of simple coloring with conjugates and closure of the exclusion matrix.

"Closure of the exclusion matrix" is what most people in this forum call multi-coloring.

This is the same as the post above, but in addition it eliminates 2@r4c2.

But, of course. Personally, I wouldn't bother with all the 2s eliminations (six or seven cells) and would use the placements (three cells) based on the statement ...

ronk wrote:Alternatively, placement of a candidate (2s) may be made in all groups of *single* cells that bear the complementary color (pink).

... letting the eliminations occur consequentially and automatically. That would include r4c2<>2. And I also wouldn't bother with writing the implication chains presented, done so only for "completeness".

flip wrote:If I made any mistakes there, feel free to give the correct x-cycles.

You made no mistakes that I can see. The basis for my illustration of grouped simple coloring is also x-cycles (turbot fish is a 5-sided x-cycle). The grouping allows one to treat many weak links as strong links .. often yielding longer strong chains ... to which then, the simplicity of simple colouring might be applied.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Simple Colouring and Grouping of Candidates

Postby angusj » Sat Jan 21, 2006 1:23 pm

ronk wrote:Instead of grouped simple coloring, I see Ocean's argument as an example of a (paraphrased) coloring rule you once illustrated on your site:

OK. I admit I haven't studied Rod Hagglund's posts (and I don't understand what he was saying in that link above) so it's quite likely I'm on the wrong foot here.

Anyhow, when I looked at the puzzle you presented above I quickly saw that if the conjugate pink cells were the 'false' cells then there'd have to be two 'true' cells in box 3 (an obvious contradiction) - otherwise there'd be no 2 value in either row 3 or column 9. That reminded me of somewhat similar logic presented by Ocean some time ago (hence the link), so it struck me that it was Ocean that first showed the power of coloring to elicit contradictions in cell groups (rows, columns or boxes). Anyhow, I suspect I've misunderstood your meaning of 'grouping of candidates'.

ronk wrote:P.S. I take your removal of the illustration as indication you've decided not to implement the rule in Simple Sudoku.

You're correct in surmising that I don't have plans (at this stage) to implement this rule in Simple Sudoku. However, I'm pretty sure I never had an illustration of it on my site either. (I've recently been persuaded by you:D that this technique is much easier to spot than I'd originally thought, but I'm still not convinced it's prevalent enough to bother adding to SS's solving matrix. IIRC, I tried using it on a large number of my http://angusj.com/sudoku/ss_unlimited_1.zip puzzles without any success.)
angusj
 
Posts: 306
Joined: 12 June 2005

Re: Simple Colouring and Grouping of Candidates

Postby ronk » Sat Jan 21, 2006 2:06 pm

angusj wrote:That reminded me of somewhat similar logic presented by Ocean some time ago (hence the link), so it struck me that it was Ocean that first showed the power of coloring to elicit contradictions in cell groups (rows, columns or boxes).
From your post here ...
angusj wrote:There are 3 ways to use Simple Coloring that I'm aware of:
1. Candidate grouped with both conjugate colors
2. Cells with the same conjugate color sharing a group
3. Candidates for an entire group also group with cells of the same conjugate color
The Ocean deduction is identical to your "third way" and is even for the same puzzle. IMO my example is a grouped version of the "second way."

angusj wrote:However, I'm pretty sure I never had an illustration of it on my site either.
I apologize for the misrepresentation. All I remembered "for sure" was that the image was from a link to your site, which *is not* the same as being on your web pages.

Ron
Last edited by ronk on Sat Jan 21, 2006 10:21 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Simple Colouring and Grouping of Candidates

Postby angusj » Sat Jan 21, 2006 2:16 pm

ronk wrote:
angusj wrote:There are 3 ways to use Simple Coloring that I'm aware of:
1. Candidate grouped with both conjugate colors
2. Cells with the same conjugate color sharing a group
3. Candidates for an entire group also group with cells of the same conjugate color
The Ocean link is obviously the same puzzle as your illustration of the "third way", while my example is a grouped version of the "second way."

I'm afraid I'd argue that the cells you've colored amber in box 3 aren't strictly conjugates so I wouldn't describe this as an example of a 'type 2' color.

Edit: It seems to me that there should now be 4 Simple Color types:
1. A candidate 'buddied' with both conjugate colors must be 'false'
2. Cells with the same conjugate color sharing a group (row column or box) must be 'false'
3. If cells of one conjugate color 'buddied' with candidates of an entire group, then it must be 'false' color
4. Where cells of one conjugate color being 'false' would imply more than one 'true' candidate in a group, then that color must be 'true'
angusj
 
Posts: 306
Joined: 12 June 2005

Re: Simple Colouring and Grouping of Candidates

Postby ronk » Sat Jan 21, 2006 2:50 pm

angusj wrote:I'm afraid I'd argue that the cells you've colored amber in box 3 aren't strictly conjugates so I wouldn't describe this as an example of a 'type 2' color.

Since there is no grouping with traditional conjugate pairs, "grouped conjugate pairs" obviously wouldn't fit the traditional definition. But the grouped conjugate pairs illustrated in my opening post certainly have the same implications as traditional conjugate pairs.
Code: Select all
 2   .   .   |A2   .   .   | 2   2  A2
 2   .   .   |A2   .   .   | 2   2  A2
 .   .   .   | .  a2   .   |A2  A2   .
-------------+-------------+-----------
 .   2   .   |a2   .   .   | 2   .   .
 .   2   .   | .   .   .   | 2   2   .
 .   .   .   | .  A2   .   | .   .  a2
-------------+-------------+-----------
 .   .   .   | .   .   .   | 2   2   .
 .   .   2   | .   .   .   | .   .   .
 .   .   .   | .   .   2   | .   .   .

... where 'A' is the amber and 'a' is the 'not amber', aka, pink.

For the traditional conjugate pair in row 6:
if r6c5=2, then r6c9<>2,
if r6c5<>2, then r6c9=2,
if r6c9=2, then r6c5<>2,
if r6c9<>2, then r6c52.

For the grouped conjugate pair (conjugate nodes, see below) in col 9:
if r6c9=2, then r12c9<>2 (meaning r1c9<>2 AND r1c9<>2),
if r6c9<>2, then r12c9=2 (meaning r1c9=2 OR r2c9=2),
if r12c9=2, then r6c9<>2,
if r12c9<>2, then r6c9=2.

Both sets of implications meet the requirements of a strong link, whether traditional or grouped. Therefore, from my POV, both describe conjugates. However, maybe a naming distinction should be made ... say 'conjugate pairs' and 'conjugate nodes' ... which is what Jeff has effectively already done on the Forcing chains: Terminology and Definition thread.

Regards, Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Simple Colouring and Grouping of Candidates

Postby ronk » Sat Jan 21, 2006 9:19 pm

angusj wrote:It seems to me that there should now be 4 Simple Color types:

2. Cells with the same conjugate color sharing a group (row column or box) must be 'false'

4. Where cells of one conjugate color being 'false' would imply more than one 'true' candidate in a group, then that color must be 'true'

There is an inverse for every logical statement AFAIK. Taking the inverse of '4' you get ...

Where cells of one conjugate color being 'true' would imply more than one 'true' candidate in a group, then that color must be 'false'

... which is '2' all over again, although in different words.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Simple Colouring and Grouping of Candidates

Postby angusj » Sat Jan 21, 2006 10:54 pm

ronk wrote:... which is '2' all over again, although in different words.

Well, that would only be true if I accepted your widened definition of conjugate pairs (which I'm currently disinclined to do). Using the original strict definition of conjugate pairs there are no conjugates in box 3, so the "type 4" rule seems to be the only way to exclude candidates in that box.

I'm not up on 'conjugate nodes' so I can't really comment there, but it seems a good way to differentiate your technique from conjugate pairs and avoid confusion.
Last edited by angusj on Sat Jan 21, 2006 7:04 pm, edited 1 time in total.
angusj
 
Posts: 306
Joined: 12 June 2005

Postby Myth Jellies » Sat Jan 21, 2006 11:02 pm

I think you need to be more careful with your wording for number 4. Up until now you have assiduously avoided becoming a T&E process by not making any prior assumptions about which color represents true or false. A statement like "if you assume one color is false and that assumption results in multiple trues in a group--then that color must be true." would blow the whole non-T&E argument out of the water.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby angusj » Sat Jan 21, 2006 11:08 pm

Myth Jellies wrote:I think you need to be more careful with ...

I agree all with your comments but I don't think changing the wording would make this rule any less like T&E. However, I'm open to suggestions.

Edit: The T&E issue seems to boil down to whether backtracking is seen as a valid (or intellectually pleasing) puzzle solving technique. Some purists have argued that what most accept as logic is also backtracking (ie try something and discard it). I fall into the camp of - if it's reasonably easy to 'see' (sometimes with the aid of colors) then it's a helpful solving technique. This is certainly a technique that falls into the gray area of what's not so reasonably easy to 'see':)
angusj
 
Posts: 306
Joined: 12 June 2005

Postby Myth Jellies » Sun Jan 22, 2006 12:48 am

angusj wrote:I agree all with your comments but I don't think changing the wording would make this rule any less like T&E. However, I'm open to suggestions.


Okay,

It's a bit wordy, so maybe someone can sharpen it up a bit. In order to avoid confusion with the grouping mentioned earlier in the post, I am going to use "unit" to represent box/row/column.

Colors rule 4

Let A and B represent two cells of the same color, X, that do not lie in the same unit.

Let A' represent all of the remaining cells in a unit containing A.
Let B' represent all of the remaining cells in a unit containing B.

If you can find an A' and a B' that lie entirely in the same unit, and that do not share any cells, then color X must be true.

Which reminds me of something...

ronk wrote:Two groups identically colored (amber) in the same unit (box 3) are a contradiction


In order for this to be a contradiction, I think you need to qualify that a little bit more and state, "Two non-intersecting groups...."

In addition, you might as well have colored the remaining cells in box 6 amber:)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Next

Return to Advanced solving techniques