[주말N수학] 스도쿠의 세계
스도쿠는 일반적으로 가로 9칸, 세로 9칸에서 진행되는 숫자 퍼즐 게임입니다. 이 게임은 18세기 스위스의 수학자 레온하르트 오일러가 창안한 라틴방진을 1979년 미국의 건축가 하워드 간즈가 '넘버 플레이스(Number Place)'라는 이름으로 미국의 퍼즐 잡지 ‘델’에 소개한 걸 시초로 보고 있습니다. 이후 1984년 일본의 출판사 니코리가 발행하는 퍼즐 잡지 ‘퍼즐통신니코리’에서 이 퍼즐을 스도쿠라 이름 붙여 수록하면서 점차 일본 내에서 대중화됐습니다.
스도쿠라는 명칭은 ‘숫자는 한 번씩만 쓸 수 있다’는 일본어 문장을 줄여서 쓴 것에서 유래했습니다. 스도쿠는 점차 유명해져 2005년 무렵부터 전 세계에서 인기를 끌기 시작했습니다. 스도쿠를 구성하는 칸은 총 81칸, 좀 더 자세히는 33칸 상자 9개로 구성됩니다. 스도쿠를 풀기 위해서는 아래와 같은 규칙을 지켜야 합니다.
스도쿠 문제를 만들다 보면 풀리지 않는 문제가 만들어지는 경우도 있고, 답이 2개 이상인 경우도 생기죠. 그래서 스도쿠는 위에서 소개한 규칙 외에도 반드시 1개의 정답만 존재해야 한다는 규칙이 있습니다. 또 니코리는 문제를 출제할 때 ‘힌트 숫자의 위치가 대칭을 이뤄야 한다’, ‘문제에 나오는 힌트 숫자는 30개 이하여야 한다’는 규칙을 세웠습니다. 이 규칙에 따라 스도쿠 문제를 만들면 난이도가 더 어려워지기 때문입니다.
○
문제를 내기 위한 최소 숫자 ‘17’
정답이 하나인 스도쿠를 만들 때 필요한 최소 힌트 숫자는 몇 개일까요? 이를 알아보기 위해 2012년 개리 맥과이어 아일랜드 더블린대 교수팀은 서로 다른 스도쿠 퍼즐 약 55억 가지를 슈퍼컴퓨터로 1년간 검증했습니다. 스도쿠 문제 하나하나를 전부 검증해 보는 방법으로 분석한 결과 16개의 힌트 숫자로는 한 개의 답을 가진 스도쿠를 만들 수 없는 것으로 나타났습니다.
대신 최소한 17개의 힌트 숫자가 있어야 스도쿠를 풀 수 있다는 결론을 얻었습니다. 연구에 참여한 고든 로일 호주 웨스턴오스트레일리아대 교수는 2012년 국제학술지 ‘네이처’와의 인터뷰에서 “슈퍼컴퓨터로 무작정 스도쿠를 계산해 컴퓨터 기술과 수학적 테크닉을 한계까지 밀어붙였다”고 말했습니다.
사실 컴퓨터를 써서 수학 문제를 증명한 것은 처음은 아닙니다. 평면에 있는 서로 다른 영역을 색칠할 때 맞닿은 부분이 다른 색이 되기 위해서는 네 가지 색이면 충분하다는 ‘4색 정리’가 그 예입니다. 지난 1852년 제안된 4색 정리는 1976년에 컴퓨터 계산으로 증명됐습니다. 미국의 수학자 케네스 아펠과 볼프강 하켄은 평면에 나타낼 수 있는 모든 배열을 1936개의 조합으로 단순화한 뒤, 각각의 조합을 모두 네 가지 색으로 칠할 수 있음을 컴퓨터로 증명했습니다.
○
스도쿠의 가능한 모든 경우의 수
2005년 영국의 수학자 프레이저 자비스는 스도쿠 판을 채울 수 있는 가지 수를 구하는 방법을 처음 소개하고 그 결과를 발표한 인물로 인정받고 있습니다. 이들이 스도쿠가 가능한 경우의 수를 구한 방법은 다음의 순서에 따라 진행됐습니다.
① 스도쿠를 33칸 상자 9개로 나눈다.
② 맨 왼쪽 위 상자의 숫자를 먼저 임의로 정한다.
③ 그 뒤 맨 윗줄의 상자들을 채우는 경우의 수를 구하고, 임의로 숫자를 정한다.
④ 나머지 상자를 채우는 경우의 수를 구한다
자비스는 이 과정에 따라 적절한 알고리듬을 세우고 컴퓨터를 이용해 스도쿠가 가질 수 있는 경우의 수를 계산할 수 있었습니다. 그 결과 스도쿠가 갖는 경우의 수는 총 6,670,903,752,021,072,936,960(66해 7090경 3752조 210억 7293만 6960)가지라는 것을 알 수 있었죠.
또 2006년 자비스는 대칭 또는 회전 등을 했을 때 같은 모양이 나오는 스도쿠 문제를 같은 문제라고 생각한다면, 서로 다른 스도쿠 문제는 5,472,730,538(54억 7273만 538)가지가 가능하다고 발표했습니다. 이 경우의 수는 한 사람이 스도쿠 문제를 1분에 한 개씩 푼다고 해도 약 1만 412년이 걸리는 양입니다. 간단한 규칙 이면에는 수없이 많은 가능성의 문제들이 있던 것입니다.
○
스도쿠를 풀 수 있는 신의 한수는 존재할까
스도쿠는 규칙이 단순함에도 불구하고, 어려운 난이도의 스도쿠가 쉽게 풀리지 않는다는 점에서 매력적인 퍼즐 게임입니다. 그래서 오래전부터 스도쿠는 어떤 컴퓨터 알고리듬이나 수학 이론이 적용된 완벽한 해결법이 있는 것은 아닌지 궁금증을 자아냈습니다. 하지만 n×n 사이즈로 무한한 크기의 스도쿠는 'NP-완전 문제'라는 것이 증명됐습니다.
‘NP 문제’란 각 단계에서 여러 가지 가능성을 고려할 수 있는 문제를 말합니다. 빠른 시간 안에 정답을 찾긴 어렵지만, 문제에 대한 답이 주어지면 그 답이 정답인지는 쉽게 확인할 수 있다는 특징이 있습니다. NP-완전 문제란 NP 문제 중에서도 또 다른 형태의 NP 문제로 변환할 수 있는 문제를 말합니다. n×n 크기의 스도쿠를 완벽히 한 번에 풀 수 있는 알고리듬이나 수학적 방법은 아직까지는 발견되지 않았습니다. 그래서 컴퓨터가 스도쿠를 풀기 위해선 모든 경우의 수를 일일이 확인하는 방법 외에는 없습니다. 스도쿠 외에도 유명한 NP-완전 문제로는 지뢰찾기 게임, 외판원 순환 문제가 있습니다.
만약 어떤 NP-완전 문제를 ‘빠른 시간안에 정답을 찾아낼 수 있는 문제’로 바꿔 풀 수 있는 알고리듬이 있다면, 모든 NP 완전 문제는 빠른 시간안에 답을 찾을 수 있습니다. 이를 P 대 NP 문제라고 하죠. P 대 NP 문제는 미국 클레이수학연구소에서 정한 7개의 수학 난제인 ‘밀레니엄 문제’ 중 하나입니다.
※관련기사
수학동아 8월호, 즐겁다! 에프매스의 무의식 스도쿠 세상
[윤태인 기자 yoon_taein@donga.com]
Copyright © 동아사이언스. 무단전재 및 재배포 금지.