티스토리 뷰

취미 얘기/스도쿠

스도쿠 06 - 고급 전략 : XY-날개

sos440 2012. 12. 28. 12:49

이번 포스팅에서는, 대다수의 고급 전략들의 공통분모라 할 수 있는 XY-날개에 대하여 알아보고, 또 이 전략을 바라보는 여러 관점을 소개함으로써 앞으로 등장할 색칠 전략, 연쇄 고리 전략, 날개 전략, 압박 전략 등에 대한 실마리를 살펴보겠습니다.

XY-날개 전략
Strategy : XY-Wing

XY-날개 전략이 무엇인지부터 우선 소개하는 것이 좋겠습니다. 이를 위하여, 새로운 용어를 도입합시다. 주어진 칸에 올 수 있는 후보 숫자가 정확히 두 개일 때, 이 칸을 이중치 칸(bivalued cell)이라고 부릅시다. 앞으로 등장할 수 많은 전략들에서 이중치 칸이라는 개념은 결정된 칸 다음으로 중요한 역할을 맏습니다. 비슷하게, 후보 숫자가 정확히 3개인 칸을 삼중치 칸(trivalued cell)이라고 합니다. 물론, 후보의 개수를 늘려가면 마찬가지 용어들을 얻습니다만, 거의 등장하지 않기 때문에 소개는 따로 안 하도록 하겠습니다.

전략 (XY-날개). 이중치 칸 h가 후보 숫자 {x, y}를 갖고 있다고 하자. 그리고 h를 볼 수 있는 다른 두 개의 이중치 칸 w1과 w2가 각각 후보 숫자로 {x, z}와 {y, z}를 갖고 있다고 하자. 그러면 w1과 w2를 동시에 볼 수 있는 모든 칸에서 후보 숫자 z를 지울 수 있다.

이 전략을 증명하는 것은 간단합니다.

증명 1. 칸 h가 후보 x를 갖는다고 가정하면, 칸 w1는 반드시 z를 후보로 가져야 합니다. 반대로 칸 h가 후보 y를 갖는다고 가정하면, 칸 w2는 반드시 z를 후보로 가져야 합니다. 따라서 어떠한 경우에도 w1나 w2 중 하나에는 반드시 후보 숫자 z가 들어가야 하고, 따라서 이 둘을 동시에 볼 수 있는 모든 칸은 z를 후보로 가질 수 없습니다.

증명 2. 칸 t가 두 이중치 칸 w1과 w2를 동시에 볼 수 있다고 가정합시다. 그리고 칸 t가 후보 숫자 z가 결정되어야 한다고 가정합시다. 그러면 w1에는 z가 올 수 없으므로, w1는 x로 결정됩니다. 그러면 h는 y로 결정되며, 따라서 w2는 z로 결정됩니다. 그러면 이로부터 t에는 z가 올 수 없으므로 모순입니다! 그러므로 t에는 z가 올 수 없습니다.

증명 3. 세 칸 U = [h|w1|w2]을 생각하고, U에 후보 z가 속하지 않는다고 가정합시다. 그러면 w1에는 x가 오고 w2에는 y가 와야 합니다. 그러면 h에는 어떠한 후보도 올 수 없으므로, 모순입니다. 따라서 U는 후보숫자 z를 포함해야 하며, 이 후보숫자 z를 모두 볼 수 있는 모든 칸에서 z를 지울 수 있습니다. 그런데 U에서 z를 포함하는 칸은 오직 w1와 w2뿐이므로, 증명됩니다.

여기서 증명 1은 일종의 가정법으로, 후에 압박 전략(forcing strategy)으로 일반화됩니다. 그리고 증명 2는 논리의 흐름이 일종의 연쇄 고리를 이루어 다시 자신으로 돌아오기 때문에, 후에 일반적으로 연쇄 고리 전략(chaining strategy)으로 일반화됩니다. 마지막으로 증명 3은 셈하기(counting)를 이용한 증명이며, 이는 후에 좀 더 일반적인 날개 전략(wing strategy)으로 발전됩니다.

가장 판별하기 쉬운 XY-날개 전략은 다음과 같은 구조로 나타납니다.

