d라이브러리

아~! 그림에 문외한인 나 오일러도 그릴 수 있을 것 같은 이 그림은 뭐지? 추상회화의 거장 피트 몬드리안의 그림이라고? 너무 단순해서 대단한 그림인지 알아보지 못했구먼.분명 무언가 심오한 의미를 담고 있겠지? 그나저나 마치 퍼즐판처럼 생긴 그림을 보니 ‘스도쿠’가 생각나는군. 스도쿠를 누구보다 빠르게 풀 방법은 없을까? 

숫자 퍼즐 하면 빼놓을 수 없는 게 스도쿠다. 한번 풀기 시작하면 시간 가는 줄 모르고 즐길 수 있다. 이런 중독성 때문에 세계적으로 사랑받고 있다. 스도쿠의 규칙은 간단하다. 가로·세로가 각각 9칸인 총 81칸의 퍼즐판에 1부터 9까지 수를 행과 열, 3×3 상자 안에 중복되지 않게 채워 넣으면 된다. 

규칙은 간단하지만 스도쿠를 만들 수 있는 경우의 수는 무려 6,670,903,752,021,072,936,960가지나 된다. 2006년 영국 수학자 프레이저 야비스는 공개된 숫자가 없을 때 가능한 경우를 모두 따져 구했다. 숫자를 많이 공개하거나 칸의 수를 줄여서 난이도를 조절할 수 있다.기본적으로 스도쿠는 정답이 1개여야 하는데, 답이 여러 개인 경우도 있다. 답이 반드시 하나려면 몇 개의 숫자를 미리 알려줘야 할까? 2012년 호주 수학자 개리 맥과이어가 이끄는 연구팀은 81칸에 최소 17개 숫자가 공개돼 있어야 한다고 밝혔다. 연구팀은 숫자가 16개만 알려져 있을 때 정답이 하나인 문제가 있는지 슈퍼컴퓨터를 돌려 일일이 찾았지만, 답이 1개인 문제를 단 하나도 찾지 못했다.

원조 스도쿠는 오일러의 직교라틴방진

스도쿠는 미국 건축가 하워드 간즈가 1979년 미국 퍼즐 잡지 ‘델지’에 ‘넘버플레이스’라는 이름으
로 처음 소개했다. 하지만 큰 인기를 누리지 못했다. 다행히 일본으로 전해져 1984년 일본 퍼즐 잡
지 ‘니코리’에 ‘스도쿠’라는 이름으로 실렸다. 스도쿠는 이때부터 대중에게 알려지기 시작해 현재는 세계인이 사랑하는 퍼즐이 됐다. 스도쿠는 일본어로 ‘숫자는 한 번씩만 쓸 수 있다’를 줄인 말이다. 

스도쿠의 개발자는 간즈지만, 스도쿠가 탄생하는 데 결정적인 역할을 한 사람은 오일러 프로젝트의 주인공, 스위스 수학자 레온하르트 오일러다. 오일러가 만든 ‘직교라틴방진’을 기초로 스도쿠가 만들어졌기 때문이다. 1782년 오일러는 아래와 같이 36명의 장교를 세우는 문제를 제시했다.

“각각 6개의 부대와 계급이 있다. 각 부대에서 계급당 1명씩 36명을 뽑아 6명씩 6줄로 세운다고 할 때, 각 행과 열에 부대와 계급이 겹치지 않게 세울 수 있는 방법이 있을까?”

이는 수학적으로 6차 직교라틴방진이 있는지 묻는 문제다. 직교라틴방진은 각 행과 열에 동일한 숫자나 알파벳이 겹치지 않게 만든 사각형 배열이다. 

오일러는 행과 열의 수가 6, 10, 14와 같이 4k+2(k=1, 2, 3…) 꼴인 배열에서는 각 행과 열에 부대와 계급이 겹치지 않게 장교를 세울 수 없다고 추측했다. 1901년 프랑스 수학자 가스통 타리가 6차직교라틴방진이 없다는 것을 증명하면서, 추측은 맞는 것처럼 보였다. 

하지만 1960년 수학자 라지 보스와 샤라드찬드라 슈리칸데, 어니스트 파커가 10차 직교라틴방진이 있다는 걸 보이면서 오일러의 추측은 빗나갔다.

한편 스도쿠는 9차 직교라틴방진의 변형이라 보면 된다. 인기 퍼즐인 만큼 규칙이 다양하게 바뀐 스도쿠도 많이 있으니 이참에 즐겨보자. 

오일러 프로젝트 96번 문제는 스도쿠를 프로그래밍으로 풀어보는 문제다. 다양한 난이도를 가진 50개의 스도쿠를 해결해야하는 만큼 쉽지 않지만 도전해 보자! 더 나아가 변형 스도쿠도 프로그램으로 해결해 보면 또 다른 재미를 느낄 수 있지 않을까?