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

드러난 부분집합
Strategy : Naked Subset

이전 포스팅에서 우리는 드러난 단일후보에 대하여 알아본 바 있습니다. 드러난 단일 후보를 후보 숫자들을 적어서 푸는 방식으로 접근할 경우, 칸 한에는 하나의 숫자가 들어가야 한다는 규칙으로부너 너무나 당연하게 결론이 따라나왔었지요. 이 아이디어는 여러 칸을 동시에 생각하는 경우에도 비슷하게 확장됩니다. 우선 전략부터 살펴보기로 합시다.

전략 (드러난 부분집합). 어떤 논리 단위(행, 열 혹은 상자) 내에 속한 m개의 주어진 칸 대하여, 그 칸들에 올 수 있는 모든 후보 숫자들의 개수가 총 m개이면, 그 논리 단위 내의 다른 모든 칸에서 그 m개의 후보숫자들을 모두 지울 수 있다.

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

2
4
3
1
2
4
5
6
1
4
8
1
4
8
2
8
9
7
1
2
5
8
9
6
1
5
9
1
3
7
8
2
1
3
7
8
1
8
1
5
8
4
7
1
2
4
8
1
4
9
5
3
1
2
6
4
8
9
4
5
8
7
3
2
4
5
6
8
2
4
8
9
1
2
5
6
8
2
8
1
4
8
9
6
1
5
8
4
7
8
9
7
8
2
5
7
8
7
8
3
2
5
7
8
5
8
3
2
5
6
8
5
6
7
1
9
5
6
7
4
2
4
1
2
4
3
5
9
1
2
8
7
1
4
8
6
5
1
7
1
6
7
1
3
8
4
1
3
6
8
2
9
1
8
1
2
4
6
8
9
1
2
6
1
6
7
1
4
5
1
4
5
3
A
B
C
D
E
F
G
H
J
1
2
3
4
5
6
7
8
9
예제 1. 드러난 후보쌍

위의 예제에서 열 1에 주목해봅시다. 칸 A1과 G1은 모두 후보 숫자들로 2와 4를 갖습니다. 따라서 이 두 칸에 올 수 있는 후보 숫자는 총 2개밖에 없습니다. 즉, [A1|G1]이 드러난 부분집합을 이룹니다. 그러면 드러난 부분집합의 규칙에 의하여 열 1의 나머지 모든 칸에서 2와 4를 지울 수 있습니다. (위의 예제에서 지워진 숫자들은 노란색 바탕색으로 강조되었습니다.)

E5를 포함하는 상자에서도 마찬가지로, E5와 F4에 올 수 있는 후보 숫자가 오직 7과 8밖에 없습니다. 따라서 [E5|F4]가 드러난 부분집합을 이루며, 이 상자 내의 나머지 모든 칸에서 7과 8을 지울 수 있습니다.

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

전략 (드러난 후보쌍; Naked Pair). 어떤 논리 단위(행, 열 혹은 상자) 내에 속한 2개의 주어진 칸 대하여, 그 칸들에 올 수 있는 후보 숫자가 오직 ab 두개뿐이면, 그 논리 단위 내의 다른 모든 칸에서 후보 숫자 ab를 지울 수 있다.

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

5
2
1
7
9
8
7
9
6
4
3
8
9
4
6
3
1
7
2
5
2
5
3
7
6
3
7
2
5
4
1
9
8
1
9
1
4
7
9
3
6
8
1
9
7
9
4
9
5
2
1
4
5
8
5
9
2
1
5
6
4
9
7
3
5
7
9
2
5
7
9
3
4
5
7
9
4
9
3
5
7
9
6
1
8
1
2
7
8
1
2
9
1
9
4
3
6
5
1
5
9
1
2
4
5
2
5
9
3
6
8
1
9
1
2
4
7
1
4
9
3
6
1
5
7
1
2
5
8
4
9
1
2
9
A
B
C
D
E
F
G
H
J
1
2
3
4
5
6
7
8
9
예제 2. 드러난 삼중쌍

위의 예제는 행 D에서 세 칸 [D6|D7|D9]가 모여 드러난 부분집합을 이룬 경우를 보여줍니다. 이처럼 세 칸이 모여 이루어진 드러난 부분집합을 드러난 삼중쌍(naked triple)이라고 부르며, 이로부터 다음과 같은 특수한 케이스를 얻습니다.

전략 (드러난 삼중쌍; Naked Triple). 어떤 논리 단위(행, 열 혹은 상자) 내에 속한 3개의 주어진 칸 대하여, 그 칸들에 올 수 있는 후보 숫자가 오직 a, b, c 이렇게 3개뿐이면, 그 논리 단위 내의 다른 모든 칸에서 후보 숫자 a, b, c를 지울 수 있다.

마찬가지로 아래 예제는 네 칸 [G8|G9|H7|J7]이 모여 드러난 부분집합을 이룬 경우를 보여주며, 이런 경우를 드러난 사중쌍(naked quad)이라고 부릅니다. 그리고 이로부터 역시 드러난 부분집합 전략의 특별한 케이스를 얻습니다.

2
4
6
8
9
3
5
2
4
6
8
9
3
5
7
4
8
9
2
4
6
8
9
4
8
9
1
2
3
5
8
9
2
3
4
5
2
4
5
9
1
3
5
6
2
8
9
7
2
4
9
1
6
7
8
9
4
6
7
8
9
4
8
2
4
8
9
5
6
8
9
3
2
3
5
8
9
1
2
8
9
2
3
4
5
3
5
7
2
4
5
8
9
6
2
4
8
9
2
3
5
6
7
9
2
3
5
6
2
5
7
9
2
3
5
6
8
1
2
4
5
2
5
7
9
2
4
5
1
2
4
5
7
9
2
6
7
8
4
5
6
7
8
9
1
5
6
1
5
6
2
7
8
3
1
5
7
8
1
4
8
5
6
7
8
9
2
6
8
9
4
6
7
9
4
9
3
2
6
7
9
2
7
4
1
5
6
3
5
6
7
1
5
6
8
3
6
7
8
4
6
7
8
6
7
8
1
5
6
7
8
9
1
5
6
7
8
9
4
6
7
1
5
6
7
9
2
A
B
C
D
E
F
G
H
J
1
2
3
4
5
6
7
8
9
예제 3. 드러난 사중쌍
전략 (드러난 사중쌍; Naked Quad). 어떤 논리 단위(행, 열 혹은 상자) 내에 속한 4개의 주어진 칸 대하여, 그 칸들에 올 수 있는 후보 숫자가 오직 a, b, c, d 이렇게 4개뿐이면, 그 논리 단위 내의 다른 모든 칸에서 후보 숫자 a, b, c, d를 지울 수 있다.

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

숨은 부분집합
Strategy : Hidden Subset

각 논리 단위(행, 열 혹은 상자)에 담긴 칸의 개수는 9개이므로, 드러난 4중쌍을 넘어서게 되면 부분집합의 크기가 나머지 부분보다 더 커지는 현상이 발생합니다. 게다가 극히 희귀한 경우를 제외하면, 이 전략을 써야 하는 단계에서는 이미 각 논리 단위마다 한두 개 씩의 칸은 이미 결정이 되어있는 상태입니다. 따라서 실제로 부분집합의 나머지 부분의 크기는 훨씬 더 작아집니다. 이해를 돕기 위해 다음 예제를 봅시다.

5
8
6
4
8
7
9
1
3
4
3
5
8
1
4
2
3
2
4
7
1
4
5
6
8
1
4
6
9
4
5
7
1
4
7
5
7
8
9
1
4
7
8
9
2
4
5
3
4
3
5
7
8
4
5
7
6
4
2
9
6
8
5
7
1
3
5
7
1
7
3
7
1
3
7
8
1
4
5
7
4
5
7
9
2
5
6
7
5
7
9
6
7
8
1
7
8
6
5
1
7
9
3
1
7
9
4
2
7
8
9
2
1
4
5
1
3
4
9
4
5
6
3
8
7
1
3
4
8
8
3
4
7
9
4
7
1
3
4
7
2
6
5
6
4
5
7
1
3
4
7
3
5
7
8
2
1
3
9
1
3
4
A
B
C
D
E
F
G
H
J
1
2
3
4
5
6
7
8
9
예제 4. 드러난 사중쌍?

행 C의 [C2|C5|C6|C8]은 현재 드러난 사중쌍을 형성하고 있습니다. 그러나 실상을 보면, 실제로 의미 있는 나머지 칸들은 단 두 개밖에 없습니다. 이때 쯤 되면 드러난 부분집합 자체보다 그 나머지 부분을 살펴보는 것이 훨씬 더 수월해 보입니다. 따라서 이러한 경우, 나머지 부분을 살펴봄으로써 새로운 결론에 도달할 수 있습니다.

전략 (숨은 부분집합). 어떤 논리 단위(행, 열 혹은 상자) 내에 속한 m개의 주어진 칸이 m개의 후보들 a1, …, am을 포함하고 있고, 그 논리 단위 내의 다른 나머지 어떠한 칸에서도 a1, …, am 중 어떠한 후보도 포함하지 않으면, 그 m개의 칸에서 a1, …, am을 제외한 나머지 모든 후보들을 지울 수 있다.

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

