티스토리 뷰

이번 포스팅에서는 가두기 전략에 대하여 설명하고자 합니다.

교차로 가두기
Strategy : Intersection Lock

스도쿠에는 주어진 영역 내에서 숫자들이 특정한 조건을 만족시켜야 하는 경우가 기본적으로 네 가지가 있습니다. 각각 칸, 행, 열 그리고 상자이지요. 각각의 칸에는 한 개의 숫자만 들어갈 수 있으며, 각각의 행, 열 또는 칸에는 각 숫자당 정확히 한 개가 들어갑니다. 그리고 이러한 영역들이 서로 겹칠 때 아주 재미있는 결론들을 내릴 수 있게 됩니다. 특히 행, 열 그리고 상자를 통틀어 논리 단위라고 부르는데, 앞으로 우리는 여러 논리단위를 넘나드는 논리들을 보게 될 것입니다. 그리고 이번 포스팅에서는 그 중 가장 기초적인 내용을 살펴보고자 합니다.

교차로 가두기 전략은, 행 또는 열과 상자가 교차하는 경우에 대한 전략이며, 그 정확한 내용은 다음과 같습니다.

전략 (교차로 가두기). 한 행(또는 열)과 상자가 만난다고 하자. 이때 행(또는 열)쪽에서 상자와 겹치지 않는 부분 A에 어떤 후보 숫자가 없다면, 상자 쪽에서 행(또는 열)과 겹치지 않는 부분 B에서도 그 후보 숫자들을 지울 수 있으며, 그 반대도 마찬가지다.

이때, 영역 A 또는 B날개(wing)라고 부릅니다. 물론 이번에도 말이 어렵게 느껴진다는 것을 알기에, 다음과 같은 그림을 준비해보았습니다.

위 그림은 행과 상자가 겹치는 모습을 나타냅니다. 이때 만약 날개 A에 후보 숫자 a가 없었다고 해봅시다. 그러면 C에 속한 세 칸중 적어도 한 칸은 반드시 a로 결정되어야 합니다. 이는 단순히 C가 후보 숫자로 a를 포함한다는 것보다 훨씬 더 강력한 조건이지요. 따라서 이 경우 날개 B는 절대로 a를 후보 숫자로 가질 수 없습니다. 이 논리는 정확히 반대방향으로도 적용되지요. 이 관계를 좀 더 단순하게 표현하면 다음과 같습니다.

이때, 우리는 C가 후보 숫자 a에 대하여 함께 모여 가리키는 쌍(pointing pair)을 이룬다고 표현합니다. 물론 셋 중 어떤 곳에 후보 숫자 a가 포함될 지는 모르기 때문에, 한 칸의 숫자가 a로 결정되는 것보다는 약한 조건이 됩니다. 하지만 셋이 모야 마치 하나의 칸처럼 행동하기 때문에, 최소한 두 날개에 대해서만큼은 a로 결정된 칸 하나와 동일한 효과를 발휘하는 것이지요. 따라서 이 경우 양쪽 날개에서 후보 숫자 a를 지울 수 있게 되는 것이지요.

이제 실제 예제들을 살펴봅시다. 우선 아래는 행→상자 방향으로의 교차로 가두기입니다.

3
4
8
9
5
9
3
8
9
3
4
7
6
2
1
5
7
9
7
9
3
4
9
2
7
1
3
4
1
3
4
5
3
4
8
4
5
6
9
4
6
9
4
5
6
1
5
6
8
9
5
7
2
4
5
6
7
3
2
5
6
7
2
7
9
3
1
2
7
9
7
9
6
5
8
4
5
6
7
9
2
6
8
9
2
3
4
7
9
3
4
7
9
2
3
4
8
9
2
3
3
6
1
2
6
2
6
8
4
1
2
5
8
2
3
5
8
9
7
2
3
6
3
6
7
8
2
3
7
8
6
7
8
9
1
5
3
7
9
4
3
7
9
1
3
4
7
1
3
4
7
5
2
7
9
7
9
2
9
6
8
2
3
9
6
7
6
8
9
3
4
2
6
7
8
2
5
7
2
5
1
A
B
C
D
E
F
G
H
J
1
2
3
4
5
6
7
8
9
예제 1. 교차로 가두기, 행→상자

