Berserker, возможно. Но посчитать все варианты размещения утопии будет очень сложно, во много раз дольше, чем проверить 50 рандомных позиций. 20 попыток мало, да. Это было слишком оптимистично.

Есть еще один вариант - разбить карту на прямоугольники 6x3 клетки (в такой прямоугольник влезают все красные клетки утопии) и проверять все такие прямоугольники. А чтобы координаты не повторялись, смещать координаты первого прямоугольника от угла карты случайным образом. Этот вариант тоже не идеален.
Нужно тестировать, чтобы понять, как будет быстрее. Я все-таки думаю, что первый способ.
Также если карта случайная, где-то в памяти игры должно храниться количество воды ("None"/"Normal"/"Islands").
Неплохо было бы его сразу прочитать, чтобы не тратить время впустую.