스도쿠 0 - 입문

• 2022/11/06 에 포맷을 다듬고 수학 부분의 내용을 싹 갈아엎었습니다.

---

이번 포스팅 시리즈에서는 스도쿠의 다양한 전략들을 살펴보고 수학적으로 분석해보고자 합니다. 설명의 단계를 나누어, 일반인들을 위한 부분과 수학적인 부분을 최대한 분리하고 단계를 나누려고 노력하였습니다. 그리고 많은 예제도 소개할 예정입니다.

1. 스도쿠란?

사진 출처: Sudoku game Stock Photo by ©Viviamo 5139395

스도쿠(数独; Sudoku)는 9×9 칸의 격자에 1 부터 9 까지의 숫자를 채워넣는 숫자 퍼즐 게임입니다. 특히 격자가 아래와 같이 3×3 짜리 상자들로 다시 나누어져 있어, 각 행, 열 그리고 상자마다 1 부터 9 까지의 숫자를 단 한 번만 들어가도록 채우는 게임입니다.

게임 자체가 등장한 지는 역사적으로 꽤 오래 되었지만, 결정적으로 1986년에 니코리라는 일본 퍼즐 게임 회사가 스도쿠라는 이름으로 유행시킨 후 2000년경 초반에 국제적인 인기를 얻었습니다. 그 후 많은 변형판이 나왔지만, 여전히 원조 스도쿠는 꾸준한 인기를 얻고 있습니다.

1.1. 게임 규칙

설명드린 것처럼, 스도쿠는 각 행과 열, 그리고 상자마다 1부터 9까지의 숫자를 정확히 한 번씩만 들어가도록 채우는 게임입니다. 다음의 예를 보시면 이해가 잘 가실 것입니다. (위 스도쿠 퍼즐의 풀이입니다.)

처음에 몇 개의 칸에 숫자를 미리 채워진 채로 문제가 제시되는데, 이때 올바르게 출제된 스도쿠 퍼즐의 경우, 게임 규칙에 의해 나머지 칸에 숫자를 다 채워넣는 가능성은 오직 한개 뿐입니다. 물론, 간혹 초보자가 어설프게 만든 스도쿠는 이러한 출제 지침을 잘 지키지 못하여 답이 여러 개가 되는 경우가 발생하곤 하는데, 이는 잘못된 스도쿠 문제라 할 수 있겠습니다.

여기서 처음에 미리 숫자가 채워진 칸을 단서(clue) 혹은 주어진 숫자(given)라고 하는데, 스도쿠 문제라 하면 보통 이 단서들에서 출발하여 나머지 모든 칸들을 게임 규칙에 맞도록 채워넣는 게임을 의미합니다.

또한 초보 수준의 스도쿠를 넘어가게 되면 각 칸마다 그 칸에 들어갈 수 있는 후보숫자(candidate)들을 적어두는 것이 거의 강제되다시피 합니다. 중급 이상의 스도쿠 논리 전략에서든 이 후보숫자들의 배치와 게임 규칙으로부터 다른 후보숫자들을 지워나가게 되기 때문이죠. 참고로, 과거 종이에 직접 스도쿠를 풀던 시절에는 나중에 지우개로 지울 수 있는 연필을 이용해 이 후보숫자들을 마크했기 때문에 후보숫자들을 연필마크(pencilmark)라고 부르기도 합니다. 아래는 맨 위의 스도쿠 퍼즐에 기본 전략들을 적용해 후보숫자들을 지우고 남은 연필마크들을 보여줍니다.

1.2. 표기법

스도쿠 동호인들 사이에서는 스도쿠의 풀이에서 각 칸을 편리하게 지칭하기 위해 다음과 같은 주소 체계를 고안해내었습니다.

• 행은 위에서 아래로 순서대로 A, B, C, D, E, F, G, H, J 라고 적습니다. (알파벳 I 는 숫자와 헷갈리기 쉽고 가독성이 떨어지므로 보통 건너뜁니다.)
• 열은 왼쪽에서 오른쪽 순서대로 1, 2, 3, 4, 5, 6, 7, 8, 9 와 같이 번호매김합니다.

