Создание судоку желаемой сложности?

Question

Итак, я сделал небольшую часть чтения в поколение головоломки судоку. Из того, что я могу сказать, стандартный способ иметь головоломку Sudoku с желаемой трудностью состоит в том, чтобы создать головоломку, а затем оценивать ее и повторять до тех пор, пока у вас не будет приемлемого рейтинга. Это может быть усовершенствовано путем генерации с помощью backtracing с использованием некоторых более сложных шаблонов решения (XY-wing, swordfish и т. Д.), Но это не совсем то, что я хочу сделать здесь.

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

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

Кто-нибудь знает что-то вроде этого? Или, может быть, с подобной методологией?

Answer 1

Это не так элегантно, как то, что вы просите, но вы можете имитировать это поведение с кэшированием:

1. Решите, сколько «ведра» вы хотите для головоломок. Например, предположим, что вы выбираете 20. Таким образом, ваши ведра будут содержать головоломки разных диапазонов сложности: 0-.05, .05-.1, .1-.15, .., .9-.95, .95- 1
2. Генерация головоломки
3. Grade головоломка
4. Поместите его в соответствующем ведре (или выбросить его, когда ковш заполнен)
5. Повторять до ваших ковши «заполненные». Размер ведер и места их хранения будет основываться на потребностях вашего приложения.

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

Answer 2

Ну, вы не можете знать, насколько это сложно, прежде чем вы узнаете, как его решить. И решение Sudoku (и, следовательно, рейтинг сложности) относится к NP-C complexity class, это означает, что логически невозможно найти алгоритм, который (асимптотически) быстрее, чем предлагаемый случайный догадка и проверка.

Однако, если вы можете найти, вы решили P versus NP problem и должен очистить шкаф для Fields Medal ... :)

Answer 3

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

Звучит как теория информации, да, здесь есть приложения.

Головоломки Sudoku должны иметь уникальное решение. Кроме того, головоломки судоку имеют определенные симметрии, то есть по строке, по столбцу и по квадрату.

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

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

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

Answer 4

Добавление другого ответа для создания судоку желаемой сложности на лету.

Это означает, что в отличии от других подходов алгоритм работает только один раз и возвращает конфигурацию судок соответствия желаемой трудности (с высокой вероятностью в пределах диапазона, или с вероятностью = 1)

различных решений для генерации (и рейтинг), трудности с судоку связаны с human-based techniques and approaches, что может быть легко оценено.

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

Проблема с этим подходом (и требование для случая использования я имел)

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

2. Нужно (до) генерировать много судоку, которое может быть оценено только с точки зрения сложности после решения человеком-подобным решателем. Таким образом, невозможно создать желаемую судоку на лету.

3. Человекоподобный решатель может быть сложным и в большинстве случаев (если не все) плотно связан с сетками судоку 9x9. Поэтому нет простого обобщения на другие судокусы (например, 4x4, 16x16, 6x6 и т. Д.)

4. Оценка сложности человекоподобных методов очень субъективна. Например, почему x-wing принято сложнее, чем скрытых синглов? (Персонально были решены многие сложные опубликованных судоку Мануалы и никогда не использовали такие методы)

Другой подход был использован, который имеет следующие преимущества:

1. хорошо обобщается на произвольное судоку (9x9, 4x4, 6x6 , 16x16 и т. Д.)
2. Конфигурация sudoku с желаемой трудностью генерируется один раз и на лету
3. Оценка сложности является объективной.

Как это работает?

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

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

Расширение Мои previous answer, было отмечено, что для любого судоку головоломки минимальное количество ключей является объективным свойством головоломки (например for 9x9 grids the minimum number of clues for having a valid sudoku is 17)

можно начать оттуда и вычислить минимальное количество ключей на трудности уровень (линейная корреляция).

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

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

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

(использовали этот интернет-sudoku solver (а также this one) соотносить ставки сложности тестового судоку)

код доступен бесплатно on github sudoku.js (along with sample demo application), уменьшенная версия CrossWord.js профессиональный кроссворд строитель в JavaScript, одним и тем же автором