  We find exponentially many exact quantum many-body scar states in a
two-dimensional PXP model -- an effective model for a two-dimensional Rydberg
atom array in the nearest-neighbor blockade regime. Such scar states are
remarkably simple valence bond solids despite being at effectively infinite
temperature, and thus strongly violate the eigenstate thermalization
hypothesis. Given a particular boundary condition, such eigenstates have
integer-valued energies. Moreover, certain charge-density-wave initial states
give rise to strong oscillations in the Rydberg excitation density after a
quantum quench and tower-like structures in their overlaps with eigenstates.