이렇게 주어진 주소 체계를 이용해 각 칸의 주소를 적어보면 아래와 같습니다.

또한 상자는 왼쪽 위에서 오른쪽으로 따라가며 번호매김을 합니다. 예컨대 행 ABC 와 열 123 이 만나 생기는 왼쪽 맨 위의 상자는 1 번째 상자, 행 DEF 와 열 789 가 만나 생기는 오른쪽 중간의 상자는 6 번째 상자인 식입니다.

이 글에서도 스도쿠 격자의 칸들을 가리킬 때 이러한 주소 체계를 사용할 것입니다.

여기까지가 스도쿠 퍼즐 게임에 대한 간략한 소개였습니다. 다음 포스팅에서는 가장 기본적이자 초보적인 스도쿠 전략에 대하여 살펴보고자 합니다.

[이전 글] (없음) <<

>> [다음 글] 스도쿠 1 - 기본전략

2. 수학도들을 위한 스도쿠

이번 절에서는 스도쿠를 수학적으로 분석하기 위한 기초를 다질 것입니다. 이 분석의 궁극적 목표는 스도쿠 커뮤니티에서 널리 알려진 많은 논리적 공략법들을 수학의 언어로 분석하는 것입니다. 좀 더 구체적으로, 현존하는 거의 대부분의 전략들이 하나의 큰 방법론의 특수한 경우가 됨을 확인할 것입니다. 더군다나 이 방법론은 기존의 전략들을 설명하는 데 멈추지 않고 새로운 전략들을 체계적으로 발견할 수 있게 해 준다는 점도 확인해 볼 것입니다. (물론, 쓸만하고 발견하게 어렵지 않은 전략들은 이미 대부분 발견되어 있을 것이므로, 어디까지나 가능성의 얘기입니다.)

지금부터는 수학적인 언어가 많이 포함되어 있으며, 앞으로의 논의에서도 수학도를 위한 부분을 제외하면 사실상 등장하지 않는 내용입니다. 따라서 스도쿠의 수학적 설명에 관심이 없으신 분들은 바로 다음 포스팅으로 넘어가시면 되겠습니다.

2.1. 완전 적중 문제 – 스도쿠 퍼즐의 수학적 구조

스도쿠를 수학을 이용해 체계적으로 분석하기 위해서는 스도쿠 퍼즐을 수학의 언어로 다시 적어야 합니다. 그 과정은 어떻게 이루어질까요? 우선 스도쿠의 규칙을 조금 더 풀어 적어봅시다. 곰곰히 생각해보면, 실제로 스도쿠는 아래와 같은 네 가지 규칙을 만족시키도록 숫자를 채워 넣는 게임임을 알 수 있습니다.

• 규칙 1. 각 행(row)에는 1 부터 9 까지의 숫자 각각이 정확히 한 개씩 들어가야 합니다.
• 규칙 2. 각 열(column)에는 1 부터 9 까지의 숫자 각각이 정확히 한 개씩 들어가야 합니다.
• 규칙 3. 스도쿠 퍼즐의 격자를 3×3 짜리 부분격자 9 개로 쪼갠 각각을 상자(box)라고 합니다. 이때, 각 상자에는 1 부터 9 까지의 숫자 각각이 정확히 한 개씩 들어가야 합니다.
• 규칙 4. 각각의 칸(cell)에는 1 부터 9 까지의 숫자 중 정확히 하나만 들어가야 합니다.

이 네 규칙을 잘 보면, '... 마다 정확히 하나만 들어간다' 라는 구조임을 알 수 있습니다. 그리고 수학에서 이러한 종류의 문제는 소위 완전 적중 문제(exact hitting problem)라는 이름으로 조합론과 컴퓨터 과학 등의 분야에서 다뤄집니다. 이 문제를 서술해보면 다음과 같습니다.

완전 적중 문제. 유한집합 $ X $ 밑 그 적당한 부분집합들의 모임인 $ \mathcal{U} \subseteq 2^X $ 가 주어져 있다고 하자. 이때 다음과 같은 조건을 만족시키는 $ X $ 의 부분집합 $ P^{\star} $ 를 (모두) 찾아라:

