Алгоритм генератора судоку
Я создал алгоритм генерации судоку, но он оказался ужасно неэффективным. На создание каждой головоломки уходило несколько минут. Так что теперь я пытаюсь снова написать его оптимальным образом.Но у меня возникли проблемы, с которыми мне нужна помощь.
- Есть два подхода: начните с пустой сетки и добавьте числа, а затем проверьте, разрешима ли она. Второй подход состоит в том, чтобы создать полную действительную сетку со всеми 81 числом, а затем удалять, пока мы не будем довольны количеством оставшихся чисел, и она все еще будет разрешима.
Сначала я использовал первый подход, но теперь я собираюсь использовать второй, потому что я думаю, что он более эффективен (мы начинаем с правильной головоломки, которая гарантированно разрешима). Я прав, что второй подход лучше?
Когда я пытаюсь создать полностью заполненную сетку, я сталкиваюсь с трудностями. Мой алгоритм:
- Задайте кандидатов для каждой ячейки. Изначально это числа от 1 до 9.
- Выбрать случайную ячейку без значения.
- Выберите случайного кандидата из этой ячейки и назначьте его как значение ячейки. Остальные кандидаты отброшены.
- Теперь для каждой строки, ячейки и квадрата, соответствующих назначенной ячейке, я удаляю значение ячейки из этих кандидатов, поэтому каждое число является уникальным в строке / столбце / квадрате
- Повторение
Этот метод гарантирует случайную сетку без дублирования числа. Однако в большинстве случаев, когда я не нарушаю никаких правил размещения, возникает конфликт - например, пустые ячейки, из которых удалены все кандидаты, и т. Д., И мне нужно начинать заново. Есть ли более элегантный / эффективный способ заполнить всю сетку числами без нарушения правил размещения и по-прежнему случайными числами?
Спасибо.