Fast way to get bitmask for delivery to all devices

Question

I have a list of devices and a bitmask of channels they are on (channels are numbered 0..3). There can be up to 256 devices.

For example:

Device1: 1 0 0 1 (on channels 0, 3)
Device2: 0 1 1 0 (on channels 1, 2)
Device3: 1 1 0 0 (on channels 2, 3)

I need to find a bitmask of channels which will result in the message to be received by all devices with a fewest possible unnecessary messages.

Correct result bitmasks for example data are 1 0 1 0 (channel 1 delivers to Device2 and channel 3 to Device1 and Device3) and 0 1 0 1 (channel 0 delivers to Device1 and channel 2 to Device2 and Device3), either one of them is OK.

Result bitmask 1 1 0 0 would be bad because Device3 would get the message twice.

Answer 1

Since there may not be a perfect solution and we only have 16 possibilities for the result I would just use a brute force approach and iterate through all 16 possible masks, and see which one(s) is/are optimal (minimum number of repeated messages).

Answer 2

Take a look at backtrack search.

Answer 3

You could add the number of 1's in each column to find out how many "receptions" will occur for a message on that channel. That way for any valid mask (that reaches all devices) you can easily add up the total number of messages received by all devices. You can then brute force all 16 possible masks seeing which ones will actually work and choosing the one that both works and has the lowest total number of receptions. Getting around the brute-force part is going to require operations on the entire matrix.

Oddly, if you actually had 256 devices you'd probably have to send on all channels anyway.