Coloring and accumulated truths

Lummox JR · Posted: Thu Oct 13, 2005 7:13 pm Post subject: Coloring and accumulated truths

In pondering coloring recently, and especially supercoloring, I'd been wondering about methods of finding intersections with more than 2 colors. That is, both complete coloring and supercoloring can make eliminations on the principle that if at least one of a pair of values is true, any placement where they intersect is false.

Today I realized there's a way to formalize a rule for 3+ colors. If a constraint (referring specifically to the columns in DLX) is completely full of colored cells, one and only one of those colors must be true. Therefore, any placement which does not use one of those colors but touches all of them, is false. I call this an accumulated truth, since it handles multiple values whose potential for truth is fractional.

This can be done in a coloring or supercoloring algorithm after other eliminations have been attempted:

1) Loop through all 324 constraints that have not yet been satisfied.
2) If any of the following apply to this constraint, move on to the next constraint:
- An uncolored possibility exists.
- There is only one possibility (single).
- There are only two possibilities (conjugates; already handled).
3) The colors in this constraint are now a set. One and only one of them is true. For convenience we'll call them a, b, c, etc. Loop through all choices for a.
4) Loop through all choices for b.
5) Find intersections of a and b. For every placement in the list, see if it also touches c, d, etc. You can use bit flags for this, or an array.
6) If the placement touched all colors in the set, it is false.

I don't expect this to be very common at all. It should be exceedingly rare in simple coloring, and not terribly common in supercoloring. However it may break deadlocks that otherwise coloring methods couldn't touch.

Nick70 · Posted: Fri Oct 14, 2005 9:50 am Post subject:

What you describe is equivalent to "multiple implication chains", and I had summarily described it when talking about advanced colouring.

But you can do more:

Let's say the only possibilities in a unit are a,b,c.
Also, b excludes d and c excludes d.
Then you can say that every x that excludes a also excludes d.

This should make colouring equivalent to bifurcating implication chains and therefore to tabling.

Lummox JR · Posted: Sat Oct 15, 2005 8:25 pm Post subject:

Quite interesting. I had given a little thought to the idea of "grouped conjugates" but not much. I'm not sure I see the direct equivalence to bifurcating chains, though, unless you assign colors to non-conjugate placements. I know your method does that, although I've found supercoloring easier by hand by not assigning extra colors. I'm also pretty sure this would be wildly difficult to do by hand if those extra colors were involved.

I figure you could develop a whole new notation for this, such as a=!{bc} or A={bc}. To properly exploit set notation for this purpose you'd have to 1) create new colors based on sets, from a group of 2 all the way up to N-1 for any given set, and fill in exclusions from their non-conjugates based on colors that exclude each member of the set. The problem here as I see it though is that keeping track of which groups are conjugates of which could be a problem; each color can be a conjugate of multiple sets, and even each set could have several conjugates based on how frequently it appears in other sets. I think you'd need to go back to using two matrices, one for exclusions and another for conjugacy.

This might be an interesting method for me to implement in my solver, but again I don't think it'll be very useful without the filler colors you use, which would make meaningful output kind of difficult. It might be worthwhile though to add filler colors only in places where a the constraint is already filled with other colors. Still I can't think of a cleaner notation for colors than lowercase and uppercase, and filler colors would probably be more common than originals.

It may be that the set notation still has some uses, though, even when no constraint is completely filled. Logically if a,b,c occur in the same constraint, even if they aren't the only choices, a!{bc} and b!{ac} and c!{ab}. If a,b,c,d all touch, then also {ab}!{cd}, {ac}!{bd}, {ad}!{bc}. I'm sure there's some hay to be made with that; the question is how much.