Уровень сложности Судоку

Question

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

Моя единственная проблема , и это то, что мешает мне публиковать свой проект в открытом доступе.в том, что я не знаю, как оценивать свои доски по уровням сложности.Я смотрел ВЕЗДЕ,размещены на форумах и т. д. Я не хочу сам писать алгоритмы, это не главное для этого проекта,и кроме того, они слишком сложны для меня, так как я не математик.

Единственное, к чему я приблизился, это этот веб-сайт, который оценивает с помощью JS но проблема в том, что код написан таким паршивым недокументированным, очень специальным образом,поэтому нельзя заимствовать ...

Я подойду к делу -Может кто-нибудь указать мне место, которое предлагает исходный код для оценки / оценки судоку?

Спасибо

Обновление 22.6.11: Это моя игра судоку , и я реализовал свою собственную систему оценок, которая опирается нана основные методы решения человеческой логики, так что проверьте это.

Answer 1

Я сам рассмотрел эту проблему, и лучшее, что я могу сделать, - это решить, насколько сложно решить головоломку, фактически решив ее и проанализировав игровое дерево.

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

Решите загадку. На каждой позиции:

• Перечислить все новые ячейки, которые могут быть логически выведены в текущей игровой позиции.
• Оценка каждого вычета (полное решение одной ячейки) - это оценка простейшего правила, достаточного для этого вычета.
• РЕДАКТИРОВАТЬ: если более одного правила должны применяться вместе, или одно правило несколько раз, чтобы сделать один вывод, отслеживать его как одно "составное" применение правила. Чтобы оценить состав, возможно, используйте минимальное количество отдельных приложений правил, чтобы вычислить ячейку, умноженную на сумму баллов каждого. (Значительно больше умственных усилий требуется для таких выводов.) Расчет минимального количества приложений может потребовать значительных ресурсов процессора в зависимости от установленных правил. Любое приложение правила, которое полностью решает одну или несколько ячеек, следует откатить, прежде чем продолжать исследовать позицию.
• Исключить все вычеты с оценкой выше минимальной среди всех вычетов. (Логика здесь заключается в том, что игрок не будет воспринимать более сложные, восприняв более легкое и взяв его; а также, это обещает сократить много вычислений из процесса принятия решений.)
• Минимальная оценка в текущей позиции, поделенная на количество «самых простых» вычетов (если их много, найти проще) - это сложность этой позиции. Таким образом, если правило A является наиболее простым применимым правилом с оценкой 20 и может применяться в 4 ячейках, позиция имеет оценку 5.
• Выберите один из "самых простых" вычетов наугад в качестве своей игры и переходите к следующей игровой позиции. Я предлагаю оставить только полностью решенные ячейки для следующей позиции, не переходя ни в какое другое состояние. Конечно, это бесполезно расходует ресурсы процессора, повторяя уже выполненные вычисления, но цель состоит в том, чтобы симулировать игру человека.

Общая сложность головоломки - это сумма баллов позиций на вашем пути через игровое дерево.

РЕДАКТИРОВАТЬ: Альтернативная оценка позиции: вместо того, чтобы полностью исключать вычеты с использованием более сложных правил, рассчитайте общую сложность каждого правила (или составного приложения) и выберите минимум. (Логика здесь заключается в том, что если правило A имеет оценку 50, а правило B имеет оценку 400, и правило A может применяться в одной ячейке, а правило B может применяться в десяти, то оценка позиции составляет 40, поскольку игрок с большей вероятностью определите одну из десяти более сложных игр, чем одну более простую, но это потребует от вас вычисления всех возможностей.)

РЕДАКТИРОВАТЬ: Альтернатива, предложенная Briguy37: Включить все вычеты в балл позиции. Оцените каждую позицию как 1 / (1/d1 + 1/d2 + ...), где d1, d2 и т. Д. Являются индивидуальными вычетами. (Это, в основном, вычисляет «сопротивление совершению любого вычета» в позиции, заданной отдельными «сопротивлениями удержания» d1, d2 и т. Д. Но для этого потребуется вычислить все возможности.)