5
8
6
4
8
7
9
1
3
4
3
5
8
1
4
2
3
2
4
7
1
4
5
6
8
1
4
6
9
4
5
7
1
4
7
5
7
8
9
1
4
7
8
9
2
4
5
3
4
3
5
7
8
4
5
7
6
4
2
9
6
8
5
7
1
3
5
7
1
7
3
7
1
3
7
8
1
4
5
7
4
5
7
9
2
5
6
7
5
7
9
6
7
8
1
7
8
6
5
1
7
9
3
1
7
9
4
2
7
8
9
2
1
4
5
1
3
4
9
4
5
6
3
8
7
1
3
4
8
8
3
4
7
9
4
7
1
3
4
7
2
6
5
6
4
5
7
1
3
4
7
3
5
7
8
2
1
3
9
1
3
4
A
B
C
D
E
F
G
H
J
1
2
3
4
5
6
7
8
9
예제 5. 숨은 후보쌍

행 C를 살펴보면, [C1|C7]을 제외한 다른 어떠한 칸에도 3과 8이 들어있지 않은 것을 확인할 수 있습니다. 따라서 [C1|C7]은 숨은 후보쌍(hidden pair)을 이루며, 이로부터 C1과 C7에서 3과 8을 제외한 나머지 후보들을 모두 지울 수 있습니다.

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

수학도들을 위한 스도쿠

이번 절에서는 드러난 부분집합과 숨은 부분집합 전략이 실제로 전략임을 증명해보고자 합니다. 그런데 숨은 부분집합 전략은 드러난 부분집합 전략과 사실상 동일하므로, 드러난 부분집합 전략이 전략임을 증명합시다.

정리 (드러난 부분집합). 드러난 부분집합 전략은 실제로 전략이 된다.

증명이 조금 복잡해보일 수 있지만, 실상 논리 자체는 간단한 비둘기집 원리입니다.

증명. 드러난 부분집합 전략에 대응되는 함수를 $\Phi : \mathcal{P}(\mathcal{S}) \to \mathcal{P}(\mathcal{S})$라고 하자. 드러난 부분집합 전략은 후보 숫자를 제거하는 전략이므로, 임의의 퍼즐 $P$에 대하여 자명하게 $\Phi(P) \subset P$가 성립한다. 한편, $LU$가 임의의 논리 단위이고, $LU$의 어떤 부분집합 $A$가 존재하여 $A$가 $P$에서 드러난 부분집합을 형성했다고 하자. 이는 $|P(A)| = |A|$임을 뜻한다. 이제 $P_0$이 $P$의 임의의 해라고 가정하자. 그러면 $P_0(A) \subset P(A)$이고 $$|A| = |P_0(A)| \leq |P(A)| = |A|$$ 이므로, $P_0(A) = P(A)$이다. 그런데 $P_0$는 해이므로, $P_0(A)$와 $P_0(LU-A)$는 합집합이 비어있고, 따라서 $$P_0(LU-A) = \mathcal{N}-P_0(A) = \mathcal{N}-P(A)$$ 가 성립한다. 따라서 $LU-A$에 속한 임의의 칸 위에서 $P_0$은 $P(A)$의 원소들을 후보로 갖지 않는다. 그런데 이것이 모든 논리 단위 $LU$와 그 드러난 부분집합 $A$에 대하여 참이므로, $P_0 \subset \Phi(P)$이고 따라서 $\Phi$는 전략이다.


Posted by aficionado

댓글을 달아 주세요

  1. j 2013.10.02 13:46  댓글주소  수정/삭제  댓글쓰기

    드러난 삼중쌍에서 5,7,9는 알겠는데 5,9는 7이없는데 왜 초록색에 포함되있는거죠?사중쌍에서도 6,7,8 4,6,7,8 4,6,7이랑 1,4,7 4,5,7 1,4가 왜 초록색인지 이해가안되요ㅠㅠ

    • aficionado 2013.10.02 15:27 신고  댓글주소  수정/삭제

      드러난 삼중쌍 전략은 세 칸에 각각 세 개의 숫자가 들어있을 필요가 전혀 없습니다. 예제 2에서 중요한 것은, 행 D에서

      D6, D7, D9

      이렇게 '3개의 칸'에 들어갈 수 있는 후보숫자가 5, 7, 9 이렇게 정확히 3개가 된다는 사실입니다. 즉 3개의 칸에 3가지 후보숫자만 가능하다는 사실이 중요합니다.

      이런 조건 하에서 D열의 나머지 모든 다른 칸에서 5, 7, 9를 지울 수 있다는 것이 드러난 삼중쌍의 결론입니다.

      심지어 만약에 예제 2가

      D6이 5, 9
      D7이 7, 9
      D9가 5, 7

      이었다고 가정해도 결론은 마찬가지입니다. D6, D7, D9 이렇게 3개의 칸에 3개의 후보숫자만 올 수 있으므로, D열의 나머지 모든 칸에서 5, 7, 9를 지울 수 있게 됩니다.

  2. 몽키둥이퍼즐 2014.05.20 12:03  댓글주소  수정/삭제  댓글쓰기

    완전 대박 ㅋ
    설명 완전 잘 되어 있어서 정말 많은 도움 되었어요 T^T
    마지막 수학기호적힌 설명은 여전히 모르겠지만 ㄷㄷㄷ;
    ㅎㅎ