척척박사 연구소

척척박사 연구소과학이야기제목별로 보기해설이 있는 과학

해설이 있는 과학

최신 소식 속에 담긴 다양한 과학정보에 대한 해설입니다.

여든 한 칸의 마법






지하철을 기다릴 때 가판대에서 파는 잡지나 주간신문을 훑어보곤 한다. 자극적인 문구와 사진으로 도배가 돼 있는 경우가 많아 민망할 때가 한 두번이 아니다. 그렇지만 잘 살펴보면 한 구석에 퍼즐 잡지 2~3가지도 눈에 띤다. 퍼즐만 가득 차 있는 잡지라니, 퍼즐을 좋아하는 사람들이 꽤 있나보다. 퍼즐 가운데 요 몇 년 사이 가장 인기를 끌고 있는 것이 ‘스도쿠(sudoku)’다.

스도쿠는 바둑판처럼 배열된 빈칸에 숫자를 채우는 퍼즐이다. 가로 세로 아홉 칸씩 전부 81칸(9×9)에 1부터 9까지 숫자를 채우는데 규칙이 있다. 즉 세로와 가로 아홉 칸에 1부터 9까지 숫자를 한 번만 넣어야 한다. 또 가로세로 줄을 각각 3등분으로 나눠 9칸(3×3)으로 된 작은 판 9개 각각에도 1에서 9까지 숫자를 한 번만 넣어야 한다.

물론 81칸을 모두 채우는 건 아니고 스물 서너 곳의 칸에는 이미 숫자가 지정돼 있다. 이를 바탕으로 나머지 빈칸의 숫자를 찾아내는 퍼즐이다. 별로 재미있을 것 같지 않은데 인기가 높은 걸 보면 나름 묘미가 있는 것 같다. 필자도 예전에 한 두 번 시도했지만, 풀지못하고 포기한 적이 있다.



●최소한 17칸은 숫자가 지정돼 있어야
사실 스도쿠는 라틴방진(Latin square)의 특수한 경우다. 라틴방진은 가로 세로 n개씩 전부 n2의 칸에 n개의 서로 다른 기호(숫자, 문자, 색깔 등 어떤 걸 써도 상관없다)가 가로 세로 겹치지 않게 배열하는 퍼즐이다. 라틴방진이라는 이름이 붙은 건 이 퍼즐을 연구하던 스위스의 천재 수학자 레오나드 오일러가 기호로 라틴어 알파벳을 사용했기 때문이다.

스도쿠는 숫자 1부터 9까지를 기호로 써서 n이 9인 라틴방진을 만들 때 조건 하나를 더한 경우다. 즉 가로세로를 3등분해 나오는 작은 판 9개 각각에도 1에서 9까지 숫자를 한 번만 넣어야 한다는 제한이다. 얼핏 생각하면 라틴방진보다 복잡한 것 같지만 사실 이 조건이 붙었기 때문에 스도쿠가 재미있다.

즉 보통 라틴방진이라면 숫자를 배열하는 경우의 수가 너무 많기 때문에(9×9 라틴방진은 5524751496156892842531225600가지다!) 정답이 하나인 퍼즐을 내려면 문제에 이미 많은 칸이 채워져 있어야 한다. 그런데 스도쿠의 추가 조건이 들어가면 배열의 수가 100만 분의 1 수준으로 줄어든다. 따라서 채워야 할 빈 칸이 많아 머리를 써서 빈 칸을 채우는 재미가 더 있다.

물론 기자처럼 스도쿠를 처음 시작하는 사람은 숫자가 채워진 칸이 좀 더 많아야 풀어볼 의욕이 생길 것이다. 한 신문에 나온 스토쿠를 보니 81칸 가운데 23칸이 정해져 있었다. 고급 문제로 갈수록 정해진 칸이 줄어들 것이다. 그렇다면 정답이 하나뿐인 퍼즐을 만들 때 숫자가 주어지는 칸 개수의 최소한계는 몇 개일까.

