An Algorithmic Puzzle

I think this works:

rg rg gr gb gg bg bg gr rb rr bb br br rb gb
bg gr bb gr rb rr br br rg gb rg rb gg gb bg
br bb rg br br gb rg gb gb gb rg gg br rg rr


I write a quick python script to do this by brute force - it finds a maximal independent set greedily, checks if it's got 15 elements, then discards it, shuffles the candidates, and tries again until it finds the maximum set. I put the code online here: http://paste.pocoo.org/show/271098/ in case you'd like to look at it.

There are certainly multiple solutions - you can, for example, take the three that have the same color for the bottom two and cycle the colors of the other four circles to get two other solutions that are almost the same. Running the program repeatedly is likely to generate different solutions.

Your problem is related to sudoku, but harder - it reduces to the Maximum Independent Set problem, which is a known NP-Complete problem (meaning that in general there are no known fast algorithms for solving it). Sudoku, by contast, can be solved in time polynomial in the size of the grid.

I retract what I said about this being NP-complete - my proof was flawed.

While you can treat this as an instance of the Maximum Independent Set problem, which is NP-complete, there's more structure to your problem and this admits several faster techniques.

One is to do what ichbin did - divide the 15 basic tiles into five groups of three such that each tile appears once and each group has no mutually overlapping tiles. You can then color each group in three different ways (r,g,b; g,b,r; b,r,g) and you'll get a solution. Then you just need to solve Independent Set on the 15-node grid; even that is very structured and I'm pretty sure there's a quick solution.

You actually have far fewer possibilities than you think unless something on the cards orients them in a specific way.

There are actually only 8 possibilities, as the 2x3 unit area has rotational symmetry. In your illustration, the first 7 of the filled-in areas is exactly the same as the last 7 if you turn the cards upside-down (with the 8th being the illustration where the 2 units in the center row are colored).

Yes, you would only need 8 cards to establish all patterns without redundancy, and there would be exactly 16 distinct solutions. (for a total of 128 cards in 16 sets of 8).

How can there be exactly 16 solutions? For any solution, you can permute the colors (e.g. replace red with green, green with blue, and blue with red) six different ways to get different solutions; it follows that the number of solutions should be a multiple of six.

There are 48 distinct cards that could be made...

The number of distinct combinations of 8 cards that fulfill the criteria of those 48 cards is somewhere in the neighborhood of 124,000.