Reconstructing a data table from cross-tabulation frequencies
We have $M$ columns $C_1, \dots, C_M$ in the original table, each with a finite set of distinct values $V_1, \dots, V_M$.

Given the cross-table frequencies $c_{i,j}(a,b)$ (frequency of $a$ in $V_i$ and $b$ in $V_j$ occurring together), proceed as follows:


Determine $V_1, \dots, V_M$ and denote $V_i = \{v^{(i)}_j \mid j \in [1,n_i] \}$ where $n_i = |V_i|$.
Solve the following integer program:

$\qquad\displaystyle \min \sum_{i_1 = 1}^{n_1} \cdots \sum_{i_M = 1}^{n_M} x_{(i_1,\dots,i_M)} \\
     \qquad \begin{align}
       \text{s.t. } \sum_{i_1 = 1}^{n_1} \cdots \sum_{i_{l-1} = 1}^{n_{l-1}} \sum_{i_{l+1} = 1}^{n_{l+1}} \cdots \sum_{i_{r-1} = 1}^{n_{r-1}} \sum_{i_{r+1}  1}^{n_{r+1}} \cdots \sum_{i_M = 1}^{n_M} x_{(i_1, \dots, i_M)} &amp;= c_{(l,r)}(i_l,i_r) \\
       \qquad \text{for all } 
       1 \leq l &lt; r \leq M, i_l \in [1,n_l], i_r \in [1,n_r], \\
       x_{(i_1, \dots, i_M)} &amp;\in \mathbb{N} \\
       \qquad \text{for all } i_1 \in [1,n_1], \dots, i_M \in [1,n_M] 
     \end{align}$


The $x_{(i_1, \dots, i_M)}$ now indicate which row should occur how often, and we get a solution with the minimum number of rows possible. If we can influence the search, we can abort as soon as we find any feasible solution.

This is not likely to be efficient, but there are honed solvers for integer programs around so it's simple to implement. It may be possible to use an LP-solver and round to a feasible solution.