예전에 LiveScript를 사용해서 스도쿠 문제를 푸는 코드를 소개한 적이 있었는데, 세상 쓸데없는 글이었습니다. LiveScript는 별로 알려지지도 않았고, 심지어 제가 처음 관심을 갖고 익혀본 그 즈음부터는 아예 개발도 중단된 상태로 방치되고 있는 언어거든요. 게다가 언어 자체가 함수형 언어식 표현을 적극적으로 도입하고 있고, 가독성하고는 크게 관련이 없다보니 코드 하나하나가 지금 읽어봐도 뭔지 도대체 알 수가 없더군요. (사실 알 수는 있습니다;)
그래서 다시 파이썬으로는 스도쿠를 푸는 프로그램을 어떻게 만드는지 소개하고자 합니다. 이번에는 최대한 간결하고 읽기 편한 코드를 만드는 것을 목표로, 가장 짧게(?) 작성하는 것을 목표로 하지 않습니다. 그러면 문제를 풀어보겠습니다.
스도쿠 해법
스도쿠의 규칙은 간단합니다. 9 x 9 의 정사각형 공간이 있고, 몇 개의 숫자가 채워진채로 문제가 제시됩니다. 스도쿠 퍼즐은 몇 가지 간단한 규칙을 지키며 퍼즐의 빈 칸에 적당한 숫자를 모두 채워넣으면 됩니다. 규칙은 아래와 같습니다.
- 모든 칸에는 1~9 사이의 한 자리 정수가 들어갈 수 있습니다.
- 같은 가로줄에서는 1 ~ 9 사이의 숫자가 한 번씩만 들어갑니다.
- 같은 세로줄에서도 1 ~ 9 사이의 숫자가 한 번씩만 들어갑니다.
- 퍼즐판 가장 윗줄 왼쪽칸에서부터 가로 x 세로가 3 x 3 인 영역으로 전체 문제판을 나누었을 때, 각각의 영역에서도 1 ~ 9 의 숫자가 한 번씩만 들어갑니다.
이렇듯 문제의 규칙은 매우 간단합니다. 당연히 대부분의 문제는 몇 개의 칸에는 숫자가 채워진채로 시작합니다. 만약 숫자가 너무 적게 채워져있다면, 사람이 풀기에는 어려울 수 있겠지만 퍼즐의 답이 두 가지 이상이 되는 경우도 있을 수 있습니다. 여기서는 모든 가능한 답을 찾기 보다는 가능한 한 가지 답을 찾으면 끝내는 것으로 하겠습니다.
문제를 풀 때, 비어 있는 한 칸을 선택하고, 그 칸과 같은 가로줄, 세로줄, 구역에 있는 숫자들을 골라보면 1~9 사이의 숫자들 중에서 겹치는 것들을 제외한 것만이 그 칸에 올 수 있는 숫자가 됩니다. 만약 그런 숫자의 후보가 1개 밖에 없다면, 운이 좋게도 그 칸의 숫자를 찾게 되는 것입니다. 그 외에도 숙달된 스도쿠 해결사들은 퍼즐을 빠르게 풀어낼 수 있는 몇 가지 테크닉과 훈련된 패턴 인식능력들을 가지고 있습니다.
접근법
하지만 우리는 그런 전략이 필요없습니다. 사용할 수 없는 숫자들을 넣어보고 규칙에 맞지 않으면 다시 해보는 전략을 사용할 겁니다. 답을 찾는 알고리듬은 대략 다음과 같습니다.
- 문제를 처음 입력받으면, 미리 값이 정해진 칸과 빈 칸을 구분합니다.
- 빈 칸의 목록에서 하나를 골라내어, 그 칸에 들어갈 수 있는 숫자들을 나열합니다.
- 나열한 후보 중에서 한 숫자를 그 칸에 넣어봅니다. 그리고 다음 칸으로 진행합니다.
- 만약 빈 칸에 들어갈 수 있는 숫자가 없다면, 앞 칸에서 잘못된 숫자를 고른 겁니다. 앞 칸의 숫자를 다음 번 후보로 바꾸고 다시 시도해봅니다.
- 만약 남아있는 빈 칸이 없다면 문제를 푼 것입니다. 만약 첫번째 칸에 사용할 수 있는 숫자가 더 이상 없다면 풀리지 않는 문제입니다.
노드
퍼즐판의 각 칸을 표현할 클래스를 먼저 다음과 같이 정의합니다. 전체 셀의 인덱스로부터 행, 열, 구역을 계산해 낼 수 있으므로 셀을 만들 때 그 값들을 미리 지정해버립니다. 나중에 같은 행이나, 같은 열의 칸들은 사실 간단한 슬라이싱으로 쉽게 구할 수 있지만, 같은 구역에 있는 숫자들을 찾는 게 제법 많이 헷갈릴 수 있어서 이게 간단한 방법인 듯 합니다. 9 x 9 퍼즐판에 들어갈 숫자들이 일렬로 주어진다라고 하면 굳이 2차원 배열을 만들 필요없이, 1차원 리스트에서의 인덱스로 행, 열, 구역을 모두 계산할 수 있습니다.
# S는 퍼즐판의 크기
W, B, S = 0, 1, 9
class Cell:
def __init__(self, pos: int, n: int):
self.n = n
self.color = W if (n == 0) else B
self.r, self.c = divmod(pos, S)
self.z = (self.r // 3) * 3 + (self.c // 3)
def __repr__(self) -> str:
return f"{self.n:^3}"그리고 나중에 결과를 출력하기 편하기 위해 __repr__() 메소드도 구현했습니다. 이제 게임판을 만들어 보겠습니다. 위에서 소개한 알고리듬은 재귀 형태로 구성되기 때문에 아주 간단하게 작성될 수 있습니다. 특정한 셀에 대해서 같은 행, 열, 구역의 숫자들을 제외한 후보를 뽑아내는 메소드만 만들어주면 됩니다.
솔루션
그 외에 결과를 출력하는 show() 메소드까지 해서 마무리할 수 있습니다. 코드 자체는 정말 단순하기 때문에 파이썬 문법이 눈에 익으셨다면 따라 읽는 것만으로도 별다른 주석은 필요 없을 것 같습니다. (아마 show() 메소드가 가장 어려운 부분이 아닐까…)
모든 셀은 자신의 행, 열, 구역 값을 가지고 있으므로, 선택한 셀과 같은 행, 열, 구역에 있는 셀들의 숫자를 모아서 사용 가능한 숫자를 찾을 수 있습니다. 이 숫자들을 하나씩 시도해보고, 더 이상 시도할 숫자가 없으면 실패로 리턴하여, 이전에 처리한 칸에서 다른 숫자를 시도하도록 합니다.
class Grid:
def __init__(self, data: str):
self.data = [Cell(i, int(c)) for (i, c) in enumerate(data)]
def available_values(self, cell: Cell) -> set[int]:
return set(range(1, 10)) - (
{r_cell for r_cell in self.data if r_cell.r == cell.r}
| {c_cell for c_cell in self.data if c_cell.c == cell.c}
| {z_cell for z_cell in self.data if z_cell.z == cell.z}
)
def show(self):
'''그리드의 현재 상태를 출력'''
rows = ["|".join(str(self.data[x * S + y])
for y in range(S))
for x in range(S)]
for i in (3, 7):
rows[i:i] = ["-" * 35]
print("\n".join(rows))
def _solve(self, unknown_cells: list[Cell]) -> bool:
# 더 이상 남아있는 빈 칸이 없으면 문제 해결 완료
if not unknown_cells:
return True
cell, *rest = unknown_cells
for v in self.available_values(cell):
cell.n = v
result = self._solve(rest)
if result:
return True
# 실패했다면 값을 초기화하고 다른 값으로 시도
cell.n = 0
# 더 이상 시도할 값이 없다면 이전으로 되돌아감
return False
def solve(self):
unknown_cells = [cell for cell in self.data if cell.color == W]
return self._solve(unknown_cells)그리고 아래와 같이 검증해보았습니다.
g = Grid(
"00302060090030500100180640000810290070000"
"0008006708200002609500800203009005010300"
)
g.show()
g.solve()
g.show()
## 결과
0 | 0 | 3 | 0 | 2 | 0 | 6 | 0 | 0
9 | 0 | 0 | 3 | 0 | 5 | 0 | 0 | 1
0 | 0 | 1 | 8 | 0 | 6 | 4 | 0 | 0
-----------------------------------
0 | 0 | 8 | 1 | 0 | 2 | 9 | 0 | 0
7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 8
0 | 0 | 6 | 7 | 0 | 8 | 2 | 0 | 0
-----------------------------------
0 | 0 | 2 | 6 | 0 | 9 | 5 | 0 | 0
8 | 0 | 0 | 2 | 0 | 3 | 0 | 0 | 9
0 | 0 | 5 | 0 | 1 | 0 | 3 | 0 | 0
4 | 8 | 3 | 9 | 2 | 1 | 6 | 5 | 7
9 | 6 | 7 | 3 | 4 | 5 | 8 | 2 | 1
2 | 5 | 1 | 8 | 7 | 6 | 4 | 9 | 3
-----------------------------------
5 | 4 | 8 | 1 | 3 | 2 | 9 | 7 | 6
7 | 2 | 9 | 5 | 6 | 4 | 1 | 3 | 8
1 | 3 | 6 | 7 | 9 | 8 | 2 | 4 | 5
-----------------------------------
3 | 7 | 2 | 6 | 8 | 9 | 5 | 1 | 4
8 | 1 | 4 | 2 | 5 | 3 | 7 | 6 | 9
6 | 9 | 5 | 4 | 1 | 7 | 3 | 8 | 2
백트래킹
참고로 이 문제의 풀이와 같이 후보들을 시험한 후 막히면 뒷단계로 되돌아가는 문제 해결 전략은 ‘백트래킹(back-tracking)’이라고 합니다. 스도쿠외에도 N색으로 칠하는 문제나, N-Queen 문제와 같은 것들이 백트래킹을 적용하기 좋은 대표적인 예라고들 하네요.