Re: венгерские кроссв о рды

From

Eugene Kilachkoff ()

To

Igor Zakhrebetkov

Date

2002-11-30T18:16:41Z

Area

RU.ALGORITHMS

From: Eugene Kilachkoff <zeus@hippo.ru>

Igor Zakhrebetkov пишет:
> По уму - не знаю. Я в свое время писал прогу, показывающую наличие слова
> в заданной матрице букв. Если позиция слова в матрице - единственная, его
> можно в ней "закрепить", чтобы не использовать эти буквы в других поисках.
Это больше похоже на отгадывание. Интересует же обратная задача.
Кстати, попутный вопрос. Есть ли быстрый способ обнаруживать запрещенные 
комбинации ? Я делал опять же в лоб, простым сравнением с образцом.
Под запрещенными комбинациями я понимаю появление областей, которые 
невозможно полностью заполнить словами.

Пример:
1)
XXX
X.X
XXX

2)
XXXX
X..X
XXXX

3)
XXXXX
X...X
XX.XX
XXXXX

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

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

Что еще сюда можно прикрутить ? Клеточные автоматы ? Напрашиваются ГА, 
но надо придумать хорошее представление раскладки слов. Что брать в 
кач-ве оценочной функции ? Здесь необходимо учитывать тот факт, что 
слова должны быть искривлены и перепутаны. Кроссворд, в котором слова 
расположены змейкой, это вообще не кроссворд ;-)

--- ifmail v.2.15dev5
 * Origin: home (2:5020/400)