d라이브러리

최근 아일랜드 더블린대 개리 맥과이어 교수팀은 스도쿠에 대한 흥미로운 연구 결과를 발표했다. 바로 스도쿠의 정답이 하나뿐이려면 먼저 공개된 숫자가 최소 17개는 돼야 한다는 것이다.

스도쿠는 3×3 정사각형을 가로세로에 각각 3개씩 배열한 81칸에 일정한 규칙에 따라 숫자를 써 넣는 퍼즐이다. 미리 공개된 20~24칸의 숫자를 기준으로, 나머지 빈 칸에 1부터 9까지 숫자가 겹치지 않도록 써 넣으면 된다. 이 때 먼저 공개된 숫자의 개수가 난이도를 결정한다. 적은 숫자를 단서로 나머지 칸을 채우는 것이 이 퍼즐의 묘미다.

맥과이어 교수는 ‘히팅-셋(Hitting-set) 알고리즘’을 개발해 연구를 진행했다. 계산이 빠른 슈퍼컴퓨터에 이 알고리즘을 적용한 뒤, 공개된 숫자가 16개일 때 정답이 하나인 문제가 있는지 일일이 확인했다. 그 결과 ‘스도쿠는 공개된 숫자가 16개일 때 정답이 하나인 문제는 없다’는 것이 밝혀졌다.

수학자들의 오랜 숙제였던 이 문제를 증명한 맥과이어 교수는 “이 연구에 사용된 알고리즘은 스도쿠 문제뿐만 아니라, 유전자 염기서열 분석에도 활용될 것으로 기대한다”고 말했다.