Алгоритм формирования кроссвордов

[tas]

Интересная идея. А вот реализация, наверно нетривиальная получится.

У меня по всему алгоритму, наверно, всего 2-3 места с нечеткой логикой, которые определяются весовыми коэффициентами — и то я искать наиболее оптимальные значения намучился — а тут все на этом завязано будет!

[gasyoun]

А для слогового письма реально? Или разные заданные картинки?

[tas]

Почему нет. Только сложность повысится из-за: В среднем слоговые азбуки (называемые также силлабариями) насчитывают 80-120 символов..

Чем больше вариантов, тем меньше шанс подобрать слово на пересечении.

[CaptainTrunky]

А нельзя ли тут как-то добавить анализ возникших конфликтов? Что-то в духе SAT — conflict-driven clause learning. Запоминать конфликтующие пересечения до достижения некоего лимита по памяти, потом вычищать БД конфликтов.
Тут же пригодится и random restart — если программа застряла в процессе построения, можно попробовать просто начать либо совсем с нуля, но с иными начальными условиями, либо откатиться на большее число итераций.

[tas]

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

Да — можно однозначно! Идей, как улучшить алгоритм очень много. Проблема в том, что на реализацию идей уходит много сил, а профита иногда не просто нет а он отрицательный (у меня были 2 идеи, которые не сработали).

По поводу «начать с нуля» — это все таки должно быть решение пользователя.

Каюсь — не все возможности алгоритма были реализованы в конечной программе. Например, для тестов, я запускал 10-20 генераций одного и того же кроссворда, с лимитом по времени или по количеству операций — чтобы наработать средние значения времени генерации.

По поводу «откатиться на большее число итераций» — боюсь, что это опять решение без четкой логики. Основная проблема — а куда именно откатываться? Уж лучше сначала начать.

Привожу несколько идей, которые не были реализованы в алгоритме.

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

Еще одна идея — поиск в сетке неких точек минимальной сложности и выстраивание порядка генерации слов таким образом, чтобы конец генерации попадал именно на эти точки

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

[McKinseyBA]

Пару недель назад купили с женой Эрудит (Scrabble) для разнообразия домашнего досуга :-)

Попробую применить кусок алгоритма на практике, а то чего-то давно не выигрывал))

[mwizard]

Автор, вы не могли бы выложить программу без инсталлятора? Или отдельно файл со словарем — на компьютерах без Windows залезть внутрь инсталлятора небольшая проблема.

[tas]

Готово.

[mwizard]

Спасибо, попробую одолеть вашу последнюю сетку :)

[logiciel]

Генерация кроссвордов! Я писала такую программу в 1995 году, в FoxPro, в DOSe. У меня задача была проще, не было предопределенной сетки. Словарь набивала сама, из разных источников.
Это был квадрет 20*20. Я брала первое случайное длинное слово, заполняла первую строку, потом подбирала второе слово так, чтобы в словаре имелись варианты для получающихся столбцов, потом третье… Если слов не находилось, происходил откат на предыдущую строку.
Процесс поиска выводился не экран, было забавно смотреть. Поначалу программа упорно топталась на месте, не проходя дальше третьей строки. В один прекрасный день она добралась до 11-й строки, это была победа.
Последние клетки, нижний правый угол, приходилось все-таки заполнять вручную, там щедро раздавались «юты», «еры» и прочие «асы».
Конечно, процесс шел не секунды, а пару часов, но это было не критично.

[tas]

Перенесено из статьи сюда:

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

[Smorodov]

Задача сложная, но если собирать кроссворд по одной букве, то посильная даже для смартфона, правда иногда почему-то задумывается.
Моя реализация здесь: play.google.com/store/apps/details?id=com.smorodov.crosswordPuzzle&hl=ru
Сделано на основе «Arc Consistency Crossword Compiler», или сокращенно «arccc».
Исходники arcc (на С) здесь: sourceforge.net/projects/arccc/
Есть наблюдение, что этот алгоритм хорошо работает только с достаточно большим словарем, я использую словарь из 125000 слов, минимально требует порядка 40000.
Кроссворд 15х15 клеток на PC составляется несколько секунд.

[andy_p]

Посмотрел файл cross.txt, где вы такие определения находите :-)

ЁБОСАН — В корейской мифологии злой дух японца, который в образе красного перца обольщал кореянок в сумерках.

[tolika]

СИФИЗ В греческой мифологии царь Коринфа, осужденный богами на вечное вкатывание камня в гору