To explore a greater realm of model phase space than has previously been mapped, we generate randomly chosen interior models for Uranus and Neptune. The models are constrained by the observed mass, rotation rate, radius, and gravitational moments of the two planets. New models with a composition gradient in the outer third of the planetary radius are found for both planets. Such composition gradients may play a significant role in controlling the internal heat flow. In agreement with previous models, we find that the pressure-density relation for the central third of both planets is consistent with either ice or a mixture of materials with a similar equation of state. While the range of allowed models is now somewhat greater, the principal conclusions drawn from traditional interior modeling techniques are robust. ¿ American Geophysical Union 1995