임의의 $ U \in \mathcal{U} $ 들은 $ P^{\star} $ 와 정확히 하나의 원소만을 공통으로 가진다. 즉, $ |U \cap P^{\star} | = 1 $ 이다.

좀 더 구체적으로 어떻게 스도쿠 게임이 완전 적중 문제와 연관되는지를 살펴봅시다. 우선 집합 $ X $ 를 스도쿠 격자 위에 적을 수 있는 모든 후보숫자, 즉 연필마크들을 모아둔 것이라고 합시다. 예컨대 '칸 C7 에 적힌 연필마크 3' 과 같은 것들이 $X$ 에 속하겠지요. 하지만 매번 $X$ 의 원소를 이렇게 부르면 말이 길어지므로, 간단하게

$(i, j, n) = $ [ $i$ 번째 행과 $j$ 번째 열이 만나는 칸에 적힌, 숫자 $n$ 인 연필마크 ]

라고 적겠습니다. 그러면 $X$ 는 가능한 모든 $(i, j, k)$ 들을 모아둔 집합이 될 것입니다:

$$ X = \{ (i, j, n) : i, j, n = 1, 2, \ldots, 9 \} $$

마찬가지로, 연필마크들이 적힌 스도쿠 퍼즐이 하나 주어지면 그 연필마크들을 모두 모은 집합 $P$ 를 그 퍼즐과 동일하게 생각할 수 있습니다. 그러면 $P$ 는 $X$ 의 부분집합이 되죠. 그리고 반대로 $X$ 의 부분집합 $P$가 하나 주어지면, 이를 연필마크들이 적힌 퍼즐과 동일하게 생각할 수 있습니다. 따라서 앞으로의 논의에서는 필요한 경우에 $X$의 임의의 부분집합을 퍼즐(puzzle)이라고 부르겠습니다. (매번 부분집합이라고만 부르면 뭔가 딱딱하니까요.)

한편, $i$ 와 $j$ 방향 각각은 원래 스도쿠 퍼즐 격자의 행과 열 방향에 대응되므로 실제로 우리 눈에 보이는 방향이 입니다. 하지만 숫자 $n$ 방향은 퍼즐에서 직접 보이는 방향이 아닙니다. 그렇지만 연필마크들을 세 번째 차원 방향으로 늘어놓음으로써 이 방향을 시각화할 수 있습니다. 예컨대 아래와 같이 칸 하나에 네 후보숫자 1, 2, 6, 8 이 적혀있는 상황을 오른쪽의 3차원 그림에서처럼 '1, 2, 6, 8 층의 연필마크는 칠해져 있고 나머지 연필마크는 지워져 있다'고 해석할 수 있습니다.

그런 의미에서 스도쿠 퍼즐을 3차원 격자 위의 퍼즐로 대신 생각할 수 있습니다.

한편, 일반적인 완전 적중 문제로 잠시 돌아가서 이제 모임 $\mathcal{U}$ 를 살펴봅시다. 이 모임은 어떻게 해석해야 할까요? 곧 살펴보겠지만, $ \mathcal{U} $ 는 스도쿠의 규칙에 대한 정보를 담고 있음을 알 수 있습니다. 구체적으로, 다음과 같은 네 가지 집합을 생각합시다.

• $ \mathtt{R}_i \mathtt{N}_n = \{ (i, *, n) : * = 1, 2, \ldots, 9 \} $ 는 행 $i$ 에 속하고 숫자가 $n$ 인 가능한 모든 연필마크들을 모아둔 집합입니다.
• $ \mathtt{C}_j \mathtt{N}_n = \{ (*, j, n) : * = 1, 2, \ldots, 9 \} $ 는 열 $j$ 에 속하고 숫자가 $n$ 인 가능한 모든 연필마크들을 모아둔 집합입니다.
• $ \mathtt{B}_k \mathtt{N}_n $ 는 $k$ 번째 상자에 속하고 숫자가 $n$ 인 가능한 모든 연필마크들을 모아둔 집합입니다.
• $ \mathtt{R}_i\mathtt{C}_j = \{ (i, j, *) : * = 1, 2, \ldots, 9 \}$ 는 칸 $(i, j)$ 에 속하는 가능한 모든 연필마크들을 모아둔 집합입니다.

