Принуждение
Принуждение
Связанные техники
Это угадывание? Споры вокруг Принудительные цепи
Принудительные цепи не являются угадыванием, когда используются в качестве метода доказательства. Вы временно исследуете каждый путь из выбранной начальной точки, логически распространяете каждый путь и сохраняете только те выводы, которые поддерживаются каждым путем или вынуждены противоречием.
Ключевое различие от угадывания — обязательство. Угадывание выбирает один путь и продолжает, как будто он истинен. Цепочка вынуждения сравнивает все относящиеся пути из начальной точки и действует только тогда, когда сравнение доказывает что-то.
Принудительные цепи менее изящны, чем методы, основанные на паттернах, но их выводы являются доказуемо верными, когда каждый путь был проверен правильно.
Ячейка Цепочка вынужденных ходов
Начните с бивалентной Ячейка {A, B}. Проделайте распространение последствий для каждого из двух вариантов. Сравните результаты.
Противоречие: один из вариантов недопустим, значит, Ячейка должен быть другим кандидатом.
Сходимость в размещении: оба варианта заставляют один и тот же цифровой элемент появиться в одном и том же отдалённом Ячейка.
Сходимость в исключении: оба варианта исключают один и тот же кандидат из одного и того же Ячейка.
Цепочка вынужденного действия (цепочка вынужденного действия по цифре)
Начните с 2-3 позиций цифры в доме. Исследуйте каждую позицию как ветвь. Те же три типа выводов.
Ячейка принуждение эффективно, когда бивалентные клетки имеют далеко идущие последствия. Принуждение региона эффективно, когда позиция цифры оказывает сильное каскадное влияние.
Принудительная сеть: Увеличение количества ветвей
Ячейка Силовой сетевой анализ: клетки с 3-6 кандидатами. Сетевой анализ региона: дома с 4-6 позициями для цифры. Более ветвей, более дорого, но можно найти выводы, которые Принудительные цепи не могут.
Логика одинакова. Разница только в количестве ветвей.
Двигатель распространения
Каждая ветвь распространяется через голые одиночки, скрытые одиночки, Заблокированные кандидаты и голые пары, итеративно, пока не станет стабильной. Одно предположение может повлиять на десятки промежуточных шагов по всей доске.
Когда две ветви приходят к одному и тому же выводу разными путями, сходимость доказывает достоверность вывода.
Три типа вывода
Противоречие: ветвь приводит к недопустимому состоянию. Это предположение ложно. Самый распространенный случай.
Сходимость по размещению: все ветви заставляют поставить одну и ту же цифру в одно и то же Ячейка. Менее распространенный, но решающий случай.
Сходимость по исключению: все ветви исключают одну и ту же кандидатуру из одного и того же Ячейка. Самый тонкий тип.
Когда использовать методы принуждения
Последний логический выход. Применяется после неудачи методов на основе паттернов и более чистых цепочек.
Сначала пробуются Принудительные цепи с 2-3 ветвями. Принудительные сети с 3-6 ветвями более затратны и обычно используются позже. Оба уровня — 12 (Экстремальный).
Для компьютерных решателей ограниченная принудительная сеть — мощный механизм доказательства, но не является автоматически полной. Полная решаемость достигается только при достаточном расширении поиска, чтобы покрыть необходимые предположения, что приближается к исчерпывающему перебору. На практике принудительный поиск лучше описывать как контролируемый логический поиск, а не как гарантию того, что любой решатель с фиксированной глубиной сможет решить любую корректную головоломку.
Философская заметка об изяществе и полноте
Методы, основанные на паттернах, раскрывают структурные связи и являются более изящными. Однако существуют допустимые головоломки, для решения которых требуется логика уровня принуждения. Методы принуждения — это страховочная сетка, которая ловит каждую головоломку, которую методы, основанные на паттернах, не могут решить.
Самый удовлетворительный подход: сначала попробуйте все методы, основанные на паттернах, а затем прибегайте к принуждению только в том случае, если головоломка действительно этого требует.
Сводка
Принудительные цепи и сетки вынуждения относятся к самым мощным логическим приемам, на уровне 12 (Экстремальный). Они исследуют каждый путь от выбранной начальной точки, распространяют последствия и сравнивают результаты. Выводы делаются на основе противоречия, сходимости к размещению или сходимости к исключению. Это последнее средство перед методом грубой силы с возвратом; если расширить без практических ограничений, они становятся полным доказательством поиска, но ограниченный человеко-подобный метод вынуждения остается целенаправленной сложной техникой.
Связанные техники