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