이번 포스팅에서는 드러난 부분집합 전략을 격자 전략으로 바꿔보겠습니다. 이를 위하여 우선 격자 전략이 무엇인지 알아보아야 할 것입니다. 그러나 설명이 약간의 수학적 상상력을 요구하므로, 당분간은 격자 위에서 칸들의 위치를 이용하는 전략이라고만 알아두시면 좋겠습니다.

드러난 격자 부분집합 전략 (물고기 전략)
Strategy : Naked Grid Subset (Fish)

드러난 격자 부분집합 전략, 혹은 간단히 물고기 전략은 다음과 같습니다.

전략 (물고기; Fish). 후보 숫자 k를 생각하자. 그리고 다음 조건을 만족시키는 m개의 행과 열을 찾을 수 있다고 하자: m개의 각 행마다, m개의 열과 교차하는 지점들을 제외한 나머지 칸에는 후보 숫자 k가 들어있지 않다.

그러면 그 m개의 각 열마다, m개의 행과 교차하는 지점들을 제외한 나머지 칸에서 후보 숫자 k를 지울 수 있다. 이를 열 방향 물고기 전략이라고 하며, 행 방향 물고기 전략도 마찬가지로 주어진다.

이때, m개의 행과 m개의 열이 만나서 생기는 m×m개의 교차점들의 모임을 물고기(fish)라고 부릅니다. 특히 m이 주어진 경우에는 m-물고기 혹은 m-물고기 전략이라는 표현 등을 사용합니다.

아마 어떤 분들은 왜 물고기라는 단어를 사용하는지 궁금해하실 것입니다. 이는 3-물고기를 적용할 때 가장 흔히 볼 수 있는 패턴인

모양의 패턴이 마치 황새치(swordfish)와 닮았다고 해서 붙여진 이름입니다. 실제로 3-물고기 전략은 보통 황새치라고 부릅니다. 저로써는 왜 저기서 황새치가 연상되는지 모르겠지만, 어쨋든 처음 이름붙이는 사람이 장땡이니 뭐 어쩔 수 없지요. 그 밖에도 2-물고기 전략은 X-날개(X-Wing), 4-물고기 전략은 해파리(jellyfish) 등으로 불립니다.

물론, 말로 설명하면 잘 와닿지 않음을 알고 있습니다. 그러므로 그림을 통하여 물고기 전략을 좀 더 자세히 알아봅시다.

위 그림은 m = 3 인 경우의 물고기 전략을 보여주며, 여기서 물고기가 형성된 부분을 C라고 적힌 파란색 사각형으로 표시하였습니다. 이때, 물고기 전략은 다음과 같이 설명할 수 있습니다.

이제 실제로 물고기 전략들이 적용된 예제를 살펴봅시다. 다음은 2-물고기 전략, 즉 X-날개 전략이 적용된 예제입니다.

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

예제 1. 열 방향 X-날개

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

예제 2. 행 방향 X-날개

다음은 3-물고기 전략, 즉 황새치 전략의 예제입니다.

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
9
4
9
3
5
9
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
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

예제 3. 열 방향 황새치

그리고 다음은 4-물고기, 즉 해파리 전략의 예제입니다.

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

예제 4. 열 방향 해파리

 

수학도들을 위한 스도쿠 : 격자 전략이란?
What is a grid strategy?

이번 절에서는 격자 전략이 무엇인지 알아보고자 합니다. 이를 위하여, 이번 절에서는 스도쿠의 규칙 중에서 상자에 대한 규칙을 잠시 잊고 오직 행과 열에만 집중해보도록 하겠습니다.

스도쿠는 행, 열 그리고 각 칸마다 적힌 숫자 이렇게 세 가지 요소로 이루어져 있습니다. 이때 우리는 지금까지 행·열과 숫자를 따로 생각하였으나, 잠시 숨을 고르고, 후보 숫자들 다음과 같은 새로운 관점에서 생각해봅시다.

"후보 숫자는 어떤 점의 높이이다."

즉, 스도쿠를 행×열×높이 이렇게 9×9×9칸으로 이루어진 정육면체로 생각하고, ij열에 후보 숫자가 k인 칸을 이 정육면체 내의 좌표 (i, j, k)에 위치한 점으로 이해하는 것입니다. 그러면 상자에 대한 규칙을 제외했을 때 스도쿠 퍼즐의 규칙

  1. 각 칸에는 오직 한 개의 숫자만 들어간다.
  2. 각각의 행에 대하여, 각 숫자는 오직 한 번만 들어간다.
  3. 각각의 열에 대하여, 각 숫자는 오직 한 번만 들어간다.

