TAOCP 7.2.2.2 Exercise 460
I cannot produce a rigorous TAOCP solution for this exercise from the supplied context alone, because the definition of $\operatorname{sweep}(X)$ from the preceding part of Section 7.
Section 7.2.2.2: Satisfiability
Exercise 460. [21] $[21]$ Given $m$, $n$, $k$, and $r$, construct clauses that are satisfied by an $m \times n$ binary matrix $X = (x_{ij})$ if and only if sweep$(X) \le k$ and $\sum_{i,j} x_{ij} \ge r$.
Verified: no
Solve time: 4m05s
I cannot produce a rigorous TAOCP solution for this exercise from the supplied context alone, because the definition of $\operatorname{sweep}(X)$ from the preceding part of Section 7.2.2.2 is missing.
Exercise 460 depends essentially on the exact meaning of $\operatorname{sweep}(X)$ and on the recurrence established in Exercise 459. The clause construction must encode the states of that recurrence, so the correct auxiliary variables, clauses, and correctness proof depend on details that are not present in the excerpt.
Please provide the paragraph defining $\operatorname{sweep}(X)$, together with the statement or solution context of Exercise 459, and I will write the complete rigorous solution in the requested TAOCP style.