Previous criteria for the feasibility of reconstructing phase information from intensity measurements, both in x-ray crystallography and more recently in coherent x-ray imaging, have been based on the Maxwell constraint counting principle. We propose a new criterion, based on Shannon's utual information, that is better suited for noisy data or contrast that has strong priors not well modeled by continuous variables. A natural application is magnetic domain imaging, where the criterion for uniqueness in the reconstruction takes the form that the number of photons, per pixel of contrast in the image, exceeds a certain minimum. Through detailed studies of asimple model, we develop an analogy between reconstruction uniqueness and the phases of a spin glass. © IOP Publishing Ltd and Deutsche Physikalische Gesellschaft.