Помогите разобраться с алгоритмом заполнения кроссворда.

Такую задачу мне дали в моем университете, может у кого есть интересный алгоритм решения задачи. В stackoverflow есть несколько решений для этого, но ни одно из них не подходит (потому что они перебирают все возможности).

Задача: найти все возможные комбинации для размещения заданных слов в заданной таблице, сетке (прямоугольной, см. ввод ниже). Свободных клеток быть не должно, а слово может располагаться слева направо или сверху вниз. Слова не могут располагаться слово за словом в строке (столбце).

Вход: прямоугольная область, пример:

+-----+
|  *  | 
|     |
+-----+

or

+-----+
|   * |
|     |
|    *|
|   * |
+-----+

Затем после этого вводятся разные слова (следующие входные данные), чтобы заполнить эту сетку, например:

cdi
zobxzst
tdxic
r
sc
zro
and etc ...

Номер изначально неизвестен, но вводится до конца стандартного ввода — активный EOF.

Вывод: если существует одно решение, выведите это возможное решение в заполненной сетке. Если нет решения или количество решений, то выведите 0 или это точное число.

Пример:

(таблица введена)

+-----+
|   * |
|     |
|    *|
|   * |
|  * *|
|  *  |
|     |
+-----+

Затем слова cdi zobxzst tdxic r sc zro rgfvacd oikf df x c r xvf ogish za sh fc hh h bfkh

(Каждый в качестве ввода, но здесь разделен пробелами.)

Вывод (только 1 решение):

+-----+
|zro*h|
|ogish|
|bfkh*|
|xvf*r|
|za*c*|
|sc*df|
|tdxic|
+-----+

Важное примечание: Вводимая сетка ограничена всего 16 (!) ячейками, количество слов меньше 60. Я написал алгоритм перебора всех возможных комбинаций, но у меня он не сработал, так как время выполнения ограничено (10 сек, я думаю), и эта проблема не может быть решена грубым алгоритмом (например, 15 на сетке 15 и около 60 возможных или более возможных перестановок, которые могут быть обработаны около 1 дня? на обычном ПК с частотой 2 ГГц).

Возможно, существует другое уникальное решение. Может быть, эта проблема более математическая, чем программирование, может быть, можно использовать какие-то комбинации влево-вправо по сравнению с вверх-вниз? или, может быть, взвешенные ячейки?

P.S. У меня есть 3 недели, чтобы решить эту проблему, если нет, я могу опубликовать решение здесь через 3 недели (хорошие новости);)


algorithm crossword
person NGix    schedule 13.11.2012    source источник
comment
Эти слова, которые вы используете, cdi, zobxzst, tdxic, я не думаю, что они означают то, что вы думаете. :)   -  person James Kolpack    schedule 13.11.2012
comment
@JamesKolpack Невероятно!   -  person Eitan T    schedule 13.11.2012
comment
@ luiges90 Он отмечает место в сетке, где вам не разрешено размещать какие-либо слова.   -  person ChrisW    schedule 13.11.2012
comment
Я бы разделил слова на группы размера, n, n-1 n-2,... 1, где n представляет максимальную длину, разрешенную прямоугольником (высотой), все слова, содержащие более n букв, исключаются из списка. После этого шага начинаются комбинации, я не могу думать ни о чем, кроме грубой силы   -  person Alberto Bonsanto    schedule 13.11.2012
comment
Также в худшем случае здесь их гораздо больше, чем 15! возможности. Когда слова {a, a, b, b, c, c, ..., z, z} и сетка состоит всего из 26 изолированных ячеек, их всего 26! ~= 4e26 решений. Вы получите немного больше, если дополните список слов до шестидесяти слов с 4 дополнительными парами однобуквенных слов и 30 ячейками, но я не могу заниматься математикой. :)   -  person verdesmarald    schedule 13.11.2012
comment
@Ir0nm Обычный ПК с частотой 2 Гц сделал мой день ;) Приветствую, путешественник во времени!   -  person das_weezul    schedule 13.11.2012
comment
Omg Lool ;)) должен оставить это для удовольствия.)   -  person NGix    schedule 13.11.2012
comment
Джи, сокурсник CTU FIT. Постепенное уменьшение количества возможных мест размещения слов для каждого поля кроссворда с помощью некоторого распространения ограничения может быть ключом здесь, это то, что я собираюсь попробовать. Однако пространственная сложность такого дерева может быть непомерно высокой. Да, и, кстати, я нахожу эту попытку получить помощь извне в проблеме конкурса презренной.   -  person Daniel Maly    schedule 08.12.2012

