스도쿠의 역사 — 미국에서 태어나 일본에서 이름을 얻기까지

스도쿠의 역사는 한 나라의 발명담이 아니라 세 무대를 거친 릴레이입니다. 규칙은 1979년 미국에서 ‘넘버 플레이스’라는 이름으로 완성됐고, 이름과 출제 문화는 1980년대 일본에서 꽃폈으며, 세계적 유행의 결정타는 2004년 영국의 한 신문이었습니다. 세 이름이 저마다 발명자로 불리곤 합니다 — “카지 마키가 발명했다”, “웨인 굴드가 만들었다”, “오일러가 원조다”라는 서술이 각각 널리 퍼져 있습니다. 다만 기록들이 전하는 세 사람의 공헌은 서로 다른 단계에 놓여 있습니다. 역할을 나눠 보면 각자의 기여가 더 선명해집니다.

1979년 미국 — 규칙이 굳다

현대 스도쿠의 직접적 출발점은 1979년 5월 미국 잡지 《Dell Pencil Puzzles & Word Games》입니다. 제16호에 ‘넘버 플레이스(Number Place)‘라는 이름으로 실렸습니다. 초기 문제에는 동그라미 친 칸에 따로 제시한 숫자를 넣는 부가 장치가 있었지만, 각 행·열·3×3 블록에 1부터 9까지가 한 번씩 들어가야 한다는 핵심 규칙은 이미 완성돼 있었고, 이후 이 부가 장치는 사라졌습니다(Ed Pegg Jr.의 조사).

만든 사람으로 인정받는 인물은 인디애나폴리스의 은퇴 건축가 하워드 간스(Howard S. Garns, 1905–1989)입니다. 첫 문제가 실렸을 때 그는 74세였습니다. 여기서 정확히 짚을 부분이 있습니다. 원 지면에는 저자 이름이 인쇄되지 않았습니다. 간스를 창안자로 보는 근거는, 《뉴욕 타임스》 퍼즐 편집자 윌 쇼츠(Will Shortz)가 델의 과월호를 뒤져 찾아낸 패턴입니다. 넘버 플레이스가 실린 호에는 기고자 명단에 간스가 있고, 실리지 않은 호에는 그의 이름도 없었습니다. 그래서 이 정황 증거가 뒷받침하는 서술은 “간스가 창안자로 널리 인정된다”입니다. 빈칸의 답을 주변 단서로 복원한다는 점에서, 창안자를 찾아낸 방식 자체가 스도쿠를 닮았습니다(Crown Hill Heritage Foundation의 약력).

간스는 1989년에 세상을 떠났습니다. 자신이 만든 퍼즐이 15년 뒤 지구를 뒤덮는 장면은 끝내 보지 못했습니다.

1984~1988년 일본 — 이름과 문화가 붙다

퍼즐을 일본에 들여온 곳은 퍼즐 회사 니콜리(Nikoli)입니다. 니콜리는 자신들이 이 퍼즐을 발명했다고 주장하지 않습니다. 오히려 공식 역사에서 미국 잡지의 넘버 플레이스를 발견해 1984년 일본 독자에게 소개했다고 밝힙니다(Nikoli 공식 역사). 이 일을 주도한 사람이 니콜리 창업자 카지 마키(鍜治真起)입니다.

이름의 유래도 흔히 압축돼 전해지는 것보다 두 단계로 나뉩니다. 일본수독협회의 기록에 따르면 1984년 4월 카지는 《월간 니콜리스트》에 자신이 만든 문제를 실으면서 「数字は独身に限る(숫자는 독신에 한한다)」라는 긴 제목을 붙였습니다(일본수독협회 역사). 같은 행·열·블록 안에서 같은 숫자가 짝을 이루지 못한다는 말장난입니다. 오늘날 쓰는 축약형 数独(스도쿠)은 1988년 니콜리 단행본이 나오면서 명확히 자리 잡았습니다. 数(숫자)와 独(독신)의 첫 글자를 딴 조합어입니다. 그러니 이름이 붙은 과정은 두 시점으로 나뉩니다. “1984년 일본에서 스도쿠라는 이름을 얻었다”는 흔한 요약이 가리키는 것은 그중 앞 시점입니다. 긴 제목으로 소개된 것이 1984년, 오늘날의 약칭 数独이 자리 잡은 것이 1988년입니다(Japan Policy Forum에 실린 카지 회고).

니콜리가 남긴 더 큰 유산은 편집 문화입니다. 1986년부터 니콜리는 힌트 숫자를 대칭으로 배치하는 것을 출제 원칙으로 삼았습니다. 대칭은 유일해를 만드는 데 필요한 수학 규칙이 아닙니다. 다만 문제를 하나의 시각적 작품처럼 보이게 하고, 손으로 만든 퍼즐에 출제자의 개성을 실었습니다. 독자가 직접 문제를 투고하고 서로 다듬는 참여형 문화도 여기서 나왔습니다. 훗날 2005년 영국 신문 경쟁에서 《가디언》이 컴퓨터 생성 문제 대신 니콜리의 수제 문제를 쓴다는 점을 차별점으로 내세운 것도 이 전통 덕분입니다.

