I discuss a set of conditions under which the strong CP problem is solved by spontaneous CP violation. Quark-mass matrix elements are polynomials in the CP-breaking order parameters, engineered to make their determinant a real constant. A limited number of textures is allowed in this scheme. This behavior is naturally reproduced in CP-invariant supersymmetric gauge theories enjoying an anomaly-free local flavor symmetry, suggesting a common solution to the strong CP problem and the flavor puzzle. In its minimal realization, this solution requires a single chiral multiplet, beyond those of the MSSM. If one of the spin-zero components is light, it provides a viable Dark Matter candidate, with specific properties. Both modular invariance and local U(1) symmetries can be adopted to implement this class of solutions.