dailysudoku.com :: View topic

dailysudoku.com
Discussion of Daily Sudoku puzzles

FAQ

Memberlist

Usergroups

Profile

Tuesday 2 May
Goto page Previous 1, 2

dailysudoku.com Forum Index -> Daily Sudoku puzzles

View previous topic :: View next topic

Author

Message

TKiel

Joined: 22 Feb 2006
Posts: 292
Location: Kalamazoo, MI

Posted: Fri May 05, 2006 10:43 am Post subject:

RogerC, Don't have time right now but check out this site Simple Sudoku for an explanation better than mine would be anyway.

David Bryant

Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

Posted: Fri May 05, 2006 6:30 pm Post subject: Simple coloring

RogerC wrote:

Can you explain [simple and multiple coloring], please, Tracy?

Since Tracy's too busy right now, I'm sure he won't mind if I take a stab at it. Smile

You can find several links to discussions of coloring logic in a message that was posted a few months ago.

Let's start with the general concept of coloring. This depends on the idea of a binary chain, which is formed when there are only two ways to enter a particular digit in a row, or column, or 3x3 box. The shortest binary chains have exactly two "links". Longer chains can be formed when one of the links in a row, or column, or box, lines up with a link in another row, or column, or box. Since setting the value in one link of the chain will determine where the particular digit can appear throughout the entire chain, we may be able to draw useful logical inferences from the chain itself.

OK, that's probably too abstract, so let's look at an example. Suppose that the digit "2" can only appear in the cells marked with an asterisk in the following grid.

Code:

*+ . . . . . *- . .
. . . . . * * . .
. . *- . * . * . .
. * . * . . . * .
. . *+ . . . . . *-
. . . * . . . * .
* . . . . * *- . .
* . . . * . . . *+
. * . * . . . . .

Let's trace the binary chain, starting at r1c1. Since there are only two ways to enter a "2" in row 1, we see that r1c1 is "strongly connected" to r1c7. Similarly, since there are only two ways to enter a "2" in the top left 3x3 box, we see that r1c1 and r3c3 are strongly connected. From there the chain extends through r5c3, to r5c9, to r8c9, and finally to r7c7. I have marked these cells with alternating "+" and "-" signs, to stress the way they are connected.

Because all the links in the chain are strongly connected, there are only two possible ways this chain can exist. Either all the cells marked "+" contain the digit "2", or else all the cells marked "-" contain the digit "2" -- no other configuration is possible. Oh -- I should explain why the term "coloring" is used. Imagine that the cells marked with a "-" sign are colored green, and the ones marked "+" are colored blue. This would allow us to visualize the chain more clearly and completely. And in fact, many popular Sudoku programs allow us to mark the cells with colors, to make these binary chains stand out.

OK, back to the example and the inferences we can draw.

-- First we note that r7c1 is in line with r1c1 (marked "+") and it's also in line with r7c7 (marked "-"). Either there's a "2" at r1c1 or else there's a "2" at r7c7 (since they are different "colors"), so there cannot possibly be a "2" at r7c1.

-- With the * at r7c1 out of the way we can mark r8c1 with a "-" sign (since there are now only two ways to enter a "2" in column 1). Once again we have a "+" (at r8c9) in line with a "-" (at r8c1), so we can eliminate the possible "2" at r8c5. This is one of the most powerful features of the "coloring" technique -- sometimes it gets rolling like a bulldozer, knocking more and more possibilities out of the way as the pattern is extended.

-- Here's another inference we can draw. Since the "-" sign at r1c7 is in line with the "-" sign at r7c7 we see that the "2"s cannot occupy any of the cells marked with a "-" sign. So all the cells marked "+" must contain the value "2".

Using all three of these inferences we can place all the "2"s in the example.

Code:

2 . . . . . . . .
. . . . . . 2 . .
. . . . 2 . . . .
. . . 2 . . . . .
. . 2 . . . . . .
. . . . . . . 2 .
. . . . . 2 . . .
. . . . . . . . 2
. 2 . . . . . . .

Most of the time "simple coloring" only allows us to eliminate a candidate from one or two cells. I have hit a few, puzzles, though, that crumbled just like the example did. When it happens it's really kind of exciting! dcb

PS This message is getting pretty long already. I'll post a description of "multi-coloring" -- and a couple of real life examples drawn from DailySudoku puzzles -- in another day or two.

TKiel

Joined: 22 Feb 2006
Posts: 292
Location: Kalamazoo, MI

Posted: Sat May 06, 2006 1:20 pm Post subject:

RogerC,

To amplify David's post and provide examples:

Code:

*-----------------------------------------------------------*
| 2349 7 8 | 369 5 39 | 46 1 29 |
| 5 239b 239X | 3689 4 1 | 68 279 279 |
| 1 49 6 | 89 7 2 | 48 3 5 |
|-------------------+-------------------+-------------------|
| 8 5 239 | 4 239 6 | 1 27 237 |
| 23 6 4 | 5 1 7 | 9 8 23 |
| 7 239B 1 | 239A 239 8 | 5 6 4 |
|-------------------+-------------------+-------------------|
| 349 349 7 | 1 8 5 | 2 49 6 |
| 2349A 8 5 | 239a 6 39 | 7 49 1 |
| 6 1 29a | 7 29A 4 | 3 5 8 |
*-----------------------------------------------------------*