이렇게 네 종류의 집합 각각은 81 가지 경우의 수가 있으므로, 총 4×81 = 324 개의 집합이 생깁니다. 이들 모두를 모은 것을 $\mathcal{U}_{\text{Sudoku}}$ 라고 적읍시다. 그러면 다음과 같은 정리가 성립합니다.

정리. 임의의 스도쿠 퍼즐 $P^{\star} \subseteq X$ 에 대해 다음은 서로 필요충분조건이다.
1. $P^{\star}$ 가 스도쿠 게임의 규칙을 모두 만족시키면서 모든 칸의 숫자가 정해져 있다. 즉, $P^{\star}$ 는 풀린 스도쿠 퍼즐이다.
2. 임의의 $U \in \mathcal{U}_{\text{Sudoku}}$ 에 대하여 $|U \cap P^{\star}| = 1$ 이다. 즉 $P^{\star}$ 는 집합 $X$ 와 모임 $\mathcal{U}_{\text{Sudoku}}$ 에 대한 완전 적중 문제의 해가 된다.

증명은 생각보다 매우 쉽습니다. 예컨대 $| \mathtt{R}_i \mathtt{N}_n \cap P^{\star} | $ 는 퍼즐 $P^{\star}$ 의 행 $i$ 에 포함된 후보숫자 $n$ 의 개수가 됩니다. 따라서 스도쿠 게임의 규칙 1 이 성립하려면 이 개수는 반드시 $1$ 이어야 하고 그 반대도 마찬가지입니다. 나머지 경우들도 마찬가지로 증명할 수 있으므로, 전체 증명은 생략하도록 하겠습니다.

2.2. 완전 적중 게임 – 스도쿠 게임의 일반화

앞 절에서는 스도쿠 게임이 완전 적중 문제와 밀접한 관련이 있음을 확인했습니다. 그리고 마찬가지 논리가 다른 변형 스도쿠에도 똑같이 통하므로, 여기서는 원조 및 변형 스도쿠를 포괄하는 일반적인 개념들을 잠깐 정의하고 넘어가겠습니다. 앞으로 설명할 내용들은 원조 스도쿠 뿐만 아니라 곧바로 소개할 일반적인 틀에서도 여전히 성립하는 내용들입니다. 그러므로 일반적인 개념을 먼저 소개하는 의미는 충분히 있다고 할 수 있습니다.

정의. 유한집합 $ X $ 와 그 부분집합들의 모임 $ \mathcal{U} $ 가 주어졌을 때, 이 두 정보로 이루어진 자료 $$ \mathcal{X} = \{ \texttt{set} : X, \, \texttt{rules} : \mathcal{U} \} $$ 를 완전 적중 게임이라고 부른다. 이때,

• $ \mathcal{U} $ 를 규칙(rule)이라고 부르고, $\mathcal{U}$ 의 각각의 원소를 규칙 유닛(rule unit)이라고 부른다.
• $X$ 의 부분집합 $P^{\star}$ 가 규칙 $\mathcal{U}$ 하에서 풀렸다(solved)는 것은 $P^{\star}$가 완전 적중 문제의 해라는 것을 뜻한다. 즉, 임의의 $ U \in \mathcal{U} $ 에 대해 $ |U \cap P^{\star} | = 1 $ 가 성립함을 뜻한다.

(그래프 이론에 익숙하신 분들이라면 $\mathcal{X}$ 가 더도 덜도 아닌 하어퍼그래프(hypergraph)임을 알아보실 겁니다.) 이제 게임의 틀을 정했으니 그 위에서 실제로 퍼즐을 고려할 수 있습니다.

정의. 완전 적중 게임 $ \mathcal{X} = \{ \texttt{set} : X, \, \texttt{rules} : \mathcal{U} \} $ 가 주어져 있다고 하자.

