  We consider one dimensional block cellular automata, where the local update
rules are given by Yang-Baxter maps, which are set theoretical solutions of the
Yang-Baxter equations. We show that such systems are superintegrable: they
possess an exponentially large set of conserved local charges, such that the
charge densities propagate ballistically on the chain. For these quantities we
observe a complete absence of "operator spreading". In addition, the models can
also have other local charges which are conserved only additively. We discuss
concrete models up to local dimensions $N\le 4$, and show that they give rise
to rich physical behaviour, including non-trivial scattering of particles and
the coexistence of ballistic and diffusive transport. We find that the local
update rules are classical versions of the "dual unitary gates" if the
Yang-Baxter maps are non-degenerate. We discuss consequences of dual unitarity,
and we also discuss a family of dual unitary gates obtained by a non-integrable
quantum mechanical deformation of the Yang-Baxter maps.
