solving every sudoku puzzle
이 글은 Peter Norvig 이 쓴 Solving Every Sudoku Puzzle 을 한국어로 번역한 것이다. 번역상의 오탈자는 번역자 (이메일, 홈페이지) 에게 신고 바란다.
이 에세이는 모든 스도쿠 퍼즐을 풀 수 있는 프로그램을 작성하는 과정에 관한 것이다. 이런 프로그램을 작성하는 것은 사실 굉장히 쉽다. (중요한 코드는 한 페이지 분량이며, 테스트와 기타 코드를 합해도 두 페이지에 불과하다) 이 프로그램은 두 가지의 큰 아이디어를 이용해 구현되었다. 제약 조건 전파 와 탐색 이 그것이다.
이 글에서 쓸 용어부터 정의하고 시작하자. 스도쿠 퍼즐은 81개의 칸 (square) 을 갖는 9x9 크기의 격자 이다. 스도쿠를 즐겨 하는 사람들은 대개 각 세로줄에 1-9, 각 가로줄에는 A-I 까지의 번호를 붙여 부른다. 가로줄이나 세로줄, 3x3 사각형처럼 9개의 칸 묶음들은 단위 (unit) 라고 부르고, 한 단위에 포함된 칸들은 서로 이웃 (peer) 이라고 한다. 스도쿠 퍼즐은 이와 같은 격자 중 일부 칸은 비어 있고, 일부 칸에는 숫자가 쓰여 있는 형태를 가진다. 이 때 스도쿠 퍼즐의 목적은 다음과 같다:
각 단위 내의 칸들이 1부터 9까지 숫자들의 순열 을 포함하도록 빈 칸을 채운다.
다시 말하자면, 한 단위에는 어떤 숫자도 두 번 출현할 수 없고, 1 부터 9 까지의 각 숫자가 정확히 한 번씩 출현해야 한다는 것이다. 각 칸에 쓰인 숫자는 이웃 칸에 쓰인 모든 숫자들과 서로 달라야 한다는 말이다. 아래는 각 칸의 이름과, 예시 퍼즐, 그리고 이 퍼즐의 답을 보여준다.
A1 A2 A3| A4 A5 A6| A7 A8 A9 4 . . |. . . |8 . 5 4 1 7 |3 6 9 |8 2 5
B1 B2 B3| B4 B5 B6| B7 B8 B9 . 3 . |. . . |. . . 6 3 2 |1 5 8 |9 4 7
C1 C2 C3| C4 C5 C6| C7 C8 C9 . . . |7 . . |. . . 9 5 8 |7 2 4 |3 1 6
---------+---------+-------- ------+------+------ ------+------+------
D1 D2 D3| D4 D5 D6| D7 D8 D9 . 2 . |. . . |. 6 . 8 2 5 |4 3 7 |1 6 9
E1 E2 E3| E4 E5 E6| E7 E8 E9 . . . |. 8 . |4 . . 7 9 1 |5 8 6 |4 3 2
F1 F2 F3| F4 F5 F6| F7 F8 F9 . . . |. 1 . |. . . 3 4 6 |9 1 2 |7 5 8
---------+---------+-------- ------+------+------ ------+------+------
G1 G2 G3| G4 G5 G6| G7 G8 G9 . . . |6 . 3 |. 7 . 2 8 9 |6 4 3 |5 7 1
H1 H2 H3| H4 H5 H6| H7 H8 H9 5 . . |2 . . |. . . 5 7 3 |2 9 1 |6 8 4
I1 I2 I3| I4 I5 I6| I7 I8 I9 1 . 4 |. . . |. . . 1 6 4 |8 7 5 |2 9 3
각 칸은 항상 3개의 단위에 속해 있고, 20개의 이웃을 갖는다. 예를 들어, 아래는 C2 칸을 포함하는 3개의 단위와 해당하는 이웃들을 보여준다.
A2 | | | | A1 A2 A3| |
B2 | | | | B1 B2 B3| |
C2 | | C1 C2 C3| C4 C5 C6| C7 C8 C9 C1 C2 C3| |
---------+---------+--------- ---------+---------+--------- ---------+---------+---------
D2 | | | | | |
E2 | | | | | |
F2 | | | | | |
---------+---------+--------- ---------+---------+--------- ---------+---------+---------
G2 | | | | | |
H2 | | | | | |
I2 | | | | | |
파이썬 을 이용하면 단위와 이웃, 칸들의 관계를 다음과 같이 표현할 수 있다. (이 코드는 파이썬 2.5 이상을 필요로 한다)
def cross(A, B):
"A 와 B 에 포함된 원소들의 교차곱 (cross product) 을 반환한다."
return [a+b for a in A for b in B]
digits = '123456789'
rows = 'ABCDEFGHI'
cols = digits
squares = cross(rows, cols)
unitlist = ([cross(rows, c) for c in cols] +
[cross(r, cols) for r in rows] +
[cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')])
units = dict((s, [u for u in unitlist if s in u])
for s in squares)
peers = dict((s, set(sum(units[s],[]))-set([s]))
for s in squares)마지막 두 줄은 파이썬에 익숙하지 않은 독자들에게는 이해하기 어려울 수도 있다. 부연 설명하자면, 위 코드의 dict 는 사전 (dictionary) 를 의미하는 것으로 파이썬에서 키를 값으로 대응시켜 주는 해시 테이블을 가리키는 용어이다. dict 를 생성할 때 각 키와 값은 (키, 값) 쌍의 목록으로 전달되며, 따라서 dict((s, [...]) for s in squares) 는 각 칸의 이름 s 를 리스트 [...] 로 대응시키는 사전을 생성하는 문장이다. 그리고 [u for u in unitlist if s in u] 는 s 를 포함하는 모든 단위들의 목록을 생성하는 리스트 축약 문법이다. 따라서 units 에 대한 대입문을 한 마디로 설명하자면 다음과 같다: units 는 각 칸의 이름을 해당 칸이 포함된 모든 단위들의 목록으로 대응시키는 사전이다. 이와 비슷한 맥락에서, peers 는 각 칸의 이름을 해당 칸과 이웃 관계를 갖는 모든 칸들의 목록으로 대응시키는 사전이라고 이해하면 된다.
이쯤해서 간단한 단위 테스트를 해봐서 나쁠 것은 없을 것이다 (전부 패스한다)
def test():
"A set of unit tests."
assert len(squares) == 81
assert len(unitlist) == 27
assert all(len(units[s]) == 3 for s in squares)
assert all(len(peers[s]) == 20 for s in squares)
assert units['C2'] == [['A2', 'B2', 'C2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2'],
['C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9'],
['A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2', 'C3']]
assert peers['C2'] == set(['A2', 'B2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2',
'C1', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9',
'A1', 'A3', 'B1', 'B3'])
print 'All tests pass.'칸과 단위, 그리고 이웃들을 정의했으니 스도쿠 게임판 (격자) 을 표현하는 자료 구조를 만들어 보자. 여기에서는 두 개의 자료 구조를 이용한다. 첫 번째는 퍼즐의 초기 상태를 나타내는 텍스트 포맷이다. 우리는 이 형태를 grid 라고 부르기로 한다. 두 번째로, 퍼즐을 푸는 중간 과정에서 내부적으로 사용할 자료 구조가 있다. 이 자료 구조는 각 칸이 주어질 때 이 칸에 들어갈 수 있는 후보 숫자들을 모두 반환할 수 있도록 구성하자. 따라서 이 자료 구조를 values 라고 부르기로 한다.
텍스트 포맷 (grid) 는 각 칸을 하나의 문자로 표현하되, 1부터 9까지의 숫자로 미리 숫자가 채워져 있는 칸, 그리고 0 또는 마침표로 비어 있는 칸을 표기하도록 하자. 다른 모든 문자들은 무시한다 (빈칸이나 가로/세로줄, 혹은 개행 문자 등). 그러므로 다음 세 가지의 입력을 모두 똑같이 처리하게 된다.
"4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......"
"""
400000805
030000000
000700000
020000060
000080400
000010000
000603070
500200000
104000000"""
"""
4 . . |. . . |8 . 5
. 3 . |. . . |. . .
. . . |7 . . |. . .
------+------+------
. 2 . |. . . |. 6 .
. . . |. 8 . |4 . .
. . . |. 1 . |. . .
------+------+------
. . . |6 . 3 |. 7 .
5 . . |2 . . |. . .
1 . 4 |. . . |. . .
"""이제 values 를 어떻게 표현할지 얘기해 보자. 물론 9x9 크기의 배열을 사용하는 방법이 맨 처음 떠오르겠지만, 우리는 각 칸을 A1 같은 이름으로 표현하기로 했지, (0,0) 같이 좌표로 표현하기로 한 것이 아니다. 그러므로 문자열 키를 갖는 dict 로 values 를 표현하기로 한다. values 의 각 값은 해당 칸이 가질 수 있는 숫자들의 집합이 된다. 만약 이 칸이 채워진 채로 주어졌거나, 어떤 값을 가져야 하는지를 탐색 중에 알아냈다면 한 개의 숫자만을 포함할 테고, 아니라면 여러 개의 숫자를 포함할 것이다. 이 숫자들의 집합을 파이썬의 리스트나 집합 자료 구조를 이용해 표현할 수도 있지만, 여기서는 문자열을 이용하기로 하자 (왜 이런 선택을 했는지는 나중에 알 수 있다). 따라서 A1 에 7 이 쓰여 있고 C7 이 비어 있는 입력은 내부적으로 {'A1': '7', 'C7': '123456789', ...} 로 표현할 수 있을 것이다.
grid 가 주어질 때 values 사전으로 파싱하는 코드를 다음과 같이 작성할 수 있다.
def parse_grid(grid):
"""텍스트 형태로 구성된 grid 가 주어질 때 {칸 이름: 숫자 목록} 꼴의
사전 형태로 변환한다. 만약 모순이 있으면 False 를 반환한다."""
# 처음에는 모든 칸이 어떤 숫자도 가질 수 있도록 하고, 숫자가 쓰인
# 칸을 발견할 때마다 해당 칸에 배정한다.
values = dict((s, digits) for s in squares)
for s,d in grid_values(grid).items():
if d in digits and not assign(values, s, d):
return False ## 칸 s 에 d 를 배정할 수 없는 경우.
return values
def grid_values(grid):
"주어진 grid 를 {square: char} 형태의 사전으로 변환한다."
chars = [c for c in grid if c in digits or c in '0.']
assert len(chars) == 81
return dict(zip(squares, chars))parse_grid 함수는 s 칸에 숫자 d 를 배정하는 함수 assign(values, s, d) 를 호출한다. 물론 이것을 간단하게 values[s] = d 같은 대입문으로 대체할 수도 있겠지만, 그것보다 더 많은 것을 할 수도 있다. 스도쿠 문제를 좀 풀어 본 사람이라면 다음과 같은 두 가지 전략을 잘 알고 있을 것이다.
- 어떤 빈 칸에 들어갈 수 있는 숫자가 하나밖에 없다면, 해당 칸의 이웃들에는 그 숫자가 들어갈 수 없다.
- 한 단위에 어떤 숫자가 들어갈 수 있는 칸이 하나밖에 없다면, 거기에 그 숫자를 쓴다.
1번 전략을 어떻게 적용할 수 있을까? 입력에서 칸 A1 에 7 이 쓰여 있다면, A1 의 이웃들에는 7 이 들어갈 수 없다. 따라서 {'A1': '7', 'A2':'123456789', ...} 대신에 모든 이웃에 7 이 들어갈 수 없도록 {'A1': '7', 'A2': '12345689', ...} 과 같은 values 를 만들 수 있다. 2번 전략은 어떻게 적용할까? 위 상태에서 A3 부터 A9 까지의 칸 중 3이 들어갈 수 있는 자리가 하나도 없다고 하자. 그러면 A2 에 3 이 들어가야 한다는 것을 쉽게 알 수 있다. 이렇게 A2 에 들어갈 값을 정하고 나면 이 두 규칙에 따라 또 그 이웃들이 가질 수 있는 값이 변하고, 또 그들의 이웃이 가질 수 있는 값이 변할 수도 있다. 이와 같은 과정을 제약 조건 전파 (constraint propagation) 라고 부른다.
함수 assign(values, s, d) 가 values 에 이와 같은 변화를 적용한 뒤, values 를 반환하도록 하자. 또한 이 과정에서 모순을 발견한다면 False 를 반환하기로 한다. 예를 들어 입력이 '77..' 로 시작한다면 두 번째로 A2 에 7 을 배정하려고 할 때 assign 은 이웃에 7 이 이미 들어갔기 때문에 A2 에 7 이 들어갈 수 없고, 따라서 모순이 발생했음을 알아야 할 것이다.
제약 조건 전파를 구현하기 위해서는 s 칸에 d 를 쓰는 assign(values, s, d) 연산과 s 칸에 d 는 들어갈 수 없다는 eliminate(values, s, d) 두 가지의 연산이 필요하다. 이 두 연산에는 겹치는 구석이 많아 보이지만, 사실 eliminate 를 구현하고 나면 assign(values, s, d) 는 "s 에 들어갈 수 있는 숫자 중에서 d 를 제외하고 모두 없앤다" 는 식으로 쉽게 구현할 수 있다.
def assign(values, s, d):
"""values[s] 에서 d 를 제외한 모든 값을 지우고 제약 조건을 전파한 뒤,
변경된 values 를 반환한다. 만약 모순이 있으면 False 를 반환한다."""
other_values = values[s].replace(d, '')
if all(eliminate(values, s, d2) for d2 in other_values):
return values
else:
return False
def eliminate(values, s, d):
"""values[s] 에서 d 를 지운다. 만약 두 전략 중 하나에 해당하면
적절히 제약 조건을 전파하고, 변경된 values 를 반환한다. 만약 모순을
발견하면 False 를 반환한다."""
if d not in values[s]:
return values ## 이미 지워진 경우
values[s] = values[s].replace(d,'')
## 1. 어떤 빈 칸에 들어갈 수 있는 숫자가 하나밖에 없다면, 해당 칸의 이웃들에는 그 숫자가 들어갈 수 없다.
if len(values[s]) == 0:
return False ## 모순: 이제 s 에는 어떤 숫자도 들어갈 수 없다
elif len(values[s]) == 1:
d2 = values[s]
if not all(eliminate(values, s2, d2) for s2 in peers[s]):
return False
## 2. 한 단위에 어떤 숫자가 들어갈 수 있는 칸이 하나밖에 없다면, 거기에 그 숫자를 쓴다.
for u in units[s]:
dplaces = [s for s in u if d in values[s]]
if len(dplaces) == 0:
return False ## 모순: d 는 이제 들어갈 자리가 없다
elif len(dplaces) == 1:
# d 는 이제 u 단위 중에 들어갈 수 있는 곳이 한 군데밖에 없다: 거기에 넣는다
if not assign(values, dplaces[0], d):
return False
return values이 코드는 유명하지는 않지만 유용한 디자인 패턴 한 가지를 이용한 것이다. 이 패턴은 다음과 같다.
객체의 상태를 변경하는 비슷한 형태의 함수가 두 개 있고, 이들이 서로를 재귀호출한다면 가능한한 하나의 함수에 모든 기능을 몰아넣도록 한다. 그렇지 않으면 결국 중복 코드가 생기게 된다.
나는 오랫동안 Lisp 프로그래밍을 했는데, Lisp 에서는 서로를 재귀 호출하는 함수들이 아주 흔하기 때문에 이 패턴이 아주 유용하다. 이 패턴이 이 코드에 어떻게 적용되었는지 유의해 보라: 이 패턴에 유의하지 않으면 assign 이 그냥 values[s] = d 를 수행한 뒤 제약 조건을 전파하도록 구현할 거라고 예상하기 쉽다. 물론 그렇게 짤 수도 있지만, 아마도 eliminate 와 거의 비슷한 코드를 한번 더 작성하게 될 것이다.
여기서 더 나아가기 전에, 이상의 코드가 잘 동작하는지를 확인하기 위해 values 를 화면에 출력하는 코드를 작성해 보자.
def display(values):
"values 가 주어질 때 2차원 격자 형태로 출력한다."
width = 1+max(len(values[s]) for s in squares)
line = '+'.join(['-'*(width*3)]*3)
for r in rows:
print ''.join(values[r+c].center(width)+('|' if c in '36' else '')
for c in cols)
if r in 'CF': print line
print자, 이제 지금까지 짠 것을 한번 실행해 보자. 프로젝트 오일러 의 스도쿠 문제 에 포함된 쉬운 퍼즐 중 첫 번째 예제를 골라 보았다.
>>> grid1 = '003020600900305001001806400008102900700000008006708200002609500800203009005010300'
>>> display(parse_grid(grid1))
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놀랍게도 이 경우에는 1번과 2번 전략을 적절히 적용하기만 해도 문제 전체를 풀 수 있다! 물론 항상 이것이 가능한 것은 아니다. 좀 더 어려운 퍼즐 목록 에서 가져온 예제를 수행하면 다음과 같은 결과를 얻을 수 있다:
>>> grid2 = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
>>> display(parse_grid(grid2))
4 1679 12679 | 139 2369 269 | 8 1239 5
26789 3 1256789 | 14589 24569 245689 | 12679 1249 124679
2689 15689 125689 | 7 234569 245689 | 12369 12349 123469
------------------------+------------------------+------------------------
3789 2 15789 | 3459 34579 4579 | 13579 6 13789
3679 15679 15679 | 359 8 25679 | 4 12359 12379
36789 4 56789 | 359 1 25679 | 23579 23589 23789
------------------------+------------------------+------------------------
289 89 289 | 6 459 3 | 1259 7 12489
5 6789 3 | 2 479 1 | 69 489 4689
1 6789 4 | 589 579 5789 | 23569 23589 2368961개의 칸에 대해 답을 찾지 못했으니, 이 경우는 아직 퍼즐을 해결하려면 갈 길이 멀다는 것을 알 수 있다. 이젠 어떻게 할까? 다른 좀더 복잡한 전략 들을 구현해 볼 수도 있다. 예를 들면 naked twins 전략 같은 것은 꽤 그럴 듯해 보인다. 이 전략은 한 단위 안에 포함된 두 개의 칸이 똑같은 2개의 후보를 갖고 있을 때 써먹을 수 있다. 예를 들어 {'A5': '26', 'A6':'26', ...} 같은 상태가 있다면, 어느 쪽이 2 고 어느 쪽이 6 인지는 알 수 없지만 한 쪽에 2, 한 쪽에 6 이 있어야 한다는 점은 확실하다. 따라서 A 가로줄의 나머지 칸들에서 2 와 6 을 전부 지울 수 있다. 이와 같은 전략은 elif len(values[s]) == 2 조건문을 eliminate 에 추가하면 간단하게 구현할 수 있다.
이와 같은 전략들을 구현하는 것도 한 가지 방법이지만, 아마도 코드가 수백 줄은 필요할 테고 (수십 가지의 이런 전략이 있다) 그러고 나서도 모든 퍼즐을 풀 수 있다는 보장은 못 할 것이다.
퍼즐을 해결하는 다른 방법은 답을 _탐색_하는 것으로, 조건에 맞는 답을 찾을 때까지 모든 가능성을 하나하나 시도해 보는 방법이다. 한 열 줄이면 이 코드를 짤 수 있지만, 다른 문제가 있을 수 있다: 프로그램이 영영 끝나지 않을 수 있으니까. 위의 예로 들은 grid2 의 경우, A2 는 4개의 후보 (1679), A3 에는 5개의 후보 (12679) 가 있다. 다 하면 경우의 수는 20 이 되고, 계속 곱해나가면 전체 경우의 수는 4.62838344 × 1038 가 된다. 어떻게 해야 할까? 두 개의 방법이 있다.
첫 번째로, 모든 가능성을 무식하게 찾아보는 탐색 (brute-force) 을 할 수 있다. 우리가 이 프로그램을 엄청나게 최적화해, 경우의 수 하나가 퍼즐의 답이 되는지를 기계어 명령 1개로 판단할 수 있게 되었다고 하자. 그리고 차세대 컴퓨팅 기술도 쓸 수 있다고 하자. 10Ghz 로 동작하는 1024코어 프로세서를 100만 개쯤 구입하고, 쇼핑하는 김에 타임머신도 하나 사서 우주의 시작인 130억년전으로 돌아가 프로그램을 돌리기 시작하자. 그러면 지금쯤은 거의 전체 경우의 수 중 1퍼센트 정도를 계산했을 것이다.
두 번째 방법은 각 연산마다 한 개 이상의 경우의 수를 처리하는 것이다. 말도 안되는 얘기 같지만, 사실 이것이 제약 조건 전파를 통해 얻을 수 있는 이점이다. 한 경우의 수를 처리할 때마다 이 경우의 수와 서로 모순되는 수 많은 경우의 수들을 제약 조건 전파가 자동으로 없애 주기 때문에, 4 × 1038 개의 경우의 수를 다 따져 볼 필요가 없다. 예를 들어, 위 퍼즐의 H7 에는 6 또는 9 가 들어갈 수 있다. 9 가 들어간다고 가정해 보자. 그러면 제약 조건 전파는 모순이 일어남을 우리에게 곧장 알려 준다: 따라서 우리가 한 개의 가능성만을 없앤 개 아니라 전체 경우의 수 중 절반을 없앤 셈이다.
실제로 시도해 보면 위 퍼즐을 풀기 위해 우리는 고작 25개의 가능성만을 확인하고, 61개의 채우지 못한 칸 중 9개만을 탐색하면 된다는 것을 알 수 있다. 나머지는 제약 조건 전파가 해 주니까. 이전에 언급한 어려운 퍼즐 목록의 퍼즐들을 이 프로그램으로 풀어 보면, 각 퍼즐마다 평균 64개의 가능성만을 고려하면 되고, 16개보다 많은 칸에 대해 탐색해야 하는 경우는 하나도 없었다.
이 탐색 알고리즘은 어떻게 만들까? 간단하다. 우선 이미 답을 찾거나, 모순이 발견되지 않았는지 확인한다. 만약 둘 다 해당되지 않는다면, 채우지 못한 칸 중 하나를 선택해 모든 값들을 하나하나 시도해 본다. 해당 칸에 이 값을 쓰고, 결과로 얻어지는 상태에서부터 탐색을 계속하는 것이다. 다시 말하면 s 에 d 를 쓴 결과로부터 탐색해서 답을 찾을 수 있는 d 를 찾는단 것이다. s 에 d 를 쓴 결과로부터 탐색이 실패한다면, 뒤로 돌아가 다른 d 를 시도한다. 이런 탐색을 재귀적인 탐색 이라고 부르며, values[s] = d 이하의 모든 가능성을 확인하기 전에는 s 에 다른 값을 넣어 보지 않기 때문에 깊이 우선 탐색 이라고도 부른다.
퍼즐의 상태를 변경했다가 되돌리는 것은 꽤나 까다롭기 때문에, 한 번 재귀호출할 때마다 values 를 복사한 새 dict 를 생성해서 넘겨주도록 하자. 이렇게 하면 탐색 과정의 각 가지 (branch) 가 어떤 자료도 공유하지 않기 때문에 서로를 혼란스럽게 할 일이 없다. (사실 이것이 values 에서 각 칸이 가질 수 있는 값의 목록을 list 나 set 으로 표현하지 않고 문자열로 표현한 이유이다. 문자열을 사용하면 간단히 values.copy() 만을 사용해서 values 의 복사본을 얻을 수 있는데 반해, list 나 set 을 이용하면 좀 더 느린 copy.deepcopy(values) 를 써야만 하기 때문이다.) 이렇게 하지 않으려면 values 를 바꿀 때마다 어디를 바꿨는지 기억해 둔 뒤, 재귀호출이 끝난 후 이 변화를 되돌리는 방법을 사용해도 된다. 흔히 이런 탐색 방법을 백트래킹 탐색 이라고 부른다. 탐색에서 커다란 자료 구조를 한 번에 하나씩만 수정하는 경우에는 이런 기법이 유용하지만, 제약 조건 전파를 통해 한 번에 여러 부분을 수정할 때는 구현하기 까다롭다.
탐색을 구현하는 과정에서 우리가 해야 하는 선택이 두 가지가 있다. 첫 번째는 변수 순서 결정 (어느 칸부터 시도할 것인가?) 이고, 두 번째는 값 순서 결정 (어느 값부터 채워넣어 볼 것인가?) 이다. 변수 순서 결정은, 흔히 사용하는 휴리스틱인 남아 있는 후보의 수가 가장 작은 칸부터 선택하기를 통해 해결하도록 하자. 후보의 수가 최소인 칸이 여러 개 있다면 아무 것이나 선택하기로 하고. 왜 이렇게 하냐고? grid2 를 다시 보자. 7개의 후보 (1256789) 가 있는 B3 을 먼저 채우기로 결정했다고 하면, 한 숫자를 선택했을 때 틀릴 확률은 6/7 이 된다. 만약 대신 G2 를 먼저 채우면, 틀릴 확률은 이제 1/2 로 줄어든다. 임의의 답을 선택했을 때 맞을 확률이 가장 높은 칸부터 먼저 시작한다는 얘기다. 값 순서 결정은 별다른 최적화를 하지 않고 그냥 숫자 순서대로 대입해 보기로 하자.
이런 결정을 모두 내렸으면 search 함수를 사용해 solve 함수를 작성할 수 있게 된다.
def solve(grid): return search(parse_grid(grid))
def search(values):
"깊이 우선 탐색과 제약 조건 전파를 이용해 모든 값들을 하나하나 시도한다."
if values is False:
return False ## 호출 이전에 실패한 경우
if all(len(values[s]) == 1 for s in squares):
return values ## 해결 성공!
## 아직 답을 못 찾은 칸 중 가장 후보의 수가 적은 칸 s 를 찾는다
n,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
return some(search(assign(values.copy(), s, d))
for d in values[s])
def some(seq):
"seq 의 원소 중 False 가 아닌 것을 하나 반환한다."
for e in seq:
if e: return e
return False이걸로 끝이다! 한 페이지 분량의 코드로, 어떤 스도쿠 퍼즐도 풀 수 있다.
전체 소스 코드를 여기에서 볼 수 있다 (구문 강조된 html 은 이쪽 을 참조하라). 이 파일을 실행하면, 50개의 쉬운 퍼즐 과 95개의 어려운 퍼즐 (답 도 제공된다), 그리고 가장 어려운 스도쿠 퍼즐 이라는 탐색어로 내가 찾은 11개의 퍼즐 과 몇 개의 임의로 생성한 퍼즐들을 순서대로 해결하고 다음과 같은 결과를 출력한다.
% python sudo.py
All tests pass.
Solved 50 of 50 easy puzzles (avg 0.01 secs (86 Hz), max 0.03 secs).
Solved 95 of 95 hard puzzles (avg 0.04 secs (24 Hz), max 0.18 secs).
Solved 11 of 11 hardest puzzles (avg 0.01 secs (71 Hz), max 0.02 secs).
Solved 99 of 99 random puzzles (avg 0.01 secs (85 Hz), max 0.02 secs).
위 결과에 보이는 퍼즐들은 전부 5분의 1초도 안되는 시간에 해결할 수 있었음을 알 수 있다. 정말 정말 어려운 퍼즐은 어떨까? 핀란드 수학자 Arto Inkala 는 자신이 2006년에 만든 퍼즐 을 "지금까지 알려진 가장 어려운 스도쿠 퍼즐" 이라고 소개했으며, 2010년에 만든 퍼즐 은 "지금까지 내가 만든 가장 어려운 퍼즐" 이라고 말했다. 내 프로그램은 두 문제를 모두 0.01 초 내에 해결할 수 있다. (아래 코드에서 사용하는 solve_all 의 코드는 아래 정의되어 있다)
>>> solve_all(from_file("hardest.txt")[0:2], 'Inkala')
8 5 . |. . 2 |4 . .
7 2 . |. . . |. . 9
. . 4 |. . . |. . .
------+------+------
. . . |1 . 7 |. . 2
3 . 5 |. . . |9 . .
. 4 . |. . . |. . .
------+------+------
. . . |. 8 . |. 7 .
. 1 7 |. . . |. . .
. . . |. 3 6 |. 4 .
8 5 9 |6 1 2 |4 3 7
7 2 3 |8 5 4 |1 6 9
1 6 4 |3 7 9 |5 2 8
------+------+------
9 8 6 |1 4 7 |3 5 2
3 7 5 |2 6 8 |9 1 4
2 4 1 |5 9 3 |7 8 6
------+------+------
4 3 2 |9 8 1 |6 7 5
6 1 7 |4 2 5 |8 9 3
5 9 8 |7 3 6 |2 4 1
(0.01 seconds)
. . 5 |3 . . |. . .
8 . . |. . . |. 2 .
. 7 . |. 1 . |5 . .
------+------+------
4 . . |. . 5 |3 . .
. 1 . |. 7 . |. . 6
. . 3 |2 . . |. 8 .
------+------+------
. 6 . |5 . . |. . 9
. . 4 |. . . |. 3 .
. . . |. . 9 |7 . .
1 4 5 |3 2 7 |6 9 8
8 3 9 |6 5 4 |1 2 7
6 7 2 |9 1 8 |5 4 3
------+------+------
4 9 6 |1 8 5 |3 7 2
2 1 8 |4 7 3 |9 5 6
7 5 3 |2 9 6 |4 8 1
------+------+------
3 6 7 |5 4 2 |8 1 9
9 8 4 |7 6 1 |2 3 5
5 2 1 |8 3 9 |7 6 4
(0.01 seconds)
Solved 2 of 2 Inkala puzzles (avg 0.01 secs (99 Hz), max 0.01 secs).이래서야 정말 어려운 퍼즐을 찾으려면 내가 만드는 수밖에 없는 것 같다. 어려운 퍼즐을 만드는 방법을 모르기 때문에, 100만 개의 퍼즐을 임의로 만들었다. 임의의 퍼즐을 만드는 방법은 간단하다. 먼저 각 칸의 순서를 임의로 뒤섞는다. 하나씩 각 칸을 임의의 숫자로 채워나가되, 모순이 발견되는지를 계속 확인한다. 만약 모순을 발견하면 처음부터 다시 시작하고, 17개 이상의 칸을 8종류 이상의 숫자로 채울 수 있었으면 거기서 종료한다. (참고로, 17개 미만의 숫자가 쓰여 있거나 쓰여 있는 숫자가 8가지가 안 될 경우 항상 중복 해가 있음을 증명할 수 있다. 숫자 가지수 제한 사항을 제안해 준 Olivier Grégoire 에게 감사한다.) 이와 같은 제약 사항에도 불구하고, 이렇게 생성한 퍼즐들에 답이 항상 하나뿐인 것은 아니다. 많은 퍼즐들에 여러 개의 답이 있고, 일부 (0.2% 정도) 는 답이 없는 퍼즐이 생성되기도 한다. 책이나 신문에 나오는 스도쿠 퍼즐들에는 항상 유일한 답이 있다.
이런 임의의 퍼즐을 해결하는 데 걸리는 시간은 평균 0.01 초였고, 99.95% 이상은 0.1 초 안에 풀 수 있었다. 그러나 가끔 그보다 훨씬 오래 걸리는 것도 있었다:
0.032% (3000분의 1) 는 0.1초보다 오래 걸렸다.
0.014% (7000분의 1) 는 1초보다 오래 걸렸다.
0.003 (30000분의 1) 는 10초보다 오래 걸렸다.
0.0001% (100만분의 1) 는 100초보다 오래 걸렸다.
아래 두 그림은 100만 개의 퍼즐 중 1초보다 오래 걸린 것들의 수행 순서를 선형과 로그 스케일로 표시한 것이다.
물론 이것만으로 뭔가 결론을 내리기는 쉽지 않다. 마지막 몇 개의 값이 엄청나게 큰 것에 의미를 부여해야 할까? 1000만개의 퍼즐을 만들어서 풀어 보면 그 중 하나는 1000초가 걸릴까? 아래가 100만개 중 가장 오래 걸리는 퍼즐이다.
>>> hard1 = '.....6....59.....82....8....45........3........6..3.54...325..6..................'
>>> solve_all([hard1])
. . . |. . 6 |. . .
. 5 9 |. . . |. . 8
2 . . |. . 8 |. . .
------+------+------
. 4 5 |. . . |. . .
. . 3 |. . . |. . .
. . 6 |. . 3 |. 5 4
------+------+------
. . . |3 2 5 |. . 6
. . . |. . . |. . .
. . . |. . . |. . .
4 3 8 |7 9 6 |2 1 5
6 5 9 |1 3 2 |4 7 8
2 7 1 |4 5 8 |6 9 3
------+------+------
8 4 5 |2 1 9 |3 6 7
7 1 3 |5 6 4 |8 2 9
9 2 6 |8 7 3 |1 5 4
------+------+------
1 9 4 |3 2 5 |7 8 6
3 6 2 |9 8 7 |5 4 1
5 8 7 |6 4 1 |9 3 2
(188.79 seconds)안타깝게도 이 문제에는 두 개 이상의 답이 있기 때문에 제대로 된 스도쿠 퍼즐은 아니다. (이 퍼즐은 8가지 이상의 숫자가 출현해야 한다는 제약 조건을 추가하기 이전에 생성한 것이기 때문에, 1과 7의 위치를 바꾼 모든 경우가 답이 된다) 그러나 이게 '정말로' 어려운 퍼즐일까? 아니면 내가 선택한 탐색 방식에 문제가 있는 것일까? 이것을 테스트하기 위해 나는 각 칸에 숫자를 대입하는 순서를 임의로 바꿔 보았다 (search 함수 내의 for d in values[d] 구문을 for d in shuffled(values[d]) 로 바꾸고, shuffled 를 random.shuffle 을 이용해 구현하면 된다). 결과는 놀랍도록 양분되어 있었다. 30회의 시도 중 27번은 이 퍼즐을 0.02초 안에 풀 수 있었지만, 3번은 거의 1만배나 큰 190초가 걸린 것이었다. 이 퍼즐에는 여러 개의 답이 있고, 이렇게 랜덤화한 탐색은 그 중 13개의 답을 찾아냈다. 내 짐작으로는, 탐색 초반에 하나나 두 개의 칸에 숫자를 잘못 채우면 이들이 모순이라는 것을 발견하는 데 거의 190초를 소모하는 것 같다. 그러나 이 정확한 조합 말고 다른 숫자를 채우면, 답을 곧장 찾거나, 곧장 모순을 발견할 수 있는 것이다. 이 가정이 정확하다면, 알고리즘의 전체 수행 속도는 이 잘못된 조합이 임의 순서에 따라 생성되는지 여부에 달려 있는 것 같다.
랜덤화는 대부분의 경우 성공적으로 문제를 해결하지만 (30번 시도 중에 27번 성공했으니), 좀 더 나은 값 순서 선택 전략을 써서 최적화해 볼 수도 있을 것이다. (유명한 휴리스틱으로는 최소 제약 값 선택 이란 것이 있는데, 이웃들에게 주는 제약을 최소화하는 답부터 시도하는 것이다) 아니면 좀 더 똑똑한 변수 순서 선택 전략을 쓰거나.
어려운 퍼즐들의 특성을 좀더 잘 이해하려면 더 많은 실험을 할 필요가 있다. 그래서 나는 100만개의 퍼즐을 새로 만들어 실험해 보았다. 단 각 퍼즐을 푸는 데 걸린 시간의 평균, 중간값, 90% 와 99% 위치에 있는 값, 최대치와 표준편차를 계산했다. 결과는 전체적으로 비슷했다. 단, 이번에는 100초 넘게 걸리는 퍼즐이 두 개 생성되었고, 하나는 무려 1439초나 걸렸다. 이 퍼즐은 사실 답이 없는 0.2% 의 일부였기에 계산에 넣지 않는 것이 맞는지도 모르지만, 하여간 평균과 중간값은 샘플 수가 늘어나더라도 변하지 않는다는 것은 확인할 수 있었다. 단지 늘어나는 것은 최대값 뿐이었다: 그것도 엄청나게. 표준편차도 조금씩 늘어나지만, 99퍼센타일 밖의 아주 큰 값 때문이다. 이 값이 정규분포가 아니라 아주 꼬리가 두터운 (heavy-tailed) 분포라는 것을 알 수 있다.
아래 두 표는 퍼즐 해결에 걸린 시간들 (왼쪽) 과 평균 0.014, 표준 편차 1.4794 를 갖는 정규분포의 샘플 (오른쪽) 을 나타낸 것이다. 정규분포에서 100만개의 샘플 중 최대치는 평균과 5 표준편차 정도 차이가 나지만 (대략 예상할 만한 범위라고 할 수 있겠다) 퍼즐 수행 시간의 최대치는 평균보다 10000 표준편차 차이가 난다.
| Samples of Puzzle Run Time | Samples of N(0.014, 1.4794) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
다음은 해결하는 데 1439초가 걸렸던 답이 없는 퍼즐이다:
. . . |. . 5 |. 8 .
. . . |6 . 1 |. 4 3
. . . |. . . |. . .
------+------+------
. 1 . |5 . . |. . .
. . . |1 . 6 |. . .
3 . . |. . . |. . 5
------+------+------
5 3 . |. . . |. 6 1
. . . |. . . |. . 4
. . . |. . . |. . .
다음은 solve_all 의 구현과, 이를 이용해 임의의 퍼즐과 파일에서 읽어들인 퍼즐들을 해결하는 소스 코드이다.
import time, random
def solve_all(grids, name='', showif=0.0):
"""여러 개의 grid 들을 풀어 보고 결과를 보고한다.
만약 showif 가 숫자라면, showif 초보다 오래 걸리는 퍼즐들을 출력한다.
만약 showif 가 None 이라면, 아무것도 출력하지 않는다."""
def time_solve(grid):
start = time.clock()
values = solve(grid)
t = time.clock()-start
## Display puzzles that take long enough
if showif is not None and t > showif:
display(grid_values(grid))
if values: display(values)
print '(%.2f seconds)\n' % t
return (t, solved(values))
times, results = zip(*[time_solve(grid) for grid in grids])
N = len(grids)
if N > 1:
print "Solved %d of %d %s puzzles (avg %.2f secs (%d Hz), max %.2f secs)." % (
sum(results), N, name, sum(times)/N, N/sum(times), max(times))
def solved(values):
"각 단위가 1 부터 9 까지의 숫자의 순열인 경우 퍼즐을 푼 것으로 한다."
def unitsolved(unit): return set(values[s] for s in unit) == set(digits)
return values is not False and all(unitsolved(unit) for unit in unitlist)
def from_file(filename, sep='\n'):
"주어진 파일을 sep 으로 구분되는 문자열의 리스트로 파싱한다."
return file(filename).read().strip().split(sep)
def random_puzzle(N=17):
"""N 개 혹은 그 이상의 숫자를 가지는 임의의 퍼즐을 만든다. 모순이 발견되면
다시 시작한다. 결과로 얻어지는 퍼즐이 항상 풀 수 있는 것은 아니지만, 실험 결과
99.8% 정도는 항상 풀 수 있다. 그 중 일부는 답이 여러 개 있을 수 있다."""
values = dict((s, digits) for s in squares)
for s in shuffled(squares):
if not assign(values, s, random.choice(values[s])):
break
ds = [values[s] for s in squares if len(values[s]) == 1]
if len(ds) >= N and len(set(ds)) >= 8:
return ''.join(values[s] if len(values[s])==1 else '.' for s in squares)
return random_puzzle(N) ## 포기하고 새 퍼즐을 만든다
def shuffled(seq):
"입력 리스트의 순서를 뒤바꾼 새 리스트를 반환한다."
seq = list(seq)
random.shuffle(seq)
return seq
grid1 = '003020600900305001001806400008102900700000008006708200002609500800203009005010300'
grid2 = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
hard1 = '.....6....59.....82....8....45........3........6..3.54...325..6..................'
if __name__ == '__main__':
test()
solve_all(from_file("easy50.txt", '========'), "easy", None)
solve_all(from_file("top95.txt"), "hard", None)
solve_all(from_file("hardest.txt"), "hardest", None)
solve_all([random_puzzle() for _ in range(99)], "random", 100.0)내가 이걸 왜 했느냐고? 컴퓨터 보안 전문가 Ben Laurie 가 말했듯이, 스도쿠는 "인류 지성에 대한 서비스 거부 공격" 이기 때문이다. 내 아내 또한 스도쿠 바이러스에 걸려, 스도쿠는 이미 해결된 문제이므로 여기에 그녀의 시간을 쓸 필요가 없음을 보여 주고 싶었다. 그녀에게는 별 효과가 없었지만 (결국엔 이 글과 상관없이 그녀는 스도쿠 하는 시간을 줄였다) 최소한 한 사람 이상이 이것이 효과가 있었다고 내게 말해주었다. 그러니 세상을 좀 더 생산적으로 만드는 데 약간은 기여한 셈이다. 그리고 그 과정에서 파이썬, 제약 조건 전파, 그리고 탐색에 관해 조금 가르치기도 했으니까.