스도쿠 1 - 기본 전략

이번 포스팅에서는 가장 기본적인 전략에 대하여 살펴보려고 합니다.

1. 기본적인 후보 지우기 전략

서로 다른 두 칸이 같은 행이나 같은 열, 혹은 같은 상자 안에 들어있을 때, 서로를 볼 수 있다고 부릅니다. 스도쿠의 규칙에 의하면, 서로를 바라볼 수 있는 두 칸이 서로 같은 값으로 결정되서는 안됩니다. 그리고 이 간단한 관찰로부터 우리는 다음과 같이 아주 간단하면서도 강력한 전략인 기본적인 후보 지우기(obvious candidate removal) 전략을 얻게 됩니다.

전략 (기본적인 후보 지우기). 숫자가 n으로 결정된 각각의 칸에 대하여, 그 칸을 볼 수 있는 다른 모든 칸들에 포함된 후보 숫자(연필마크) n을 지울 수 있다.

아래는 예제입니다.

예제 1. 기본적인 후보 지우기 전략을 사용하여 후보 숫자들을 지운 결과물.

빨간 색으로 X가 쳐진 노란색 칸들은 모두 기본적인 후보 지우기 전략에 의하여 지워진 후보 숫자들입니다.

2. 드러난 하나 전략

가장 간단한 전략 중 하나인 드러난 하나(naked single) 전략은, 주어진 칸에 올 수 있는 후보 숫자가 단 하나밖에 없을 경우 그 숫자로 칸이 결정된다는 내용입니다. 즉, 정리하자면 다음과 같습니다.

전략 (드러난 단일후보). 주어진 칸에 올 수 있는 후보 숫자가 오직 n 하나밖에 없으면, 그 칸은 숫자 n으로 결정된다.

예를 들어, 위의 예제 1에서 칸 C2와 G7은 8로 결정됩니다. 그리고 이렇게 칸들이 결정되고 나면, 다시 기본적인 후보 지우기 전략으로 돌아가 후보들을 더 지울 수 있게 되지요. SudokuWiki 사이트의 통계에 의하면, 약 75%의 스도쿠 퍼즐들은 오직 기본적인 후보 지우기와 드러난 단일후보 이렇게 단 두 개의 전략만으로 모두 풀린다고 합니다.

사실 내용만 보면 이 전략은 너무나 당연해보입니다. 그러나 여러분이 후보 숫자를 적지 않고 눈으로만 푸는 스타일을 선호하신다면 의외로 이 전략을 사용하기가 조금 힘듭니다. 왜냐하면 눈으로 나머지 8개의 후보 숫자들이 지워지는 것을 다 추적해야 하는데, 머릿속으로 세기가 쉽지 않기 때문이지요. 예를 들어 위의 예에서 C2에 8이 와야만 한다는 것을 보이기 위해서는 아래 청록색으로 표시된 칸을 확인해야 합니다.

예제 2. C2가 8임을 알아내기 위해 확인해야 할 칸

보다시피 예제 2의 청록색으로 표시된 칸들에 8을 제외한 나머지 숫자들이 모두 포함되어 있으므로, 파란색으로 표시된 칸 C2에는 오직 8만이 올 수 있게 됩니다.

3. 숨은 하나 전략

후보 숫자를 적어두지 않고 눈으로만 따라갈 때, 드러난 하나 전략보다 대체로 더 적용하기 쉬운 전략이 있습니다. 숨은 하나(hidden single) 전략은, 주어진 행이나 열, 혹은 상자 내에서 후보 숫자 n이 들어갈 수 있는 칸이 오직 하나밖에 없을 때 그 칸의 값을 n으로 결정하는 전략입니다. 이때 그 칸에 다른 후보숫자들이 얼마나 많이 적혀있는지는 전혀 상관 없습니다. 즉, 이 전략은 하나의 후보숫자에만 집중하면 되는 전략입니다. 다음 예제를 봅시다.

예제 3. 숨은 단일후보 전략을 적용한 퍼즐

위의 예제에서, F3을 포함하는 상자를 주목합시다. 이 상자에서 3이 들어갈 수 있는 칸은 오직 F3밖에 없기 때문에 이 칸의 값을 3으로 결정할 수 있습니다. 이는 위 그림에서 해당 칸의 3을 제외한 나머지 후보 숫자들을 모두 지우는 과정으로서 표현되었습니다. 물론 위 예제에서는 후보 숫자를 적어두어 이를 확인했지만, 이 전략은 사실 눈으로 따라가봐도 아래와 같이 쉽게 확인 가능합니다.

예제 4. 눈으로 따라가는 숨은 하나 전략.

청록색 사각형으로 강조된, 3으로 결정된 두 칸 C1과 E7을 살펴봅시다. 빨간색으로 표시된 칸들은 이 두 칸 중 하나라도 볼 수 있는 칸들 중 일부를 표시한 것입니다. 쉽게 말해서, C1과 같은 열에 있는 칸 혹은 E7과 같은 행에 있는 칸들을 표시한 것입니다. 이 칸들에는 3이 들어갈 수 없지요. 그런데 상자 4를 살펴보면, 이 두 청록색 칸들의 시야에서 벗어나 있으면서 아직 결정되지 않은 칸은 오직 F3 (파란색으로 칠해진 칸)밖에 없음을 알 수 있습니다. 따라서 숨은 후보 전략에 의해 이 칸의 값은 3으로 결정됩니다. 이는, 3으로 결정된 각각의 칸에서 3을 지우는 레이저 광선이 발사되는 이미지를 떠올려보면 위 상황을 머릿속으로 그리기 더 쉬울 것입니다.

지금까지의 내용을 다음과 같이 요약할 수 있습니다.

전략 (숨은 단일후보). 주어진 행, 열 혹은 상자 안에서 후보 숫자 n을 포함하는 칸이 단 하나 있으면, 그 칸에 다른 모든 후보 숫자들을 지우고 그 칸의 값을 n으로 결정할 수 있다.

<< [이전 글] 스도쿠 0 - 입문

>> [다음 글] 스도쿠 2 - 셈하기 전략