What kind of coloring is this?

Lummox JR · Posted: Wed Sep 28, 2005 8:25 pm Post subject: What kind of coloring is this?

I've been using a technique that's new to me, an advanced extension of coloring, but from what I've been reading I have yet to find a name for this method. I've been calling it multicoloring on the assumption that someone would have to have found this technique already, and it's clearly not the same as ultracoloring (which is also called supercoloring, is it not?).

Basically I was pondering coloring and thinking that I could extend conjugates into the 3rd dimension (or rather the 4th, when you consider the box constraint in sudoku). Instead of coloring for a single digit I'd color them all. Then of course I'd compute full transitivity (which my simple coloring algorithm doesn't even do, settling instead for finding just basic paired weak links) because the number of colors would be higher. With this method I should be able to make inferences such as: Either (1,5)=1 or (4,5)=7; therefore (1,5)<>7 and (4,5)<>1.

After finally implementing this in my solver I found that it's most common for a color to be eliminated rather than for conjugates to eliminate an intersecting cell. This method seems to solve about 2/3 to 3/4 of the puzzles that my solver--which does not implement forcing chains or Nishio--had deemed unsolvable with its previous set of methods. As for the remaining boards, usually Nishio alone won't solve them, but more advanced methods of the trial and error set will. (Ultracoloring may also work.)

The nice thing about this method is that it can be done by hand. The main thing is that you need to be sure to place all conjugates and find the implications for each. Usually a contradiction will jump right out at you, but sometimes it requires some tricks with transitivity. However this technique seems to be limited to boards where a lot of conjugates exist, either in houses or in cell candidates. Because it operates best where cells with only 2 candidates exist, I also realized this is a superset of forcing chains.

I've also finally realized that the one thing that keeps fishy cycles from being a form of coloring is a certain kind of transitive subset. That is, if you use coloring and deduce that for each of a set of colors, they imply all the others in that set but nothing else, you can consider them to be the same color, and likewise all their conjugates are the same. This rule I haven't yet implemented, and I'm wondering if it will further improve the results of this 4D coloring algorithm.

I'm sure something like this has to have been done before, but what is it called? From what I've read on multicoloring, that seems to be something else.

AMcK

Lummox JR · Posted: Sun Oct 02, 2005 2:50 am Post subject:

On the player's forum Jeff seems to be of the opinion that this should be called advanced coloring, so I guess we'll go with that.

Over there I've also been honing the technique. If you use Nick70's method of just marking exclusions and propagating using the rule ex(x,y) + ex(y^1,z) -> ex(x,z), then you can make another interesting leap which also applies to simple coloring. If colors a and A are conjugates, b and B, and so on, and a excludes b (a!b), then you can say that since a and b cannot both be true, at least one of A or B must be true. Any placement which intersects A and B is invalid.

Jeff posted one grid where using advanced coloring I actually found two cases that could have been handled this way with simple coloring. Observe this layout in the 7's:

DHallman · Posted: Mon Oct 03, 2005 1:21 am Post subject: colors

Lummox JR · Posted: Mon Oct 03, 2005 5:15 am Post subject:

Indeed this does simplify many puzzles, and it makes coloring dominant over fishy cycles. Nick70's concept of using exclusions is listed more thoroughly here, but he never made mention of using the conjugates of mutually exclusive colors. I'm wondering now if I'm the first person to have stumbled onto this or if someone else had picked it up before now.

Scott H · Posted: Mon Oct 03, 2005 8:53 am Post subject:

Lummox JR · Posted: Mon Oct 03, 2005 7:29 pm Post subject:

Yes, it can also be found by turbot fish. However turbot fish is really just a subset of coloring when using this exclusion rule, just as fishy cycles is. I don't even bother with it.

Interestingly, aside from coloring being a superset of fishy cycles, I've also realized that it supercedes Nishio as well. Andrew appeared to be onto that track when he realized that supercoloring covers Nishio, but in fact simple coloring using this exclusion rule will work as well.

I really think this is the first time that simple coloring has been extended so far, in that it uses some of the rules of supercoloring--albeit differently--for a single color. And with coloring extended this far, it catches turbot fish and fishy cycles easily. You don't have to assign dummy colors for non-conjugates, although this may be a good way to handle it in a program.

And I found an answer to my question in my previous post: The "conjugates of mutually exclusive colors" rule was already in used, but formalized in a very different way, in supercoloring. Once I realized that, I realized colors were only being assigned to non-conjugate choices as a filler for applying this rule; in other words, the advanced coloring I posted in this thread is identical to supercoloring; it just uses a slightly different route to reach its conclusions. Previously, I don't think anybody ever said "Any placement that intersects the conjugates of two mutually exclusive choices must be false." With Nick's observation rephrased in this way, though, it's clear that it applies very well to simple coloring, so much so that I think the use of this method should be called "complete simple coloring".

Lummox JR · Posted: Thu Oct 06, 2005 2:40 am Post subject:

Well, another charming theory bites the dust. Supercoloring may still supercede Nishio, but complete simple coloring does not. The proof is here:

rkral · Posted: Sun Jan 01, 2006 12:03 pm Post subject: