티스토리 뷰

이번 포스팅에서는 기본적인 전략 바로 다음에 등장하는 전략들을 살펴보고자 합니다.

1. 드러난 부분집합

이전 포스팅에서 우리는 드러난 하나 전략에 대하여 알아본 바 있습니다. 드러난 하나 전략을 후보 숫자들을 셈하는 접근할 경우, 전략의 논리 자체는 칸 한에는 하나의 숫자가 들어가야 한다는 규칙 자체에서 곧바로 따라나왔었지요. 그리고 이 논리는 여러 칸을 동시에 생각하는 경우에도 비슷하게 확장됩니다. 우선 전략부터 살펴보기로 합시다. 이를 위하여, 용어를 하나 정의하고 넘어가겠습니다.

정의. 스도쿠 퍼즐에서 유닛(unit)이란 각각의 행, 열, 혹은 상자를 가리킨다.

이때, 드러난 하나 전략을 일반화한 드러난 부분집합(naked subset) 전략은 다음과 같이 서술할 수 있습니다.

전략 (드러난 부분집합). 주어진 유닛 내에 속한 m개의 주어진 칸을 생각하자. 그리고 그 m개의 칸들 전체에 오직 m개의 후보숫자 k1, ..., km들만 나타나는 상황을 생각하자. 그러한 상황이 성립하면, 그 유닛 내의 다른 모든 칸에서 후보숫자 k1, ..., km들을 모두 지울 수 있다.

이와 같이 한 논리 단위 내에서 m개의 칸에 m개의 후보 숫자가 들어가는 경우 그 m개의 칸들을 드러난 부분집합(naked subset) 혹은 잠긴 부분집합(locked subset)이라고 부릅니다. 말로 설명하면 잘 안 와닿는다는 것을 알기에, 아래와 같은 예제를 준비해보았습니다.

예제 1. 드러난 둘

위의 예제에서 행 J에 주목해봅시다. 칸 J2과 J5는 모두 후보 숫자들로 3과 4를 갖습니다. 따라서 이 두 칸에 올 수 있는 후보 숫자는 총 2개밖에 없습니다. 즉, 두 칸이 이루는 쌍 [J2|J5]가 잠긴 부분집합을 이룹니다. 그러면 드러난 부분집합 전략으로부터 행 J의 나머지 모든 칸에서 3과 4를 지울 수 있습니다. (위의 예제에서 지워진 숫자들은 노란색 바탕에 빨간 X자가 쳐져 있습니다.)

또 다른 예제로, 예제 1의 퍼즐을 계속 진행하다 보면 다음과 같은 상황에 맞닥뜨리게 됩니다.

예제 2. 드러난 둘

위 퍼즐의 상자 9를 주목해보면, [H7|J9]에 올 수 있는 후보 숫자가 오직 2와 9밖에 없습니다. 따라서 [H7|J9]가 드러난 부분집합을 이루므로, 드러난 부분집합 전략에 의해 상자 9 내의 나머지 모든 칸에서 2와 9를 지울 수 있습니다.

이처럼 두 칸이 모여 드러난 부분집합을 이룬 경우를 드러난 둘(naked pair)이라고 부르며, 이로부터 다음과 같은 특수한 관찰을 얻습니다.

전략 (드러난 둘). 주어진 유닛 내에 속한 2개의 주어진 칸을 생각하자. 그리고 그 2개의 칸들 전체에 오직 2개의 후보숫자 a, b만 나타나는 상황을 생각하자. 그러한 상황이 성립하면, 그 유닛 내의 다른 모든 칸에서 후보숫자 ab를 모두 지울 수 있다.

물론 칸이 2개가 아니라 3개, 4개여도 마찬가지 논리가 적용됩니다.

예제 3. 드러난 셋

위의 예제는 열 2에서 세 칸 [B2|D2|E2]가 모여 크기 3짜리 드러난 부분집합을 이룬 경우를 보여줍니다. 왜냐하면 이 세 칸에는 후보 숫자 3, 6, 9만 들어올 수 있으니까요. 이처럼 세 칸이 모여 이루어진 드러난 부분집합을 드러난 셋(naked triple)이라고 부르며, 이로부터 다음과 같은 특수한 케이스를 얻습니다.

전략 (드러난 셋). 주어진 유닛 내에 속한 3개의 주어진 칸을 생각하자. 그리고 그 3개의 칸들 전체에 오직 3개의 후보숫자 ab, c만 나타나는 상황을 생각하자. 그러한 상황이 성립하면, 그 유닛 내의 다른 모든 칸에서 후보숫자 ab, c를 모두 지울 수 있다.

아래 예제는 행 H에서 네 칸 [H1|H3|H4|H6]이 모여 크기 4짜리 드러난 부분집합을 이룬 상황을 보여줍니다. 왜냐하면 이 네 칸에 올 수 있는 후보숫자는 3, 4, 8, 9 이렇게 넷 밖에 없기 때문입니다. 이런 경우를 드러난 넷(naked quad)이라고 부릅니다.

예제 4. 드러난 넷

그리고 이로부터 역시 드러난 부분집합 전략의 특별한 케이스를 얻습니다.

전략 (드러난 넷). 주어진 유닛 내에 속한 4개의 주어진 칸을 생각하자. 그리고 그 4개의 칸들 전체에 오직 4개의 후보숫자 ab, c, d만 나타나는 상황을 생각하자. 그러한 상황이 성립하면, 그 유닛 내의 다른 모든 칸에서 후보숫자 ab, c, d를 모두 지울 수 있다.

아마 어떤 분들은 이러한 논리가 드러난 다섯, 드러난 여섯 등등으로 계속 이어지는지 궁금하실 것입니다. 그러나 9×9 스도쿠에서 드러난 넷을 넘어서는 전략은 사실상 무의미합니다. 그 이유를 다음에 소개할 전략에서 알아보도록 합시다.

2. 숨은 부분집합

각 유닛에 담긴 칸의 개수는 9개이므로, 드러난 넷을 넘어서게 되면 드러난 부분집합의 크기가 유닛 내에 속한 나머지 칸의 개수보다 더 커지는 현상이 발생합니다. 게다가 많은 경우, 이 전략을 써야 하는 단계에 이르러서는 이미 각 논리 단위마다 한두 개 씩의 칸은 이미 결정이 되어있는 상태입니다. 그렇기에 유닛 내의 "드러나지 않은" 칸들의 개수는 훨씬 더 적어지게 됩니다. 이해를 돕기 위해 다음 예제를 봅시다.

예제 5. 드러난 넷?

행 C의 [C4|C5|C6|C9]은 현재 드러난 넷을 형성하고 있습니다. 그러나 실상을 보면, 실제로 의미 있는 나머지 칸들은 단 두 개밖에 없습니다. 이때 쯤 되면 드러난 부분집합 자체보다 그 나머지 부분을 살펴보는 것이 훨씬 더 수월해 보입니다. 실제로, "드러나지 않은" 칸들을 대신 살펴보는 방식의 전략이 존재합니다.

전략 (숨은 부분집합). 주어진 유닛 내에 속한 m개의 칸을 생각하자. 그리고 해당 유닛 내에서, 오직 이 m개의 칸만이 후보들 a1, …, am을 포함하고 있는 상황을 생각하자. 그러면 그 m개의 칸에서 a1, …, am을 제외한 나머지 모든 후보들을 지울 수 있다.

이때 위와 같은 m개의 칸들의 묶음을 숨은 부분집합(hidden subset)이라고 합니다. 어떠한 의미에서, 위 전략은 부분 집합이 드러나 있는 대신 숨어있는 상황으로도 이해할 수 있고, 그러한 특성 때문에 이와 같은 이름이 붙었습니다. 예를 들어 예제 5의 상황을 숨은 부분집합으로 이해하면 다음과 같습니다.

예제 6. 숨은 둘

행 C를 살펴보면, 오직 [C7|C8]만이 후보숫자 3 또는 7을 포함할 수 있습니다. 따라서 [C7|C8]은 숨은 둘(hidden pair)을 이루며, 이로부터 C7과 C8에서 3과 7을 제외한 나머지 후보들을 모두 지울 수 있습니다.

물론 마찬가지 논리로 숨은 셋(hidden triple)이나 숨은 넷(hidden quad) 등도 생각할 수 있습니다. 그러나 위의 예제 6만 보더래도, 드러난 넷을 찾는 것보다 숨은 둘을 찾는 것이 딱히 더 쉽다고 이야기하기 힘들 정도로 숨은 부분집합은 찾기 힘듭니다. 사실 드러난 부분집합과 숨은 부분집합은 같은 논리를 다른 방식으로 해석한, 서로 쌍보적인 관계에 있는 전략입니다. 때문에 둘 중 어떤 것을 사용해도 결론은 같고, 따라서 둘 중 어떤 것을 선호할지는 여러분들의 성향에 달렸다고 할 수 있습니다.

<< [이전 글] 스도쿠 1 - 기본전략 >> [다음 글] 스도쿠 3 - 교차로 전략

3. 수학도들을 위한 스도쿠

여기서는 입문 파트에서 정의했던 완전 적중 게임에 두루 적용되는 일반적인 전략에 대해 소개해보겠습니다. 이번 포스팅에서 소개한 드러난 부분집합과 숨은 부분집합 전략을 포함하여, 앞으로 소개할 전략들인 교차로, 물고기, X-순환, XY-날개 및 그 확장, W-날개, 핀드 피쉬, 거의 잠긴 집합, Sue de Coq, 불꽃놀이, 교대 추론 사슬 등 스도쿠 동호인들 사이에서 알려진 수많은 전략들이 모두 이 일반적인 전략의 특수한 경우에 해당합니다.

이 파트는 다음과 같이 구성되어 있습니다: 약간 추상적이지만 매우 중요한 개념들을 몇 가지 소개한 후, 메인 정리를 증명할 것입니다. 그리고 메인 정리의 따름정리로서 매우 일반적인 형태의 전략을 소개한 후, 지금까지 소개한 모든 전략들의 이 일반적인 전략의 특수한 경우임을 확인할 것입니다.

3.1. 강한 링크와 약한 링크

수학에서 논리적인 부분을 이야기할 때 거의 항상 등장하는 개념이 바로 존재성(existence)과 유일성(uniqueness)입니다. 존재성과 유일성을 보장받음으로서 수학에서는 많은 일들을 할 수 있지요. 그리고 그것은 스도쿠를 논리적으로 푸는 과정에서도 예외가 아닙니다. 애초에 스도쿠에서는 각각의 규칙 유닛마다 정확히 하나의 연필마크가 들어가야 하기 때문에, 필연적으로 '존재성' (연필 마크가 최소 하나는 포함된다) 과 '유일성' (연필 마크는 기껏해야 하나밖에 올 수 없다) 라는 성질이 논리의 매우 중요한 부분을 차지합니다. 따라서 스도푸를 풀 때 어느 연필 마크들의 집합이 존재성과 유일성을 만족하는지를 아는 것은 매우 중요하며, 이들의 적절한 결합을 통해 풍부한 결론을 내릴 수 있습니다. 이 과정을 돕기 위하여 다음과 같은 용어를 정의하도록 하겠습니다.

정의. 완전 적중 게임 $\mathcal{X} = \{ \texttt{set} : X, \, \texttt{rules} : \mathcal{U} \}$ 및 $X$ 의 부분집합 $P$ 가 주어져 있다고 하자. (여기서 $P$ 는 연필마크들의 집합, 즉 스도쿠 퍼즐 혹은 그 퍼즐을 풀고 있는 도중 상태에 해당한다.)

1. $X$ 의 부분집합 $S$ 가 $P$ 위의 강한 링크(strong link)라는 것은, $P$ 의 임의의 해 $P^{\star}\in\operatorname{Sol}(P)$ 에 대하여 $|S\cap P^{\star}|\geq 1$ 임을 (즉, $S$ 가 해 $P^{\star}$ 와 연필마크를 최소 1개 이상 공유한다는 것을) 뜻한다.

2. $X$ 의 부분집합 $W$ 가 $P$ 위의 약한 링크(weak link)라는 것은, $P$ 의 임의의 해 $P^{\star}\in\operatorname{Sol}(P)$ 에 대하여 $|W\cap P^{\star}|\leq 1$ 임을 (즉, $W$ 가 해 $P^{\star}$ 와 연필마크를 기껏해야 1개만 공유한다는 것을) 뜻한다.

여기서 링크(link)라는 단어가 쓰이는 이유는, 이 개념이 처음 스도쿠 동호인들 사이에서 인지된 계기가 X-사슬이나 연쇄 추론 사슬 등의 사슬 전략에서 유래했기 때문입니다. 그리고 보다시피 각각의 개념은 존재성과 유일성의 개념을 좀 더 퍼즐지향적인 관점에서 서술한 것이지요. 그런데 위 정의에는 한가지 약점이 있습니다. 바로 정의 자체가 퍼즐 $P$ 의 해집합 $\operatorname{Sol}(P)$에 의존한다는 것이지요. 때문에 아무 집합이나 가져다 놓고 이게 강한 링크 혹은 약한 링크인지를 판별하는 것은 매우 어려운 일입니다. (해를 찾기 위해 전략을 적용하는데, 거기서 해에 관한 정보를 이용한다는 게 순서가 거꾸로라는 느낌을 주죠.) 다행스럽게도, $P$ 의 선택에 의존하지 않고 어느 퍼즐 위에서나 항상 절대적으로 강한 링크 혹은 약한 링크가 보장되는 경우가 있습니다.

정리. 임의의 규칙 유닛 $U \in \mathcal{U}$ 는 임의의 퍼즐 $P$ 위에서 강한 링크이자 약한 링크이다.

증명은 매우 간단합니다. 위 정리는 $U$ 가 규칙 유닛이라는 것의 정의를 다시 풀어쓴 것에 불과하니까요. (규칙 유닛이 무엇인지 기억나지 않으신다면 입문 파트의 해당 부분을 체크하고 오시길 바랍니다.) 그리고 이러한 편리성으로 인해, 강한/약한 링크 개념을 이용하는 절대 다수의 전략들은 규칙 유닛들만 이용해서 논증합니다. 물론, 불꽃놀이 전략과 같이 강한 링크 혹은 약한 링크를 직접 찾아서 논증하는 전략들도 소수이지만 분명히 존재하지요. 이는 나중에 다시 언급하기로 하겠습니다.

3.2. 셈하기와 멀티셋

메인 정리 및 이로부터 파생되는 전략들에서는 강한 링크와 약한 링크 여러개를 동시에 고려하며, 이 과정에서 연필 마크의 개수를 셈하는 논증이 사용됩니다. 때문에 여러 집합들의 원소의 개수를 셈하기(counting)의 관점에서 다루는 방법을 알아야 합니다. 이때 다음의 정의가 유용합니다.

정의 (지시 함수). 집합 $X$ 의 부분집합 $A$ 가 주어졌을 때, 함수 $\mathbf{1}_{A} : X \to \{0, 1\}$ 을 $$ \mathbf{1}_{A}(x) = \begin{cases} 1, & x \in A; \\ 0, & x \notin A; \end{cases} $$ 와 같이 정의하고, 이를 $A$ 의 지시 함수(indicator function)라고 부른다.

즉, 지시함수란 각각의 $X$ 의 원소가 $U$ 에 포함되는지 아닌지를 $1$ 과 $0$ 이라는 값으로 지시해서 알려주는 함수가 됩니다. 지시 함수의 개념을 이용하면 집합의 많은 연산들을 함수의 연산으로 대신 표현할 수 있기에, 이 개념은 수학의 여러 분야에서 두루 쓰입니다. 이 포스팅에서 그 모든 쓰임을 알 필요는 없으며, 앞으로 사용될 지시함수의 성질들을 추리면 다음과 같습니다.

정리. 집합 $X$ 의 두 부분집합 $A$, $B$ 를 생각하자.
1. $\mathbf{1}_A \cdot \mathbf{1}_B = \mathbf{1}_{A \cap B}$ 이다. 즉 두 지시함수의 곱은 교집합의 지시함수와 같다.
2. $\sum_{x\in X} \mathbf{1}_A (x) = |A| $ 이다. 즉, 지시함수의 함수값들을 모두 더하면 원래 집합의 크기와 같다.

증명은 매우 간단하므로 그냥 넘어가겠습니다. 한편, 두 지시함수의 합은 일반적으로 합집합과 대응되지 않습니다. 아래의 예제를 살펴봅시다:

예제. 집합 $X = \{ 1, 2, 3, 4, 5 \} $ 의 두 부분집합 $A = \{1, 2, 3\}$ 과 $B = \{2, 3, 5\}$ 를 생각합시다. 그러면 $$ A \cup B = \{1, 2, 3, 5\} $$ 이지만 $$ \mathbf{1}_{A}(x) + \mathbf{1}_{B}(x) = \begin{cases} 1, & x=1 \\ 2 & x=2 \\ 2 & x=3 \\ 0 & x=4 \\ 1 & x=5 \end{cases} $$ 입니다. 즉, 합집합은 중복된 원소를 제거하고 두 집합을 합친다면, 두 지시함수의 합은 '중복도를 따져서' 두 집합을 합치는 과정으로 이해할 수 있습니다.

따라서 두 지시함수의 합은 합집합의 개념이 아니라 소위 멀티셋(multiset)이라고 부르는 개념에 대응됩니다. 중복된 원소를 허용하는 개념이죠. 이를 염두에 두고 있으면, 앞으로 나올 지시함수들의 합을 어떻게 직관적으로 해석해야 할지 감이 오실 것입니다.

3.3. 메인 정리

이번 절에서는 메인 정리를 소개하겠습니다. 메인 정리에 앞서 메인 정리가 왜 셈하기 논증에 속하는지를 설명하기 위한 역할인 보조 정리를 하나 증명한 후 넘어가봅시다.

보조 정리. 완전 적중 게임 $\mathcal{X} = \{ \texttt{set} : X, \, \texttt{rules} : \mathcal{U} \}$ 및 $X$ 의 부분집합 $P$ 가 주어져 있다고 하자. 또한, $X$ 위에서 실수값을 갖는 함수 $f : X \to \mathbb{R}$ 과 실수 $r \in \mathbb{R}$ 이 다음 두 성질을 만족시킨다고 하자.

1. 임의의 $P$ 에 속한 연필마크 $p \in P$ 에 대하여, $f(p) \geq 0$ 이다.
2. 임의의 $P$ 의 해 $P^{\star} \in \operatorname{Sol}(P)$ 에 대하여 $\sum_{p\in P^{\star}} f(p) \leq r$ 이다.

그러면 $P$ 의 임의의 해 $P^{\star} \in \operatorname{Sol}(P)$ 및 그 해에 속한 임의의 연필마크 $p\in P^{\star}$ 에 대하여 $f(p) \leq r$ 이 성립한다.

보조 정리의 증명. 임의의 $P^{\star}\in\operatorname{Sol}(P)$ 와 $p \in P^{\star}$ 를 생각합시다. 그러면 $P^{\star}\subseteq P$ 이므로, $f(\cdot)$ 는 $P^{\star}$ 위에서도 항상 $0$ 이상의 값을 갖습니다. 따라서 $$ f(p) \leq \sum_{x\in P^{\star}} f(x) \leq r $$ 이 성립하고 원하는 바가 증명됩니다. $\square$

이 간단해보이는 관찰은 실제로는 상당히 강력한 내용을 담고 있습니다. 실제로, 이 보조정리의 특수한 경우로서 기다리고 기다리던 메인 정리를 소개하고 증명해봅시다.

메인 정리. 완전 적중 게임 $\mathcal{X} = \{ \texttt{set} : X, \, \texttt{rules} : \mathcal{U} \}$ 및 $X$ 의 부분집합 $P$ 가 주어져 있다고 하자. 또한 다음과 같은 상황을 가정하자.

조건 1. $P$ 위의 강한 링크 $S_1, \ldots, S_m$ 이 주어져 있다.
조건 2. $P$ 위의 약한 링크 $W_1, \ldots, W_n$ 이 주어져 있다.
조건 3. 인덱스 함수 $I(p)$ 를 \begin{align*} I(p) &= \sum_{k=1}^{n} \mathbf{1}_{W_k}(p) - \sum_{j=1}^{m} \mathbf{1}_{S_j}(p) \\ &= \text{[$p$ 를 덮는 $W_k$ 의 개수]} - \text{[$p$ 를 덮는 $S_j$의 개수]} \end{align*} 와 같이 정의했을 때, $P$ 에 속한 임의의 점 $p$ 에 대하여 $I(p) \geq 0$ 이다. (즉, $P$ 위에서 $W_k$ 들이 $S_j$ 들을 덮는다.)

