영국의 <Times>지를 펼치면, 빽빽한 영어 사이로 네모칸 속 숫자가 눈에 들어온다. 지면의 한쪽을 채우고 있는 81개의 네모 칸 스도쿠. 스도쿠는 세계 여러 나라 사람들을 작은 네모 속으로 빠트리는 블랙홀이다. 스도쿠를 개발한 일본에서는 매년 60만 권의 스도쿠 책이 팔리고, 우리나라에도 뒤늦게 스도쿠 열풍이 불어 관련 책자만 80여 권이 출간됐다. 스도쿠 게임은 최근 두뇌개발이라는 타이틀을 달고, 보드 게임은 물론 핸드폰 게임으로까지 출시됐다.


이름조차 생소한 스도쿠(SuDoku), 그 정체는 무엇일까? 일본말로 ‘겹치지 않아야한다’는 뜻의 스도쿠는 18세기 스위스 수학자 레온하르트 오일러의 ‘라틴사각형’이라는 게임에서 유래됐다. 이 게임은 19세기를 지나 20세기가 다 가도록 인기를 얻지 못하다가 1970년대에 들어서며 ‘넘버 플레이스’라는 게임으로 다시 소개돼 주목받았다. 1984년에는 일본의 퍼즐회사 니코리가 ‘스도쿠’라는 브랜드로 판매하면서 널리 알려졌다. 게임의 규칙은 간단하다. 가로ㆍ세로 9칸씩, 총 81칸 정사각형에 1~9의 숫자를 겹치지 않게 적어 넣기만 하면 된다. 단, 가로ㆍ세로 3칸, 총 9칸으로 이뤄진 작은 사각형 안에서도 1~9가 겹치지 않아야 한다.


단순한 숫자게임으로 보이지만 스도쿠는 수학 7대 난제 중 하나인 NP-Complete 문제이다. NP-Complete 문제는 완벽한 알고리즘으로 풀어도 최적의 해를 구하는 계산 시간이 기하급수적으로 늘어난다. 답이 무한히 많기 때문이다. 따라서 21세기 컴퓨터 과학의 도움으로 해결해야 할 난제이기도 하다.


알고리즘이란 수학적으로는 해답을 구하는 과정을 뜻하며, 컴퓨터분야에서는 문제 해결을 위해 컴퓨터가 사용하는 정확한 방법을 말한다. 그러나 풀이과정이 길고 경우의 수가 많아 아예 답을 구할 수 없거나 문제해결을 할 수 없을 때는 어떻게 해야할까. 이때에도 적용할 수 있는 알고리즘이 있다. 그것은 바로 휴리스틱(Heuristic) 알고리즘이다. 휴리스틱 알고리즘은 계산을 하다가 어느 정도의 시간이 흐르면 계산을 멈추고 최선의 방법을 선택하는 방식으로 돼 있다. 스도쿠 역시 기본틀인 81칸의 셀에 81개의 숫자들을 겹치지 않도록 배열 할 방법이 무한히 많기 때문에 휴리스틱 알고리즘을 적용해야 한다. 인간과 컴퓨터가 체스나 바둑을 둘 때, 인간이 컴퓨터를 이길 수 있는 이유도 게임이 휴리스틱 알고리즘으로 설계돼 있기 때문이다. 스도쿠의 경우처럼 체스나 바둑도 말을 움직이는 경우의 수가 무한해서, 움직일 경로를 탐색하던 컴퓨터가 시간제한에 걸리면 최적의 경로를 찾는 것을 중단하고 탐색한 경로 중 하나를 임의로 선택해버린다.


이러한 휴리스틱 알고리즘 외에 스도쿠에 적용할 수 있는 특정한 알고리즘도 있다. 물론 스도쿠를 제작할 때에도 이 알고리즘을 사용한다. X-Wing, Swordfish, Solving with Colors, Solving with Multi-Colors, XY-Wing 등의 알고리즘이 그것이다. 스도쿠는 무작위의 숫자로 이뤄진 퍼즐로 규칙이 없어 보이지만 알고보면, 알고리즘에 의해 철저히 계산돼 만들어진 것이다. 그렇기에 풀수 없게 만들어진 스도쿠는 없다.

이제 X-wing 알고리즘에 의한 스도쿠 풀이 법을 배워보자. X-wing은 ‘X자 모양으로 생겼다’라고 생각하면 쉽다. 위에 주어진 퍼즐을 살펴보자. 하나의 셀 안에 하나씩 들어있는 숫자는 원래부터 주어져 있던 것이며, 여러 개 들어있는 숫자는 이를 근거로 셀 안에 들어갈 수 있는 후보 숫자를 모두 적어 넣은 것이다.


두 개의 세로줄과 두 개의 가로줄을 임의로 선택하고, 그 교차점을 ★로 표시했다. 선택된 4개의 ★셀 안에는 공통된 숫자①이 들어있다. 여기서 ★셀을 제외한 세로와 가로줄의 1은 전부 지워줄 수 있다. 선택된 ★셀 중 하나가 확정된 숫자라 하더라도 이 원칙을 적용할 수 있다. 이러한 X-wing에 대한 알고리즘을 이해했다면, 3개의 세로줄과 3개의 가로줄을 이용하는 Swordfish나 4개의 세로줄과 4개의 가로줄을 이용하는 Jellyfish알고리즘을 이용해 문제를 풀 수도 있다.


사람이 보통 스도쿠 문제를 풀 때는 컴퓨터의 알고리즘이 아닌 추론의 방법을 사용한다. 즉 이미 알고 있는 숫자를 전제로, 빈칸을 채울 때는 연역적 사고를 빈 칸에 들어갈 수 없는 숫자를 지울 때는 귀납적 사고를 하게 된다. 때문에 스도쿠 게임을 하면 논리적 사고를 탄탄하게 할 수 있다. 또한 집중력과 추리력이 좋아져 지능향상과 두뇌계발에도 도움이 된다. 스도쿠 관련도서를 다수 집필한 정호성씨는 “스도쿠는 계산에 의한 수학적 해결법 보다는 직접 추론하는 물리적 해결법을 요하며, 주어진 명제를 이용하기 때문에 논리적 해결법이라고 볼 수 있다”고 말했다. 실제로 외국에서 유행하고 있는 스도쿠 문제들을 보면, 숫자가 아닌 알파벳 등을 이용해 새로운 퍼즐을 만들기도 한다.


이처럼 스도쿠는 수학과 직접적인 관련은 없다. 그러나 논리라는 접점은 있다. 수학과 스도쿠 모두 논리를 이용해 문제를 해결해야 하며 문제를 해결하는 과정을 통해 논리력을 기를 수 있기 때문이다. 국가수리과학 연구소의 조용승 소장은 “수학은 각 단계에서 논리적 비약 없이 답을 찾아야 하기 때문에 논리의 사고가 매우 중요하다”고 말했다.


학창시절 열심히 공부했던 수학을 까맣게 잊어버렸다고 다시 수학책을 집어들 필요는 없다. 작은 종이 위에 갇힌 81개의 숫자, 스도쿠와 함께라면 충분히 논리적 사고를 끌어낼 수 있기 때문이다. 요즘 유난히 건망증이 심해졌다거나 공강 시간에 무료함을 느낀다면 스도쿠의 매력에 푹 빠져보는 것은 어떨까.

도움주신 분 : 정호성

저작권자 © 숙대신보 무단전재 및 재배포 금지