해결 팁

【체인 추론②】구축편: 교대 규칙과 상태 전달

2025-06-06 · 15 분 읽기

이전 글에서 우리는 체인 추론의 두 가지 기본 구성 요소인 강 연결과 약 연결에 대해 배웠습니다. 이번 글에서는 이러한 연결들을 어떻게 결합하여 완전한 추론 체인을 구축하고, 거기서 유효한 결론을 도출하는지 더 깊이 탐구하겠습니다.

체인 추론 시리즈 (2/3)

← ① 기초편 ② 구축편 (현재) ③ 응용편 →

이 글은 기초편의 이어지는 내용이므로 ①편을 먼저 읽어주세요

체인 구축: 강약 연결을 교대로 연결하여 완전한 추론 경로 형성

체인의 기본 구조

체인은 후보 숫자 노드와 연결로 구성된 순서열입니다. 각 노드는 하나의 후보 숫자(특정 칸의 특정 숫자)를 나타내며, 인접한 노드들은 강 연결 또는 약 연결로 연결됩니다.

         체인의 형식적 표현:

        A ═ B - C ═ D - E ═ F

        여기서:

        • A, B, C, D, E, F는 후보 숫자 노드

        • ═ 는 강 연결을 나타냄

        • - 는 약 연결을 나타냄

        • 전체 체인은 A에서 F까지의 논리적 추론 경로를 설명함

후보 숫자 노드의 표현

체인 추론에서 우리는 일반적으로 다음과 같은 방식으로 후보 숫자 노드를 표현합니다:

위치+숫자: R3C5(4)는 "3행 5열 칸의 후보 숫자 4"를 의미
축약 형식: r3c5=4 또는 (3,5)4

각 노드는 하나의 단언을 나타냅니다: 해당 후보 숫자가 참(그 칸에 해당 숫자가 들어감) 또는 거짓(해당 후보 숫자가 제거됨).

연결의 교대 규칙

유효한 체인을 구축하는 핵심 규칙은: 강 연결과 약 연결이 교대로 나타나야 합니다. 이 규칙은 논리적 추론의 유효성을 보장합니다.

왜 교대해야 하는가?

강 연결: "거짓→참"을 전달하며, "참→참"은 전달할 수 없음
약 연결: "참→거짓"을 전달하며, "거짓→거짓"은 전달할 수 없음

두 개의 강 연결을 연속으로 사용하면 (거짓→참→?), 두 번째 강 연결은 계속 전달할 수 없습니다;
두 개의 약 연결을 연속으로 사용하면 (참→거짓→?), 두 번째 약 연결은 계속 전달할 수 없습니다.
교대로 사용해야만 연속적인 추론 체인을 형성할 수 있습니다.

특수한 경우: 연속 강 연결
여러 개의 강 연결이 연속으로 나타날 때 (예: A ═ B ═ C ═ D), 교대 규칙을 위반하는 것처럼 보이지만, 실제로는 유효합니다.

이유: 강 연결의 조건은 "정확히 하나만 참, 하나만 거짓"이고, 약 연결의 조건은 "최대 하나만 참"입니다. "정확히 하나"는 필연적으로 "최대 하나"를 만족하므로, 모든 강 연결은 동시에 약 연결이기도 합니다.

해석 방법:
A ═ B ═ C ═ D
다음과 같이 이해할 수 있습니다:
A ═ B - C ═ D(중간의 강 연결을 약 연결로 사용)

따라서 표현법상 연속된 강 연결은 오류가 아니며, 중간의 강 연결이 암묵적으로 약 연결의 역할을 담당합니다.

강약 연결 교대 규칙: 교대해야만 유효한 추론 체인 형성 가능

유효한 체인의 패턴

교대 규칙에 따라, 유효한 체인은 다음 형식 중 하나여야 합니다:

1 강 연결로 시작하고 강 연결로 끝남:
A ═ B - C ═ D - E ═ F
체인 길이는 홀수 개의 연결 (강-약-강-약-강)

2 약 연결로 시작하고 약 연결로 끝남:
A - B ═ C - D ═ E - F
체인 길이는 홀수 개의 연결 (약-강-약-강-약)

3 강 연결로 시작하고 약 연결로 끝남 (또는 그 반대):
A ═ B - C ═ D - E
체인 길이는 짝수 개의 연결

색칠 개념 (Coloring)

색칠은 체인 추론을 이해하는 강력한 사고 도구입니다. 우리는 체인의 노드에 두 가지 "색상"을 교대로 부여하여 두 가지 가능한 참거짓 상태를 나타냅니다.

         색칠 규칙:

        체인의 시작점에 색상 A를 부여 (예: 파란색)