이름을 둘러싼 역설도 하나 짚어 둘 만합니다. 니콜리는 일본에서 数独 관련 상표를 확보해 둔 반면 해외 상표는 넓게 확보하지 않았던 것으로 전해집니다. 그 결과 일본에서는 다른 출판사들이 상표를 피해 영어식 이름 ‘ナンプレ(난푸레, Number Place의 준말)‘를 쓰고, 영어권에서는 일본식 이름 ‘Sudoku’를 장르명처럼 씁니다. 영어 이름은 일본에 남고, 일본 이름은 영어권에서 세계어가 된 셈입니다. 카지는 해외 상표를 독점하지 않은 것이 수익에는 불리했지만 확산에는 도움이 됐다고 회고했습니다.

1997~2005년 — 웨인 굴드와 세계화

일본 밖에서 스도쿠가 무명에 가깝던 약 20년을 끝낸 사람은 웨인 굴드(Wayne Gould)입니다. 뉴질랜드 출신으로 홍콩에서 판사를 지낸 인물입니다. 본인의 회고에 따르면 그는 1997년 도쿄의 한 서점에서 스도쿠 책을 발견했습니다. 일본어를 읽지 못했지만 격자만 보고 규칙을 이해할 수 있었다고 합니다. 이 언어 비의존성이 나중에 세계화의 핵심 조건이 됩니다(The Independent, “The rise and rise of Sudoku”).

굴드가 한 일은 퍼즐 발명이 아니라 공급망의 발명에 가깝습니다. 그는 약 6년에 걸쳐 새 문제를 생성하고 난이도를 분류하는 컴퓨터 프로그램을 만들었습니다. 사람이 손으로 만들 때보다 훨씬 많은 문제를 뽑아낼 수 있었고, 신문은 매일 다른 난이도의 문제를 안정적으로 공급받을 수 있게 됐습니다.

굴드의 첫 신문용 퍼즐은 2004년 9월 미국 뉴햄프셔의 지역지 《The Conway Daily Sun》에 실렸습니다. 다만 대중적 전환점은 런던이었습니다. 굴드는 스도쿠가 들어간 지면을 직접 합성한 모형을 들고 《The Times》 편집부를 찾아갔습니다. 특집 편집자 마이크 하비(Mike Harvey)는 처음에는 그를 돌려보내려 했지만, 완성된 지면 모형을 보고 약 2분 만에 채택을 결정했다고 회고했습니다(The Guardian, 2005). 《The Times》는 2004년 11월 12일 ‘Su Doku’라는 표기로 첫 문제를 실었습니다.

이후는 빨랐습니다. 2005년 5월에는 《텔레그래프》, 《인디펜던트》, 《가디언》, 《데일리 메일》, 《선》 등 영국 전국지가 경쟁하듯 스도쿠를 실었습니다. 《선》은 자사 이름을 붙여 ‘Sun doku’로 홍보했고, 전문 잡지 초판은 10만 부 규모로 나왔습니다. 2006년 윌 쇼츠가 쓴 《TIME 100》 소개에 따르면, 굴드의 퍼즐은 400개가 넘는 세계 신문에 실렸고 관련 책은 400만 부 이상 팔렸습니다(TIME 100 — Wayne Gould).

그래서 2005년의 붐은 “좋은 퍼즐이 자연스럽게 발견된 사건”만은 아니었습니다. 일본의 수제 퍼즐 문화, 컴퓨터 생성 기술, 신문 간 독자 확보 경쟁, 무료 배포형 마케팅이 한자리에서 만난 미디어 사건이었습니다. 숫자라 번역이 필요 없고, 규칙 설명이 몇 줄이면 끝나고, 격자 하나만 인쇄하면 되고, 매일 새 문제를 낼 수 있다는 조건이 그 위에 겹쳤습니다.

숫자로 본 스도쿠

스도쿠는 수학자들의 좋은 소재이기도 했습니다. 아래 세 숫자는 모두 계산되거나 증명된 값입니다.

6,670,903,752,021,072,936,960 — 규칙을 만족하는 완성된 9×9 격자의 총 개수입니다. 약 6.67×10²¹개죠. 2005년 베르트람 펠겐하우어와 프레이저 자비스가 계산했고, 에드 러셀이 별도 프로그램으로 검산했습니다(Felgenhauer–Jarvis 계산 페이지). 주의할 점은 이것이 “만들 수 있는 문제의 수”가 아니라 유효한 완성 해답 격자의 수라는 것입니다. 하나의 완성 격자에서도 어떤 칸을 힌트로 남기느냐에 따라 수많은 문제가 나오고, 그중 상당수는 유일해를 갖지 않습니다.

