# What is an efficient algorithm to solve the following combinatorial optimization problem?

I have a combinatorial puzzle to solve. The puzzle has 10 interconnected spots for polyhedral blocks to fill in. The blocks have these attributes:

1. weight,
2. shape (denoted by number of faces, $n_{\rm block} \in [4, 14]$, $n_{\rm block}=4$ is a tetrahedron, $n_{\rm block}=5$ is a pentahedron etc.),
3. a rank number printed on the blocks,
4. color, and
5. material.

None of these attributes are unique, there might be more than one blocks with the same attributes.

The slots are marked with a number $n_{\rm slot}$. Any block can be put in any slot, one slot can hold only one block. A solution must have all the slots filled in. There is a goodness score of a solution. If a block is put into a slot it receives a score $10 - |n_{\rm block} - n_{\rm slot}|$. After all the slots are filled, extra score is added to each block depending on the neighboring blocks. For each neighboring blocks matching both color and material, a block gets +3 score; for each neighboring blocks with either matching color or material, a block gets +1.5 score; for a non-matching neighbor no point is added. The total goodness score of the solution is the sum of all the blocks' scores. Now a solution has to satisfy the two following constraints.

1. a minimum goodness score
2. a minimum average rank number (average of the rank numbers of all the blocks)

The inputs of the problem are:

1. The map of the connected slots showing which slots are inter-connected,
2. A list of available blocks with all of their attributes (5000~15000 blocks)
3. Minimum goodness score necessary
4. Minimum average rank necessary

The output of the problem is:

A solution with the lowest total weight of all the blocks.

If finding the lowest-weight-solution is not feasible within 10-15 minutes in Python, a good enough solution with total weight lower than a specified budget can be a plan B.

• Interesting question. Have you tried integer linear programming or simulated annealing? How many different colors are there? How many materials? What's the range of values for $n_\text{block}$ and $n_\text{slot}$? Are they in the range 1-10? – D.W. Oct 2 '17 at 14:26
• There is not fixed number of colors or material types, they can be as many as 100. $n_{\rm block}$ and $n_{\rm slot}$ are between 4 and 14. I haven't tried any approach that you have mentioned. The only way I could think about was brute forcing through recursion, but that would just take too much time. – Silent Sabreur Oct 2 '17 at 14:48