• 임의의 퍼즐 $P \subseteq X$ 에 대하여, $P$ 의 부분집합이면서 풀린 퍼즐을 모두 모은 집합을 $\operatorname{Sol}(P)$ 라고 적고 $P$ 의 해집합이라고 부른다: $$ \operatorname{Sol}(P) = \{ P^{\star} \subseteq P : \text{$P^{\star}$ is solved} \} $$ 이때 $\operatorname{Sol}(P)$ 의 원소들을 $P$ 의 해(solution) 또는 답이라고 부른다.
• 퍼즐 $P \subseteq X$ 가 잘 만들어졌다는 것은 $ P $ 가 정확히 한 개의 해를 가짐을 뜻한다. 즉, $ |\operatorname{Sol}(P)| = 1 $ 임을 뜻한다.

이러한 관점에서, 완전 적중 게임의 퍼즐을 푼다는 것은 주어진 퍼즐 $P \subseteq X$ 의 해를 모두 찾는 것을 의미하게 됩니다. 스도쿠 퍼즐을 푼다는 것은 이 개념의 훌륭한 예제가 되지요.

이제 스도쿠의 전략의 개념을 추상적으로 정의하고 일반적인 완전 적중 게임으로 확장하는 문제를 생각해봅시다. 이를 위해서는 스도쿠에 논리적 전략을 적용한다는 것이 본질적으로 어떠한 과정인지를 짚어보는 것이 좋습니다. 곰곰히 생각해보면, 스도쿠 게임에서의 논리적 전략이라 함은 스도쿠의 답이 만족해야 하는 규칙들을 바탕으로 연역적 추론 과정을 거쳐 어떤 연필마크들이 답에 포함될 수 없는지를 판단하고, 그 판단으로부터 연필마크를 지우거나 혹은 칸에 들어갈 숫자를 확정하는 과정이라 할 수 있습니다. 때문에 논리적 전략을 적용하기 이전과 이후에도 퍼즐의 해 혹은 가능한 모든 해들의 모임은 변하지 않을 것입니다. 모든 해들은 스도쿠 게임의 규칙을 전부 만족시키니까요. 따라서 우리는 논리적 전략이 만족해야 할 두 가지 중요한 성질을 추려낼 수 있습니다:

• 전략을 적용한 이후의 퍼즐은 이전의 퍼즐과 비교하여 새로운 연필마크를 가져서는 안됩니다. 즉, 이전의 연필마크들을 그대로 갖고 있거나 그들 중 일부가 지워지는 것만이 가능합니다.
• 전략을 적용하기 이전 퍼즐과 이후의 퍼즐은 동일한 답들을 공유해야 합니다. 즉, 새로운 답이 생겨나거나 가능한 답 중 일부를 잃어버려서는 안됩니다.

이 두 성질을 추상화시키면 다음과 같은 정의를 내리는 것이 가능해집니다.

정의. 완전 적중 게임 $ \mathcal{X} = \{ \texttt{set} : X, \, \texttt{rules} : \mathcal{U} \} $ 이 주어져 있다고 하자. 이때 함수 $ \Phi : 2^{X} \to 2^{X} $ 가 게임 $ \mathcal{X} $ 의 전략(strategy)이라는 것은 다음 두 조건이 만족됨을 뜻한다.

• $ \Phi(P) \subseteq P $ 가 항상 성립한다. 즉, $ \Phi $ 는 오직 연필마크들을 줄이는 것만 가능하다.
• $ \operatorname{Sol}(\Phi(P)) = \operatorname{Sol}(P) $ 가 항상 성립한다. 즉, $ \Phi $ 는 가능한 해들을 모두 온전히 보존한다.

물론 절대 다수의 스도쿠 퍼즐들은 잘 만들어져있기 때문에 (즉, 해가 유일하게 설계되어 있기 때문에) 굳이 해집합 전체를 보존하는 논리에 집착할 필요까지는 없습니다. 즉 해집합의 전부는 아니어도 최소한 일부는 보존하는 논리도 개인의 취향에 따라 충분히 쓸만할 것입니다. 이러한 종류의 약한 전략들은 스도쿠 커뮤니티에서 흔히 유일성 전략이라고 알려져 있습니다. 그러한 전략들은 기회가 될 때 다시 소개하도록 하고, 한동안은 해집합을 모두 보존하는 논증들에 집중하도록 하겠습니다.

---