5,472,730,538 — 회전·반사, 숫자 이름 바꾸기, 규칙을 보존하는 행·열 교환 등으로 같아지는 것을 하나로 묶은, ‘본질적으로 다른’ 격자의 수입니다. 약 54.7억 개죠. 러셀과 자비스가 계산했습니다(Russell–Jarvis, Mathematics of Sudoku II). 앞의 6.67×10²¹과 이 54.7억은 같은 대상을 다르게 센 것이 아니라, 애초에 서로 다른 질문에 대한 답입니다.

17 — 유일한 정답을 보장하는 문제에 필요한 최소 힌트 개수입니다. 17개짜리 유일해 문제는 오래전부터 알려져 있었지만, 16개짜리가 절대 존재하지 않는지는 오랫동안 미해결이었습니다. 2012년 게리 맥과이어, 바스티안 투게만, 질 치바리오 연구진이 이를 증명했습니다(University College Dublin 발표). 이들은 81칸 중 16칸을 고르는 모든 조합을 무작정 대입하지 않았습니다. 다른 완성으로 바뀔 수 있는 셀 집합(‘unavoidable set’)을 찾고, 그 집합들을 모두 건드리는 후보만 골라 효율적으로 탐색했습니다. 아일랜드 고성능컴퓨팅센터(ICHEC)의 장비로 약 1년, 700만 CPU 시간이 들었습니다. 결과 공개는 2012년, 동료심사를 거친 《Experimental Mathematics》 학술지 게재는 2014년이라 “2012년에 증명”과 “2014년에 논문 출판”은 서로 모순되지 않습니다(arXiv:1201.0749).

한 가지는 솔직하게 적어 둡니다. 이것은 종이와 연필의 증명이 아니라 방대한 컴퓨터 탐색에 기대는 증명이라, 탐색 코드에 오류가 있었을 가능성이 원리적으로는 남습니다. 그럼에도 이 결과가 받아들여지는 이유는 게재지의 권위가 아니라 구조에 있습니다 — 16힌트 유일해 문제가 단 하나만 발견돼도 즉시 무너지는 주장인데, 공개 후 지금까지 반례가 나오지 않았고, 선행했던 수만 건 규모의 17힌트 문제 수집에서도 16힌트는 끝내 나타나지 않았습니다.

이 17이라는 수가 뜻하는 범위도 적어 둘 만합니다. 17은 ‘유일해를 갖는 문제가 존재할 수 있는 가장 적은 힌트 수’를 가리킵니다. 개별 문제 차원에서는 17개 힌트로도 답이 여럿인 배치가 있을 수 있고, 힌트 수와 체감 난이도의 관계는 느슨합니다 — 사람이 느끼는 난이도는 힌트 수보다 풀이에 필요한 추론 기법에 더 크게 좌우된다고 알려져 있습니다.

대회, 오일러, 그리고 두 개의 일화

첫 국제 대회는 2006년 3월 이탈리아 루카에서 열린 제1회 세계 스도쿠 선수권입니다. 22개국에서 85명이 참가했고, 우승자는 체코의 31세 회계사 야나 틸로바(Jana Tylová)였습니다. 시상식에서는 웨인 굴드가 우승 트로피를 건넸습니다(Guinness World Records). 종이 신문 유행이 시작된 지 약 16개월 만에 취미가 국제 종목이 된 셈입니다.

스도쿠를 이야기할 때 18세기 수학자 레온하르트 오일러의 라틴 방진이 조상으로 자주 언급됩니다. 한 줄과 한 열에 같은 기호가 두 번 나오지 않는다는 점에서 둘은 분명 닮았습니다. 다만 라틴 방진에는 각 3×3 블록이 1~9를 담아야 한다는 조건이 없습니다. 그래서 두 격자의 관계를 그대로 옮기면, 완성된 스도쿠 격자는 3×3 블록 제약을 더한 특수한 라틴 방진으로 서술됩니다. ‘오일러가 스도쿠를 발명했다’는 기원 서술과 ‘구조적으로 친척뻘’이라는 관계 서술은 서로 다른 층위의 이야기입니다.

마지막으로, 스도쿠가 얼마나 사람을 사로잡는지 보여 주는 일화 하나. 호주 언론 보도에 따르면 2008년 시드니의 한 마약 사건 재판이 중단됐습니다. 약 3개월간 100명 넘는 증인이 증언한 뒤, 배심원 몇 명이 증언을 듣는 대신 스도쿠를 풀고 있었다는 사실이 드러났기 때문입니다. 열심히 메모하는 것처럼 보였지만, 노트에 적힌 것은 재판 기록이 아니라 숫자였다고 전해집니다(ABC News Australia).