【체인 추론①】기초편: 강한 링크와 약한 링크

체인 추론(Chain)은 스도쿠 고급 기법의 핵심 이론 프레임워크입니다. 간단한 X-Wing에서 복잡한 AIC에 이르기까지 거의 모든 고급 제거 기법은 체인 추론으로 통합적으로 이해하고 설명할 수 있습니다. 이 글에서는 체인 추론의 가장 기본적이고 중요한 두 가지 개념인 강한 링크와 약한 링크를 깊이 탐구합니다.

체인이란?

스도쿠에서 체인(Chain)은 후보 숫자 간의 특정 논리적 관계를 통해 형성된 연결 시퀀스입니다. 상상해 보세요: 후보 숫자 간에 "A가 참이면 B는 참/거짓"이라는 추론 관계를 확립하고 이러한 관계를 연결하면 체인이 형성됩니다.

체인의 본질은 논리적 전파입니다: 한 시작점에서 출발하여 일련의 논리적 추론을 거쳐 결론에 도달합니다. 이 결론은 일반적으로 다음 목적으로 사용됩니다:

• 특정 후보 숫자가 반드시 참이어야 함을 확정 (배치 확인)
• 특정 후보 숫자가 반드시 거짓이어야 함을 확정 (후보 제거)

체인을 이해하려면 먼저 체인을 구성하는 기본 단위인 링크(Link)를 이해해야 합니다. 링크는 두 후보 숫자 간의 논리적 관계를 설명하며, 관계의 강도에 따라 강한 링크와 약한 링크로 나뉩니다.

강한 링크 (Strong Link)

강한 링크의 출처

강한 링크는 다음 상황에서 발생할 수 있습니다:

1. 이중값 셀 내의 강한 링크 (Bi-value Cell)

셀에 두 개의 후보 숫자만 있을 때, 이 두 후보 숫자 사이에 강한 링크가 존재합니다.

이중값 셀은 가장 일반적인 강한 링크의 출처입니다. 직관적이기 때문입니다: 셀에는 이 숫자 아니면 저 숫자가 들어갑니다.

2. 켤레쌍에 의한 강한 링크 (Conjugate Pair)

어떤 숫자가 유닛(행, 열 또는 박스) 내에서 두 위치에만 나타날 때, 이 두 위치의 해당 후보 숫자 사이에 강한 링크가 존재합니다. 이 관계를 켤레쌍이라고 합니다.

3. 그룹 강한 링크 (Grouped Strong Link)

더 넓게 말하면, 후보 그룹과 다른 그룹 사이에 "정확히 한 그룹이 참" 관계를 만족할 때 강한 링크가 존재합니다. 이것은 고급 기법에서 다루어지며, 이 시리즈의 세 번째 글에서 자세히 논의합니다.

강한 링크의 핵심 속성

약한 링크 (Weak Link)

약한 링크의 출처

약한 링크도 여러 출처가 있습니다:

1. 같은 셀 내 다른 후보 간의 약한 링크

같은 셀 내에서 임의의 두 다른 후보 사이에 약한 링크가 존재합니다.

2. 같은 유닛 내 같은 후보 간의 약한 링크

같은 유닛(행, 열 또는 박스) 내에서 같은 후보의 모든 위치 사이에 쌍별 약한 링크가 존재합니다.

약한 링크의 핵심 속성

강한 링크와 약한 링크 비교

강한 링크와 약한 링크의 차이를 이해하는 것이 체인 추론을 마스터하는 핵심입니다. 비교 표로 정리해 봅시다:

특별한 경우: 강한 링크는 약한 링크이기도 함

여기서 중요한 개념을 이해해야 합니다: 강한 링크는 종종 약한 링크이기도 합니다.

"보는" 개념

체인 추론에서 "보다"(see)라는 개념이 자주 사용됩니다. "보다"를 이해하는 것은 링크 관계를 식별하는 데 중요합니다.

"보는" 관계는 다음 사이에 존재합니다:

• 같은 셀 내의 다른 후보 사이
• 같은 행 내의 같은 후보 사이
• 같은 열 내의 같은 후보 사이
• 같은 박스 내의 같은 후보 사이

이 개념은 체인 응용을 논의할 때 자주 사용됩니다. 예를 들어 "양 끝에서 볼 수 있는 후보는 제거될 수 있다" 등.

왜 강한 링크와 약한 링크를 구별하는 것이 중요한가?

강한 링크와 약한 링크의 구별은 체인 추론의 초석입니다. 그 차이는 다음을 결정합니다:

다음 단계

이 글에서는 체인 추론의 가장 기본적인 두 개념인 강한 링크와 약한 링크를 소개했습니다. 이 개념들을 이해한 후, 이들을 결합하여 완전한 체인을 구축하는 방법을 배울 수 있습니다.

다음 글에서는 다음을 논의합니다:

• 강한 링크와 약한 링크를 번갈아 사용하여 체인을 구축하는 방법
• 체인에서 참/거짓 상태를 전파하는 규칙
• 체인 추론의 "색칠" 접근 방식
• 체인 양 끝에서 결론을 도출하는 방법