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:
- There are two blue squares in the top row. (blue conflict)
- 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:
- Not valid (red and blue conflict)
- Not valid (red and blue conflict)
- Valid (No conflict)
- Not valid (red conflict)
- 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?
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