Надеемся, что эта стратегия выигрыша даст метрику для головоломок, которая увеличивается по мере увеличения вашей субъективной оценки сложности. Если этого не произойдет, то при корректировке баллов ваших правил (или вашего эвристического выбора из указанных выше вариантов) может быть достигнута желаемая корреляция. Как только вы достигнете последовательной корреляции между оценкой и субъективным опытом, вы сможете судить, какими должны быть числовые пороги «легкий», «жесткий» и т. Д. И тогда все готово!

Answer 2

Дональд Кнут изучил проблему и придумал алгоритм Dancing Links для решения судоку, а затем оценил их сложность.

Google вокруг, есть несколько реализаций движка Dancing Links.

Answer 3

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

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

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

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

Майк

Answer 4

Я делал это в прошлом.

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

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

При подсчете sodoku каждой методологии присваивается какое-то значение балла, которое вы бы суммировали для каждого поля, которое вам нужно было заполнить.В то время как «одна пустая ячейка» может получить 0, «Цепь XY» может получить 100. Вы табулируете все необходимые методы (и частоту), и в итоге вы получаете окончательное взвешивание.Есть много мест, в которых перечислены ожидаемые значения для этих весов, но все они довольно эмпирически.Вы пытаетесь смоделировать человеческую логику, поэтому не стесняйтесь придумывать свои собственные веса или улучшать систему (если вы действительно только используете цепочки XY, головоломка, вероятно, проще, чем если бы она требовала более продвинутых механизмов).

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

Кроме того, обратите внимание, что все это требует гораздо больше ресурсов процессора, чем ее решение встандартный, узорчатый способ.Несколько лет назад, когда я писал свой код, для решения некоторых сгенерированных головоломок, которые я создал, потребовалось несколько (я точно забыл, но, может быть, даже до 15) секунд.

Answer 5

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

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

Конечно, я на самом деле не играю в судоку (мне просто нравится писать игры и решатели для него), поэтому я понятия не имею, верный ли это показатель, просто размышляю вслух =)

Answer 6

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

1. Произвольно генерирует фиксированное количество начальных макетов головоломки, скажем, 100.
2. Изначально предложите раздел со случайной сложностью, который позволит пользователю играть в случайные головоломки из доступных макетов.
3. Держите среднее время случайного решения для каждого пользователя. Я бы, наверное, сделал топ-10 / топ X лидеров, чтобы вызвать интерес к игре в случайные головоломки.
4. Сохраняйте средний множитель времени решения для каждого решения головоломки (если пользователь обычно решает головоломку за 5 минут, а решает ее за 20 минут, 4 следует вычислить в множителе среднего времени решения головоломки)
5. После того, как головоломка была сыграна достаточно раз, чтобы получить базовую сложность для головоломки, скажем, 5 раз, добавьте эту головоломку в свой список оцененных головоломок и добавьте еще одну случайно сгенерированную головоломку в доступные макеты головоломки.
   Примечание: Вы должны оставить первую головоломку в своем списке случайных головоломок, чтобы вы могли получать более точную статистику по ней.
6. Как только у вас будет достаточно головоломок с базовым рейтингом, скажем, 50, разрешите пользователям получать доступ к разделу «Оценка сложности» вашего приложения. Трудность для каждой головоломки будет средним множителем времени для этой головоломки.
   Примечание: Когда пользователи предпочитают играть в пазлы с номинальной сложностью, это НЕ должно влиять на среднее время случайного решения или множитель среднего времени решения, если вы не хотите переходить к вычислению взвешенных средних (в противном случае, если пользователь играет много из более сложных головоломок, их среднее время и множители времени будут искажены).

Используя метод, описанный выше, решение будет оценено от 0 (уже решено / нет времени на решение) до 1 (пользователи, вероятно, решат эту головоломку в свое среднее время) до 2 (пользователям, вероятно, потребуется вдвое больше времени для решения). эта головоломка, чем их среднее время) до бесконечности (пользователи будут всегда искать решение этой головоломки).