Самый сложный кроссворд, составленный компьютером

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

Странно. Я думал, что кроссворды уже давно программно все генерируются, они же каждый день появляются.

Вот же, не знал, что составление кроссворда является сложной проблемой. Когда работал в газете — написал программу для составления готовых кроссвордов.

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

Кому интересно — объясняю принцип построения.

1) Каждая клетка кроссворда анализировалась на предмет, является ли она первой, второй,… последней.
2) Определялись самые длинные слова в кроссворде и заполнялись первыми словами с учетом той информации, которая получена на шаге № 1 (например, нельзя ставить слово, у которого мягкий знак попадает на клетку, помеченную признаком «Первая» — то есть какое-то другое слово начинается с этой клетки).
3) Методом перебора к первым самым длинным словам прикреплялись подходящие все более короткие слова, но не менее 4 знаков. При этом каждая цепочка запоминалась и если для более короткого слова варианты заканчивались, предыдущее слово в цепочке менялось попытка подобрать более короткое слово повторялось.

К этому моменту кроссворд уже на 80% заполнен, в нем нет только слов на 3 и 4 буквы.

4) Подбирались короткие слова для пустых мест. Таких слов в базе было больше всего и обычно это не составляло труда (опять следует иметь ввиду, что все слова, поставленные ранее, ставились не на обум, а по правилам, т.е. не было такой экзотики, как двойные или тройные одинаковые буквы по соседству… ).

Некоторые замечания:

Надо сказать, что мои сетки были попроще, чем вариант выше.
Успешными были более 90% попыток, при этом этот процент рос по мере добавления правил, какую букву куда нельзя, а какое сочетание букв можно.
Время формирования — от минуты до часов. Обычно если время переваливало за час, делался стоп и все запускалось по новой.

Обожаю скндинавские кроссворды. Особенно «правильно составленные» — это искусство!

Cтатью вообще-то здесь. А ваша почему-то ведет на неё через некий «прокси» Sci-Hub, который тут же просит денег. Я не очень понимаю, почему нельзя было дать прямую ссылку на arXiv (ну т.е. понимаю, но всё же). Сорри за некропостинг.