[alexti]

Your algorithm looks reasonable, but sometimes it will fail. Consider a small map with a chokepoint that splits map in 2. If you need to allocate 2 somewhat equal areas your algorithm will fail is the first province will be at the chokepoint. You can also fail on step 3 before finding 5-8 provinces. I think your algorithm will work well on open wraparound maps with few impasses, but not on highly segmented maps.

Generally, this kind of tasks is considered in graph theory. I would suggest some modification to your algorithm:
- the first step is to build a graph. Initially you have connected graph (at least usually)
- find simple chokepoints (nodes, which if removed would make the graph unconnected). This is easy to do by iterating through all nodes and checking if the graph is still connected or not if all incoming edges to this node are removed.
- or optionally find complex chokepoints (pair of nodes, which if removed would make the graph disconnected). This is similar to the previous step.
- Now consider graphs produced by removal of chokepoints. Each of those graphs is a "mega-area". Those are suitable for area placement. Count number of provinces in each mega-area (number of nodes) and see if there's a reasonable way to divide them in required number of area. There's no need for exact match, because some of the areas can overflow through chokepoints. This step may fail. For example, if you have 2 equal areas connected through the chokepoint, you can't make 3 "equal" areas. So you have to decide something. (see more in the following step).
- Now you have number of areas to create out of each "mega-area". Start from the most densely populated "mega-area"
(one that have least provinces per required area). Start from the most remote point from any of chokepoints. Use your original algorithm, but in step 2,3 give more preference to the province further from the chokepoint. Degree of preference should depend on density of "mega-area" population. More densely it is populated, the more preference you should give to the outward provinces.
This will let the last area overflow through the chokepoint, if necessary.
- Update the graphs to take into account possible overflow, and repeat previous step for the next densest "mega-area".

If you have larger map and fewer required areas, you may want to execute this algorithm for the size of the area approaching to total of "mega-area" areas divided by number of required areas, and after it is complete, remove outward provinces from each of the areas to reach your original target size.

Concerning implementation, I don't see any problems implementing it in Java, but this algorithm may be resource intensive (I have no idea actually), so it may be better to do it in C++. Besides you'll probably have easier time finding libraries to use (like for graph handling).