The structural properties of the (Zn, Mg) (S, Se) solid solutions are determined by a combination of the computational alchemy and the cluster expansion methods with Monte Carlo simulations. We determine the phase diagram of the alloy and show that the homogeneous phase is characterized by a large amount of short-range order occurring among first-nearest neighbors. Electronic-structure calculations performed using the special quasirandom structure approach indicate that the energy gap of the alloy is rather sensitive to this short-range order.