Вызов Кода. Создайте Однозначно Решаемый Кроссворд... Без Подсказок.

Можете ли вы представить себе решение кроссворда New York Times без каких-либо подсказок? Возможно, не со всей креативностью и новыми словами и фразами, появляющимися в современных кроссвордах, но с фиксированным списком слов есть некоторая надежда. В этом задании вы создадите сетку кроссворда, в которой это теоретически возможно.

Задача

Увеличьте количество белых квадратов в сетке кроссворда 15х15, закрашенной белым и черным, так, чтобы белые квадраты можно было уникально заполнен буквами, так что каждое слово поперек и вниз появляется в международном списке слов Scrabble.

Уточнения по построению сети

В газетах США кроссворд сетки обычно строятся так, что каждая буква «проверяется», то есть она является частью как слова «поперек», так и слова «вниз». В Великобритании и других странах (особенно в загадочные кроссворды), это не обязательно так: если слово «поперек» или «вниз» будет состоять только из одной буквы, это не обязательно должно быть настоящее слово (например, «А» или «Я»). Для этого задания следуйте более мягким правилам: однобуквенные слова не обязательно должны появляться в списке слов.

Существуют и другие традиции (в США и других странах), ни одной из которых не нужно следовать в этом вызове. Например, слова могут состоять только из двух букв, слова могут повторяться, а сетка не обязательно должна иметь (вращательную) симметрию.

Возможно ли это вообще?

Да! Можно написать короткий скрипт, чтобы убедиться, что единственным решением для следующей пустой сетки слева является заполненная сетка справа:

Отобразить заполненную сетку в машиночитаемом формате можно следующим образом:

 R 

Ваше решение

В приведенной выше сетке 56 белых квадратов из 225 в сетке 15x15. Это служит основой для решения этой задачи. Сетки с меньшим количеством белых квадратов могут быть интересны и по другим причинам, помимо их оценки, например, если они удовлетворяют некоторым эстетическим традициям, упомянутым выше.

Пожалуйста, отправьте свое решение в том же формате, что и компьютерный базовый вариант, указанный выше. Пожалуйста, включите код, который проверяет, что для вашей сетки существует уникальное решение.

Приветствуются интересные фрагменты кода (например, для поиска в пространстве возможностей) и обсуждение того, как вы нашли свою сетку.

Список слов

Международный список слов для скрэббла ранее назывался SOWPODS, а теперь называется Коллинз Эрудитные слова (ЧСВ). Он используется в большинстве стран (за исключением США). Мы предпочитаем использовать этот список, поскольку он включает британские варианты написания и, как правило, содержит значительно больше слов, чем американский список слов. Существует несколько редакций этого списка, которые немного отличаются. Вы можете найти разные версии этого списка. ссылка из Википедии, на Гитхаб, в Корпус естественного языка Питера Норвига и в других местах, часто до сих пор называемых «SOWPODS».

Эта проблема очень чувствительна к широкому характеру выбора списка слов, но в меньшей степени к более мелким деталям. Например, приведенный выше базовый пример работает с любой версией CSW, но D is not a word in the American Scrabble word list. In the event of a discrepancy, we prefer to use CSW19, the most recent edition of CSW. (If we use this list, which was released this year, we can expect answers to this challenge to remain valid longer). You may query this list interactively on the official Поиск слов в стиле скрэббл сайте или загрузите его (как и предыдущую редакцию CSW15) с сайта Обмен стеками настольных и карточных игр или Reddit r/scrabble.

Тлдр: авторитетный список слов для этого задания доступен в виде обычного текстового файла (279 496 слов, по одному в строке) на Обмен стеками настольных и карточных игр.

Дальнейшее обсуждение

Одна из проблем, поднятая в ранних ответах и ​​комментариях, заключается в том, почему существующие кроссворды (например, в «Нью-Йорк Таймс») не отвечают на этот вопрос. В частности, рекорд по наименьшему количеству черных квадратов (и, следовательно, по наибольшему количеству белых квадратов) в опубликованном кроссворде NYT уже является самым известным рекордом в кроссвордах. Почему мы не можем использовать сетка записи? Есть несколько проблем:

