We study the Potts spin glass model, which generalizes the Sherrington-Kirkpatrick model to the case when spins take more than two values but their interactions are counted only if the spins are equal. We obtain the analogue of the Parisi variational formula for the free energy, with the order parameter now given by a monotone path in the set of positive-semidefinite matrices. The main idea of the paper is a novel synchronization mechanism for blocks of overlaps. This mechanism can be used to solve a more general version of the Sherrington-Kirkpatrick model with vector spins interacting through their scalar product, which includes the Potts spin glass as a special case. As another example of application, one can show that Talagrand's bound for multiple copies of the mixed $p$-spin model with constrained overlaps is asymptotically sharp. We consider these problems in the subsequent paper, arXiv:1512.04441, and illustrate the main new idea on the technically more transparent case of the Potts spin glass.