7 ответов:
просто:
- найти все решения с эффективным алгоритмом обратного отслеживания.
- Если есть только одно решение, вы молодец. В противном случае, если у вас есть более одного решения, найдите позицию, в которой большинство решений отличаются. Добавьте число в этой позиции.
- перейти к 1.
Я сомневаюсь, что вы можете найти решение, которое бы значительно быстрее.
вот как это делает моя собственная программа судоку:
начните с полной, действительной доски (заполненной 81 номером).
составьте список всех 81 позиций ячеек и перемешайте его случайным образом.
пока список не пуст, возьмите следующую позицию из списка и удалите номер из связанной ячейки.
проверить уникальность с помощью быстрого обратного поиска решателя. Мой решатель-это - в теории-способен посчитать все решения, но для проверки уникальности он сразу остановится, когда найдет более одного решения.
если текущая плата имеет еще только одно решение, перейдите к шагу 3)и повторите.
если текущая плата имеет более одного решения, отменить последнее удаление (Шаг 3), и Продолжить Шаг 3 со следующей позиции из списка
остановитесь, когда вы проверили все 81 должностное положение.
Это дает вам не только уникальные доски, но доски, где вы не можете удалить больше чисел, не разрушая уникальность решения.
конечно, это только вторая половина алгоритма. Первая половина состоит в том, чтобы сначала найти полную действительную доску (случайным образом заполненную!) Работает очень похоже, но "в другую сторону":
начать с пустого правление.
добавить случайное число в одну из свободных ячеек (ячейка выбирается случайным образом, и число выбирается случайным образом из списка чисел, действительных для этой ячейки в соответствии с правилами судоку).
используйте решатель обратного хода, чтобы проверить, имеет ли текущая плата хотя бы одно допустимое решение. Если нет, отмените Шаг 2 и повторите с другим номером и ячейкой. Обратите внимание, что этот шаг может привести к созданию полных действительных плат самостоятельно, но это никоим образом не так случайность.
повторяйте, пока доска не будет полностью заполнена цифрами.
вы можете обмануть. Начните с существующей доски судоку, которая может быть решена, а затем поиграйте с ней.
вы можете поменять любую строку из трех блоков 3x3 с любой другой строкой. Вы можете поменять любой столбец из трех блоков 3x3 на другой столбец. Внутри каждой строки блока или столбца блока вы можете поменять местами отдельные строки и отдельные столбцы. Наконец, вы можете переставлять числа, чтобы в заполненных позициях были разные числа, если перестановка согласована по всему объему правление.
ни одно из этих изменений не сделает разрешимую плату неразрешимой.
Если P = NP, не существует алгоритма полиномиального времени для генерации общих задач судоку с ровно одним решением.
в своей магистерской диссертации Такаюки Ято определил Другое Решение Проблемы (ASP), где целью является, учитывая проблему и некоторое решение, найти другое решение этой проблемы или показать, что его нет. Ято затем определил ASP-полноту, задачи для которых трудно найти другое решение, и показал, что судоку является Жерех-полный. Поскольку он также доказывает, что ASP-полнота подразумевает NP-твердость, это означает, что если вы допускаете доски судоку произвольного размера, нет алгоритма полиномиального времени, чтобы проверить, имеет ли головоломка, которую вы создали, уникальное решение (если только P = NP).
Извините, что испортил ваши надежды на быстрый алгоритм!
Это не легко дать общее решение. Вам нужно знать несколько вещей, чтобы создать определенный вид судоку... например, вы не можете построить судоку с более чем девятью пустыми группами из 9 чисел (строки, блоки 3x3 или столбцы). Минимальные заданные числа (т. е. "подсказки") в судоку с одним решением считаются 17, но числовые позиции для этого судоку очень специфичны, если я не ошибаюсь. Среднее количество подсказок для судоку составляет около 26, и я не уверен, но если вы выходите из числа a заполненную таблицу до 26 и в симметричном случае, вы можете иметь действительный судоку. С другой стороны, вы можете просто случайно выйти из числа завершенных сеток и проверить их с помощью CHECKER или других инструментов, пока не появится ОК.
Я также думаю, что вам придется явно проверить уникальность. Если у вас меньше 17 givens, уникальное решение очень маловероятно, хотя: ни один еще не найден, хотя пока не ясно, может ли он существовать.)
но вы также можете использовать SAT-решатель, в отличие от написания собственного алгоритма обратного отслеживания. Таким образом, вы можете в некоторой степени регулировать, насколько трудно будет найти решение: если вы ограничите правила вывода, которые использует SAT-решатель, вы можете проверить если вы можете решить головоломку легко. Просто google для "SAT решения судоку".
вот способ сделать классическую головоломку судоку (головоломка судоку с одним и единственным решением; предварительно заполненные квадраты симметричны вокруг центрального квадрата R5C5).
1) Начните с полной сетки (используя групповое заполнение плюс круговой сдвиг, чтобы получить его легко)
2) Удалите число (ы) из двух симметричных квадратов, если очищенные квадраты могут быть выведены с помощью оставшихся подсказок.
3) повторяйте (2), пока не будут проверены все числа.
используя этот метод вы можете создать очень простой головоломки судоку с или без программирования. Вы также можете использовать этот метод для создания более сложных головоломок судоку. Вы можете искать "создать классическую судоку" на YouTube, чтобы иметь пошаговый пример.
Comments