• Многие ответы в кроссвордах NYT не указаны в нашем списке слов. Например, сетка записей включает в себя STE (a brand name), APASSAGETOINDIA (имя собственное из четырех слов для фильма и романа, написанное без пробелов) и PEPCID (an abbreviation for "Sainte"). It appears that the record grid is not solvable with Scrabble words.

• Простое расширение списка слов для включения большего количества слов не обязательно поможет решить эту задачу: даже если бы все слова в сетке записей появились в нашем списке слов, решение не было бы таким: уникальный без подсказок. Часто можно изменить некоторые буквы в конце ответов, сохранив при этом все слова. (Например, самую нижнюю правую букву можно заменить на CH to an ###CH########## ###YE########## ###AM########## CYANOCOBALAMINE HEMOCHROMATOSES ###CH########## ###OR########## ###BO########## ###AM########## ###LA########## ###AT########## ###MO########## ###IS########## ###NE########## ###ES########## .) Действительно, это часть (человеческого) процесса построения кроссворда, попытка получить «лучшие» слова.

  Причина, по которой обычные кроссворды (обычно) имеют единственное решение, заключается в том, что подсказки помогите сузить правильные ответы. Если вы просто попытаетесь заполнить сетку словами без используя подсказки, вполне вероятно, что возможностей либо не будет, либо много возможности. Вот пример трех разных заливок (с использованием списка слов для этого задания!) для одной и той же сетки (той, которая относительно часто используется в «Нью-Йорк Таймс»):

• Еще одна проблема, поднятая в комментариях, — это некоторое неверие в то, что этот вопрос является задача кодирования. Возможно, это не сразу понятно, но трудно найти хоть один правильный ответ на этот вопрос. Для поиска приведенного выше базового показателя потребовалось несколько специально созданных поисковых программ, которые не гарантировали, что найдут ответ. Я лично даже не знаю общий способ решения произвольной сетки, если вы хотите получить ответ в разумные сроки. Существующие программы построения кроссвордов могут помочь, но я предполагаю (возможно, ошибочно), что они на самом деле не производят полного поиска возможностей. (Я использовал такую ​​программу для трех расположенных рядом сеток выше; это сработало, потому что эта конкретная сетка допускает множество решений.)

#вызов кода #оптимизация #кроссворд

180 белых квадратов

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

 
 
 HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES
B##############
INCOMMUNICATIVE
NEUROANATOMICAL
DETERMINATENESS
###############
HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES
B##############
INCOMMUNICATIVE
NEUROANATOMICAL
DETERMINATENESS
 
 
 

Затем я помещаю в сетку 4 таких прямоугольника. Это означает, что каждое слово встречается в решении 4 раза, что обычно не одобряется при составлении кроссворда, но подходит для этой задачи. С другой стороны, это решение имеет симметрию как слева/справа, так и сверху/вниз!

Читаемая компьютером сетка:

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

• установка первых двух столбцов (два трехбуквенных слова)
• затем перебираем все 15-буквенные слова, начиная с первых двух букв, которые теперь установлены.
• для каждого возможного выбора слов из 15 букв я затем проверяю, все ли сгенерированные слова из 3 букв находятся в словаре.

Например, для окончательного решения сначала вводится код ITS и TAS , затем завершено в ANE , MON and RID , and finally verified all the 3-letter words ( ONE , NIS , OPS , ROE , ERS , TES , EVO , HOP , POSSESSEDNESSES , OVEROPINIONATED , HETERNORMATIVE , EVO , HOP , HETERONORMATIVE OVEROPINIONATED POSSESSEDNESSES ############### HETERONORMATIVE OVEROPINIONATED POSSESSEDNESSES ############### HETERONORMATIVE OVEROPINIONATED POSSESSEDNESSES ############### HETERONORMATIVE OVEROPINIONATED POSSESSEDNESSES , k=15 ).

код R

Называется как 3×k . Took a few hours on my personal computer.

182 белых квадрата

Вдохновлено Ответ Робина Райдера, я попробовал втиснуть еще пару белых квадратов. Я считаю, что это решение уникально, и вскоре опубликую соответствующий код проверки.

Читаемая компьютером сетка: