  We present exact calculations of the zero-temperature partition function
(chromatic polynomial) and $W(q)$, the exponent of the ground-state entropy,
for the $q$-state Potts antiferromagnet with next-nearest-neighbor spin-spin
couplings on square lattice strips, of width $L_y=3$ and $L_y=4$ vertices and
arbitrarily great length $L_x$ vertices, with both free and periodic boundary
conditions. The resultant values of $W$ for a range of physical $q$ values are
compared with each other and with the values for the full 2D lattice. These
results give insight into the effect of such non-nearest neighbor couplings on
the ground state entropy. We show that the $q=2$ (Ising) and $q=4$ Potts
antiferromagnets have zero-temperature critical points on the $L_x \to \infty$
limits of the strips that we study. With the generalization of $q$ from
${\mathbb Z}_+$ to ${\mathbb C}$, we determine the analytic structure of $W(q)$
in the $q$ plane for the various cases.
