Мне дали матрицу, содержащую план кроссворда — незаполненный, конечно. Цель состоит в том, чтобы заполнить всю головоломку — это задача от Checkio, и я уже довольно давно борюсь с этим.
Насколько я понимаю сложность, для этой задачи нет идеального алгоритма. Тем не менее, должен быть лучший способ сделать это, верно? Я пробовал разные вещи, и результаты были не такими хорошими с увеличением количества слов в кроссворде и/или словаре.
Итак, некоторые из вещей, которые я пробовал:
- простой брутфорс. Не работал вообще, так как игнорировал и перезаписывал пересечения.
- брутфорс с сохранением всех релевантных данных - работал как положено с конкретным словарем, превратился в ад с умеренно большим словарем даже с оптимизацией длины слова. Цифры.
- заполнение слепого пересечения - идея, в которой я подумал, что было бы лучше не заморачиваться с пересекающимися словами, вместо этого сосредоточившись на буквах. Например, начните с As и проверьте, сможете ли вы заполнить весь кроссворд с этими ограничениями. Если это не сработало для какого-то слова, увеличьте одну из букв и попробуйте все снова. Результаты были ужасны, как и следовало ожидать.
- рекурсивное исследование - отлично работало на более простых чертежах, но не работало с более сложными. Была проблема с простыми петлями, которая разрешилась достаточно просто, но я не нашел разумного решения для ситуации, когда путь разветвляется, а затем снова соединяется несколькими дальнейшими разветвлениями (поэтому для второй ветви уже нечего решать, но она не не знаю).
- минимизация пересечений — еще не проверял, но выглядит многообещающе. Идея в том, что я нахожу кратчайший список слов, содержащий все пересечения... которые также не пересекаются друг с другом. Затем я могу просто использовать генератор для каждого из этих слов, а затем проверить, существуют ли зависимые слова с этими пересечениями. Если нет, я просто беру следующее слово из генератора.
И вот где я сейчас нахожусь. Я решил спросить об этом здесь, так как это уже в тот момент, когда я думаю, что это заняло больше времени, чем должно было, и даже тогда моя последняя идея может даже не быть правильным способом сделать это.
Итак, как есть правильный способ сделать это?
Редактировать: ввод представляет собой список строк, представляющих кроссворд, и список строк, представляющих словарь. Результатом является список строк, представляющих заполненный кроссворд.
И пример кроссворда:
['...XXXXXX',
'.XXX.X...',
'.....X.XX',
'XXXX.X...',
'XX...X.XX',
'XX.XXX.X.',
'X......X.',
'XX.X.XXX.',
'XXXX.....']
На выходе будет аналогичный список с заполненными буквами вместо точек.
Обратите внимание, что «словарь» — это всего лишь небольшой словарь английского языка, а не список слов, подходящих для ответов на эту головоломку.
