TAOCP 7.2.2.2 Exercise 105
The parts that can be derived directly are as follows.
Section 7.2.2.2: Satisfiability
Exercise 105. ▶ [M28] [M28] A matrix whose entries are ${-1, 0, +1}$ is tomographically balanced if its row, column, and diagonal sums are all zero. Two binary images $X = (x_{ij})$ and $X' = (x'_{ij})$ clearly have the same row, column, and diagonal sums if and only if $X - X'$ is tomographically balanced.
a) Suppose $Y$ is tomographically balanced and has $m$ rows, $n$ columns, and $t$ occurrences of $+1$. How many $m \times n$ binary matrices $X$ and $X'$ satisfy $X - X' = Y$?
b) Express the condition "$Y$ is tomographically balanced" in terms of clauses, with the values ${-1, 0, +1}$ represented respectively by the 2-bit codes ${10, 00, 01}$.
c) Count the number of $n \times n$ tomographically balanced matrices, for $m, n \le 8$.
d) How many such matrices have exactly four occurrences of $+1$?
e) At most how many $+1$s can a $2n \times 2n$ tomographically balanced matrix have?
f) True or false: The positions of the $+1$s determine the positions of the $-1$s.
Verified: no
Solve time: 5m46s
The parts that can be derived directly are as follows.
For part (a), let $Y=(y_{ij})$. If $y_{ij}=+1$, then necessarily
$$ (x_{ij},x'_{ij})=(1,0), $$
and if $y_{ij}=-1$, then necessarily
$$ (x_{ij},x'_{ij})=(0,1). $$
If $y_{ij}=0$, then the two entries must agree, giving the two possibilities
$$ (0,0),\qquad (1,1). $$
Because every row sum of $Y$ is zero, the number of $+1$'s equals the number of $-1$'s. Hence if there are $t$ occurrences of $+1$, there are also $t$ occurrences of $-1$, and therefore
$$ mn-2t $$
zero entries. Each zero entry contributes an independent factor of $2$, so the number of ordered pairs $(X,X')$ is
$$ \boxed{2^{mn-2t}} . $$
For part (b), introduce two Boolean variables for every entry:
$$ y_{ij}= -1,0,+1 $$
are encoded respectively by
$$ 10,\qquad 00,\qquad 01 . $$
Let the two bits be $u_{ij},v_{ij}$. The code restrictions are
$$ (u_{ij},v_{ij})\neq (1,1), $$
so every cell contributes the clause
$$ \boxed{\neg u_{ij}\lor \neg v_{ij}} . $$
The value of the cell is $v_{ij}-u_{ij}$. Therefore every row, column, and diagonal constraint is an equality of two cardinalities:
$$ \sum v_{ij}=\sum u_{ij} $$
over the cells belonging to that line. These equalities can be converted into clauses by the standard cardinality encoding: for each line $L$,
$$ \sum_{(i,j)\in L}v_{ij}-\sum_{(i,j)\in L}u_{ij}=0 $$
is encoded as the conjunction of clauses forbidding every assignment whose number of $01$ codes differs from the number of $10$ codes. Thus the complete CNF consists of the cell clauses above together with these clauses for all rows, columns, and both diagonal families.
Parts (c) and (d) require an explicit enumeration of the solutions of this constraint system. A direct exhaustive search is not practical without implementing the SAT/counting computation requested by the exercise. The necessary computation is to enumerate all assignments to the $2mn$ Boolean variables satisfying the balance clauses, and then count the resulting ${-1,0,+1}$-matrices. The same enumeration with an additional cardinality constraint on the $+1$ variables gives part (d).
For part (f), the statement is false. Knowing the positions of the $+1$'s only specifies one binary image $P$. The positions of the $-1$'s form another binary image $N$ with the same row, column, and diagonal sums as $P$, but discrete tomography does not in general give uniqueness. Hence two different placements of the $-1$'s can produce the same projections. Therefore
$$ \boxed{\text{False}.} $$
A complete answer to parts (c), (d), and (e) requires the missing enumeration results or a reproducible computation of them. I cannot supply those numerical values without risking giving incorrect data.