Ответы (2)


arrow_upward
2
arrow_downward

В stackoverflow есть несколько решений для этого, но ни одно из них не подходит (потому что они перебирают все возможности).

Тогда моя идея, вероятно, тоже неверна: но вот идея, которая пришла мне в голову.

Я написал алгоритм, который перебирает все возможные комбинации

Если их слишком много, то проблема, вероятно, в том, что вы ищете/перебираете невозможные комбинации, а также возможные комбинации.

Например, когда вы помещаете слово «zro» в верхний левый угол, существует очень мало «возможных» комбинаций, которые можно поместить в вертикальные слова под ним:

  1. первое вертикальное слово должно начинаться с «z»
  2. второе вертикальное слово должно начинаться с 'r'
  3. третье вертикальное слово должно начинаться с «о»
  4. Комбинации букв во втором ряду (полученные в результате размещения слов по вертикали) сами по себе должны быть допустимым словом.
  5. и т.п.

Следовательно:

  1. Выберите любое слово и поместите его в верхний левый угол.
  2. Найдите существующие слова, которые удовлетворяют приведенным выше ограничениям.
  3. Если вы найдете одно или несколько таких слов, продолжайте в том же духе, чтобы посмотреть, сможете ли вы решить все это; или, если вы потерпите неудачу, попробуйте еще раз, используя другое начальное слово

Резюме:

  • Не создавайте каждую полную сетку, а затем проверяйте ее, чтобы увидеть, удовлетворяет ли она всем ограничениям.
  • Вместо этого используйте ограничения при построении сетки, чтобы уменьшить количество проверяемых возможностей.

Я предлагаю вам решить сетку, начиная с начального слова.

Вместо того, чтобы проверять каждое слово в верхнем левом углу, лучше (например, потому что это быстрее устраняет невозможности) способ создания начальной позиции [s]:

  • Найдите самое длинное слово (например, rgfvacd)
  • Найдите все возможные комбинации слов, которые пересекают/присоединяются к нему.
  • Попробуйте разместить каждую из этих допустимых комбинаций на сетке.
person ChrisW    schedule 13.11.2012
comment
Да, это похоже на теорию множеств, когда программа пробует слово в строке или столбце, возможные другие слова в других позициях уменьшаются, так что на самом деле проблема не в том, чтобы найти несколько решений, а в том, чтобы найти решение, которое соответствует перекрестной доске. моя точка зрения. - person Alberto Bonsanto; 13.11.2012
comment
@AlbertoBonsanto область/область математики можно (я не уверен) назвать комбинаторикой с ограничениями. - person ChrisW; 13.11.2012

arrow_upward
1
arrow_downward

Я предлагаю вам сначала посмотреть, какую длину слов вы должны заполнить, в вашем примере:

+-----+
|   * |
|     |
|    *|
|   * |
|  * *|
|  *  |
|     |
+-----+

у вас есть два слова из 7 букв, три слова из 1 буквы и т. д.

вы должны отсортировать этот список в соответствии с количеством и сначала попробовать длины слов с наименьшим количеством, на следующей итерации вы должны составить список слов, которые вам нужно найти, например, три слова из 4 букв, которые начинаются с «а». - вы должны подсчитать, сколько из этих слов у вас осталось в вашем списке слов, а затем выбрать то, в котором меньше всего слов - если это 0, то вернитесь.

надеюсь, это имеет смысл.

person zenpoy    schedule 13.11.2012