강 연결로 연결된 다음 노드에는 반대 색상 B를 부여 (예: 초록색)
약 연결로 연결된 다음 노드에는 같은 색상을 부여
체인의 끝점까지 순서대로 교대

    

색칠 개념: 강 연결은 색상 반전, 약 연결은 색상 유지

색칠의 논리적 해석

강 강 연결은 색상 반전:
강 연결의 양 끝은 "정확히 하나만 참, 하나만 거짓"입니다. 한쪽이 거짓이면 다른 쪽은 반드시 참이고, 한쪽이 참이면 다른 쪽은 반드시 거짓입니다.
따라서 강 연결 양 끝의 색상은 반대이며, 반대의 참거짓 상태를 나타냅니다.

약 약 연결은 색상 유지:
약 연결의 양 끝은 "최대 하나만 참"입니다. 한쪽이 참(색상 A=참)이라고 가정하면, 다른 쪽은 반드시 거짓입니다.
하지만 한쪽이 거짓이면, 다른 쪽의 상태는 불확실합니다. 따라서 색칠할 때 우리는 "이전 노드가 참일 경우"의 상황에 주목하므로, 약 연결 후의 노드는 이전 노드의 "참거짓 가정"과 같습니다.
(참고: 여기서 "색상 유지"는 "참" 상태 전달을 추적할 때의 행동을 의미함)

색칠의 핵심 의미:
같은 색 노드: 모두 참이거나 모두 거짓
다른 색 노드: 참거짓 상태가 반대

색칠을 통해 체인상의 임의의 두 노드 간 참거짓 관계를 빠르게 판단할 수 있습니다.

상태 전달의 두 가지 관점

체인 추론을 이해하는 두 가지 상호보완적 관점이 있습니다: "참" 상태 추적과 "거짓" 상태 추적.

관점 1: "참" 상태 전달 추적

체인의 시작점이 참이라고 가정하고, 이 "참" 상태가 체인을 따라 어떻게 전달되는지 관찰합니다:

A ═ B - C ═ D - E ═ F

A = 참이라고 가정
→ A-B는 강 연결, A가 참일 때 B는 참일 수도 거짓일 수도 있음, 상태 불확실

(순수 강 연결에서는 "참"을 효과적으로 전달할 수 없음)

A - B ═ C - D ═ E - F

A = 참이라고 가정
→ A-B는 약 연결, A가 참 → B는 반드시 거짓
→ B-C는 강 연결, B가 거짓 → C는 반드시 참
→ C-D는 약 연결, C가 참 → D는 반드시 거짓
→ D-E는 강 연결, D가 거짓 → E는 반드시 참
→ E-F는 약 연결, E가 참 → F는 반드시 거짓

결론: A가 참 → F는 거짓

관점 2: "거짓" 상태 전달 추적

체인의 시작점이 거짓이라고 가정하고, 이 "거짓" 상태가 체인을 따라 어떻게 전달되는지 관찰합니다:

A ═ B - C ═ D - E ═ F

A = 거짓이라고 가정
→ A-B는 강 연결, A가 거짓 → B는 반드시 참
→ B-C는 약 연결, B가 참 → C는 반드시 거짓
→ C-D는 강 연결, C가 거짓 → D는 반드시 참
→ D-E는 약 연결, D가 참 → E는 반드시 거짓
→ E-F는 강 연결, E가 거짓 → F는 반드시 참

결론: A가 거짓 → F는 참

         핵심 관찰:

        강 연결로 시작하고 끝나는 체인의 경우:

        • 시작점 거짓 → 끝점 참 ("거짓" 상태 추적을 통해)

        • 시작점과 끝점의 색상은 반대

        약 연결로 시작하고 끝나는 체인의 경우:

        • 시작점 참 → 끝점 거짓 ("참" 상태 추적을 통해)

        • 시작점과 끝점의 색상은 같음

체인에서 결론 도출

유효한 체인을 구축한 후, 제거에 사용할 수 있는 결론을 어떻게 도출할까요? 이는 체인의 구조와 양 끝의 관계에 달려 있습니다.

결론 유형 1: 양 끝에 약 연결 관계가 존재

