Как разместить слова в матрице 6x6 для игры в филворды?
У меня есть список слов, включающий ['требование', 'хозяйство', 'сторона', 'поезд', 'номер'] или ['миллион', 'красота', 'дорога', 'здание', 'голос', 'класс'], которые в сумме составляют 36 букв. Я хочу создать матрицу 6x6 и разместить эти слова в ней, используя различные формы. У кого-то есть советы или алгоритмы, как это сделать?
p.s Будет здорово, если у вас есть пример на Python!
Общий совет для таких вещей.
Сначала делается самое простое заполнение. Например вообще слова последовательно вписаны. Т.е. я прям самое-самое простое и соответствующее правилам.
А потом итеративно что то в стакане меняется, с сохранением правил. По одному шагу. Обычно сложность тогда регулируется количеством итераций +вариативностью итераций.
Ну и самое важно - начать с описания првил. Ваше описание непонятно вообще
"Филвордами" сейчас называют что попало: и "вычеркни слова по вертикали-горизонтали-диагонали", и "двигаться можно только вниз и вправо", и давно известные венгерские кроссворды, где слова вписаны змейками из соседних клеток.
Для последнего варианта алгоритм довольно простой: генерируешь путь по полю, включающий все его клетки (гуглим "обход доски", например), и на его отрезки укладываешь слова.
В общем случае - только комбинаторикой. Играть с каждым словом в змейку и замораживать его в произвольной позиции. Если филворд не складывается, то изменять форму изгиба предыдущего слова. Перебрать все формы изгиба и начальной точки этого слова. Не получилось собрать филворд? Вернуться на предыдущее за предыдущим словом - покрутить его форму и начальную точку, покрутить следующее слово. Опять не получилось? Вернуться на 2 слова назад, опять тоже самое, но поменять следующие за ним слова местами.
Можно оптимизировать алгоритм, чтобы змейка не стремилась расти в область пустых клеток, а чаще старалась огибать уже существующие контуры, тогда вероятнее собрать филворд в кратчайшие сроки, но слова будут меньше перемешаны, это будет заметно на больших площадях доски.
