# Theoretical Puzzle

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
-
No. Consider the 2x2 grid where all rows and columns contain one "1" value. This has two possible solutions. In general, the closer a count is to n/2, the less information it gives. –  qaphla Aug 18 '14 at 22:43
Well, in that case, supplying the diagonal counts would help; you would know on which diagonal to put the "1"s. That's true about the counts being less informative as they approach n/2 though. –  KevinOrr Aug 18 '14 at 22:51
@qaphla Sorry, I forgot to mention you –  KevinOrr Aug 18 '14 at 22:59
Diagonal count (consisting of just the two major diagonals) still wont be enough. For example in the following 4x4: 1 0 0 0, 0 1 0 0, 0 0 0 1, 0 0 1 0 and 0 1 0 0, 1 0 0 0, 0 0 0 1, 0 0 1 0 both have row counts 1 1 1 1, column counts 1 1 1 1, and diagonal counts 2 0 –  Penguino Aug 18 '14 at 23:04
@Penguino wouldn't that second one's diagonals be 0,0? But I can understand how it could conflict with other boards even given the diagonals. What if all the diagonals are given, not just the major ones? –  KevinOrr Aug 18 '14 at 23:15

## 2 Answers

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 C(2n,n) = (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 teh 2x(2n) array as described above. But I don't think they are enough for arrays with more rows.

To confirm that. Just consider mxm 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 ~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*sqrt((m^2)/2)])^4 . i.e. it grows approximately as exp(m).

But the number of possible arrays of that form grows as ~ C(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 ~exp(m^2), which is much faster than the possible combinations of row/col/diag numbers which only grows as ~exp(m), and that won't be enough information to uniquely identify the array.

-
Oh true. I forgot that there's a whole lot less info in the counts than in the grid. Thanks! –  KevinOrr Aug 21 '14 at 2:32

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.

-
I'm not entirely certain this answers/addresses the original question of the OP: "What extra information can I give you so that you can solve, with certainty, any sized board?" –  Emrakul Aug 23 '14 at 20:30
@Emrakul this is more of a long comment than a direct answer. I posted this after the first answer was accepted just as a reference to related material. :) –  Memming Aug 24 '14 at 12:43
One answer to "what extra information can I give you..." would be to provide the coordinates of each point in the board or a 'compressed' jpeg-like version of that information - but this information grows as n^2. In practice, the number of possible boards grows as exp(n^2), so any edge information that grew at a slower rate, for example a fixed number of data points per row or column (or even a number of data points per row/column that grew at n^k, where k < 1), will probably be insufficient. –  Penguino Aug 24 '14 at 22:49