1 시나리오: 체인의 양 끝 A와 F가 서로 "볼 수 있음" (약 연결 존재)
체인: A ═ B - C ═ D - E ═ F, 그리고 A와 F는 같은 행/열/구역 또는 같은 칸
분석:
• A가 거짓이면 → F는 참 (체인의 전달)
• A가 참이면 → F는 거짓 (A와 F의 약 연결)
결론: A의 참거짓과 무관하게, A와 F 중 반드시 하나는 참 (A가 거짓이면 F가 참, A가 참이면 A 자체가 참).
적용: A와 F를 동시에 볼 수 있는 다른 같은 숫자의 후보를 제거할 수 있습니다!

결론 유형 2: 양 끝이 같은 후보 숫자

2 시나리오: 체인의 양 끝이 정확히 같은 칸의 같은 후보 숫자 (루프 형성)
체인: A ═ B - C ═ D - E ═ A (시작점으로 회귀)
분석:
• A가 거짓이면 → ... → A는 참 (모순!)
결론: A는 거짓일 수 없으므로, A는 반드시 참.

결론 유형 3: 색칠 충돌

3 시나리오: 체인상의 같은 색 두 노드 사이에 약 연결 존재 (서로 볼 수 있음)
분석:
• 같은 색은 참거짓 상태가 같다는 의미
• 약 연결은 동시에 참일 수 없다는 의미
결론: 이 두 노드는 반드시 동시에 거짓. 모든 같은 색 노드는 거짓, 모든 다른 색 노드는 참.

체인에서 결론을 도출하는 세 가지 주요 방법

교대 추론 체인 (AIC)

교대 추론 체인(Alternating Inference Chain, 약칭 AIC)은 체인 추론의 표준 형식입니다. 그 특징은:

강 연결과 약 연결이 엄격하게 교대
강 연결로 시작하고 강 연결로 끝남
체인의 양 끝에 약 연결 관계 존재

         AIC의 표준 형식:

        A ═ B - C ═ D - ... - Y ═ Z

        여기서 A와 Z 사이에는 약 연결이 존재 (서로 볼 수 있음).

        결론: A와 Z 중 반드시 하나는 참이므로, A와 Z를 동시에 볼 수 있는 다른 후보를 제거할 수 있습니다.

AIC는 강력한 프레임워크이며, 많은 구체적 기법들을 특수한 형태의 AIC로 볼 수 있습니다:

X-Wing, Swordfish: AIC로 설명 가능
Skyscraper: 단순한 형태의 AIC
XY-Wing: 3개 노드의 AIC
XY-Chain: 순수 이중값 칸으로 구성된 AIC

체인 구축 실전 기법

실제 문제 풀이에서 유효한 체인을 구축하려면 몇 가지 기법과 경험이 필요합니다:

1 이중값 칸에서 시작:
이중값 칸은 강 연결(칸 내의 두 숫자)을 제공하고, 약 연결(같은 단위의 다른 같은 숫자 후보)을 쉽게 발견할 수 있습니다. 체인 구축의 이상적인 출발점입니다.

2 공액쌍 찾기:
행, 열, 구역에서 두 번만 나타나는 숫자를 찾으세요. 이들이 형성하는 공액쌍은 강 연결의 중요한 원천입니다.

3 연결 유형 판단에 주의:
같은 후보 숫자 쌍 사이에 강 연결과 약 연결이 동시에 존재할 수 있습니다(예: 이중값 칸 또는 공액쌍). 체인을 구축할 때 어떤 연결을 사용하는지 명확히 해야 합니다.

4 목표 지향적 접근:
특정 후보 숫자 X를 제거하고 싶다면, 체인의 양 끝이 모두 X를 "볼 수 있도록" 체인을 구축해 보세요.

흔한 실수:

두 개의 약 연결을 연속으로 사용 (상태를 전달할 수 없음)
약 연결을 강 연결로 잘못 판단 (잘못된 결론 도출)
체인 양 끝의 관계 검증 누락 (결론을 도출할 수 없음)

참고: 연속 강 연결은 허용됩니다. 강 연결을 약 연결로 사용할 수 있기 때문입니다 (위 "특수한 경우" 참조)

다음 단계

이 글에서는 체인을 구축하는 방법과 체인에서 결론을 도출하는 방법을 소개했습니다. 다음 글에서는 다음을 논의하겠습니다:

체인의 다양한 응용 패턴 (열린 체인, 닫힌 체인, 루프)
일반적인 체인 기법의 통합적 이해
그룹 연결과 복잡한 체인 구조
불연속 루프와 고급 추론

관련 읽기:

체인 추론 기초 - 강 연결과 약 연결 개념 복습
XY 체인 기법 - 체인 추론의 구체적 응용
마천루 기법 - 단순 AIC의 실례

체인 추론 기초 체인 응용 패턴 기법 목록