Trying to understand color collisions

Puzzler

In Angus' example of a puzzle containing colliding colors, he shows he following:

2. Cells with the same conjugate color sharing a group

Please could someone explain why {R5,C8} is blue and not green? If I follow the chain of colors, it would seem to me that this cell is a conjugate of {R9,C8}.

This makes a big difference because if it's green, the colliding chain is different. I think this is why my collision code isn't working - I'm coloring in the wrong order, perhaps because I'm choosing a different start cell.

Is there a rule I can apply to selecting which cells to color, in what order?

Thanks

daj95376 · Posted: Sun May 10, 2009 5:29 am Post subject:

Cell [r5c8] is blue because it is a conjugate of cell [r5c1], which is green.

The rules for coloring aren't affected by where you start. However, the order in which you color the cells can sometimes affect where you detect a contradiction, but not which color has the contradiction.

In the example you selected, the contradiction will always appear between cells [r5c8] and [r6c9] in box 6.

JasonLion · Posted: Sun May 10, 2009 12:58 pm Post subject:

If R5C8 was the other color, R6C9 would also end up being the other color.

In this case there is a five cell chain that can never be colored without a contradiction:

R5C8, R5C1, R8C1, R8C9, R6C9

Because R5C8 and R6C9 are not a conjugate pair, and because of the chain, no coloring will ever end up with them being different colors

Different orders of coloring can change the color that is contradicted, but not the cells in which the contradicted color occurs.

Puzzler · Posted: Sun May 10, 2009 6:17 pm Post subject: How reliable is this method?

I'm really missing a simple concept here.

There are so many ways to create chains that collide, depending on the exact sequence that you color the chains. Each collision appears "equally invalid", yet only one of the many 'invalids" is the right "invalid"

It just doesn't seem like a very reliable method.

PIsaacson · Posted: Sun May 10, 2009 11:14 pm Post subject:

Puzzler,

There are 11 possible conjugate pair starting positions for coloring this example:

Boxes - b1 r2c2-r2c3, b4 r5c1-r6c2, b7 r8c1-r9c3, b9 r8c9-r9c8
Rows - r1 r2c2-r2c3 (dup), r5 r5c1-r5c8, r8 r8c1-r8c9, r9 r9c3-r9c8
Cols - c1 r5c1-r8c1, c2 r2c2-r6c2, c3 r2c3-r9c3, c9 r6c9-r8c9

Regardless of where you start and which color you start with, simple conjugate coloring will always arrive at the "collision" in box 6 for r5c8 and r6c9. The great thing is that because you've used simple conjugate coloring, in this case all cells colored the same as the collision color can be eliminated:
r2c3<>9, r5c8<>9, r6c2<>9, r6c9<>9, r8c1<>9 and r9c8<>9 all at once.

They're conjugates and you've proven that one color is "false", so it should make sense as to why all the eliminations are legal. Try coloring all 11 possible start positions and remember to only color conjugates and this should start to make sense. Coloring is a handy tool to have at your disposal since it's kind of a mechanical process and doesn't require memorizing all the various fishing rules or spotting a pattern other than a conjugate pair to kick off the coloring algorithm. Personally, I like X-coloring for single digit analysis, but coloring in general is a very reliable and powerful technique, especially advanced multi-coloring such as 3d-medusa or GEM etal.

In answer to your original question, r5c8 is not a conjugate pair with r9c8 because of r6c8.

Cheers,
Paul

Puzzler · Posted: Mon May 11, 2009 2:25 pm Post subject: Almost had it

Hi Phil

Thanks for your help. It's much appreciated.

I've re-written my code and finally have it coloring correctly to solve the puzzled above.

My code checks for traps and collisions and works many of the test cases I have, but then comes unstuck on this one:

807090602952860040306020598781934256264000009539602004600000421120046980408210065

The code immediately finds a trap for 1 in {R1,C8}

Blue chain: {r1,c2},{r2,c6},{r9,c7}
Green Chain: {R2,C7},{r3,c2},r6,c8}

Conjugating pairs:
{R1,c2}->{R3,C1}
{r2,c6}->{r2,c7}
{r6,c7}->{r6,c8}

All of the conjugates are correct, and there is quite clearly an intersection between green and blue chains so I'm puzzled why this trap is wrong. There must be an additional rule I'm not aware of.

