Как создать платы судоку с уникальными решениями

Question

Как вы создаете доску судоку с уникальным решением? Я решил инициализировать случайную доску, а затем удалить некоторые цифры. Но мой вопрос в том, как сохранить уникальность решения?

Answer 1

Easy:

1. Найти все решения с эффективным алгоритмом обратного прослеживания.
2. Если есть только одно решение, все готово. В противном случае, если у вас есть несколько решений, найдите позицию, в которой большинство решений отличается. Добавьте номер в эту позицию.
3. Перейти к 1.

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

Answer 2

Непросто дать общее решение. Вам нужно знать несколько вещей, чтобы создать определенный тип судоку ... например, вы не можете построить судоку с более чем девятью пустыми 9-числовыми группами (строки, 3x3 блоки или столбцы). Минимальные заданные числа (т. Е. «Подсказки») в единственном решении Судоку, как полагают, составляют 17, но числовые позиции для этой Судоку очень специфичны, если я не ошибаюсь. Среднее количество подсказок для судоку составляет около 26, и я не уверен, но если вы оставите числа заполненной сетки до 26 и оставите их симметрично, у вас может быть действительная судоку. С другой стороны, вы можете просто случайно вывести числа из готовых сеток и проверить их с помощью CHECKER или других инструментов, пока не появится OK.

Answer 3

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

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

Ни одно из этих изменений не сделает разрешимую доску неразрешимой.

Answer 4

Вот как моя собственная программа SuDoKu делает это:

---

1. старт с полным, действительным борту (заполняется с 81 номерами)

2. составить список всех 81 ячейки позиции и случайным образом перетасовать его.

3. Пока список не пуст, перейдите в следующую позицию из списка и удалите номер из связанной ячейки

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

5. Если текущая плата имеет только одно решение, перейдите к шагу 3) и повторите.

6. Если текущая плата имеет более чем одно решение, отменить последнее удаление (этап 3), и по-прежнему шаг 3 со следующей позицией из списка

7. стопа, когда вы проверили все 81 позиций.

---

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

Конечно, это только вторая половина алгоритма. Первая половина найти полный действительный совет первый (в случайном порядке заполнения!) Он работает очень похож, но «в другом направлении»:

---

1. начать с пустой доской

2. надстройка случайное число в одной из свободных ячеек (ячейка выбирается случайным образом, а число выбирается случайным образом из списка чисел, действительных для этой ячейки в соответствии с правилами SuDoKu).

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

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

Answer 5

Если P = NP, не существует полиномиальный алгоритм для генерации общих задач судоку ровно одно решение.

В своей магистерской диссертации Такаюки Ято определил The Another Solution Problem (ASP), где цель, заданная проблемой и некоторым решением, найти другое решение этой проблемы или показать, что никто не существует. Затем Ято определил ASP-полноту, проблемы, для которых трудно найти другое решение, и показали, что Sudoku является ASP-полным. Поскольку он также доказывает, что ASP-полнота подразумевает NP-твердость, это означает, что если вы разрешаете доски судоку произвольного размера, нет алгоритма с полиномиальным временем, чтобы проверить, имеет ли головоломка, которую вы создали, уникальное решение (если только P = NP).

Извините, что испортил ваши надежды на быстрый алгоритм!

Answer 6

Я также считаю, что вам придется явно проверить уникальность. Если у вас меньше 17 givens, уникальное решение маловероятно: хотя еще не найдено, хотя пока неясно, может ли он существовать.)

Но вы также можете использовать SAT-решатель, так как против написания собственного алгоритма обратного отслеживания. Таким образом, вы можете в какой-то мере отрегулировать, насколько сложно будет найти решение: если вы ограничиваете правила вывода, используемые SAT-решателем, вы можете проверить, легко ли вы можете решить головоломку. Просто Google для «SAT решения судоку».

Answer 7

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

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

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

3) повторите (2), пока не будут проверены все номера.

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