Самый простой алгоритм для создания Филворда (Часть 1)

[GCU]

3й способ
Генерируем разбиения числа, например для 25 их всего 1958.
Для 25ти слов: 1, 24х: 1,…
{25: 1, 24: 1, 23: 2, 22: 3, 21: 5, 20: 7,
19: 11, 18: 15, 17: 22, 16: 30, 15: 42, 14: 56, 13: 77, 12: 100, 11: 131, 10: 164,
9: 201, 8: 230, 7: 248, 6: 235, 5: 192, 4: 120, 3: 52, 2: 12, 1: 1}
На 5 слов 192 разбиения. Нас не интересуют разбиения, содержащие единицу, больше одной двойки или больше одной тройки (как пример, это эвристика для «интересного» разбиения, можно отфильтровать и все 1958 разбиений, тут фильтр что ровно 5 слов)
После фильтрации остаётся 37 вариантов:
[6, 6, 6, 4, 3], [6, 6, 5, 5, 3], [6, 6, 5, 4, 4], [6, 5, 5, 5, 4], [5, 5, 5, 5, 5],
[7, 6, 5, 4, 3], [7, 6, 4, 4, 4], [7, 5, 5, 5, 3], [7, 5, 5, 4, 4], [6, 6, 6, 5, 2],
[7, 7, 6, 3, 2], [7, 7, 5, 4, 2], [7, 7, 4, 4, 3], [7, 6, 6, 4, 2], [7, 6, 5, 5, 2],
[8, 6, 5, 4, 2], [8, 6, 4, 4, 3], [8, 5, 5, 5, 2], [8, 5, 5, 4, 3], [8, 5, 4, 4, 4],
[9, 4, 4, 4, 4], [8, 8, 4, 3, 2], [8, 7, 5, 3, 2], [8, 7, 4, 4, 2], [8, 6, 6, 3, 2],
[9, 7, 4, 3, 2], [9, 6, 5, 3, 2], [9, 6, 4, 4, 2], [9, 5, 5, 4, 2], [9, 5, 4, 4, 3],
[11, 4, 4, 4, 2], [10, 6, 4, 3, 2], [10, 5, 5, 3, 2], [10, 5, 4, 4, 2], [10, 4, 4, 4, 3],
[12, 4, 4, 3, 2], [11, 5, 4, 3, 2], выбираем любой, перемешиваем :)

[Akina]

БД со словами

Ну сразу следовало бы повыкидывать те слова, которые содержат в себе более короткие слова как подстроки (Кадык, Кумыс) — зачем обеспечивать алгоритм проверки корректности лишней работой? ему и так несладко придётся…

[GCU]

По логике там хеш-таблица или какое-нибудь префиксное дерево. Обычный бинарный поиск тоже довольно быстр — ведь там не больше нескольких сотен тысяч слов, а это около 18ти сравнений.

[apps]

Но ведь на сложность Филворда влияет не только кол-во и длинна слов, но и расположение области в которой слова находятся:
М О Л О
- - - К
- - - О
- - - -

- - О М
- - Л -
- К О -
- О - -

И во втором случае мы уже не сможем подставить слова 5 букв + 5 букв.
Поэтому первичная задача — разбить поле на области и затем, исходя из их длинны и количества, подбирать слова из БД.