강제
강제
관련 기법
추측인가? 강제 체인 논란
강제 체인는 증명 기법으로 사용될 때 추측이 아니다. 선택한 시작점에서 모든 분기를 일시적으로 조사하고, 각 분기를 논리적으로 전파하며, 모든 분기가 지지하는 결론 또는 모순에 의해 강제되는 결론만 남긴다.
추측과의 핵심 차이는 확신이다. 추측은 하나의 분기를 골라 그것이 참인 것처럼 계속한다. 포싱 체인은 시작점에서 관련된 모든 분기를 비교하고 그 비교가 무언가를 증명할 때만 행동한다.
강제 체인는 패턴 기반 기법보다 우아하지는 않지만, 모든 분기가 정확히 확인되었다면 그 결론은 증명 가능하게 옳다.
셀 포싱 체인
이중값 셀 {A, B}에서 시작한다. 각 분기의 함의를 전파한다. 결과를 비교한다.
모순: 한 분기가 유효하지 않으므로 셀는 다른 후보여야 한다.
배치로의 수렴: 두 분기가 같은 숫자를 같은 멀리 떨어진 셀에 강제한다.
제거로의 수렴: 두 분기가 같은 셀에서 같은 후보를 제거한다.
영역 포싱 체인(숫자 포싱 체인)
하우스에서 어떤 숫자의 2~3개 위치에서 시작한다. 각 위치를 분기로 탐색한다. 추론 유형은 같은 세 가지다.
셀 포싱은 이중값 셀이 멀리까지 영향을 미칠 때 효과적이다. 영역 포싱은 어떤 숫자의 위치가 강한 연쇄 효과를 가질 때 효과적이다.
포싱 네트: 분기 수 확장
셀 포싱 네트: 후보가 3~6개인 셀. 영역 포싱 네트: 어떤 숫자에 대해 4~6개 위치를 가진 하우스. 분기가 많아지고 비용이 커지지만, 강제 체인가 찾을 수 없는 추론을 찾아낼 수 있다.
논리는 동일하다. 분기 수만 다를 뿐이다.
전파 엔진
각 분기는 네이키드 싱글, 히든 싱글, 잠긴 후보, 네이키드 페어를 통해 안정될 때까지 반복적으로 전파된다. 하나의 가정이 보드 전체에 걸쳐 수십 개의 중간 단계로 파급될 수 있다.
두 분기가 완전히 다른 경로를 통해 같은 결론에 도달하면, 그 수렴은 결론을 확실하게 증명한다.
세 가지 추론 유형
모순: 어떤 분기가 잘못된 상태를 만들어낸다. 그 가정은 거짓이다. 가장 흔한 유형.
배치로의 수렴: 모든 분기가 같은 숫자를 같은 셀에 강제한다. 덜 흔하지만 결정적.
후보 제거로의 수렴: 모든 분기가 같은 셀에서 같은 후보를 제거한다. 가장 미묘한 유형.
강제 기법을 사용할 때
마지막 논리적 수단. 패턴 기반 기법과 더 깔끔한 체인이 실패한 후에 적용한다.
2~3개 분기의 강제 체인를 먼저 시도한다. 3~6개 분기의 강제 네트는 더 비용이 많이 들어 보통 나중으로 미룬다. 둘 다 레벨 12(극한)이다.
컴퓨터 솔버에게 유계 강제는 강력한 증명 엔진이지만 자동으로 완전하지는 않다. 완전성은 필요한 가정을 모두 포괄할 만큼 탐색을 충분히 확장할 때만 얻어지며, 이는 완전 탐색 백트래킹에 가까워진다. 실제로 강제는 고정 깊이 솔버가 모든 유효한 퍼즐을 풀 수 있다는 보장이라기보다 통제된 논리 탐색으로 설명하는 것이 가장 적절하다.
우아함과 완전성에 관한 철학적 고찰
패턴 기반 기법은 구조적 관계를 드러내며 더 우아하다. 그러나 강제 수준의 논리가 필요한 유효한 퍼즐도 존재한다. 강제 기법은 패턴 기반 기법이 다루지 못하는 모든 퍼즐을 잡아내는 안전망이다.
가장 만족스러운 접근: 먼저 모든 패턴 기반 기법을 시도하고, 퍼즐이 진정으로 요구할 때만 강제에 의존한다.
요약
강제 체인와 강제 네트는 가장 강력한 논리 기법 중 하나로 레벨 12(극한)에 속한다. 선택한 시작점에서 모든 분기를 탐색하고 결과를 전파하며 비교한다. 추론은 모순, 배치로의 수렴, 후보 제거로의 수렴을 통해 이루어진다. 이들은 무차별 백트래킹 전의 마지막 수단이며, 실용적 한계 없이 확장하면 완전한 탐색 증명이 되지만, 유계 인간식 강제는 표적화된 고급 기법으로 남는다.
관련 기법