Theoretical Puzzle: Making a binary puzzle with a unique solution

Question

If I have a table of binary values, and tell you the column and row counts for "on" or "1" values, is it possible to solve, with certainty, any grid of size n*m?

Take the following puzzle for example:

   | 4 | 5 | 3 | 2 | 1
---|---|---|---|---|---
 3 | ? | ? | ? | ? | ?
 2 | ? | ? | ? | ? | ?
 3 | ? | ? | ? | ? | ?
 3 | ? | ? | ? | ? | ?
 4 | ? | ? | ? | ? | ?

1 possible solution is:

   | 4 | 5 | 3 | 2 | 1
---|---|---|---|---|---
 3 | 1 | 1 | 1 | 0 | 0
 2 | 0 | 1 | 0 | 1 | 0
 3 | 1 | 1 | 0 | 1 | 0
 3 | 1 | 1 | 1 | 0 | 0
 4 | 1 | 1 | 1 | 0 | 1

The only problem is that there could be (and likely are) more than 1 solution. What extra information can I give you so that you can solve, with certainty, any sized board?

Some examples of extra info are:

• Diagonal counts
• 1 count for even indices per value in a row or collumn, and 1 count for odd indices

Answer 1

Clearly the column and row counts alone isn't enough. Consider a 2x(2n) array (2 rows of 2xn columns) as described below:

Using A = |1|, B = |0|, build the array by randomly ordering n of each of A and B 
          |0|      |1|                                          

Each possible array will have identical column and row counts:

   | 1 | 1 | 1 | ... | 1 | 1 |
---|---|---|---| ... |---|---|
 n | 0 | 1 | 1 | ... | 0 | 1 |
 n | 1 | 0 | 0 | ... | 1 | 0 |

But there are $\binom{2n}{n} = \frac{(2n)!}{(n!)^2}$ different such arrays.

This function grows fairly fast (first few values are 1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620, 184756, 705432, 2704156, 10400600, 40116600, 155117520, 601080390, 2333606220, 9075135300, 35345263800, 137846528820, 538257874440, 2104098963720,...) so you would need to add a lot more information to uniquely identify any such array. If you add more rows the problem only gets worse.

In answer to KevinOrr's question, all diagonals will be sufficient to solve for the 2x(2n) array as described above. But I don't think they are enough for arrays with more rows.

To confirm that. Just consider $m \times m$ arrays with half of the elements set. So there will be $(m^2)/2$ set elements. The row count will consist of m integers that add to $(m^2)/2$, as will the column count and each of the two sets of TL-BR and TR-BL diagonal counts will be $2m$ elements with the same sum. Each of these counts is a partition of the number $(m^2)/2$, for example see http://en.wikipedia.org/wiki/Partition_(number_theory), broken into m parts for the row and column or 2m parts for the diagonal counts.

The number of possible partitions of n elements grows as $\sim\exp[c \sqrt n]$ (for some constant c) and this is strictly greater than the number of partitions into some fixed k parts.

So the number of possible row,column plus diagonal partitions for the mxm problem (with $(m^2)/2$ elements set) is less than $(\exp[c\times\sqrt{(m^2)/2}])^4$ . i.e. it grows approximately as $exp(m)$.

But the number of possible arrays of that form grows as $\sim\binom{m^2}{(m^2)/2}$ which, if you 'solve' using Sterling's approximation, seems to grow approximately as $2^{m^2}$ or $\exp[m^2]$.

So possible arrays grows as $\sim\exp(m^2)$, which is much faster than the possible combinations of row/col/diagonal numbers which only grows as $\sim\exp(m)$, and that won't be enough information to uniquely identify the array.

Answer 2

A more general form of this puzzle is known as Nonogram or Nemo-Nemo-logic where the consecutive number of 1's is known for each column and row. Even in this form, there are often ambiguities and one is encouraged show the uniqueness of the solution before making a new puzzle available in public.

from: http://japonskie.ru/pics/full/krolik_1.gif