Генерация минимального / несводимого судоку

Question

Головоломка судоку является минимальной (также называемой неприводимой), если она имеет уникальное решение, но удаление любой цифры приведет к головоломке с несколькими решениями. Другими словами, каждая цифра необходима для определения решения.

У меня есть базовый алгоритм для генерации минимального судоку:

• Создайте законченную загадку.
• Посетите каждую клетку в случайном порядке. Для каждой посещенной ячейки:
  • Предварительно убрать свою цифру
  • Решите головоломку дважды, используя рекурсивный алгоритм возврата. Один решатель пробует цифры 1-9 в прямом порядке, другой в обратном порядке. В некотором смысле, решатели обходят дерево поиска, содержащее все возможные конфигурации, но с противоположных концов. Это означает, что оба решения будут совпадать, если головоломка имеет уникальное решение.
  • Если у головоломки есть уникальное решение, удалите цифру навсегда; в противном случае, верните его обратно.

Этот метод гарантированно создает минимальную головоломку, но он довольно медленный (100 мс на моем компьютере, несколько секунд на смартфоне). Я хотел бы сократить количество решений, но все очевидные способы, которые я могу придумать, неверны. Например:

• Добавление цифр вместо их удаления. Преимущество этого состоит в том, что, поскольку для минимальных головоломок требуется не менее 17 заполненных цифр, первые 17 цифр гарантированно не будут иметь уникального решения, что сокращает объем решения. К сожалению, поскольку ячейки посещаются в случайном порядке, перед добавлением одной важной цифры, которая "запирает" уникальное решение, будет добавлено много ненужных цифр. Например, если все первые 9 добавленных ячеек находятся в одном и том же столбце, там много избыточной информации.
• Если никакая другая цифра не может заменить текущую, сохраните ее и не решайте загадку. Поскольку проверка легальности размещения в тысячи раз быстрее, чем решение головоломки дважды, это может значительно сэкономить время. Однако то, что сейчас нет другой допустимой цифры, не означает, что ее не будет позже, как только мы удалим другие цифры.
• Поскольку мы создали исходное решение, решите только один раз для каждой ячейки и посмотрите, соответствует ли оно оригиналу. Это не работает, потому что оригинальное решение может быть в любом месте дерева поиска возможных решений. Например, если исходное решение находится рядом с "левой" стороной дерева, и мы начинаем поиск слева, мы пропустим решения в правой части дерева.

Я также хотел бы оптимизировать сам алгоритм решения. Сложная часть - определить, является ли решение уникальным. Я могу сделать микрооптимизации, такие как создание битовой маски легальных мест размещения для каждой ячейки, как описано в этом замечательном посте. Однако более продвинутые алгоритмы, такие как Dancing Links или имитация отжига, предназначены не для определения уникальности, а просто для того, чтобы найти какое-либо решение.

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

Answer 1

Вот основные оптимизации, которые я реализовал с (весьма приблизительным) процентным увеличением скорости:

• Использование битовых масок для отслеживания того, какие ограничения (строка, столбец, поле) выполняются в каждой ячейке. Это значительно ускоряет поиск законности места размещения, но медленнее делает размещение. Сложный фактор при создании головоломок с битовыми масками, а не просто их решение, заключается в том, что цифры, возможно, должны быть удалены, что означает, что вам нужно отслеживать три типа ограничений как отдельные биты. Небольшая дальнейшая оптимизация - сохранение масок для каждой цифры и каждого ограничения в массивах. 40%
• Сроки генерации и перезапуска, если это занимает слишком много времени. Смотрите здесь. Оптимальная стратегия состоит в том, чтобы увеличивать период ожидания после каждого неудачного поколения, чтобы уменьшить вероятность того, что оно продолжается бесконечно. 30%, в основном за счет сокращения времени выполнения в худшем случае.
• Предложения mbeckish и user295691 (см. комментарии к исходному сообщению). 25%

Answer 2

У меня есть идея on the 2nd option Вы предложили, будет лучше для этого, если вы добавите 3 дополнительных проверки для первых 17 номеров

• найти список из 17 случайных чисел от 1 до 9

• добавить каждый элемент в произвольном расположении

  1. эти новые номера не соответствуют 3 основным критериям судоку

     • в одном ряду нет одинакового номера
     • в том же столбце нет одинакового номера
     • в той же матрице 3х3 нет одинакового номера

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

  3. если следующей строки (т.е. в 9-м столбце или 9-й строке) нет, добавьте в 1-й столбец после заполнения 17 символов, запустите логическую схему решения этой проблемы и найдите свое уникальное решение.