Принуждение

Это угадывание? Споры вокруг Принудительные цепи

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

Ячейка Цепочка вынужденных ходов

Начните с бивалентной Ячейка {A, B}. Проделайте распространение последствий для каждого из двух вариантов. Сравните результаты. Противоречие: один из вариантов недопустим, значит, Ячейка должен быть другим кандидатом. Сходимость в размещении: оба варианта заставляют один и тот же цифровой элемент появиться в одном и том же отдалённом Ячейка. Сходимость в исключении: оба варианта исключают один и тот же кандидат из одного и того же Ячейка.

Цепочка вынужденного действия (цепочка вынужденного действия по цифре)

Начните с 2-3 позиций цифры в доме. Исследуйте каждую позицию как ветвь. Те же три типа выводов. Ячейка принуждение эффективно, когда бивалентные клетки имеют далеко идущие последствия. Принуждение региона эффективно, когда позиция цифры оказывает сильное каскадное влияние.

Принудительная сеть: Увеличение количества ветвей

Ячейка Силовой сетевой анализ: клетки с 3-6 кандидатами. Сетевой анализ региона: дома с 4-6 позициями для цифры. Более ветвей, более дорого, но можно найти выводы, которые Принудительные цепи не могут. Логика одинакова. Разница только в количестве ветвей.

Двигатель распространения

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

Три типа вывода

Противоречие: ветвь приводит к недопустимому состоянию. Это предположение ложно. Самый распространенный случай. Сходимость по размещению: все ветви заставляют поставить одну и ту же цифру в одно и то же Ячейка. Менее распространенный, но решающий случай. Сходимость по исключению: все ветви исключают одну и ту же кандидатуру из одного и того же Ячейка. Самый тонкий тип.

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

Последний логический выход. Применяется после неудачи всех других методов. Сначала пробуется Принудительные цепи (2-3 ветви). Если цепочки не работают, применяется Принуждающий сет (3-6 ветвей). Оба метода относятся к уровню 12 (Экстремальный). Для компьютерных решателей принуждение обеспечивает полноту: гарантию того, что любая корректная головоломка может быть решена исключительно логикой.

Философская заметка об изяществе и полноте

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

Сводка

Принудительные цепи и forcing net — самые мощные логические техники, на уровне 12 (Экстремальный). Они исследуют все возможности из начальной точки, распространяют последствия и сравнивают результаты. Выводы делаются на основе противоречия, сходимости в размещении или сходимости в исключении. Это последнее средство перед грубым перебором с возвратом, обеспечивая полноту для любого корректного Судоку-пазла.