1년쯤 전에 풀었던 스도쿠를 다시 풀었다. 이번 판은 빈칸이 64개다. 앞에서 풀던 39개짜리와는 규모가 다르다.
0 0 0 0 0 0 0 0 0
0 0 0 0 0 3 0 8 5
0 0 1 0 2 0 0 0 0
0 0 0 5 0 7 0 0 0
0 0 4 0 0 0 1 0 0
0 9 0 0 0 0 0 0 0
5 0 0 0 0 0 0 7 3
0 0 2 0 1 0 0 0 0
0 0 0 0 4 0 0 0 9
푸는 방식 자체는 같다. 후보를 집합 연산으로 구하고, 넣고, 내려가고, 되돌린다.
def sudoku(idx=0):
if idx == n:
for line in grid:
print(*line)
return
i, j = blank[idx]
hor = set(grid[i])
ver = set([k[j] for k in grid])
box = set([num for k in grid[i//3*3:][:3] for num in k[j//3*3:][:3]])
poss = t - (hor | ver | box)
for num in poss:
grid[i][j] = num
sudoku(idx + 1)
grid[i][j] = 0
달라진 건 blank 의 순서다.
후보가 적은 칸부터
전에는 빈칸을 왼쪽 위에서 오른쪽 아래로 훑은 순서 그대로 채웠다. 이번에는 채우기 전에 정렬한다.
blank = [(i, j) for i in range(len(grid)) for j in range(len(grid[0])) if grid[i][j] == 0]
temp = {}
for g in blank:
i, j = g
hor = set(grid[i])
ver = set([k[j] for k in grid])
box = set([num for k in grid[i//3*3:][:3] for num in k[j//3*3:][:3]])
poss = t - (hor | ver | box)
temp[g] = len(poss)
temp = sorted(temp.items(), key=lambda item: item[1])
blank = [k for k, v in temp]
각 빈칸의 후보 개수를 세어 적은 순서로 놓는다.
후보가 2개인 칸을 먼저 채우면 가지가 2갈래로 갈라진다. 후보가 8개인 칸을 먼저 채우면 8갈래다. 갈라지는 폭이 작은 것부터 처리하면 위쪽에서 트리가 덜 벌어진다.
틀린 선택도 빨리 드러난다. 제약이 많은 칸일수록 잘못 넣었을 때 곧바로 후보가 0인 칸이 생긴다.
정렬을 한 번만 한다
이 코드의 한계이기도 하다. blank 의 순서는 탐색 시작 전 상태를 기준으로 정해지고 그 뒤로는 바뀌지 않는다.
칸을 하나 채우면 같은 줄과 같은 상자의 다른 칸들은 후보가 하나씩 줄어든다. 처음에 후보가 6개였던 칸이 지금은 1개일 수도 있다. 그런데 순서는 처음 그대로다.
매번 다시 세면 순서는 좋아지는데 빈칸마다 세 집합을 다시 만들어야 한다. 64개 칸이면 그게 적지 않다. 여기서는 한 번만 세는 쪽으로 갔다.
idx 하나로 진행 상황이 정해지는 구조도 정렬을 고정했기 때문에 가능하다. 매번 다시 고르는 방식이면 어느 칸이 남았는지를 따로 들고 다녀야 한다.
되돌리기는 그대로
grid[i][j] = num
sudoku(idx + 1)
grid[i][j] = 0
판 하나를 계속 고쳐 쓴다. N-Queens에서 판을 통째로 복사했던 것과 다른데, 여기서는 되돌리기가 간단해서 그럴 이유가 없다. 내가 넣은 숫자를 0으로 바꾸면 정확히 원래 상태다.