Здравствуйте,

Сегодня передо мной поставили задачу, целью которой является реализация онлайн кроссворда на одном из сайтов компании. ТЗ еще толком не сформулировано, задача пока в слишком общем виде. Однако, я должен, в краткие сроки, предложить один из вариантов:

• использование готового алгоритма;
• написание своего;
• установка локального софта, который генерит «HTML»-страницу с кроссвордом, а потом ручками его размещать на сайте;
• другое.

Первый  может оказаться самым оптимальным, главное – гибкость и изменяемость.  Второй мне интересен больше всего, его бы хотелось рассмотреть отдельно. Третий вариант самый неприятный, но зато реализовать его можно быстро, т.к. такой софт уже найден. Хотелось бы услышать предложения по каждому из методов.

Самописный вариант я вижу так: 

• есть в БД словарь – термин и определение к нему (может на один термин несколько определений);
• из словаря выбирается случайное слово, вокруг которого формируется все остальное, неким алгоритмом;
• готовый кроссворд отображается в браузере у пользователя.

Если с первым и третьим пунктами все понятно, то реализация алгоритма – тот еще вопрос. Единственное, что пришло в голову – это заполнять сетку полным перебором слов из словаря (исключая уже выбранные) с остановкой на первом подходящем.  Как это реализовать? Рекурсия? Может, кто-то сталкивался и поделится алгоритмом?

1 
Я бы предложил бы лучше сделать в виде конструктора с полуавтоматической генерацией

Словарь должен быть это по любому, это 1 таблица

2 таблица это название кроссвордов  id name , size_matrix  размер сеточной матрицы квадрата
3 Таблица это сущности связи слов из 2х таблиц

id = инкремент,
name = слово или id из таблицы слов.
help   = слову подсказке.
pos_x >=0,   пиксильное позиционирование по матрице квадрата.
pos_y=>0,
vertical = 0|1 расположить по вертикали или по горизонтали

На основе размера матрицы  у нас известная область пусть она будет равна  30,  1 единица это например 25px
Выставляем диву размер  30*25.

полу автоматическая генерация заключается в том что бы найти к указному слову подходящие слово с указными подсказками.
Запрос естественно проще сделать с WHERE LIKE 'г%%%%' AND CHAR_LENGTH(word) < 5 
Оставляем те буквы которые  должны быть обязательными в выдаче.

С автоматическим режимом нужно много пыхтеть 
Нужно выбрать слово от которого пойдет цепочка слов, также каждая буква это определенный размер в сетке нужно проверять не пересекаются ли слово с другим словом.
Как вариант можно сделать кусочек фрагмента гинирируеммого куска. 
Для конструктора, можно выбрать Query ui, плагин перетаскивания выставить ему перемещение  по сетки.
Минис всего написанного нужен будет человек который этим будет пользоваться, выполнять эту работу.


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

генерация кроссворда на делфи
Еще я находил на C#






Это сообщение отредактировал(а) Sanchezzz - 19.7.2013, 13:11

Sanchezzz, спасибо за пример на делфи, самому мне неудалось нагуглить. 
Может, все-таки, кто-нибудь посоветует готовое решение?