# Finding redundant constraints

I'm looking for an algorithm or a way to formalize my problem and be able to solve it. Not sure what kind of mathematics this should be categorized as.

Let's assume we have some tiles marked with colors:

Take two (or more) of them (perhaps the same one) and put them next to eachother, sliding one or the other up/down by whole rows. We say that the tiles have a valid placement if a single row does not contain the same color more than once.

For example, take two tiles {2, 2} and put them side by side like in the picture below.

Here all but the leftmost placement is valid. The leftmost placement is not valid because each of these separately:

1. There are two blue squares in the top row. (blue conflict)
2. There are two red square in the second row. (red conflict)

In this case, this is the only way to have an invalid placement of {2, 2}. Since there is no way to have a blue conflict without having a red conflict, we say that blue is redundant. That is, by avoiding red conflicts we automatically avoid blue conflicts. In reverse, red is also redundant when placing {2, 2}.

Let's try placing {4, 5}:

From left to right:

1. Not valid (red and blue conflict)
2. Not valid (red and blue conflict)
3. Valid (No conflict)
4. Not valid (red conflict)
5. Valid (No conflict)

If we guarantee no red conflict, then we implicitly will have no blue conflict. So for this set of tiles ({4, 5}) blue is redundant. Red is however not redundant because there is a way to place the tiles and get a red conflict without a blue conflict.

## The question:

Given a set of tiles how can I decide which colors are redundant? What kind of mathematics can I use? Do I have to fall back on some kind of exhaustive search?

• I'm not sure of what you are trying to achieve. Are you asking, given two tiles, all the possible correct placement of this two tiles? or given two placed tiles is the placement correct? or given 2 placed tiles what are the row where there is a problem? Also what do you mean by "What kind of mathematics can I use?". Are you asking for a formal representation of your tiles? – wece Oct 14 '16 at 7:47
• Neither, I'm asking how I canfind out which colors are redundant. Consider all non-valid placements of the two tiles. Consider why they are non-valid. Is (at least one of) the reasons always because of red? Then blue is redundant. But how can I figure out that blue is redundant without exhaustive testing? – Moberg Oct 15 '16 at 11:57
• Maybe I should formulate it like this: By satisfying the constraint on the red color in the second example ({4, 5}), the blue constraint is automatically satisfied. Thats when we call the blue constraint redundant. How can I find out whether a constraint is redundant? – Moberg Oct 15 '16 at 12:05
• My intuition is that you have to fall back on some kind of exhaustive search. – wece Oct 17 '16 at 9:55

Let say you have 2 tiles $T_1$ and $T_2$, with some marks on them given by sets $B_1,R_1,B_2,R_2\subset\{1,2,3,4\}$ (positions of the marks)

Let $f(x,y)=x-y$

Define sets $B=f(B_1\times B_2)$ and $R=f(R_1\times R_2)$ => $B,R\subset\{0,1,2,3,-1,-2,-3\}$

So you have $B\subset R <=>$blue is redundant

$R\subset B <=>$red is redundant