Как показать решение sodoku уникально

Question

Учитывая нерешенную содоку, как можно показать, что у нее есть уникальное решение?

Answer 1

Существуют определенные конфигурации, которые в конечном итоге приводят к неуникальному решению, например:

* *  *  | * * * | * * *
* *  *  | * * * | * * *
* 12 12 | * * * | * * *
--------+-------+------
* *  *  | * * * | * * *
* *  *  | * * * | * * *
* 12 12 | * * * | * * *
--------+-------+------
* *  *  | * * * | * * *
* *  *  | * * * | * * *
* *  *  | * * * | * * *

, где * s может быть любым числом, а 12 - единственные возможности в этих ячейках. В этом случае определенно будет как минимум два возможных решения:

* * * | * * * | * * *    * * * | * * * | * * *
* * * | * * * | * * *    * * * | * * * | * * *
* 1 2 | * * * | * * *    * 2 1 | * * * | * * *
------+-------+------    ------+-------+------
* * * | * * * | * * *    * * * | * * * | * * *
* * * | * * * | * * *    * * * | * * * | * * *
* 2 1 | * * * | * * *    * 1 2 | * * * | * * *
------+-------+------    ------+-------+------
* * * | * * * | * * *    * * * | * * * | * * *
* * * | * * * | * * *    * * * | * * * | * * *
* * * | * * * | * * *    * * * | * * * | * * *

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

Существуют некоторые сочетания клавиш, отличные от грубой силы, однако вам необходимо проявлять особую осторожность при написании гибридного решателя. Большинство методов решения Судоку позволяют вам находить несколько решений, если они существуют, но некоторые продвинутые методы решения Судоку основаны на том факте, что надлежащее Судоку имеет уникальное решение, и может привести к тому, что вы не сможете найти второе решение.

Answer 2

Попробуйте найти два решения.

Самый простой алгоритм - это грубая сила рекурсивный алгоритм с возвратом. Как только вы нашли первое решение, вернитесь назад и найдите второе. Это медленно, но (в отличие от алгоритмов, которые опираются только на логику), он гарантированно сможет найти все решения в конце концов. Следовательно, если этот алгоритм завершает работу, найдя только одно решение, то это решение должно быть уникальным.

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

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

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

• Методы решения судоку
  • Одиночная позиция
  • Один кандидат
  • Кандидатные линии
  • и т.д ...

Answer 3

Soduko - это CSP для 81 переменной, по одной на каждую ячейку.Используя имена переменных от A1 до A9 для верхней строки (слева направо), до I1-I9 для нижней строки.Пустые поля имеют домен {1,2,3,4,5,6,7,8,9}, и они уже заполнили домен, состоящий из одного значения.Существует также 27 различных ограничений «все по-разному», по одному для каждой строки, столбца и прямоугольника 9. Боксы

Вы можете использовать алгоритм AC-3 для простых шаблонов или PC-2 для более сложных, ноэто имеет больше вычислительных затрат.

Answer 4

Как уже упоминалось выше, можно использовать рекурсивный алгоритм грубой силы с возвратом. Я хотел бы предложить, просто применив алгоритм два раза один раз вверх; что означает, что значения кандидатов увеличиваются при поиске, а затем с использованием алгоритма в сторону уменьшения, что означает, что значения кандидатов проверяются в порядке убывания от максимально возможного числа до 1, тогда могут быть обнаружены по меньшей мере два решения. Если результаты восходящего и нисходящего подходов остаются прежними, можно сказать, что головоломка имеет уникальное решение.

Answer 5

На мой взгляд, единственный способ это решить. Если вы сможете решить его (не догадываясь - только со 100% «ходами»), то это означает, что у него есть только одно решение. Если вы не сможете решить ее, то я вижу только один способ - использовать алгоритм грубой силы и проверить, сколько реальных решений вы сможете найти.