  We obtain a correspondence between pairs of $N\times N$ orthogonal Latin
squares and pairs of disconnected maximal cliques in the derangement graph with
$N$ symbols. Motivated by methods in spectral clustering, we also obtain
modular conditions on fixed point counts of certain permutation sums for the
existence of collections of mutually disconnected maximal cliques. We use these
modular obstructions to analyze the structure of maximal cliques in $X_N$ for
small values of $N$. We culminate in a short, elementary proof of the
nonexistence of a solution to Euler's $36$ Officer Problem.
