Итак, первый период, назовём его стихийным :), когда я написал программу и методом Монте-Карло генерировал поля, прошёл у меня за пару недель.
Для других задач он длился у меня намного дольше. Поэтому могу смело сказать что участие в конкурсах нас точно развивает.
Второй период, назовём его периодом регулярных замощений, длился практически до конца конкурса. К следующему уровню осознания я так и не поднялся, хотя попытки построения нерегулярных замощений были.
Итак, какие замощения я испробовал.
Сначала я сделал Замощение 1
У этого замощения период 14, поэтому каждому полю соответствовало 14 вариантов.
Для этого варианта я написал программу, которая генерировала поле размера N со сдвигом P, подставляла близкие к идеальным для данного замощения гексы на границах.
Затем я вручную подгонял ближайшие к вершинам поля гексы, добиваясь отсутствия противоречий в решении.
Потом запускался другой алгоритм этой же программы, который пробовал:
1. увеличивать значения гексов,
2. менять местами два гекса если это возможно,
3. переставлять местами три гекса, если это возможно.
Этот алгоритм работал надёжно, хотя и не очень быстро. Но, так как идей было мало, спешить особо было некуда.
Как оказалось, Замощение 1 было одним из самых продуктивных. Им я получил большинство своих максимальных значений полей. Связано это видимо с тем, что период повторения 14 - достаточно большой, и поэтому случайные совпадения с границами поля были более вероятны чем у других вариантов замощения.
Затем я проверил некоторые из других подобных замощений:
Они не дали никакого прогресса по сравнению с первоначальным Замощением 1.
Тогда я стал искать и нашёл самое простое замощение, Замощение 2:
Его период равен 7, и оно, как мне казалось сначала, может дать преимущества по сравнению с Замощением 1.
Но реально получилось только увеличить на 1 рекорд для поля R15.
Нужны были новые идеи, и я получил Замощение 3:
Была надежда на то, что такое замощение даст больший результат, так как при деградации тройки 5,6,7 уменьшается всегда самый большой элемент - 7, а при уменьшении длинной последовательности 5,6,7 возможно под деградацию попадёт 6 или 5.
К сожалению, предположение оказалось неверным. При деградации гексов на пересечении последовательностей 5,6,7 с гранями поля из-за отбрасывания гексов 2 и 3 деградировали гексы 4, что вызывало деградацию более одного гекса в последовательностях 5,6,7.
Я понимал что вариантов Замощения 3 как минимум 3, но все их проверять не стал, так как и по одному было понятно что это не даст улучшения.
Тогда родилось концентрическое Замощение 4, сразу в двух вариантах:
и
Как я сейчас понимаю, я уже стоял на пороге осознания существования сложных замощений из комбинации линий и концентрических элементов. Шаг этот сделать не удалось, но сами концентрические замощения дали для некоторых полей увеличение результата на 2-3 единицы.
Спасибо всем дочитавшим мой опус до конца, был рад поделиться своими изысканиями.
Также очень хочу услышать детали вашего пути решения задачи.