물론 많은 사람들이 이 문제에 도전했고 그 개수가 17이라는 결과를 얻었다. 즉 16칸이 채워진 문제에서는 답(가능한 배열)이 둘 이상이라는 말이다. 그러나 아직까지 누구도 이 사실을 증명하지는 못했다. 이런 식의 문제를 증명하려면 모든 경우의 수를 확인해봐야 하는데(즉 16칸이 채워진 모든 경우에 대해 정답이 하나인 경우가 없어야 한다) 너무나 많은 시간이 걸리기 때문이다.

그런데 개리 맥과이어라는 아일랜드 수학자가 최근 스도쿠 퍼즐의 정답이 하나만 있으려면 최소한 17칸이 정해져 있어야 함을 증명하는데 성공했다고 한다. 유니버시티 칼리지 더블린의 맥과이어 교수는 ‘hitting-set 알고리즘’이라고 명명한 기발한 컴퓨터 알고리즘을 고안한 뒤 슈퍼컴퓨터를 돌려(700만 CPU 시간) 마침내 이 문제를 증명했다고 한다. 이 알고리즘을 써서 가능한 16칸 지정 배열을 좀 더 적은 수의 집합으로 묶을 수 있어 컴퓨터로 확인해야 하는 경우의 수를 대폭 줄일 수 있었다고 한다.




컴퓨터를 이용한 증명
궁금증 하나. 수학 증명이라고 하면 엄밀한 연역 과정을 통해 얻어져야 하는 게 아닐까. 실마리가 16칸인 모든 경우의 수를 (이 경우는 알고리즘을 써서 줄인 뒤) 일일이 확인해서 퍼즐의 정답이 하나인 것이 없으니까 최소한 17칸이 정해져야 한다는 게 증명됐다고 하면 왠지 어색하다.

사실 컴퓨터를 써서 수학 문제를 증명 한 것은 처음이 아니다. 가장 유명한 사례가 바로 ‘4색정리(four color theorem)’다. 평면을 여러 부분으로 나눈 뒤 각 부분에 색칠을 할 때 서로 맞닿은 부분이 다른 색이 되기 위해서는 네 가지 색이면 충분하다는 정리다. 예를 들어 우리나라 지도에서 맞닿은 시도 행정구역이 서로 다른 색을 띠게 만드는데 4색이면 된다는 말이다.





4색정리는 1852년 처음 제안된 뒤 이를 증명하려는 시도가 계속됐으나 번번이 실패했다. 그러다 1976년 미국 일리노이대의 케네스 아펠과 볼프강 하켄이 무한한 배열을 1936개의 패턴(집합)으로 단순화할 수 있음을 보인 뒤 컴퓨터를 써서 이를 증명했다. 그리고 각각의 패턴에 대해 일일이 네 가지 색으로 칠을 할 수 있음을 보였다. 그 결과 모든 배열에서 성공해 4색이면 충분하다는 정리가 증명됐다.

이처럼 증명 과정에서 컴퓨터를 이용한 계산이 들어있는 경우를 ‘컴퓨터를 이용한 증명(computer-assisted proof)’이라고 부른다. 수학 문제 가운데는 컴퓨터의 도움이 불가피한 경우가 있지만 이를 좋아하지 않는 수학자들이 있으리라는 건 어렵지 않게 짐작할 수 있다. 어떤 수학자들은 이것이 계산이지 증명은 아니라고 주장하기도 한다.

컴퓨터의 도움을 받았든 말든 스도쿠 퍼즐의 '퍼즐'이 풀렸다니, 애호가들에겐 재미있는 이야깃거리가 아닐까.




강석기 기자 sukki@donga.com

관련주제가 없습니다.
내과학상자담기  E-MAIL 프린트 카카오스토리 트위터 페이스북 RSS
관련 콘텐츠가 없습니다.

나도 한마디 0개의 댓글이 있습니다.

등록하기

목록


내 당근 보러가기

내 뱃지 보러가기

TOP