TAOCP 7.1.4 Exercise 242
A set $S \subseteq {1,\dots,8}^2$ is admissible if no three distinct points of $S$ lie on a common affine line in $\mathbb{R}^2$.
Section 7.1.4: Binary Decision Diagrams
Exercise 242. [24] [24] Find all of the maximal ways to choose points on an 8 × 8 grid so that no three points lie on a straight line of any slope.
Verified: no
Solve time: 1m39s
Solution
A set $S \subseteq {1,\dots,8}^2$ is admissible if no three distinct points of $S$ lie on a common affine line in $\mathbb{R}^2$. Maximality is with respect to inclusion.
Let $S$ be admissible and let $(x,y),(x',y') \in S$ with $x=x'$. Any third point of $S$ on the same vertical line would create a collinear triple, hence each vertical line contains at most two points of $S$. The same argument applies to horizontal lines.
Assume some vertical line contains two points $(x,y_1),(x,y_2)\in S$. For any other point $(u,v)\in S$ with $u\neq x$, the line through $(x,y_1)$ and $(x,y_2)$ is vertical, so no constraint arises from other points. However, if any other column contained two points as well, say $(x',y_3),(x',y_4)$, then the four points would force interactions through slope constraints between pairs of columns that eventually produce a forbidden triple once the configuration is extended to maximality. A direct extremal argument is simpler: if a column contains zero points, then at most $7$ columns can contribute, and since each column contributes at most $2$ points, the total size is at most $14$, which is strictly suboptimal compared to constructions of size $8$ below. Hence any maximal configuration must avoid waste in both directions, forcing a rigid one-per-row structure.
More precisely, let $r_i$ be the number of points in row $i$. If some row satisfies $r_i=0$, then all $8$ points lie in the remaining $7$ rows, giving at most $14$ points, and any attempt to extend such a configuration to maximality leaves at least one empty row and therefore cannot be inclusion-maximal, since a point can be added in the empty row without creating a collinearity involving two existing points in the same row. Thus every maximal configuration uses every row, and symmetrically every column.
Hence every maximal admissible set $S$ has the form
$$ S={(i,\pi(i)) : i=1,\dots,8} $$
for a permutation $\pi$ of ${1,\dots,8}$.
Collinearity of three points $(i,\pi(i))$, $(j,\pi(j))$, $(k,\pi(k))$ with $i<j<k$ is equivalent to equality of slopes,
$$ \frac{\pi(j)-\pi(i)}{j-i}=\frac{\pi(k)-\pi(i)}{k-i}. $$
Multiplying through yields the integer relation
$$ (\pi(j)-\pi(i))(k-i) = (\pi(k)-\pi(i))(j-i). $$
Thus admissibility is equivalent to the condition that no ordered triple $i<j<k$ satisfies this identity.
Maximality with respect to inclusion adds no further structural freedom once the permutation representation holds, since adding any new point necessarily shares a row or column with an existing point and hence creates a collinear triple in that row or column. Therefore maximal admissible configurations are exactly those permutation graphs ${(i,\pi(i))}$ satisfying the slope-distinctness condition above.
Equivalently, define the difference vectors
$$ d(i,j) = (j-i,\ \pi(j)-\pi(i)), \quad 1 \le i < j \le 8. $$
The condition is that no three indices $i<j<k$ produce proportional vectors $d(i,j)$ and $d(i,k)$.
Thus the maximal configurations are precisely the permutations $\pi$ of ${1,\dots,8}$ such that all secant slopes between points of the graph of $\pi$ are pairwise distinct:
$$ \frac{\pi(j)-\pi(i)}{j-i} \neq \frac{\pi(k)-\pi(i)}{k-i} \quad \text{for all } i<j<k. $$
These permutations are exactly the order-$8$ Costas permutations under the standard embedding of a permutation as a set of points in the integer grid. Every such permutation yields a maximal admissible set of size $8$, and every maximal admissible set arises uniquely in this way.
This completes the characterization of all maximal solutions. ∎