самая маленькая доска для скрэббла, содержащая каждое слово из списка

Я ищу алгоритм, способный построить массив (2D) букв, из которого я мог бы извлечь каждое слово из заданного списка. Как и в Scrabble, слова могут пересекаться друг с другом, быть горизонтальными, вертикальными или диагональными. Конечно, есть некоторые очевидные решения, но цель здесь состоит в том, чтобы сделать его как можно меньше, что также означает максимальное количество пересечений.

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

Спасибо за вашу помощь.

PS: это для арт-проекта, без шуток.


arrays algorithm letter
person aymeric l    schedule 11.04.2012    source источник
comment
Найти минимальное решение будет крайне сложно. Разве вы не можете просто согласиться на хорошее решение, а не на оптимальное? Относительно того, что также означает максимальное количество пересечений: это неверное утверждение. Максимизация числа пересечений — очень похожая задача, но во многих случаях оптимальный результат для этих двух задач будет разным.   -  person Mark Byers    schedule 11.04.2012
comment
Спасибо, ребята, и извините за неточность. Хорошего решения было бы достаточно, наверняка найти абсолютно оптимальное было бы адом. Кроме того, спасибо, что подчеркнули, что это не такая же проблема, как оптимизация пересечения. Я полностью согласен, я имел в виду, что эти проблемы кажутся близкими.   -  person aymeric l    schedule 11.04.2012
comment
(подсчет) слова в scrabble не являются диагональными.   -  person andrew cooke    schedule 03.05.2012

Ответы (1)


arrow_upward
0
arrow_downward

Это был бы некоторый алгоритм. Я подозреваю, что решение будет включать какую-то рекурсию.

Допустим, у вас есть начальная сетка G0 со всеми пустыми квадратами, и что f(G0) является оптимизированной завершенной сеткой.

Тогда я бы попробовал:

Для каждой возможной позиции первого слова - установите G1 = сетка с этим словом в этой позиции и всеми остальными пустыми квадратами - проработайте G1 Перейти к следующей позиции

Чтобы вычислить G1, вы можете рекурсивно вызвать f(G1).

Если бы у вас была большая сетка и много слов, это заняло бы целую вечность, так как это расточительный алгоритм, но я думаю, что с типичной доской Scrabble это будет достаточно быстро на ноутбуке.

person Andy Brown    schedule 11.04.2012