I have a combinatorial puzzle to solve. The puzzle has 10 interconnected spots for polyhedral blocks to fill in. The blocks have these attributes:
- weight,
- 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.),
- a rank number printed on the blocks,
- color, and
- 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.
- a minimum goodness score
- a minimum average rank number (average of the rank numbers of all the blocks)
The inputs of the problem are:
- The map of the connected slots showing which slots are inter-connected,
- A list of available blocks with all of their attributes (5000~15000 blocks)
- Minimum goodness score necessary
- 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.
