Уровень сложности Sudoku

Ответ 1

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

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

Решите головоломку. В каждой позиции:

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

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

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

EDIT: Альтернатива, предложенная Briguy37: Включите все вычеты в счете позиции. Оцените каждую позицию как 1 / (1/d1 + 1/d2 + ...), где d1, d2 и т.д. - отдельные вычеты. (Это в основном вычисляет "сопротивление выполнению какого-либо вывода" в позиции с учетом индивидуальных "сопротивлений вычитания" d1, d2 и т.д. Но для этого потребуется вычислить все возможности.)

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

Ответ 2

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

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

Ответ 3

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

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

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

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

Mike

Ответ 4

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

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

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

Ответ 5

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

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

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

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

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

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

Ответ 6

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

• Произвольно создавайте фиксированное количество начальных макетов головоломок, скажем 100.
• Сначала предложите случайный раздел сложности, который позволяет пользователю играть случайные головоломки из доступных макетов.
• Сохраняйте среднее случайное время решения для каждого пользователя. Я бы, вероятно, сделал топ-10/топ-лидеров X для этого, чтобы вызвать интерес к случайным головоломкам.
• Сохраняйте средний множитель времени решения для каждого решения головоломки (если пользователь обычно решает головоломку через 5 минут и решает ее через 20 минут, 4 следует добавить к среднему множителю времени решения головоломок)
• Как только головоломка была сыграна достаточно раз, чтобы получить базовую трудность для головоломки, скажем, 5 раз, добавьте эту головоломку в свой список головоломок и добавьте еще одну случайную головоломку к вашим доступным макетам головоломок.
  Примечание:. Вы должны сохранить первую головоломку в своем списке случайных головоломок, чтобы вы могли получить лучшую и лучшую статистику по ней.
• Как только у вас будет достаточно основанных на базе головоломки головоломок, скажем 50, разрешите пользователям получать доступ к разделу "Rated Difficulty" вашего приложения. Трудность для каждой головоломки будет средним умножителем времени для этой головоломки.
  Примечание.. Когда пользователи предпочитают играть головоломки с заданной сложностью, это НЕ должно влиять на среднее случайное время решения или средний множитель времени решения, если вы не хотите входить в расчет взвешенных средних значений (в противном случае, если пользователь играет много более сложных головоломок, их средние множители времени и времени будут искажены).

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