https://www.acmicpc.net/problem/2580
https://github.com/stellaluminary/Baekjoon
스도쿠는 행/열/3x3 사각형에 대해서 공통적인 것을 도출하는 문제이다.
하여 이를 고려한 함수를 기반으로 백트래킹을 진행하였으나 시간초과가 나타났다. (Python3, PyPy3 모두 시간초과)
def row_ck(x):
row = [0]*10
zero = []
for i in s[x]:
if i != 0:
row[i]=1
for i in range(1, 10):
if row[i] == 0:
zero.append(i)
return zero
def col_ck(y):
col = [0]*10
zero = []
for i in range(9):
if s[i][y] != 0:
col[s[i][y]]=1
for i in range(1, 10):
if col[i] == 0:
zero.append(i)
return zero
def sq_ck(x,y):
sq = [0]*10
zero = []
a, b = x%3, y%3
for i in range(3):
for j in range(3):
if a == 0:
if b == 0 and s[x+i][y+j] != 0:
sq[s[x+i][y+j]] = 1
elif b == 1 and s[x+i][y+1-j] != 0:
sq[s[x+i][y+1-j]] = 1
elif b == 2 and s[x+i][y-j] != 0:
sq[s[x+i][y-j]] = 1
elif a == 1:
if b == 0 and s[x+1-i][y+j] != 0:
sq[s[x+1-i][y+j]] = 1
elif b == 1 and s[x+1-i][y+1-j] != 0:
sq[s[x+1-i][y+1-j]] = 1
elif b == 2 and s[x+1-i][y-j] != 0:
sq[s[x+1-i][y-j]] = 1
elif a == 2:
if b == 0 and s[x-i][y+j] != 0:
sq[s[x-i][y+j]] = 1
elif b == 1 and s[x-i][y+1-j] != 0:
sq[s[x-i][y+1-j]] = 1
elif b == 2 and s[x-i][y-j] != 0:
sq[s[x-i][y-j]] = 1
for i in range(1, 10):
if sq[i] == 0:
zero.append(i)
return zero
def dfs(idx):
if idx == len(loc):
res.append(copy.deepcopy(s))
return
x, y = loc[idx]
c = []
for i in row_ck(x):
for j in col_ck(y):
for k in sq_ck(x,y):
if i == j == k:
c.append(i)
for i in c:
s[x][y] = i
dfs(idx+1)
s[x][y] = 0
import sys
import copy
s = [list(map(int, sys.stdin.readline().split())) for _ in range(9)]
visit = [[0]*9 for _ in range(9)]
loc = []
res = []
for i in range(9):
for j in range(9):
if not s[i][j]:
loc.append((i,j))
dfs(0)
for i in res[0]:
print(' '.join(map(str, i)))
방법 1의 경우 공통적인 것을 직접 구해서 비교하고 남은 것들을 토대로 백트래킹을 했다면 방법 2에서는 단순 비교를 진행한다.
0인 위치를 blank list에 저장해서 1~9까지의 숫자를 하나씩 넣어보고 행/열/3x3 사각형에 있는지 없는지 체크하고 된다면 다음 위치로 넘어가는 식으로 진행한다.
방법 1에 비해서는 훨씬 깔끔해진 것을 확인할 수 있다.
import sys
s = [list(map(int, sys.stdin.readline().split())) for _ in range(9)]
blank = []
for i in range(9):
for j in range(9):
if s[i][j] == 0:
blank.append((i,j))
def row_ck(x, a):
for i in range(9):
if a == s[x][i]:
return False
return True
def col_ck(y, a):
for i in range(9):
if a == s[i][y]:
return False
return True
def sq_ck(x, y, a):
nx, ny = x//3 * 3, y//3*3
for i in range(3):
for j in range(3):
if a == s[nx+i][ny+j]:
return False
return True
def dfs(idx):
if idx == len(blank):
for i in range(9):
print(*s[i])
exit(0)
for i in range(1, 10):
x, y = blank[idx]
if row_ck(x, i) and col_ck(y, i) and sq_ck(x, y, i):
s[x][y] = i
dfs(idx+1)
s[x][y]= 0
dfs(0)
방법 2에서는 행/열/사각형에 대해 별도로 checking하였다면 이 코드에서는 한 번에 체크하고 그 후보군을 활용하는 방법이다.
시간이 단축한만큼 더 많은 메모리 활용이 있다.
import sys
s = [list(map(int, sys.stdin.readline().split())) for _ in range(9)]
blank = [(i,j) for i in range(9) for j in range(9) if s[i][j] == 0]
def check(x, y):
num = [i for i in range(1, 10)]
for i in range(9):
if s[x][i] in num:
num.remove(s[x][i])
if s[i][y] in num:
num.remove(s[i][y])
nx, ny = x//3*3, y//3 *3
for i in range(3):
for j in range(3):
if s[nx+i][ny+j] in num:
num.remove(s[nx+i][ny+j])
return num
def dfs(idx):
if idx == len(blank):
for i in range(9):
print(*s[i])
exit(0)
x, y = blank[idx]
candi = check(x, y)
for c in candi:
s[x][y] = c
dfs(idx + 1)
s[x][y] = 0
dfs(0)