스도쿠(sudoku) 數獨(수독), 의 수학

스도쿠라는 수학 퍼즐이 있다. 스도쿠는 전세계적으로 인기를 끌고 있어 다양한 컴퓨터, 휴대폰 게임으로도 만들어질 정도로 인기가 있다. 이 스도쿠를 수학자가 만들었다고 하던데, 어떤 사람일까? 그리고 스도쿠의 수학적 원리는 무엇일까? 스도쿠를 쉽게 푸는 수학적 원리 같은 게 있을까 한번 알아보자.

스도쿠란 어떤 것일까?

스도쿠는 가로 세로 9칸인 정사각형 모양의 빈 칸에 1부터 9까지 아홉 개의 숫자를 적당히 넣어 다음 세 조건을 만족하게 하는 것이다.

1. 어떤 가로줄에도 같은 숫자가 나타나지 않는다. 바꿔 말하면, 어떤 가로줄에도 1부터 9까지 아홉 개의 숫자가 모두 나타난다.
2. 어떤 세로줄에도 같은 숫자가 나타나지 않는다. 즉, 어떤 세로줄에도 아홉 개의 숫자가 모두 나타난다.
3. 굵은 테두리를 두른, 가로 세로 3칸인 작은 정사각형에도 같은 숫자가 나타나지 않는다. 즉, 아홉 개의 숫자가 모두 나타난다.

아래는 스도쿠 문제의 사례이다.

스도쿠 문제의 사례

스도쿠(sudoku)라는 이름은 數獨(수독), 즉 외로운 숫자라는 뜻의 한자어를 일본식으로 읽은 것이다. 당연한 일이겠지만, 이 이름은 일본에서 지은 것이다. 그렇다면 스도쿠를 만든 사람도 일본인일까?

스도쿠를 만든 사람은 누구일까?

스도쿠가 처음 등장한 것은 1979년으로, 미국의 퍼즐 잡지인 델지(Dell magazine)에 Number Place라는 제목으로 실린 것이 인쇄 상태로는 최초의 것이다. 이 퍼즐은 하워드 간즈(Howard Garns)가 창안한 것으로 알려져 있다. 이 새로운 퍼즐은 이후 일본에 전해져 “숫자는 혼자로 제한된다 (数字は独身に限る)”라는 긴 이름으로 소개되었다. 일본의 퍼즐 잡지인 니코리(ニコリ)의 카지 마키(鍜治 真起) 회장은 이 긴 이름을 數獨으로 줄여서 세상에 내놓았고, 이후 전세계에 스도쿠 열풍이 불어닥쳤다.

스도쿠의 창안자는 하워드 간즈이지만, 이것을 상품화하여 세계적으로 유행하게 만든 데는 카지 마키의 공이 커서, 그는 “스도쿠의 아버지”라는 별명으로 불리기도 한다. 물론 그는 자신이 스도쿠를 창안했다고 주장한 적이 없으니, 일본이 독도에 이어 스도쿠까지 넘본다는 걱정은 할 필요없다. 하워드 간즈나 카지 마키는 뛰어난 퍼즐 작가이기는 하지만 수학자라고는 할 수 없다. 스도쿠를 만든 사람이 수학자라는 말은 어디서 나온 것일까?

오일러와 라틴 방진

18세기 최고의 수학자 오일러. 스도쿠의 할아버지라 할 수 있다.

수학의 역사에는 손꼽히는 천재들이 많은데, 18세기 최고의 수학자라면 단연 스위스의 오일러(Leonhard Euler, 1707-1783)라 할 수 있다. 그는 17세기에 개발된 미적분학을 최고의 수준으로 발전시켰을 뿐 아니라, 선대 수학자들은 생각지도 못했던 새로운 분야를 개척하여 수학의 수준을 한 단계 끌어올린 위대한 인물이었다. 오일러는 “해석학의 화신”이라는 별명이 있을 정도로 미적분학 분야에 뛰어난 수학자였지만, 한편으로 그는 지금은 조합론(combinatorics)이라 부르는 분야에서도 많은 업적을 남겼다.

그가 연구했던 주제 가운데 라틴 방진(Latinsquare)이라 불리는, 특수한 규칙에 따라 숫자를 배열하는 문제가 있다. 이것은 가로 세로 n개의 칸으로 이루어진 정사각형의 각 칸에 1부터 n까지의 수를 넣어, 가로와 세로 어느 쪽으로도 같은 수가 나오지 않게 하는 것으로, 바로 스도쿠의 세 가지 규칙 가운데 첫 번째와 두 번째에 해당한다. 다시 말해, 스도쿠는 가로와 세로가 아홉 개의 칸으로 이루어진 라틴 방진, 즉 9차 라틴 방진이다. 오일러가 라틴 방진에 대해 여러 가지 재미있는 결과들을 얻었기에, 수학자가 스도쿠를 만들었다는 말도 아주 틀린 말은 아닌 셈이다.

다만 원래 수학자란 존재는 자신의 발견으로 돈을 버는 데 익숙하지 않은 법이어서, 20세기가 될 때까지 라틴 방진은 수학자들 사이에서만 알려져 있을 뿐, 이것을 퍼즐로 만들 생각은 아무도 하지 못하였다. 오일러를 스도쿠의 창안자라고 할 수는 없더라도, “스도쿠의 할아버지” 정도로는 생각할 수 있지 않을까?

