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

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

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

• Создайте завершенную головоломку.
• Visit each cell in a random order. For each visited cell:
  • Tentatively remove its digit
  • Решите головоломку дважды, используя алгоритм рекурсивного поиска с возвратом. Один решатель пробует цифры от 1 до 9 в прямом порядке, другой — в обратном. В некотором смысле решатели обходят дерево поиска, содержащее все возможные конфигурации, но с противоположных концов. Это означает, что два решения совпадут, если головоломка имеет единственное решение.
  • Если головоломка имеет единственное решение, удалите цифру навсегда; в противном случае вставьте его обратно.

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

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

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

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