728x90
문제
2580번: 스도쿠
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루
www.acmicpc.net
코드
#dfs+백트래킹
import sys
sys.stdin = open("8.txt", "r")
graph = []
blank = []
for i in range(9):
graph.append(list(map(int, sys.stdin.readline().rstrip().split())))
for i in range(9):
for j in range(9):
if graph[i][j] == 0:
blank.append((i, j))
def checkRow(x, a):
for i in range(9):
if a == graph[x][i]:
return False
return True
def checkCol(y, a):
for i in range(9):
if a == graph[i][y]:
return False
return True
def checkRect(x, y, a):
nx = x // 3 * 3
ny = y // 3 * 3
for i in range(3):
for j in range(3):
if a == graph[nx+i][ny+j]:
return False
return True
def dfs(idx):
if idx == len(blank):
for i in range(9):
print(*graph[i])
exit(0)
for i in range(1, 10):
x = blank[idx][0]
y = blank[idx][1]
if checkRow(x, i) and checkCol(y, i) and checkRect(x, y, i):
graph[x][y] = i
dfs(idx+1)
graph[x][y] = 0
dfs(0)
풀어야 할 예제
푼 결과
댓글