스도쿠는 몇 가지나 가능할까?

스도쿠는 9차 라틴 방진에 가로 세로 3칸인 작은 정사각형 9개에 대한 규칙을 추가한 것이다. 스도쿠의 조건을 만족하는 배열을 “스도쿠 방진”으로 부르자. 이제 자연스러운 질문은 스도쿠 방진이 몇 가지나 될지, 그리고 라틴 방진 전체에 비해 어느 정도의 비율이 될지를 묻는 것이다.

수학자 펠겐하우어(Bertram Felgehauer)와 자비스(Frazer Jarvis)는 스도쿠 방진으로 가능한, 그야말로 모든 경우의 수를 구하였는데, 그 값은 다음과 같다.

한편 9차 라틴 방진의 개수는 다음과 같다.

두 값을 비교해 보면 9차 라틴 방진에 대한 스도쿠 방진의 비율은 100만 분의 1 정도밖에 되지 않는다. 스도쿠 방진의 개수가 대단히 많지만, 이것은 좌우를 뒤집거나 전체를 회전하거나 1과 2의 자리를 맞바꾸는 등의 방법을 일일이 다 센 것이다. 적당히 변형하여 같은 방진이 되는 경우를 하나로 세기로 한다면 스도쿠 방진의 개수는 대폭 줄어든다. 그 개수는 다음과 같다.

줄었다고는 하지만 본질적으로 다른 스도쿠 방진이 54억 개가 넘는 셈이니, 스도쿠 문제가 더 이상 만들어지지 않을까 걱정할 필요도 없고, 스도쿠 문제를 모조리 풀어보겠다는 무모한 도전을 할 필요도 없다.

스도쿠는 언제나 풀 수 있을까?

스도쿠는 처음 몇 개의 칸에 숫자를 주고서 나머지 칸을 규칙에 따라 채우는 것이다. 당연한 일이지만, 처음에 아무렇게나 숫자를 주어서는 칸을 채울 수 없는 경우가 있다.그러니 스도쿠를 푸는 것이 쉬운 일이 아니지만, 만드는 것도 쉬운 일이 아니다. 또, 어떤 스도쿠는 처음에 공개하는 숫자가 아주 많으면서도 둘 이상의 풀이가 존재하기도 한다. 다음 그림의 왼쪽은풀 수 없는사례이며, 오른쪽은 풀이가 2개 존재하는 사례이다.

풀이가 없는 스도쿠 문제

풀이가 2개 존재하는 스도쿠 문제

이런 이유로 스도쿠는 유일한 풀이가 존재하도록 만드는 것이 원칙이다. 그렇다고 처음부터 너무 많은 숫자를 공개하면 푸는 재미가 줄어들어서, 되도록 적은 힌트를 주는 쪽이 더 어렵고 멋진 문제라고 할 수 있다. 스도쿠에 대한 미해결 문제 가운데 가장 유명한 것도 이에 관한 것이다. 즉, 유일한 풀이가 가능하도록 공개할 수 있는 숫자는 최소 몇 개가 가능하겠냐는 것이다. 현재 알려져 있는 최솟값은 17로 다음이 그 한 예이다.

현재까지 밝혀진 최악의 스도쿠 문제 중 하나. 공개된 숫자가 17개 뿐이다.

17개의 숫자만 공개되어 있을 때 유일한 풀이가 존재하는 스도쿠 문제는 현재 48826개가 알려져 있지만, 16개의 숫자가 주어진 스도쿠 문제는 하나도 알려져 있지 않다. 그러나 이런 압도적인 증거에도 불구하고, 16개의 숫자면 충분한 스도쿠 문제가 단 하나라도 존재하면 17은 최솟값이 될 수 없다.

스도쿠를 간단히 푸는 수학적 방법이 있을까?

스도쿠의 묘미는 간단한 규칙으로 이루어져 있으면서도 푸는 것이 간단치 않은 데 있다고 할 수 있으니, 스도쿠를 간단히 푸는 방법을 찾는다는 것은 뭔가 모순된 상황이다. 어떤 알고리듬에 따라 해결하는 문제가 얼마나 쉽게 풀리는지를 설명하는 방법 가운데 하나가 복잡도(complexity)이다. 스도쿠는 복잡도에 따른 분류에서 NP-완전 문제임이 증명되어 있다. NP-완전 문제란 모든 경우의 수를일일히 확인해 보는 것 외에 뾰족히 푸는 방법이 없는 문제를 말한다. 따라서, 아무리 최첨단 수학 이론을 쓴다고 해도, 스도쿠를 한 방에 푸는 방법은 사실상 없다고 할 수 있다. 그러니 스도쿠를 푸는 기본 요령에 따라 열심히 풀어 보는 방법밖에 없다. 뭔가 놀라운 수학적 방법이라도 있을 것으로 기대한 분이 있다면 실망을 안겨드려 죄송하다. 그러나 세상 일이란 게 원래 그런 거 아니겠나.

네이버캐스트