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

Ответ 1

Просто:

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

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

Ответ 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 3

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

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

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

Ответ 4

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

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

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

Ответ 5

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

Ответ 6

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

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

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

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

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

Ответ 7

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

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

Шаг 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

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

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

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

Ответ 8

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

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

Ответ 9

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

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

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

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

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