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

Question

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

Answer 1

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

---

1. Начните с полной, действительной доски (заполненной 81 цифрой).

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

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

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

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

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

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

---

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

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

---

1. Начните с пустой доски.

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

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

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

Answer 2

Легко:

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

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

Answer 3

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

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

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

Answer 4

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

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

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

Answer 5

Решение делится на 2 части:
A. Генерация числового шаблона 600 миллиардов
B. Создание шаблона маскирования ~ 7e23 комбинаций

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

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

Первая строка - числа в порядке возрастания
Второй ряд также в порядке возрастания, но начинается с 4 и вращается вокруг
Третий ряд также находится в порядке возрастания, но начинается с 7 и вращается вокруг
Строка 4,5,6: заменить столбец из трех ячеек на верхний правый столбец - 2 5 8 и перевернуть ячейку 3x3 для последнего столбца
Строка 7,8,9: заменить столбец из трех ячеек на верхний правый столбец - 3 6 9 и перевернуть ячейку 3x3 для последнего столбца

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
9 7 8 3 1 2 6 4 5

Шаг 2. Перемешайте цифры и замените все остальные ячейки
Шаг 3. Произвольно переставить столбцы 1,2 и 3 внутри себя
Шаг 4. Произвольно переставить столбцы 4,5 и 6 внутри себя
Шаг 5. Произвольно переставить столбцы 7,8 и 9 внутри себя
Шаг 6. Произвольно переставить ряды 1,2 и 3 внутри себя
Шаг 7. Произвольно переставить ряды 4,5 и 6 внутри себя
Шаг 8. Произвольно переставить строки 7,8 и 9 внутри себя
Шаг 9. Произвольно переставить в 3 группы столбцов размером 9x3
Шаг 10. Произвольно переставить в 3 ряда строк размером 3х9

вуаля ...

5 8 3 1 6 4 9 7 2
7 2 9 3 5 8 1 4 6
1 4 6 2 7 9 3 8 5
8 5 2 6 9 1 4 3 7
3 1 7 4 2 5 8 6 9
6 9 4 8 3 7 2 5 1
4 6 5 9 1 3 7 2 8
2 3 1 7 8 6 5 9 4
9 7 8 5 4 2 6 1 3

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

Шаг 1. Начните с выбора 15 случайных местоположений из 81.
Шаг 2: Проверьте с помощью решателя, есть ли у него уникальное решение
Шаг 3: Если решение не уникально, выберите дополнительное местоположение. повторять шаги 2 и 3, пока не будет найдено уникальное решение

Это должно дать вам очень уникальную и быструю доску судоку.

Answer 6

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

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

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

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

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

Answer 7

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

Answer 8

Один способ быстрее создать судоку.

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

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

Вы можете пометить судоку с 9 сетками, обмен строк и столбцов должны выполняться в одной сетке. Как вы можете поменять строки 1-3, строки 4-6, строки 7-9, не обменивать строки 1-4 или строки 1-7. Вы также можете поменять сетку строк (поменять строку 1 ~ 3 на строку 4 ~ 6 или строку 7 ~ 9).

Решите судоку: запишите пустое со всеми возможными значениями, затем проверьте значение от 1 до 9. Если одно значение уникально, удалите его из цикла.

Answer 9

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

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