Комментарии 7
НЛО прилетело и опубликовало эту надпись здесь
Слишком много чисто американских атрибутов, тяжеловато будет разгадывать.
Странно. Я думал, что кроссворды уже давно программно все генерируются, они же каждый день появляются.
Вот же, не знал, что составление кроссворда является сложной проблемой. Когда работал в газете — написал программу для составления готовых кроссвордов.
Самой большой проблемой было составление базы слов и вопросов. После пробного пользования — составили огромную базу слов, а по фактически заполненной сетке уже писали вопросы всех редакцией :)
Кому интересно — объясняю принцип построения.
1) Каждая клетка кроссворда анализировалась на предмет, является ли она первой, второй,… последней.
2) Определялись самые длинные слова в кроссворде и заполнялись первыми словами с учетом той информации, которая получена на шаге № 1 (например, нельзя ставить слово, у которого мягкий знак попадает на клетку, помеченную признаком «Первая» — то есть какое-то другое слово начинается с этой клетки).
3) Методом перебора к первым самым длинным словам прикреплялись подходящие все более короткие слова, но не менее 4 знаков. При этом каждая цепочка запоминалась и если для более короткого слова варианты заканчивались, предыдущее слово в цепочке менялось попытка подобрать более короткое слово повторялось.
К этому моменту кроссворд уже на 80% заполнен, в нем нет только слов на 3 и 4 буквы.
4) Подбирались короткие слова для пустых мест. Таких слов в базе было больше всего и обычно это не составляло труда (опять следует иметь ввиду, что все слова, поставленные ранее, ставились не на обум, а по правилам, т.е. не было такой экзотики, как двойные или тройные одинаковые буквы по соседству… ).
Некоторые замечания:
Надо сказать, что мои сетки были попроще, чем вариант выше.
Успешными были более 90% попыток, при этом этот процент рос по мере добавления правил, какую букву куда нельзя, а какое сочетание букв можно.
Время формирования — от минуты до часов. Обычно если время переваливало за час, делался стоп и все запускалось по новой.
Самой большой проблемой было составление базы слов и вопросов. После пробного пользования — составили огромную базу слов, а по фактически заполненной сетке уже писали вопросы всех редакцией :)
Кому интересно — объясняю принцип построения.
1) Каждая клетка кроссворда анализировалась на предмет, является ли она первой, второй,… последней.
2) Определялись самые длинные слова в кроссворде и заполнялись первыми словами с учетом той информации, которая получена на шаге № 1 (например, нельзя ставить слово, у которого мягкий знак попадает на клетку, помеченную признаком «Первая» — то есть какое-то другое слово начинается с этой клетки).
3) Методом перебора к первым самым длинным словам прикреплялись подходящие все более короткие слова, но не менее 4 знаков. При этом каждая цепочка запоминалась и если для более короткого слова варианты заканчивались, предыдущее слово в цепочке менялось попытка подобрать более короткое слово повторялось.
К этому моменту кроссворд уже на 80% заполнен, в нем нет только слов на 3 и 4 буквы.
4) Подбирались короткие слова для пустых мест. Таких слов в базе было больше всего и обычно это не составляло труда (опять следует иметь ввиду, что все слова, поставленные ранее, ставились не на обум, а по правилам, т.е. не было такой экзотики, как двойные или тройные одинаковые буквы по соседству… ).
Некоторые замечания:
Надо сказать, что мои сетки были попроще, чем вариант выше.
Успешными были более 90% попыток, при этом этот процент рос по мере добавления правил, какую букву куда нельзя, а какое сочетание букв можно.
Время формирования — от минуты до часов. Обычно если время переваливало за час, делался стоп и все запускалось по новой.
Обожаю скндинавские кроссворды. Особенно «правильно составленные» — это искусство!
НЛО прилетело и опубликовало эту надпись здесь
Cтатью вообще-то здесь. А ваша почему-то ведет на неё через некий «прокси» Sci-Hub, который тут же просит денег. Я не очень понимаю, почему нельзя было дать прямую ссылку на arXiv (ну т.е. понимаю, но всё же). Сорри за некропостинг.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Самый сложный кроссворд, составленный компьютером