[Algorithm] generate a random square 2D map from N countries

Question

Java

I can't think of an algorithm to generate a random square 2D map from N countries in such a way that the area of ​​each country is the same.
Let's say there is a 100 x 100 map - a two-dimensional array. There are 10 countries - from 0 to 9. Once a cell on the map is not occupied, it is equal to -1. It is necessary to make sure that the territory is divided among all countries equally. The territory must be integral, that is, the country cannot consist of two pieces that are not connected to each other. With each generation, the result should be slightly different (in appearance, that is, the shape of the countries is different each time).
I started doing the following:
1) for each country I chose a point in different parts of the map
2) then for each country, starting from the starting point, I look for neighboring free points and attach them to the country's territory.
3) and so on until all countries gain equal territory
. The problem is that due to the randomness of the choice of the point and the direction of accession, sometimes it turns out that one country blocks access to another country to unoccupied neighboring points. And then everything is an endless cycle. Since the blockading country has gained territory, but the blocked one has not, but it cannot reach the points either.
Therefore, two requests:
1) if you know the name of the algorithm that solves this problem, please write.
2) if you have any ideas how to solve the problem, also write.

Answer 1

An interesting problem, if solved head-on, it can be resource-demanding.
You can add to your algorithm:
1) The queue for selecting the next cell (most likely already exists)
2) The possibility of re-selecting the cell (chosen, but it is busy, tell the one who grabbed it that he can choose out of turn)
In general, the task can be interesting with point of view of mathematics, since it is possible to choose the initial location of the players in such a way that it will not work to select all the same territory.
It seems to me that @wyfinger 's suggestion of leaving the center of the map to the edges seems to be the best.
Then you can invite the rest to make N number of exchanges with neighbors, according to some rules. This method will eat up a finite calculated number of resources and at the same time you can set any exchange rules (aim for the center or edge, etc.)

Answer 2

1. We consider what the area of ​​countries should be - map_size / number_of_countries, or pre-set.
2. We select a random point on the map from the unoccupied ones, randomly attach neighboring points to it until the desired size of the country is reached (calculated in 1.)
3. Repeat step 2 N times.

Answer 3

Remember the Peak formula (the area of ​​a polygon on a plane whose vertices lie at the nodes of the coordinate grid). Here is a selection of warm-up tasks: zaba.ru/cgi-bin/tasks.cgi?tour=books.sms700.fpika&solution=1
Based on the Pick formula, we formulate an invariant (the area of ​​any two countries at any time is equal). Any boundary transformation must preserve the invariant. We build the initial partition randomly, based on the maximum or minimum possible length of borders between countries.