그러면 $P$ 의 임의의 해 $P^{\star} \in \operatorname{Sol}(P)$ 및 그 해에 속한 임의의 연필마크 $p\in P^{\star}$ 에 대하여, 인덱스 함수가 $$I(p) \leq n - m$$ 를 만족시킨다.

이 메인 정리의 직관적인 느낌을 먼저 전달하자면 다음과 같습니다: 강한 링크 $S_1, \ldots, S_m$ 들이 이루는 멀티셋 안에는 최소 $m$ 개 이상의 연필마크가 항상 해에 포함됩니다. 한편, 약한 링크 $W_1, \ldots, W_n$ 들이 이루는 멀티셋 안에는 최대 $n$ 개의 연필마크만 해에 포함될 수 있다는 것이 강제됩니다. 이런 상황에서 만약 퍼즐 $P$ 위에서 약한 링크들이 강한 링크들을 덮으면 (조건 3이 나타내는 부분이 바로 이것입니다), 약한 링크들의 멀티셋에서 나올 수 있는 $n$ 개의 후보숫자 중 최소 $m$ 개가 이미 강한 링크 안에 나타나야 합니다. 따라서 약한 링크들의 멀티셋에서 강한 링크들을 제하고 남은 나머지 부분에서는 최대 $n - m$ 개의 후보숫자만이 추가로 더 나타날 수 있게 됩니다. 이것이 바로 이 메인 정리가 말하고자 하는 바입이다.

메인 정리의 증명. 조건 3에서 정의된 인덱수 함수 $I(\cdot)$ 및 $r = n - m$ 가 보조 정리의 조건을 만족시킴을 확인하면 충분합니다. 우선, 조건 3으로부터 임의의 $p \in P$ 에 대해 $I(p) \geq 0$ 가 성립함은 자명합니다. 한편, $P$ 의 임의의 해 $P^{\star} \in \operatorname{Sol}(P)$ 에 대하여 \begin{align*} \sum_{p \in P^{\star}} I(p) &= \sum_{k=1}^{n} \Biggl( \sum_{p \in P^{\star}} \mathbf{1}_{W_k}(p) \Biggr) - \sum_{j=1}^{m} \Biggl( \sum_{p \in P^{\star}} \mathbf{1}_{S_j}(p) \Biggr) \\ &= \sum_{k=1}^{n} |W_k \cap P^{\star}| - \sum_{j=1}^{m} |S_j \cap P^{\star}| \\ &\leq \sum_{k=1}^{n} 1 - \sum_{j=1}^{m} 1 = n - m = r \end{align*} 입니다. 따라서 보조 정리의 조건이 모두 만족되고 원하는 바가 증명됩니다. $\square$

이제 메인 정리로부터 다음과 같은 전략이 파생됨은 자명합니다.

전략 (잠김 전략). 위 메인 정리와 같은 조건 하에서, 퍼즐 $P$ 에서 인덱스 값이 $n-m$ 보다 큰 연필마크를 지우는 과정은 전략이다. (즉, 해집합을 보존한다.)

이제 지금까지 소개한 모든 전략들이 이 잠김 전략의 예제임을 증명해봅시다.

예제 1. 아래와 같이 규칙 유닛 $S$ 와 $W$ 가 주어져 있다고 합시다. 둘의 구체적인 모양은 딱히 신경쓰지 않고 벤 다이어그램 스타일로 그려봤습니다.

일반적인 퍼즐 $P$ 의 경우, 두 집합에 의해 나뉘는 각 영역마다 연필마크들이 포함될 것이며, 따라서 이 둘을 이용해 정의한 인덱스 함수 $$ I(p) = \mathbf{1}_W(p) - \mathbf{1}_S(p) $$ 의 값은 아래와 같이 주어질 것입니다.

따라서 퍼즐 $P$ 위에서 인덱스 함수가 항상 $0$ 이상의 값을 가지려면, 필연적으로 $S \setminus W$, 즉 $S$ 에는 포함되지만 $W$ 에는 포함되지 않는 부분에 연필마크가 없어야 합니다. 그러한 상황이 실제로 $P$ 위에서 벌어졌다고 합시다. 그러면 잠김 전략으로부터 인덱스가 $r = 1 - 1 = 0$ 보다 큰 점들을 퍼즐 $P$ 에서 모두 지우는 것은 전략이 됩니다.