This is the grid as posted by George Woods . I've marked one chain with (A-a) and one with (B-b). The cells marked with (A) or (a) are known as conjugate (or binary or strongly linked) cells. These are the only two cells in their respective groups (row, box or column) that can possibly contain the digit 2. R9c5 is linked with r9c3 (row) which is linked with r8c1 (box) which is linked with r8c4 (row) which is linked with r6c4 (column). Either all cells marked with (A) must be 2 and (a) not be 2 or all cells marked with (a) must be 2 and (A) not be 2. The same holds true for the chain marked with (B-b). All we are doing is mapping the cells relationships relative to each other.

Simple colouring uses one conjugate chain, while multiple colouring uses two or more chains. In this case we are going to use two chains. As you can see by looking at the grid, the two chains are connected together by the cells r6c4 (A) and r6c2 (B), because they share the same row. But those two cells are not conjugate, since there are three places in that row that can have a 2 and that is why they are two separate chains. (A) and (B) both cannot be 2, since they are in the same row. Therefore either or both of (a) and (b) must be 2. Any cell that shares a group with both (a) and (b) cannot be 2. R2c3 (marked X) is such a cell and the 2 can be excluded. Now we can extend the (B-b) chain and include a new chain marked (C-c) as shown below:

Code:

*-----------------------------------------------------------*
| 2349B 7 8 | 369 5 39 | 46 1 29b |
| 5 239b 39 | 3689 4 1 | 68 279c 279 |
| 1 49 6 | 89 7 2 | 48 3 5 |
|-------------------+-------------------+-------------------|
| 8 5 239X | 4 239 6 | 1 27C 237 |
| 23 6 4 | 5 1 7 | 9 8 23 |
| 7 239B 1 | 239 239 8 | 5 6 4 |
|-------------------+-------------------+-------------------|
| 349 349 7 | 1 8 5 | 2 49 6 |
| 2349 8 5 | 239 6 39 | 7 49 1 |
| 6 1 29 | 7 29 4 | 3 5 8 |
*-----------------------------------------------------------*

Again, there are two separate chains connected by cells that are not conjugate (b & c) but that share the same group. We can use the same logic as before: Both of (b) & (c) can't be true, so either/both of (B) & (C) are true and any cell that shares a group with cells marked as such can have the 2 excluded. This allows us to remove the 2 from r4c3 (marked X), which leaves r9c3 as the only cell in c3 that contains a 2. Once that value is placed, naked and hidden singles are all that are needed to solve the puzzle.

Last edited by TKiel on Fri Oct 05, 2007 1:51 am; edited 1 time in total

ravel

Joined: 21 Apr 2006
Posts: 536

Posted: Sat May 06, 2006 6:31 pm Post subject:

The samples of David and Tracy are not the best for multiple coloring, because they also can be resolved box/line interaction and x-wing.
This is David's:

Code:

2 . . | . . . | 2 . .
. . . | . . 2 | 2 . .
. . 2 | . 2 . | 2 . .
----------------------------
. 2 . | 2 . . | . 2 .
. . 2 | . . . | . . 2
. . . | 2 . . | . 2 .
----------------------------
2 . . | . . 2 | 2 . .
2 . . | . 2 . | . . 2
. 2 . | 2 . . | . . .

---------
Box/line interaction:
r46=2 => r9c4<>2 => r9c2=2
and it directly brings us here (the naked x-wing cannot be resolved with coloring):

Code:

2 . . | . . . | . . .
. . . | . . . | 2 . .
. . . | . 2 . | . . .
----------------------------
. . . | 2 . . | . 2 .
. . 2 | . . . | . . .
. . . | 2 . . | . 2 .
----------------------------
. . . | . . 2 | . . .
. . . | . . . | . . 2
. 2 . | . . . | . . .

This is Tracy's sample:

Code:

2 . . | . . . | . . 2
. 2 2 | . . . | . 2 2
. . . | . . 2 | . . .
---------------------------
. . 2 | . 2 . | . 2 2
2 . . | . . . | . . 2
. 2 . | 2 2 . | . . .
---------------------------
. . . | . . . | 2 . .
2 . . | 2 . . | . . .
. . 2 | . 2 . | . . .

The x-wing in rows 15 (cols 19) eliminates 2 in r8c1 => r9c3=2.

But note that there are samples, where multiple coloring can lead to eliminations that cannot be done with x-wing, swordfish or advanced coloring (strong links). You would need grouped coloring then.

Display posts from previous:

	dailysudoku.com Forum Index -> Daily Sudoku puzzles	All times are GMT Goto page Previous 1, 2
Page 2 of 2

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum