🖋️ 문제
스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.
각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.
하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.
입력
9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.
출력
9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.
🤔 접근
n-queen 문제에서 호되게 당하고 난 뒤, 백트래킹 문제만 보면 두렵다. 우선, 백트래킹 문제를 풀기 위해서 두 가지를 먼저 생각했다.
- promising 한지 판단하는 함수
- 백트래킹 함수
promising 함수는 두 가지를 고민하였다. 매번 table을 돌며 유망한지 확인하는 방법과 집합을 만들어 확인하는 방법 중 집합을 택했다.
백트래킹 함수 같은 경우엔, 종료 조건으로는 depth가 0의 개수와 같아지면 exit() 함수로 프로그램을 종료시켰다. 그렇지 않다면 depth에 해당하는 자리(0 위치)에서 1부터 9까지의 숫자 중 promising 한 것만 재귀호출 시키는 방식을 사용했다.
💻 코드
# 2239
import sys
sys.setrecursionlimit(10**7)
table = []
zeros = []
for i in range(9):
tmp = list(map(int, input()))
table.append(tmp)
for j in range(9):
if not tmp[j]:
zeros.append((i, j))
row_arr = []
for i in range(9):
tmp = set(table[i])
row_arr.append(tmp)
columns = list(zip(*table))
col_arr = []
for i in range(9):
tmp = set(columns[i])
col_arr.append(tmp)
square_arr = [[],[],[]]
for i in range(3):
I = i * 3
for j in range(3):
j *= 3
tmp = set()
for s in range(3):
tmp.add(table[I+s][j])
tmp.add(table[I+s][j+1])
tmp.add(table[I+s][j+2])
square_arr[i].append(tmp)
def promising(x, y, num):
if num in row_arr[x]:
return False
elif num in col_arr[y]:
return False
elif num in square_arr[x//3][y//3]:
return False
return True
def backtrack(depth):
if depth == len(zeros):
for t in table:
print(''.join(map(str, t)))
exit()
i, j = zeros[depth] # 확인할 위치
for num in range(1, 10):
if promising(i, j, num):
row_arr[i].add(num)
col_arr[j].add(num)
square_arr[i//3][j//3].add(num)
table[i][j] = num
backtrack(depth+1)
table[i][j] = 0
row_arr[i].remove(num)
col_arr[j].remove(num)
square_arr[i//3][j//3].remove(num)
backtrack(0)매번 확인할 때마다 집합에서 원소를 넣었다 뺐다를 반복하게 되어 효율적인 프로그램인가에 대해 의문이 들긴 하였지만, python3로 제출했을 때 통과되었으니... 만족하겠다.
