으으으으으으!! 왜 이렇게 땀을 삐질삐질 흘리고 있냐고? 내가 요새 스도쿠에 빠져버려서 말이야. 어려운 난이도의 스도쿠를 풀고 있는데 생각만큼 잘 안 풀리네. 응? 너도 스도쿠 좋아한다고? 역시 수학동아 독자다워! 나도 잠시 머리 좀 식히고 싶은데, 내가 재밌는 스도쿠 이야기 좀 해줄까?
스도쿠는 일반적으로 가로 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년 영국의 수학자 프레이저 자비스는 스도쿠 판을 채울 수 있는 가지 수를 구하는 방법을 처음 소개하고 그 결과를 발표한 것으로 인정받고 있습니다. 이들이 스도쿠가 가능한 경우의 수를 구한 방법은 다음의 순서에 따라 진행됐습니다.
자비스는 이 과정에 따라 적절한 알고리듬을 세우고 컴퓨터를 이용해 스도쿠가 가질 수 있는 경우의 수를 계산할 수 있었습니다. 그 결과 스도쿠가 갖는 경우의 수는 총 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년이 걸리는 양입니다. 간단한 규칙 이면에는 수없이 많은 가능성의 문제들이 있던 것이죠.
에프매스와 스도쿠 풀어볼래?
도전! 폴리매스배 스도쿠 대회!
수학동아 독자들이라면 나 에프매스가 등장하는 ‘에프매스의 무의식 퍼즐세계’를 좋아하겠지?
이번에는 폴리매스에서 스도쿠 게임을 선보이게 됐어. 폴리매스 스도쿠는 어떤 흥미로운 점이 있을까?
무의식중에서도 수학 문제를 생각하는 에프매스. 어느 날 에프매스가 수학동아 편집부와 폴리매스 홈페이지 관리진에게 “폴리매스 홈페이지에서도 스도쿠를 풀 수 있게 해달라!”고 요청했습니다. 에프매스의 적극적인 요청을 받아들인 박은정 수학동아 편집장! 그렇게 폴리매스 홈페이지에 스도쿠 게임이 탄생했답니다. 폴리매스 스도쿠는 어떤 기능이 있을까요?
폴리매스 스도쿠는 5개의 기능으로 구성돼 있습니다. 먼저 폴리매스 스도쿠에 등록된 스도쿠 문제를 풀 수 있는 기능입니다. 문제를 푸는 도중에 한 줄 댓글도 달 수 있죠. 폴리매스 홈페이지의 개발과 관리를 담당하는 닉네임 ‘라면먹는 몰랑’이 직접 스도쿠 기능을 개발하고 1000개 가량의 스도쿠 문제를 제공해주셨습니다. 라면먹는 몰랑은 “적어도 스도쿠 문제가 부족하지는 않을 것”이라고 말했죠. 폴리매스 회원들 사이의 스도쿠 랭킹을 확인할 수 있는 기능도 있습니다. 이외에 스도쿠가 아직 낯선 회원들은 ‘스도쿠란?’ 메뉴에 들어가 규칙을 익히며 스도쿠 푸는 법을 알 수 있죠.
폴리매스 스도쿠만의 매력, 문제 출제!
폴리매스 스도쿠의 차별화된 기능은 바로 회원들 각자가 만든 스도쿠 문제를 출제할 수 있고, 그 문제를 풀어볼 수도 있다는 것입니다. 폴리매스 스도쿠의 문제를 한 번이라도 풀어본 회원은 문제를 출제할 수 있죠. 문제를 출제하기 위해서는 지켜야하는 규칙이 있는데요. 그 규칙은 ‘스도쿠의 규칙에 맞게 출제할 것’, ‘출제하려는 스도쿠의 정답이 단 한 가지로만 나와야할 것’, ‘최소 17개의 힌트 숫자를 사용할 것’입니다. 또 라면먹는 몰랑은 “기존에 출제된 문제와 똑같은 스도쿠 문제를 제출하려는 것을 막기 위해 폴리매스 스도쿠가 일일이 출제 문제와 기존 문제를 비교한다”며 “회원들의 창의적인 스도쿠 문제 출제를 기대한다”고 말했죠. 에프매스, 수학동아 편집부, 폴리매스 관리진 모두가 회원 여러분의 적극적인 스도쿠 참여를 기다리고 있답니다!
● 스도쿠를 풀 수 있는 신의 한수는 존재할까?
스도쿠는 규칙이 단순함에도 불구하고, 어려운 난이도의 스도쿠가 쉽게 풀리지 않는다는 점에서 매력적인 퍼즐 게임입니다. 그래서 오래전부터 스도쿠는 어떤 컴퓨터 알고리듬이나 수학 이론이 적용된 완벽한 해결법이 있는 것은 아닌지 궁금증을 자아냈죠. 하지만 n×n 사이즈로 무한한 크기의 스도쿠는 'NP-완전 문제'라는 것이 증명됐습니다.
‘NP 문제’란 각 단계에서 여러 가지 가능성을 고려할 수 있는 문제를 말합니다. 빠른 시간 안에 정답을 찾긴 어렵지만, 문제에 대한 답이 주어지면 그 답이 정답인지는 쉽게 확인할 수 있다는 특징이 있죠. NP-완전 문제란 NP 문제 중에서도 또 다른 형태의 NP 문제로 변환할 수 있는 문제를 말합니다. n×n 크기의 스도쿠를 완벽히 한 번에 풀 수 있는 알고리듬이나 수학적 방법은 아직까지는 발견되지 않았습니다. 그래서 컴퓨터가 스도쿠를 풀기 위해선 모든 경우의 수를 일일이 확인하는 방법 외에는 없죠. 스도쿠 외에도 유명한 NP-완전 문제로는 지뢰찾기 게임, 외판원 순환 문제 등이 있습니다.
만약 어떤 NP-완전 문제를 ‘빠른 시간안에 정답을 찾아낼 수 있는 문제’로 바꿔 풀 수 있는 알고리듬이 있다면, 모든 NP 완전 문제는 빠른 시간안에 답을 찾을 수 있습니다. 이를 P 대 NP 문제라고 하죠. P 대 NP 문제는 미국 클레이수학연구소에서 정한 7개의 수학 난제인 ‘밀레니엄 문제’ 중 하나입니다.