행 A에서 6이 후보 숫자로 들어있는 칸은 오직 [A7|A9]밖에 없습니다. 따라서 행 쪽의 날개에는 6이 들어있지 않고, 이로부터 상자 쪽의 날개에 들어 있는 6들을 지울 수 있게 됩니다.

한편 아래는 반대로 상자→열 방향으로의 교차로 가두기입니다.

4
6
7
8
9
5
2
4
7
4
6
7
9
1
4
7
4
8
3
2
4
3
4
9
2
4
6
9
4
6
3
4
5
9
8
4
5
6
7
2
4
5
1
1
3
7
4
7
8
3
4
5
2
4
5
7
6
9
4
5
8
2
9
3
1
4
6
5
7
8
4
5
4
5
8
2
7
9
6
1
3
7
1
6
8
5
3
2
4
9
3
4
7
6
9
4
7
8
1
3
4
7
2
5
8
4
5
2
4
5
9
3
4
5
7
1
4
6
9
4
6
7
3
4
5
3
7
1
4
5
9
6
2
3
4
9
8
4
7
A
B
C
D
E
F
G
H
J
1
2
3
4
5
6
7
8
9
예제 2. 교차로 가두기, 상자→열

여기서 G1을 포함하는 상자에 주목해봅시다. 이 상자에서 후보 숫자 4와 7은 오직 [G1|H1|J1]에만 속합니다. 즉, 상자 쪽 날개에는 4와 7이 포함되어 있지 않습니다. 따라서 4와 7 각각에 대하여, 교차로 가두기로부터 열 쪽의 날개에 속한 후보 숫자 4와 7을 모두 지울 수 있습니다. 여기서 재미있는 것은, 이 상황을 드러난 삼중쌍으로 이해할 수도 있다는 것이지요. 즉, 서로 다른 두 전략이 동시에 적용될 수 있는 경우가 생긴 것입니다. 이와 같은 상황은 앞으로도 계속 만날 수 있습니다.

교차로 가두기 전략은 눈으로 푸는 전략으로서는 상당히 어려운 축에 속하지만, 반대로 후보를 적어놓으면 훨씬 적용이 수월해집니다. 그리고 웹사이트나 프로그램, 혹은 어플 등을 이용할 경우에는 해당 번호를 강조해주는 기능도 함께 들어있는 경우가 많기 때문에, 이 경우에는 매우 적용하기 쉬워집니다. 아래는 Sudoku+라는 iPad 어플로 스도쿠를 푸는 과정입니다.

보시다시피 행 G의 [G1|G2]가 후보 숫자 7에 대하여 함께 모여 가리키는 쌍을 이루며, 날개 [G4|G5|G6]의 후보 숫자 7을 지우는 모습을 보실 수 있습니다.

지금까지도 몇몇 예제들을 통해 보셨겠지만, 어려운 스도쿠 퍼즐의 경우는 후보를 적지 않고서는 풀기가 거의 불가능합니다. 다행히 지금까지 소개된 전략들은 그래도 많은 스도쿠 퍼즐가들을 통해 눈으로도 따라갈 수 있는 전략 축에 속한다고 평가되어 온 것들입니다. 하지만 이러한 전략들만으로는 통계적으로 10% 미만에 해당하는 어려운 스도쿠들을 풀 수가 없지요. 따라서 앞으로 스도쿠를 푼다고 하면 무조건 후보 숫자들을 적어 두고 푸는 것으로 이해하겠습니다. 물론, 여러분들이 어려운 스도쿠를 푸셔야 할 이유는 전혀 없습니다. 어차피 여가 시간용으로 퍼즐을 하는 경우가 대부분일 테니까, 오히려 가벼운 두뇌 운동 격으로 적당한 난이도의 퍼즐을 푸는 것이 더 이득일 수도 있습니다. 하지만 호승심과 호기심이 강하신 분들이라면 여기서 멈추고 싶지 않을 것입니다. 그리고 그러한 분들은 이 이후에 소개되는 전략들도 충분히 도전해보실 수 있으리라 믿습니다.


댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
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
글 보관함