스도쿠는 종이와 연필만 있으면 풀 수 있는 간단한 논리 퍼즐입니다. 80년대에 일본에서 유행했다가 잠잠해졌는데, 요즘들어 뒤늦게 영국에서 유행중이라는군요. 스도쿠는 數獨의 일본식 발음이라고 하네요.

이 퍼즐을 푸는 방법은 간단합니다.

3가지 규칙이 있습니다.

1. 가로줄에는 1부터 9까지의 숫자가 하나씩 들어간다.
2. 세로줄에는 1부터 9까지의 숫자가 하나씩 들어간다.
3. 9개의 3x3 사각형에는 1부터 9까지의 숫자가 하나씩 들어간다.

세 개의 규칙을 가지고 이쪽저쪽으로 끼워맞춰보고, 시행착오를 겪다 보면, 어느 칸에 어느 숫자가 들어가게 될지 짐작할 수 있습니다. 하나하나 채워서 81개의 칸을 다 채우면 완성.

시시하게 들릴지도 모르지만 굉장히 재미있어요. 시험기간은 제쳐두고 요즘 이 퍼즐에 말려 있습니다 oTL



그런데, 프로그래머라면 이 퍼즐을 갖고 놀다가 본능적으로 떠오르는 의문이 있을 겁니다. 이 퍼즐을 자동으로 풀어주는 프로그램을 만들 수 있지 않을까? 네. 자동화는 프로그래머의 본성인 겁니다 -_-

간단하고 쉽게 예상할 수 있는 알고리즘이 있습니다.
1. 모든 칸마다 들어갈 수 있는 후보 숫자들을 표시한다.
2. 후보 숫자가 하나뿐인 칸은 그 숫자로 채운다.
3. 가로줄, 세로줄, 혹은 3x3 사각형에 한 숫자가 들어갈 수 있는 자리가 하나밖에 없으면 그 칸을 채운다.

네. 간단한 퍼즐의 경우 위의 1, 2, 3을 반복하면 퍼즐을 풀 수 있습니다. 손으로 풀 때도 종이와 연필만 있으면 쉽게 문제를 풀 수 있는 방법이지요. 그러나 퍼즐이 좀더 어려워지면 위의 1, 2, 3만으로는 문제가 해결되지 않는 상황에 맞닥뜨리게 됩니다.

손으로 문제를 풀 때는, 여기서부터 복잡한 논리적 추론이 들어가게 됩니다. 논리적인 추론을 통해서 몇가지 후보들을 제거하다 보면 막혔던 게 풀리는 경우도 있고, 그것도 안되면 후보들 중에 하나를 그냥 찍어봐서 모순이 생길 때까지 밀고 나가보는 방법도 있습니다.

그러면 컴퓨터로 이 문제를 풀 수 있는 좀더 스마트한 알고리즘은 없는 걸까요?



안타깝게도, 없습니다. -_- 이 문제는 NP-Complete라는 사실이 증명되었거든요. 따라서 P=NP 문제가 증명되어 컴퓨터과학계가 통째로 열번쯤 뒤집히기 전에는 이 문제를 푸는 스마트한 알고리즘은 안 나옵니다. 그저 CPU의 성능을 믿고 열심히 백트래킹해보는 수밖에요. 다행히 81칸밖에?! 되지 않으니 해가 유일할 경우 합리적인 시간 내에 답이 나오긴 합니다.

이런 순수한 논리 퍼즐 가운데 많은 문제가 NP-Complete라는 사실이 알려져 있지요. 지뢰찾기를 해결하는 문제도 NP-Complete라고 해요. 그런 걸 보면, 실은 NP-Complete 문제는 인간은 비교적 쉽게 풀 수 있지만 컴퓨터는 절대 쉽게 풀 수 없는 문제들의 집합일지도? 하는 실없는 생각을 잠시 해보았습니다...;