Could you shed some light for me?

Thanks

Puzzler · Posted: Mon May 11, 2009 4:56 pm Post subject: Programatic selection of colors

In the following puzzle there is a collision for 1's in R1,C4 and r2,C5

I've tried selecting cells based on following the conjugate chain and by selecting cells in row/column order but in both cases end up coloring R1,c9 green, not blue.

I don't understand how to programmatically select colors in this puzzle

How does the program know which cells to color what color? It's obviously not random, but I'm damned if I can see how its doing it.

There HAS to be a consistent, repeatable method for cell selection, can anyone tell me what it is?

Thanks

Lunatic · Posted: Mon May 11, 2009 5:14 pm Post subject:

Hi Puzzler,

In simple coloring, you can only consider single chains. Your example has more than one chain, and you cannot implement Simple Coloring logic on more then one of these chains at the same time. You must apply Multiple Coloring for working with two (multiple) chains.

In your example,

807090602952860040306020598781934256264000009539602004600000421120046980408210065

I can see 5 strong links (conjugating pairs) on candidate 1:
1) {r1,c2}->{r3,c2}
2) {r1,c8}->{r2,c7}
3) {r2,c6}->{r2,c7}
4) {r5,c4}->{r5,c6} (in the centre box)
5) {r6,c7}->{r6,c8}

Only conjugate pairs n° 2 and n° 3 will link up to form a (short) chain, but Simple Coloring will not deliver any eliminations.

Candidate 1, by the way, is locked in the centre box at row 5, eliminating 1 from both cells {r5,c7} and {r5,c8}
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~

PIsaacson · Posted: Mon May 11, 2009 5:19 pm Post subject:

Puzzler,

The conjugate pair r1c2-r3c2 stands alone. There are no conjugate links to the other colored pairs, so its coloring cannot participate in any deductions.

7 conjugate pairs: b1 r1c2-r3c2, b3 r1c8-r2c7, b5 r5c4-r5c6, r2 r2c6-r2c7, c7 r2c7-r6c7, c8 r1c8-r6c8.

b1 r1c2-r3c2 stands alone - cannot participate in other colorings
b5 r5c4-r5c6 stands alone - cannot participate in other colorings

According to templates, there are no single digit eliminations possible for the 1s after the initial r5c78<>1 from a box/line pointing pair. However, the 3s and the 7s are vulnerable, at least to X-coloring. Loading the grid into SS and using X-coloring starting from the conjugate pair r1c8-r5c8 quickly leads to r1c8<>3. Try simple coloring starting with 3r1c8 blue (true) and then extend the green false lines. B2 becomes totally green from r1c8 and r9c6 blue, so the initial premise (r1c8 true) is false and it can be eliminated.

Step by step - filter on three:
1) r1c8 = blue => r1c46, r2c79, r5c8 = green (all the peers colored false)
2) r5c8 = green => r5c7 = blue (conjugate pair)
3) r5c7 = blue => r9c7 = green (peers colored false)
4) r9c7 = green => r9c6, r8c9 = blue (conjugate pair + from r2c9 = green for r8c9 conjugate pair)
5) r9c6 = blue => r27c6 = green (all peers colored false)

At this stage box 2 is colored all green, so the original premise is false and r1c8<>3.

Hope this helps,
Paul

Lunatic · Posted: Mon May 11, 2009 6:10 pm Post subject:

Puzzler · Posted: Mon May 11, 2009 8:26 pm Post subject: Thanks!

Phil and Marc,

Thanks for your help. I believe I have nailed the code now. At least, it works for the test cases I have.

My breakthrough was the realization that I was colliding and trapping against cells in different chains. I was confusing one chain with two colors and two chains of the same color. Thanks guys for pointing that out to me.

Marc, you mentioned that this technique only works if you have a single chain. I'm finding with the test cases I have that it doesn't matter if I have more than one chain, as long as I only test one chain at a time. Is this correct, or have I just been lucky in my test cases?

I'm intrigued by the x-colors technique and may try to implement this too, but for now, I'm exhausted and I think I'll rest my brain for a day or two!

Regards

Kevin

PIsaacson · Posted: Mon May 11, 2009 11:25 pm Post subject:

Pseudo code for X-coloring (plus) algorithm

Lunatic · Posted: Tue May 12, 2009 3:40 am Post subject: Re: Thanks!