은 다음과 같이 새롭게 표현할 수 있습니다.

  1. 각각의 i, j에 대하여, 행의 좌표가 i이고 열의 좌표가 j인 점은 오직 한 개 뿐이다.
  2. 각각의 i, k에 대하여, 행의 좌표가 i이고 높이가 k인 점은 오직 한 개 뿐이다.
  3. 각각의 j, k에 대하여, 열의 좌표가 j이고 높이가 k인 점은 오직 한 개 뿐이다.

따라서, 상자에 대한 규칙만 제외하면 스도큐 규칙은 사실 3차원 정육면체에서의 세 축 방향에 대해 모두 대칭적인 규칙으로 이루어져 있는 셈입니다.

한편, 상자라는 개념에 의존하지 않는 어떤 스도쿠 풀이 전략이 있다고 합시다. 그러면 그 전략은 사실상 위와 같이 새롭게 해석된 대칭적인 퍼즐 게임의 풀이 전략이 됩니다. 이것이 무엇을 의미할까요? 바로 이 전략에서 언급된 축들을 임의로 바꿔치기해도 여전히 퍼즐 풀이 전략이 된다는 것을 뜻합니다! 예를 들어, 우리가 상자라는 개념을 사용하지 않는 어떤 전략에서

칸 (i, j)에 숫자 k가 들어간다.

라는 표현을

칸 (j, k)에 숫자 i가 들어간다.

로 몽땅 바꾸어도 그 결과물은 여전히 퍼즐의 풀이 전략이 됩니다. 특히 행-숫자 전략이나 열-숫자 전략에서 축을 잘 바꿔치기하면 행-열에 대한 전략을 얻을 수 있습니다. 이것이 마치 3차원 공간상에서 행-숫자 평면이나 열-숫자 평면을 행-열 평면으로 회전시키는 것과 같기 때문에, 이런 원리를 적용하여 얻어낸 새로운 전략을 특별히 격자 전략(grid strategy)이라고 불러도 손색 없을 것입니다.

그러면 실제로 예를 들어봅시다. 지지난 포스팅에서 우리는 드러난 부분집합 전략을 살펴보았습니다. 그런데 적어도 행과 열에 대한 드러난 부분집합 전략의 경우, 우리는 상자의 개념을 사용하지 않고서도 전략이 여전히 성립함을 쉽게 확인할 수 있습니다. 이제 드러난 부분집합 전략에 위와 같은 원칙을 적용하면 어떤 결론을 얻는지 확인해봅시다. 우선 행에 대한 드러난 부분집합 전략을 다음과 같이 풀어서 써 봅시다.

im개의 열 j1, …, jm에 대하여, 칸 (i, j1), …, (i, jm) 이 m개의 후보 숫자 k1, …, km를 가진다고 하자. 그러면 jj1, …, jm인 모든 열 j에 대해 칸 (i, j)에서 후보 숫자 k1, …, km를 지울 수 있다.

이 전략에 격자 전략의 원칙을 적용하면, 다음과 같은 격자 전략을 얻습니다.

숫자 im개의 행 j1, …, jm에 대하여, m개의 열 k1, …, km에서 후보 숫자 i를 포함하고 있는 칸들이 오직 행 j1, …, jm에만 속한다고 하자. 그러면 jj1, …, jm인 모든 행 j에 대해 칸 (j, k1), …, (j, km)에서 후보 숫자 i를 지울 수 있다.

이제 위 전략을 일상적인 언어로 옮기면, 행 방향의 물고기 전략을 얻습니다. 물론 다른 방식으로 축을 바꿔치기하면 열 방향의 물고기 전략 역시 얻어낼 수 있습니다.


Posted by aficionado

