colours

Advanced methods and approaches for solving Sudoku puzzles

colours

Postby cheesemeister » Mon Oct 10, 2005 12:25 pm

Having spent the last week trying to figure out colours, (I'm english, that word DOES contain a "u") I *think* I've come to the conclusion that it's a subset of forcing chains. ie where a candidate in a particular square is excludable based on both/all the possible arrangements for connected squares.
Am I also right in thinking theres some debate as to whether forcing chains are just a complex form of t+e and therefore not valid pure-logic techniques or not?
and if so does the colours technique also fall into this debate? or have I to a greater or lesser extent missed the ball on this?
cheers muchly
cheese
cheesemeister
 
Posts: 8
Joined: 02 October 2005

Postby PaulIQ164 » Mon Oct 10, 2005 1:04 pm

As I understand it, a lot of the advanced techniques can be thought of as forcing chains, colours included (but I'm about the worst person around here to ask about them, so don't take my word for it). Forcing chains certainly aren't trial and error, since there's no error involved (it's mor a sort of 'trial and confirmation'), but there is disagreement on whether it's correctly categorised in with T&E or in with the more 'mainstream' tactics (or indeed whether it belongs in its own special thrid category).
PaulIQ164
 
Posts: 533
Joined: 16 July 2005

Postby Lummox JR » Mon Oct 10, 2005 9:38 pm

I can definitively state that coloring is not a subset of forcing chains. Nor is simple coloring even a superset; it will find some of the same conclusions but not all. Supercoloring, however, appears to supercede several, perhaps most, forms of forcing chains. The common kind used in Trebor's Sudoku Susser, for instance, is covered by supercoloring.

Complete simple coloring is a superset of fishy cycles and turbot fish. It does not catch all cases of Nishio, but supercoloring just might.
Lummox JR
 
Posts: 125
Joined: 22 September 2005

Postby cheesemeister » Tue Oct 11, 2005 1:56 pm

afraid you raised more questions than you answered with that; what are turbot and nishio?
and whats different about supercolouring to the kind of colouring in the program simple sudoku
cheers again
cheese
cheesemeister
 
Posts: 8
Joined: 02 October 2005

Postby Lummox JR » Tue Oct 11, 2005 7:14 pm

cheesemeister wrote:afraid you raised more questions than you answered with that; what are turbot and nishio?

Turbot fish was first described here by Nick70. It's a simple pattern to spot, but it's also just as easy to spot with complete coloring.

Nishio is a limited form of trial and error that tries to place a digit, and then looks to see if it can place the remaining positions for that digit based on "single" rules. If it finds a contradiction, the placement is invalid. It can also tell you if, for example, all possible placements of 2 in row 3 lead to a 2 being in (8,6), or if all possible placements of 5 in column 1 eliminate 5 from (4,2).
and whats different about supercolouring to the kind of colouring in the program simple sudoku

Well I haven't used simple sudoku, so I can't speak to that, but I can tell you the difference between simple coloring as commonly practiced, complete simple coloring, and advanced coloring (which is also called supercoloring, multicoloring, ultracoloring, etc.).

Traditionally simple coloring involves taking the candidates of just a single digit, and then finding all sets of conjugates that you possibly can. If a color appears twice in the same house (box/column/row), it's false, and its conjugate must be true. If a color appears alongside two others that are conjugates (i.e., if b shares a house with a, but it also shares a house with A), it is also false. You can also look for colors which must be equivalent; if x and y appear together, and x' and y' (their conjugates) also appear together, then x=y' and x'=y. Finally, this form of coloring can also make eliminations based on places where conjugates intersect: For example, if you have x in (5,1) and x' (x's conjugate) in (9,6), you can't have the digit at (5,6) or (9,1).

Complete simple coloring, which is the form I've recently started using, operates on some extra rules used in supercoloring; in spite of that it's not hard. It looks at colors that share the same house, and says they exclude each other. For example if x and y are together, x!y. If one is true, the other must be false; nothing says either one is necessarily true, but at least one of them is false. Now with exclusions, if x!y, and y'!z, then x!z. You can say this because if x is true, y is false, and y's conjugate y' must be true; since y'!z, z must then be false. Complete simple coloring makes the following observation: If x!y, then x' or y' or both must be true. Therefore any placement where x' and y' intersect must be false. If that placement is labeled with a color, the entire color is false. I don't think many people do coloring this way, which is why I felt free to name it. If you're going to bother to use coloring, this is really the way to go, though, since it's not much harder to use this exclusion rule and it finds things you otherwise won't.

Supercoloring does not restrict itself to one digit; you don't color an entire cell, but merely a candidate. It can find conjugates not just in a box, column, or row, but also in a single cell with only 2 candidates. It uses the same logic rules as complete simple coloring. Typically I find this ends up with around 15-20 conjugate pairs (that's 30-40 colors!), and it's up to you to calculate the exclusions. Once you've calculated exclusions, you may notice that one of the colors excludes itself, in which case it is false. You can also look for intersections as in complete simple coloring, which may be difficult but is doable. This can provide some interesting insights, such as: "Either (4,1)=2 or (4,7)=5, or both. Therefore, (4,1)<>5, and (4,7)<>2."
Lummox JR
 
Posts: 125
Joined: 22 September 2005

Postby tso » Tue Oct 11, 2005 10:55 pm

Is complete simple coloring as you describe it, human implementable, at least in some cases? Could you post a graphic of this in action?
tso
 
Posts: 798
Joined: 22 June 2005

Postby angusj » Tue Oct 11, 2005 11:16 pm

tso wrote:Is complete simple coloring as you describe it, human implementable, at least in some cases? Could you post a graphic of this in action?

I suspect what Lummox JR calls "complete simple coloring" is the same as what I call "multiple colors" (which traces multiple conjugate relationships of a single candidate).

Here's a collection of my multi-color puzzles: http://angusj.com/sudoku/multi-color_puzzles.zip

Here's a graphic.
Image
In this example one conjugate pair is represented by blue/green and the other by pink/orange. Since the blue cells share a group with both the pink and orange cells (one of which must be true), the blue cells must be false.
angusj
 
Posts: 306
Joined: 12 June 2005

Postby Lummox JR » Wed Oct 12, 2005 2:16 am

Yep, I'm aware of the discrepancy on the terminology there. However multiple conjugate pairs does fall under the common definition of simple coloring. See here for some examples. As most people have been using it, "simple" coloring refers merely to coloring that's done with a single digit, vs. advanced coloring which is the same as supercoloring. The term "multicoloring" seems to be most often used as a synonym for supercoloring.

And yes, complete simple coloring is human-implementable. Even supercoloring is, really; it's just a lot harder because of the large number of colors. With simple coloring you're just using one digit, though, so the number of colors is a lot smaller. There's a simple example here, which I post again here for expediency:
Code: Select all
. . .|. . .|. . .
a . .|. A .|. . .
. * *|b * .|. . .
-----------------
* * *|.*. .|. * .
* * .|B . .|. * .
* * *|. * .|. * .
-----------------
* * *|. . .|. . .
. . .|. . .|. . .
. . .|. . .|. . .

As you can see, colors A and b are mutually exclusive, so at least one of them is false. Therefore at least one of their conjugates a and B must be true. Where a and B intersect at (1,5), you can eliminate a candidate.
Lummox JR
 
Posts: 125
Joined: 22 September 2005

Postby Lardarse » Wed Oct 12, 2005 12:16 pm

That's a turbot fish, isn't it?
Lardarse
 
Posts: 106
Joined: 01 July 2005

Postby Lummox JR » Wed Oct 12, 2005 8:16 pm

Yes, it is also a turbot fish. Complete simple coloring eclipses turbot fish and fishy cycles, though, so I don't have occasion to use either of those techniques.
Lummox JR
 
Posts: 125
Joined: 22 September 2005


Return to Advanced solving techniques