【체인 추론③】응용편: 패턴 분류와 고급 구조
이전 두 편의 글에서 우리는 강한 링크와 약한 링크의 개념과 체인의 구축과 전달 규칙을 배웠습니다. 이 글에서는 체인 추론의 다양한 응용 패턴을 체계적으로 소개하고, 통합된 체인 프레임워크로 다양한 구체적인 기법을 이해하는 방법을 보여드리겠습니다.
형태별 분류: 개방 체인과 폐쇄 체인
체인의 시작과 끝이 연결되어 있는지에 따라 체인은 개방 체인과 폐쇄 체인(루프)으로 나눌 수 있습니다.
개방 체인(Open Chain)
- 체인에 명확한 시작점과 끝점이 있음
- 시작과 끝이 연결되지 않음
- 결론은 시작과 끝 사이의 관계에 기반함
개방 체인은 가장 일반적인 체인 구조입니다. 체인의 양 끝에 약한 링크 관계가 존재할 때(서로 볼 수 있을 때), 후보 숫자를 제거할 수 있습니다.
A ═ B - C ═ D - E ═ FA와 F가 서로 볼 수 있다면(약한 링크가 존재), A와 F 중 하나는 반드시 참이므로, A와 F를 동시에 볼 수 있는 다른 동일 숫자 후보를 제거할 수 있습니다.
폐쇄 체인/루프(Closed Chain / Loop)
- 체인의 끝점이 시작점으로 다시 연결되어 루프를 형성
- 특정 후보의 참/거짓을 직접 결정하는 데 사용 가능
- 루프의 홀짝성이 결론 유형을 결정
폐쇄 체인은 그 구조에 따라 연속 루프(Nice Loop)와 불연속 루프(Discontinuous Loop)로 나뉩니다.
루프의 모든 노드는 두 그룹의 색상으로 나눌 수 있으며, 같은 색은 같은 참/거짓, 다른 색은 반대입니다.
모순점의 후보 숫자는 참 또는 거짓으로 결정될 수 있습니다.
내용별 분류: 단일 숫자 체인과 이중값 체인
체인의 후보 숫자 유형에 따라 체인은 단일 숫자 체인과 이중값 체인으로 나눌 수 있습니다.
단일 숫자 체인(Single-digit Chain)
체인의 모든 노드가 동일한 숫자의 후보입니다. 링크는 공액쌍(같은 단위 내에 해당 숫자가 있는 위치가 두 개뿐인 경우)에서 비롯됩니다.
- 하나의 숫자가 다른 위치에 있는 관계만 추적
- 강한 링크는 공액쌍에서 비롯됨
- 약한 링크는 같은 단위의 다른 위치에서 비롯됨
- 대표 기법: X-Wing, Skyscraper, X-Chain
이중값 체인(Bi-value Chain / XY-Chain)
체인의 모든 노드가 이중값 셀(두 개의 후보 숫자만 있는 셀)에서 비롯됩니다. 링크는 서로 다른 숫자 사이에서 변환됩니다.
- 모든 노드가 이중값 셀에서 비롯됨
- 셀 내의 두 후보 숫자가 강한 링크를 형성
- 인접한 셀이 하나의 후보 숫자를 공유하여 약한 링크 형성
- 대표 기법: XY-Wing, XY-Chain, Remote Pairs
XY-Chain은 순수한 이중값 셀로 구성된 교대 체인입니다. 예를 들어:
R1C1{3,5}(5) - R1C4{5,7}(7) - R3C4{7,9}(9) - R3C8{4,9}(4)시작점은 3, 끝점은 4이며, 시작점과 끝점을 동시에 볼 수 있는 후보 숫자 3과 4를 제거할 수 있습니다.
혼합 체인(Mixed Chain / AIC)
체인에 단일 숫자 체인 노드와 이중값 체인 노드가 동시에 포함됩니다. 이것은 가장 범용적인 체인 구조입니다.
- 다양한 링크 소스를 유연하게 조합
- 단일 숫자 노드와 이중값 노드 사이를 자유롭게 전환 가능
- 표현력이 가장 강하며, 더 많은 제거를 발견 가능
- 대표 기법: AIC(Alternating Inference Chain)
그룹 링크(Grouped Links)
그룹 링크는 여러 후보 숫자를 하나의 전체로 취급하여 체인 추론에 참여시키는 것입니다. 이것은 체인 기법의 적용 범위를 크게 확장합니다.
특정 숫자가 한 단위(행/열/박스) 내의 모든 후보 위치가 다른 단위의 교차 영역에 집중되어 있을 때, 이러한 위치들을 "그룹"으로 간주할 수 있습니다.
예: 박스 1에서 숫자 5가 1행의 세 위치에만 나타나면, 이 세 위치는 그룹으로 체인에 참여할 수 있습니다.
그룹 강한 링크
그룹과 다른 후보 숫자/그룹 사이에 "정확히 하나가 참"인 관계가 만족될 때, 그룹 강한 링크가 존재합니다.
1행의 다른 위치(박스 2와 박스 3)에서 숫자 5가 R1C8 한 위치에만 있고, 이것이 단일점 B를 구성합니다.
그룹 A와 B 사이에는 강한 링크가 존재: 1행에는 반드시 하나의 5가 있어야 하며, 그룹 A(박스 1) 또는 B(R1C8)에 있어야 합니다.
그룹 약한 링크
그룹과 다른 후보 숫자/그룹이 같은 단위에 있을 때, 그들 사이에 그룹 약한 링크가 존재합니다.
불연속 루프(Discontinuous Loop)
불연속 루프는 특수한 폐쇄 체인으로, 어떤 노드에서 "불연속"이 나타납니다 — 즉, 해당 노드의 두 인접 링크가 동일한 유형(모두 강한 링크 또는 모두 약한 링크)입니다.
- Type 1(연속 두 개 강함):불연속점의 후보 숫자는 반드시 거짓
- Type 2(연속 두 개 약함):불연속점의 후보 숫자는 반드시 참
Type 1: 연속 두 개의 강한 링크
A ═ B - C ═ D - ... ═ A(시작점으로 돌아올 때 강한 링크)A가 거짓이라고 가정:
→ 루프의 전달을 거쳐 → A가 참(모순!)
A가 참이라고 가정:
→ 마지막 강한 링크의 다른 끝(X라고 가정)은 참 또는 거짓일 수 있음 → 모순 없음
그러나, X에서 "거짓"을 추적하면:
X거짓 → A참(강한 링크)→ ... → X참
이것은 X가 거짓일 수 없음을 의미하므로, X는 참이고, 따라서 A는 거짓입니다.
결론: 불연속점 A는 반드시 거짓입니다.
Type 2: 연속 두 개의 약한 링크
A - B ═ C - D ═ ... - A(시작점으로 돌아올 때 약한 링크)A가 참이라고 가정:
→ 루프의 전달을 거쳐 → A가 거짓(모순!)
결론: 불연속점 A는 반드시 거짓...잠깐, 이게 맞나요?
실제로 Type 2의 경우 더 신중한 분석이 필요합니다. 올바른 결론은:
"참"을 추적하여 A에서 출발하여 최종적으로 A로 돌아오고 A가 거짓이어야 한다면, 이것은 모순을 만듭니다.
결론: 불연속점 A는 반드시 참입니다.
일반적인 기법의 체인식 이해
많은 다르게 보이는 스도쿠 기법들이 체인 추론 프레임워크로 통합하여 이해할 수 있습니다.
| 기법 명칭 | 체인식 설명 | 체인의 특징 |
|---|---|---|
| X-Wing | 4노드 단일 숫자 체인 루프 | 2행 2열의 공액쌍이 직사각형 형성 |
| Skyscraper | 4노드 단일 숫자 체인 개방 체인 | 두 공액쌍이 한 끝을 공유 |
| 2-String Kite | 4노드 단일 숫자 체인 개방 체인 | 행열 공액쌍이 박스를 통해 연결 |
| XY-Wing | 3노드 이중값 체인 | 축이 두 날개를 연결 |
| XY-Chain | 다노드 이중값 체인 | 순수 이중값 셀 체인 |
| Remote Pairs | 짝수 노드 이중값 체인 | 동일 후보 숫자의 이중값 셀 체인 |
| W-Wing | 혼합 체인 | 이중값 셀이 공액쌍을 통해 연결 |
| AIC | 범용 혼합 체인 | 임의 조합의 교대 체인 |
체인 기법의 선택 전략
실제 문제 해결에서 적절한 체인 기법을 선택하는 방법은 무엇일까요? 다음은 몇 가지 제안입니다:
공액쌍 추론, Skyscraper와 같은 간단한 기법부터 시작하여, 복잡한 AIC를 시도합니다.
이중값 셀은 체인을 구축하는 훌륭한 재료입니다. 이중값 셀이 많을 때는 XY-Wing과 XY-Chain을 우선적으로 고려하십시오.
제거하기 어려운 특정 숫자에 대해, 각 단위에서 공액쌍을 형성하는지 확인하면 단일 숫자 체인을 발견할 수 있습니다.
특정 후보 숫자를 제거하고 싶다면, 양 끝이 모두 해당 후보 숫자를 "볼 수 있는" 체인을 구축해 보십시오.
체인 추론의 가치
체인 추론 이론을 학습하는 가치는 더 많은 고급 기법을 사용할 수 있다는 것뿐만 아니라:
- 통합 이해:하나의 프레임워크로 많은 구체적인 기법을 이해
- 유연한 적용:고정된 패턴에 얽매이지 않고, 상황에 따라 유연하게 체인을 구축
- 새로운 체인 발견:특정 패턴 암기에 의존하지 않고, 원리를 이해한 후 스스로 발견
- 스도쿠에 대한 깊은 이해:논리적 본질에서 후보 숫자 간의 관계 이해
요약
이 세 편의 글을 통해 우리는 체인 추론의 이론적 기초를 체계적으로 학습했습니다:
- 첫 번째 편:강한 링크와 약한 링크의 정의, 출처 및 성질
- 두 번째 편:체인의 구축 규칙, 전달 논리 및 색칠 사상
- 세 번째 편:체인의 분류, 응용 패턴 및 일반적인 기법의 통합 이해
이러한 이론을 마스터하면, 다양한 체인 기법을 이해하고 발견할 수 있는 능력을 갖게 됩니다. 실습에서 지속적으로 적용하고 강화하면, 체인 추론은 복잡한 스도쿠를 해결하는 강력한 무기가 될 것입니다.
스도쿠 게임 시작하기, 체인 사고로 후보 숫자 관계를 분석해 보세요! 어려움에 직면했을 때, 생각해 보세요:
- 어디에 이중값 셀이 있나요? 그들이 체인을 형성할 수 있나요?
- 특정 숫자가 어떤 단위에서 공액쌍을 형성하나요?
- 제거하고 싶은 후보 숫자를 양 끝이 동시에 볼 수 있는 체인을 찾을 수 있나요?