randomly coloring an nXn matrix

I have an nXn matrix (or an image) and I want to randomly break it into different continuous regions where each region has its unique color. The following specs for each region:

1. The union of regions must give the whole matrix.
2. Each region has its unique color. Colors cannot be repeated.
3. The maximum number of elements within each region is M and the minimum is Z.
4. Each region must be continuous. That is a color should be only seen in a continuous region. Having two disjoint regions with the same color is prohibited.
5. Preferably, each region boundary is smooth. That is there is no narrow areas and then expansion such as Maryland state map but more like Wyoming, Oregon, and Washington.

My initial thought is to start with point (0,0) and then randomly generate xandy such as np.random.randint(Z,M). Then, draw a line between the randomly generated x and y. However, the problem with this approach that it needs to keep track of all pixels/elements or some of them will end up not assigned to any region, which is time consuming. Anyone has a better idea?