댓글을 달아 주세요

  1. The Phototainer 2012.12.25 19:01 신고  댓글주소  수정/삭제  댓글쓰기

    물고기전략까지 정주행 완료했습니다. 역시 예제를 통한 이해가 빠르네요.

  2. 질문자 2013.08.09 22:33  댓글주소  수정/삭제  댓글쓰기

    몇번을 봐도 잘 모르겠네요.
    파란색 주황색은 뭘 의미하는 건가요?
    어떻게 보아야 황새치 물고기 해파리 패턴을 보는 건가요?

    • aficionado 2013.08.10 07:08 신고  댓글주소  수정/삭제

      파란색은 물고기가 형성된 부분을 뜻합니다.

      예를 들어서 예제 1을 보시면 C열과 E열의 C1, C8, E1, E8 이 후보숫자 8에 대하여 2-물고기 (즉 X-날개) 를 이루고 있지요. 왜냐하면 C행과 E행에서는 1열과 8열을 제외한 나머지 모든 칸에 8이 후보숫자로 나타나질 않기 때문입니다. 그러면 물고기 전략이 이야기해주는 것은, 1열과 8열에서 물고기 이외의 나머지 부분에서 8을 지울 수 있다는 것을 의미합니다. 주황색 칸들은 실제로 이 전략에 의해서 8이 지워지는 칸들을 강조한 것입니다.

  3. 질문자 2013.08.10 13:14  댓글주소  수정/삭제  댓글쓰기

    아ㅋ감사합니다 이제야 이해했네요

  4. 궁금 2013.09.17 06:20  댓글주소  수정/삭제  댓글쓰기

    잘 읽고 있습니다. 그런데 궁금한게 있어서요 ㅠㅠ 몇번을 다시 읽어봐도 이해가 되질 않네요. 3-물고기 전략부터 후보숫자k가 적혀있지 않은 칸도 적혀있는 것으로 보아서 푼 것으로 보이는데요. 위의 예를 들면 예제3의 c6이 후보숫자9를 포함한 것으로 보고 있고 또 예제4의 h1도 후보숫자8을 포함한 것을 전제로 풀고 있는 것으로 보이네요. 여기서 제가 궁금한 점은 위 예제3을 들어 말하면, 왜 E6 부분은 후보숫자9가 생략된 걸로 보지 않느냐는 것 입니다. 다시 말해 m행을 cdg가 아니라 cde 등도 가능하지 않냐는 질문입니다. 해파리 전략에서도 이 질문으로 인해 막히네요 ㅠㅠ 제가 무엇을 놓치고 있는지 가르켜 주셨으면 해요^^
    그리고 이 포스트를 직접 작성하시는 건가요??? 아니면 다른 포스트를 번역하신 것인지 궁금하네요 ㅎㅎ

    • aficionado 2013.09.17 18:04 신고  댓글주소  수정/삭제

      사실 물고기 전략에서, 예를 들면 예제 3의 황새치 전략에서 주어진 3x3 칸 CDG x 679 에 9가 모두 차있는가는 중요한 점이 아닙니다.

      중요한 점은, 예제 3의 경우 행 CDG 안에 들어있는 칸 중에서 열이 1, 2, 3, 4, 5, 8 인 칸에 9가 '안 들어있다'는 점입니다. 이 점은 이미 설명상의 이미지에서도 설명한 바가 있지요. 이는 행을 CDG 대신 CDE로 택하면 성립하지 않는 사실입니다. 행을 CDE로 택하면, 이 행에 속한 칸 중에서 9를 포함하는 칸은 C7, C9, D6, D7, D9, E2, E7, E9 가 되므로 최소 4개의 행 - 2, 6, 7, 9 - 이 필요하게 되어 물고기 전략의 조건을 만족하지 않습니다.

    • 감사 2013.09.18 17:51  댓글주소  수정/삭제

      아! 완전 이해가 잘되었습니다. 감사해요!

  5. 2014.04.20 16:30  댓글주소  수정/삭제  댓글쓰기

    난 머리가 나쁜가봐요 모르겟네........................

  6. 몽키둥이퍼즐 2014.05.20 18:00  댓글주소  수정/삭제  댓글쓰기

    3번 정독해서 50% 이해했네욤;
    완전 어려워요 스도쿠 ㅠㅠㅠㅠ

  7. 안녕하세요 2014.12.12 01:27  댓글주소  수정/삭제  댓글쓰기

    이렇게 설명을 다 보고나면 당연한 얘기인 것 같은데 생각해내기가 쉽지도 않을뿐더러, 실전에서 써먹는 것도 굉장히 어렵겠네요. 알기 쉽게 잘 설명해주셔서 잘 배워갑니다 !