Вопрос по дискретной математике - найти все возможные варианты связывания элементов таблицы

Как-то рекурсивно, наверное, поле обходить надо с буфером в размер максимальной длины слова. Это если слова могут в любом направлении вилять. А если только вертикально и горизонтально, то можно и циклом обойтись, мне кажется.

Начните с простого — с одной строки и найдите там все возможные слова.

Хотелось бы сначала на бумаге решить.
Я догадываюсь как решить и в принципе, могу, но:
1) Скорее всего это решение будет неоптимально 2) Нет 100% уверенности что я найду все возможные комбинации

Собственно, в 1м пункте нам не важно что там буквы, задача именно на нахождения возможностей связать (простите) связуемые элементы в N-е число графов N-го размера, так чтобы получить максимальную выборку таковых графов.

Слова могут располагаться не по линии, а змейкой? Самое быстрое, мне кажется, взять список всех слов и пробовать подставлять. Предварительно можно составить всевозможные N-граммы небольшой длины и отфильтровать часть слов и позиций.

Ну таки да, я и говорю: надо предварительно составить список всех возможных n-грамм, которые можно разместить в таблице.
Слова могут быть как вертикальными, так горизонтальными и змейкой.
Диагоналей нет, слава Одину.

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

А, да, забыл сказать: сравнение со сканвордами не совсем корректно.
У меня нет изначально списка слов, только словарь Ожегова распарсеный, а решение подойдет только конкретное.

Тогда вроде просто. Берешь слово, берешь из него N-грамму пореже и пытаешься подставлять в таблицу по месту таких же N-грамм. Я бы так сделал.

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

Линейной скорости тут никак не получится. По моим подсчётам, на поле 10х10 с максимальной длиной слова в 10 букв будет порядка 7 млн вариантов «слов».

n*n графов у тебя уже есть. загоняй по ним поиск в глубину пока остаются слова-кандидаты. для поиска по всему словарю сразу см ахо-корасика.

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

И я абсолютно не понимаю как найти все возможные перестановки.

Рекурсивно. Представь, что уже построена часть слова из N букв, занимающая ячейки (x0;y0); (x1;y1).... (xN; yN). Какие слова можно построить на ее основе? Очевидно, такие, у которых N+1-я буква находится рядом с (xN; yN), не выходит за рамки таблицы и не пересекается с буквами (x0; y0)... (xN-1; yN-1). Далее остается перебрать слова, начинающиеся из каждой клетки таблицы.