즉, 이 경우 잠김 전략은 [퍼즐 $P$ 위에서 $S \setminus W$ 위에 연필마크가 없다] 라는 조건이 성립했을 때 [퍼즐 $P$ 위에서 $W \setminus S$ 위에 연필마크가 없다] 라는 결론을 내리게 해 주는 전략임을 알 수 있습니다. 구체적으로,

  • $S = \mathtt{R}_i\mathtt{C}_j$ 와 $W = \mathtt{R}_i\mathtt{N}_n$ 을 각각 [행 $i$ 열 $j$ 에 놓인 칸에 들어갈 수 있는 모든 후보숫자] 와 [행 $i$ 에 놓일 수 있는 모든 후보숫자 $n$] 라고 둡시다. 그리고 퍼즐 $P$ 위에서 $S$ 에 단 하나의 후보숫자 $n$ 만이 올 수 있다고 합시다. (예컨대 $S$ 가 가리키는 칸이 퍼즐 처음부터 단서로 주어져 있거나, 혹은 풀이과정 중에서 해당 칸의 값이 결정되었거나 하는 경우가 있겠지요.) 그러면 $S\setminus W$, 즉 $S$ 에 올 수 있는 후보숫자 중 $n$ 을 제외한 나머지들의 모임이 $P$ 위에서 비어 있으므로, 잠김 전략으로부터 $W\setminus S$ 또한 $P$ 에서 비어 있어야 함을 압니다. 즉, 퍼즐 $P$ 위의 행 $i$ 에서 $S$ 를 제외한 나머지 칸에 있는 후보숫자 $n$ 을 모두 지울 수 있게 되는 것이지요. 이는 곧 기본적인 후보숫자 지우기의 행 방향 버전입니다.
  • 후보숫자 $n$ 을 하나 고정하고, $S$ 를 주어진 유닛(행/열/상자) 위에서 후보숫자 $n$ 이 올 수 있는 가능한 모든 위치라고 합시다. 또한, 퍼즐 $P$ 위에서 $n$ 이 그 유닛 내의 단 한 칸에만 올 수 있다고 합시다. (즉 $n$ 이 숨은 하나가 된 상황을 생각하는 것이죠.) 그러면 $P$ 위에서 그 칸 안에 놓일 수 있는 모든 후보숫자들의 모임을 $W$ 라고 부를 때, 잠긴 전략으로부터 $W$ 에서 후보숫자 $n$ 을 제외한 나머지 후보숫자들을 모두 지울 수 있습니다. 이는 숨은 하나 전략이 됩니다.

예제 2. 아래와 같이 규칙 유닛 $S_1, S_2, W_1, W_2$ 가 주어져 있다고 합시다. ($S_j$ 들은 파란색으로, $W_k$ 들은 녹색으로 표현하였습니다.)

그러면 일반적인 퍼즐 $P$ 위에서 인덱스 함수 $$ I(p) = \mathbf{1}_{W_1}(p) + \mathbf{1}_{W_2}(p) - \mathbf{1}_{S_1}(p) - \mathbf{1}_{S_2}(p) $$ 의 값은 아래와 같이 주어질 것입니다.

이때 $P$ 위에서 $(S_1 \cup S_2) \setminus (W_1 \cup W_2)$ 가 비어있는 상황, 즉 $P$ 위에서 $S_1 \cup S_2$ 속하는 연팔마크들이 항상 $W_1 \cup W_2$ 에도 속하는 상황을 생각합시다. 그러면 잠김 전략으로부터 $W_1 \cup W_2$ 에는 속하지만 $S_1 \cup S_2$ 에 속하지 않는 모든 연필마크들을 $P$ 에서 지울 수 있습니다.

드러난 둘 전략과 숨은 둘 전략은 모두 이 상황의 특수한 예제입니다. (이 상황의 또 다른 예제는 후에 다룰 X-날개 전략입니다.) 또한 이 논리를 확장하면 드러난 부분집합과 숨은 부분집합, 그리고 후에 다를 물고기 전략이 모두 증명됩니다.

 

댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함