While trying to find a bijection which preserves various combinatorial statistics, I was led to the problem below. Very much to my surprise, a closely related question, Coloring summands of given n-partition with given weights of colors, was asked here almost the same day I stumbled across the problem.

I have a number of boxes, each with a number of items in it, and a number of coloured tags. The total number of items equals the total number of coloured tags.

Essentially, Coloring summands of given n-partition with given weights of colors asks how to find the number of possibilities to assign the tags to the items, such that the items in one box all have the same colour.

I have to consider the following variant: each item has additionally a number written on it and so has each coloured tag.

I am in need of a reasonably efficient algorithm that decides whether one can assign the tags to the items in the boxes, such that

- the number on the tag and on the item is always the same, and
- the items in one box all have the same colour.

I am currently stuck with an instance of the problem that has roughly 350 boxes with a total of roughly 2800 items. The numbers on the tags range from 1 to 8 and there are 4 different colours.

Examples:

Suppose we have 4 boxes with items numbered either 1 or 2: \begin{array}{ccc} 1&1&1,\\ 1&1&2,\\ 1&2,&\\ 2&2.& \end{array} and colour tags blue with numbers 1,1,2,2,2 and red with numbers 1,1,1,1,2. Then there is a unique way to colour the boxes: first and last box red.

If the colour tags are blue with numbers 1,1,1,2,2 and red with numbers 1,1,1,2,2 then there are two ways to colour the boxes.

EDIT:

To facilitate playing with the problem, here is some python/sage code, including some examples, and the instance I am stuck with. I'll award the bounty to any presenter of an algorithm which yields a colouring in reasonable time (or proves that no such colouring exists)...

NEXT EDIT:

I discovered that it makes a huge difference in which order the colours are tried. The most natural heuristic is to try colours which have tags for all numbers still available first. The linked file reflects this finding.

ANOTHER EDIT:

A possibly helpful observation is that in the problematic instance, any box contains either 2 items, 4 items or 8 items. More precisely: there are 2 distinct boxes with 2 items, 11 distinct boxes with 4 items, the remaining boxes contain 8 items. Is there an obvious way to take advantage of this?

Is there any strategy to show that no solution exists?

1more comments