스도쿠(数独, Sudoku) - 예제

PUBLISHED 2007. 3. 3. 11:22
POSTED IN 놀이터
지하철 역에서 몇 번 무가지를 들고 와서 스도쿠를 하다 보니, 문제를 풀 때 몇 가지 공통된 패턴이 존재한다는 느낌을 받았다. 즉, 이전 글(스도쿠(数独, Sudoku) - 개요와 규칙)에서 살폈던 규칙을 잘 이용하면 보다 쉽게 문제에 접근할 수 있다는 말이다.

이미 많은 사람들이 좋은 풀이법을 제시해 왔겠지만, 여기에서는 내가 경험을 통해 익힌 방법만으로 얘기해 보려 한다. (사실, 다른 방법은 어떤 게 있는지 모르겠다. -_-) 높은 난이도의 문제에 대해서 다른 해결 방법이 있는지는 모르겠는데, 적어도 지금까지는 잘 먹히고 있다. 행, 열, 서브매트릭스와 같은 용어는 지난 번 글에서 사용했던 그대로 이용하기로 한다.

일단 다음은 지난 글에서 보았던 스도쿠 매트릭스이다.

사용자 삽입 이미지

중간 중간이 비어 있는 스도쿠 매트릭스


사용자 삽입 이미지

서브매트릭스



[1]
스도쿠 게임의 특성 상 각 행이나 열에는 1부터 9까지의 숫자가 각각 하나씩만 들어갈 수 있고, 또 각 서브매트릭스에도 마찬가지 특성을 나타내도록 해야 한다. 위 그림에서 보이듯이, 2행과 3행(아래 그림에서 붉은색 음영으로 나타낸 부분)에 각각 1이 하나씩 있다. 다시 말하자면, 2행과 3행에 있는 다른 모든 빈칸에는 1이 들어가서는 안된다는 뜻이다. 또 서브매트릭스 A와 B에 1이 각각 하나씩 있으므로 서브매트릭스 A와 B에도 1이 들어가서는 안된다. 그러니 C 서브매트릭스(아래 그림에서 노란색 음영으로 나타낸 부분)에서 1이 들어갈 수 있는 곳은 1행 밖에 없다. 따라서 1행 7열의 자리에는 1 밖에 들어갈 수가 없다.

사용자 삽입 이미지

1행 7열


이제 F 서브매트릭스(아래 그림에서 노란색 음영으로  나타낸 부분)를 살펴 보면, 8열에서 1과 3 사이에 빈 칸 하나가 보인다. 이때 7열과 9열(아래 그림 붉은색 음영)에 각각 4가 있기 때문에 7열과 9열에 있는 빈칸에는 4가 들어가서는 안된다. 따라서 이 빈 칸에는 4가 들어가야 한다.

마찬가지로, H 서브매트릭스(아래 그림 녹색 음영)는 5, 6열(아래 그림 푸른색 음영)의 5 때문에 5, 6열 부분에는 5가 들어갈 수 없고, 따라서 7행 4열에 있는 빈칸에 들어갈 숫자는 5가 된다.

사용자 삽입 이미지

5행 8열과 7행 4열


같은 방법을 이용하여 다음과 같이 숫자를 하나씩 채워 나간다.

사용자 삽입 이미지

A 서브매트릭스(2행 2열)와 E 서브매트릭스(4행 4열)


사용자 삽입 이미지

A 서브매트릭스(3행 2열)



[2]
이처럼 나란히 줄지어 있는 서브매트릭스를 이용하여 빈칸을 메꾸다 보면 어느새 이 방법만으로는 더 이상 빈칸을 메꾸지 못하는 때가 온다. 그럴 때에는 행과 열의 조합을 통해 해결책을 알아 보는 것도 좋다.

사용자 삽입 이미지

행과 열의 조합을 통한 문제 해결


위 그림을 보면 1, 2행(붉은색 음영)에는 각각 8이 하나씩 있다. 그리고 3열(푸른색 음영)에도 마찬가지로 8이 있다. 따라서 A 서브매트릭스에서 1행, 2행, 혹은 3열에 해당하는 빈칸에는 8이 들어가서는 안된다. 따라서 남아 있는 3행 1열에 있는 빈칸에는 8이 들어가야 한다.

위에서 이야기한 두 가지 방법을 통해 빈칸을 채워 나간다.

사용자 삽입 이미지

G 서브매트릭스(7행 2열)


사용자 삽입 이미지

F 서브매트릭스(6행 7열)


사용자 삽입 이미지

B 서브매트릭스(2행 4열)



[3]
이제 남은 일은 빈칸을 하나씩 깔끔하게 채워 나가는 일 밖에 없다. 위 그림을 보면 2행(아래 그림에서는 푸른색 음영)에는 빈 칸이 두 개가 남아 있다(7, 8열). 채워진 숫자는 1, 4, 5, 6, 7, 8, 9로 2, 3을 빼고는 모두 하나씩 들어 있다.

사용자 삽입 이미지

빈칸 메꾸기(2행 8열)


이때 7열을 살피면, 7열(붉은색 음영)에는 이미 2가 있기 때문에 2행에서 2가 들어가야 할 곳은 8열이 된다. 이제 2행에는 빈칸이 하나 밖에 없다. 그때는 1부터 9까지의 숫자 가운데 남아 있는 숫자를 채워 주기만 하면 된다.

사용자 삽입 이미지

빈칸 채우기(2행 7열)


비슷한 과정이 A 서브매트릭스에서도 생긴다. A 서브매트릭스 역시 빈칸이 두 개로, 현재 1, 2, 5, 6, 7, 8, 9가 들어 있다. 따라서 나머지 채울 숫자는 3, 4이다. 이때 3열을 살피면, 7행 3열에 이미 숫자 3이 있기 때문에 3행 3열의 빈칸에는 3이 들어갈 수 없다. 따라서 1행 1열에 3이 들어가야 한다.

사용자 삽입 이미지

빈칸 채우기(1행 1열)


남아 있는 3행 3열에 숫자 4를 채운다.

사용자 삽입 이미지

빈칸 채우기(3행 3열)


이제 중요한 부분은 다 끝났다. 나머지는 지금까지 이용한 방법을 토대로 빈칸을 채우는 일 뿐이다. 참고로, 다음은 이 문제의 정답!

사용자 삽입 이미지