2580: 스도쿠

• dfs + backtracking 문제
• 일단 zero 리스트의 0번 index부터 시작하여 dfs 진행
• dfs함수에선 해당 depth의 zero의 위치에 1~9까지 모두 넣어봄
  -> checkRow(), checkCol(), checkSquare() 함수를 통해 스도쿠 규칙에 맞는 지 확인하고, 모두 True라면 값을 넣어주고 다음 index로 dfs진행
• 종료조건: zero의 index가 마지막 인덱스 + 1 이라면 모든 칸을 조건에 맞게 채웠음을 의미하므로 해당 board를 출력하고 process 종료

import sys

def checkRow(i, x):
    for y in range(9):
        if board[x][y] == i:
            return False
    return True

def checkCol(i, y):
    for x in range(9):
        if board[x][y] == i:
            return False
    return True

def checkSquare(i, x, y):
    x = (x // 3) * 3; y = (y // 3) * 3
    for a in range(x, x+3):
        for b in range(y, y+3):
            if board[a][b] == i:
                return False
    return True

def dfs(idx):
    if idx == len(zero):
        for a in range(9):
            for b in range(9):
                print(board[a][b], end=" ")
            print()
        exit() #모든 칸을 조건에 맞게 채웠을 때 board 출력하고 exit
    
    x = zero[idx][0]; y = zero[idx][1]
    for i in range(1, 10): #zero의 위치에 1~9까지 넣기
        if checkRow(i, x) and checkCol(i, y) and checkSquare(i, x, y): #해당 조건이 충족되는 경우 dfs
            board[x][y] = i
            dfs(idx + 1)
            board[x][y] = 0 #for backtracking

board = []; zero = []
for i in range(9):
    tmp = list(map(int, sys.stdin.readline()[:-1].split()))
    board.append(tmp)
    for j in range(9):
        if tmp[j] == 0:
            zero.append([i, j])

dfs(0) #zero의 처음부터 시작