We formulate general 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 such that their determinant is a real constant. These conditions can be realised in supersymmetric theories with an anomaly-free local flavour symmetry, suggesting a unified solution to the strong CP problem and the flavour puzzle.  Our solution can be implemented using either a local U(1) symmetry or modular invariance. We present concrete modular-invariant realisations. Heavy vector-like quarks are in general not required, but their presence allows for models where coloured particles fill non-singlet representations of the finite modular groups.