아래는 위와 같은 구조를 지닌 XY-날개의 예제입니다.

1
3
4
9
1
3
9
2
1
4
7
9
1
7
9
5
1
9
8
6
8
9
7
1
8
6
3
2
5
9
1
5
4
6
1
5
9
4
5
9
8
1
9
1
4
9
3
7
2
1
3
9
1
3
9
4
6
5
8
1
2
3
1
2
3
7
1
2
5
8
5
8
7
1
2
4
3
1
5
9
6
2
5
6
1
3
5
7
1
2
9
1
9
4
8
1
3
5
2
5
4
1
2
5
7
2
7
9
8
6
3
7
6
8
9
3
2
6
8
5
8
4
1
2
1
5
2
5
3
6
8
1
4
6
8
9
2
5
7
A
B
C
D
E
F
G
H
J
1
2
3
4
5
6
7
8
9

하지만 이러럼 깔끔하게 떨어지는 경보다, 보통 다음과 같이 휘어진 형태가 통계적으로 더 많이 등장합니다.

그리고 이처럼 XY-날개 전략은 많은 경우에 위의 예제에서처럼 휘어진 형태로 등장하기 때문에, 스도쿠 고급 전략에 입문한 사람들이 이 전략을 쓰는 데 많은 애를 먹습니다. 그러나 일단 XY-날개 전략이 이중치 칸들만을 이용하고, 또 후보 숫자들 사이에 아주 분명한 연관관계가 있기 때문에, 조금만 인내심을 가지면 충분히 적용 가능한 전략이기도 합니다.

아래는 일반적인 XY-날개의 예제입니다.

3
6
5
7
9
1
7
9
1
9
4
2
8
9
4
8
2
8
2
4
6
3
7
1
5
1
2
7
2
4
7
1
7
2
4
8
5
3
6
9
8
7
9
6
9
6
7
5
4
1
3
2
1
3
4
6
2
6
7
8
2
8
5
4
7
9
4
7
5
2
9
1
3
8
4
7
6
5
4
7
2
8
1
3
6
9
1
9
1
3
6
9
3
2
1
4
6
9
4
6
8
5
7
6
9
8
5
3
7
1
7
1
2
2
3
4
A
B
C
D
E
F
G
H
J
1
2
3
4
5
6
7
8
9

아래는 조금 더 극적인 예제로, 한 번에 세 칸을 지우는 모습입니다.

4
6
9
6
9
3
6
8
7
1
5
1
4
5
3
5
2
1
5
3
4
6
2
9
3
4
8
7
2
7
8
1
5
3
4
5
6
1
9
5
6
9
5
6
1
3
6
8
2
4
3
5
8
5
9
3
5
9
7
2
7
3
5
8
9
1
3
5
8
3
5
4
6
9
4
3
5
3
5
6
7
8
2
1
1
5
6
2
4
5
6
3
8
9
7
5
6
1
4
5
6
8
3
4
5
7
6
1
4
5
9
2
7
1
9
6
9
4
5
2
1
3
6
8
3
6
A
B
C
D
E
F
G
H
J
1
2
3
4
5
6
7
8
9

위의 예제들에서, XY-날개가 적용되는 칸들은 모두 사각형과 비슷한 형태를 띠고 있습니다. 그러나 반드시 이러한 형태만 가져야 하는 것은 아닙니다. 아래 그림

에서 확인할 수 있듯이, 두 날개에 해당하는 w1와 w2가 동시에 바라볼 수 있는 칸이기만 하면 항상 이 전략이 적용 가능합니다. 그리고 아래는 실제로 이러한 예제를 보여줍니다.

5
2
1
7
8
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
3
6
8
1
9
7
4
9
5
2
1
4
8
5
9
2
1
5
6
4
9
7
3
5
7
9
2
5
7
9
3
4
5
4
9
3
5
6
1
8
1
2
7
8
1
2
9
1
9
4
3
6
5
5
1
2
4
2
9
3
6
8
1
9
1
2
4
7
4
9
3
6
1
5
7
1
2
5
8
4
9
1
2
A
B
C
D
E
F
G
H
J
1
2
3
4
5
6
7
8
9


댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2024/04   »
일 월 화 수 목 금 토
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
글 보관함