Equally coloring the edges of square tiles that form a grid

Question

I need to generate a set of square tiles that are colored and are grid-able. Each square tile must have a unique set of 4 colors and each exterior edge of each tile is colored with a different color. There are 8 colors, so that leaves us with 8 choose 4 (70) tiles.

In order for these tiles to be placed into a grid, orthogonal tile edges must share a matching color. For example, if we look at just four square tiles in a 2x2 grid, the right edge of the top left tile must be the same color as the left edge of the top right tile. Additionally, the top edge of the bottom left tile must be the same color as the bottom edge of the top left tile. Most importantly, to place the bottom right tile, it must match the bottom of the top right tile AND the right of the bottom left tile. This gives a lot of importance to the pairs of coloring on consecutive edges of a tile.

If we ignore rotation (0, 90, 180, 270), there are only 6 ways to color each specific tile given the unique set of four colors derived above from the 8 choose 4 combinatorics. So if we color a tile with red on the top and move clockwise with green, yellow and blue, we end up with the following four colored edge pairs relating to each corner: red|green, green|yellow, yellow|blue, and blue|red. Because order matters for each corner when we place in a grid and we started with 8 colors, there are 8 * 7 (56) colored edge pairs possible.

The question is the following: Is it possible to color all 70 tiles in such a way that all 56 colored edge pairs are equally distributed? Since each tile generates 4 color pairs and there are 70 tiles, this generates 280 color pairs. Dividing by the 56 unique colored pairs possible would leave us with 5 colored edge pairs for each two color combination. Apologies if this is a known and solved problem but my searches have not yielded an answer or good approach to solving this. It is also possible that this is NP and may only be approached by approximations. I have written a solver that uses a Las Vegas algorithm approach with different heuristics. It has gotten close but is not completely balanced. I'd be grateful for any pointers or knowledge about this type of problem.

Answer 1

I would suggest you try to search for a coloring using a SAT solver or ILP solver.

To solve with an ILP solver: use zero-or-one (boolean) variables $x_{i,j}$, where $x_{i,j}=1$ means that the $i$th tile is colored with the $j$th of the 6 possibilities. This gives you $70 \times 6 = 420$ variables. Next, for each colored edge pair $p$, add a linear equality constraint $\sum x_{i,j} = 5$, where the sum is over all $(i,j)$ that correspond to a tile coloring that contains the colored edge pair $p$. Also, for each $i$, add the constraint $\sum_j x_{i,j} = 1$. Ask the ILP solver whether it can find feasible solution.

Alternatively, you could use a SAT solver. You'll need to use 1-out-of-n and 5-out-of-n constraints; see Encoding 1-out-of-n constraint for SAT solvers and Reduce the following problem to SAT and Can a propositional threshold connective be expressed by standard connectives? and Recipe book for SAT encodings? for methods, or use a solver like Z3 that has built-in support for these kinds of constraints (sometimes called pseudo-boolean constraints).