5
$\begingroup$

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
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – qaphla
    Aug 18, 2014 at 22:43
  • $\begingroup$ 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. $\endgroup$
    – KevinOrr
    Aug 18, 2014 at 22:51
  • $\begingroup$ @qaphla Sorry, I forgot to mention you $\endgroup$
    – KevinOrr
    Aug 18, 2014 at 22:59
  • $\begingroup$ 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 $\endgroup$
    – Penguino
    Aug 18, 2014 at 23:04
  • $\begingroup$ @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? $\endgroup$
    – KevinOrr
    Aug 18, 2014 at 23:15

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Oh true. I forgot that there's a whole lot less info in the counts than in the grid. Thanks! $\endgroup$
    – KevinOrr
    Aug 21, 2014 at 2:32
0
$\begingroup$

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.

enter image description here

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

$\endgroup$
3
  • $\begingroup$ 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?" $\endgroup$
    – user20
    Aug 23, 2014 at 20:30
  • $\begingroup$ @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. :) $\endgroup$
    – Memming
    Aug 24, 2014 at 12:43
  • $\begingroup$ 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. $\endgroup$
    – Penguino
    Aug 24, 2014 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.