Filling a rectangle with 0/1 (constraints on columns/lines sums)

82 Views Asked by At

Let's consider a $n \times m$ rectangle wich has to be filled in by $0$s and $1$s. The sum of the values contained in each colum/line is known. Here is an example:

enter image description here

This is a solution:

enter image description here

Does someone know if this problem has a name (it looks like magic square)? I'm especially interested in the uniqueness (up to permutation of the columns) of the solution (if it exists): are there conditions that can enforce it?

1

There are 1 best solutions below

0
On

Essentially this is the Discrete Tomography problem.

The problem in general is hard. Yan Gerard has proved that the problem of rearranging the known integer entries of a matrix to satisfy known sums of rows and columns is a NP-hard problem.

I don't know if it is easier of $\{0,1\}$.