I think you could remove a lot of your fairness and logistical concerns by at stage N choosing one solution and everyone group has to start from there.

Now for pedagogical purposes it might be that the professor chooses the best solution or a substantially worse solution.

There might be some concern that this unfairly advantages one group over the others but it’s not completely clear to me that it does.