We prove the ergodicity of the Wang--Swendsen--Kotecký (WSK) algorithm for the zero-temperature $q$-state Potts antiferromagnet on several classes of lattices on the torus. In particular, the WSK algorithm is ergodic for $q\ge 4$ on any quadrangulation of the torus of girth $\ge 4$. It is also ergodic for $q \ge 5$ (resp. $q \ge 3$) on any Eulerian triangulation of the torus such that one sublattice consists of degree-4 vertices while the other two sublattices induce a quadrangulation of girth $\ge 4$ (resp.~a bipartite quadrangulation) of the torus. These classes include many lattices of interest in statistical mechanics.