2580 스도쿠

1. 코드

sudoku = [list(map(int,input().split())) for _ in range(9)]
 
def findBlank():
    for i in range(9):
        for j in range(9):
            if sudoku[i][j] == 0:
                return i,j
    return -1, -1
 
def checkrow(r,n):
    for i in range(9):
        if sudoku[r][i] == n:
            return False
    return True
 
def checkcol(c,n):
    for i in range(9):
        if sudoku[i][c] == n:
            return False
    return True
 
def checkbox(r,c,n):
    row = (r//3)*3
    col = (c//3)*3
    for i in range(3):
        for j in range(3):
            if sudoku[row+i][col+j] == n:
                return False
    return True
 
def Isok(r,c,n):
    if checkrow(r,n) and checkcol(c,n) and checkbox(r,c,n):
        return True
    return False
 
def fill():
    r, c = findBlank()
    if r == -1:
        return True
    for n in range(1,10):
        if Isok(r,c,n):
            sudoku[r][c] = n
            if fill():
                return True
            sudoku[r][c] = 0
    return False
 
fill()
for i in range(9):
    print(*sudoku[i])
 

2. 후기

알고리즘 분류 - 백트래킹

파이썬으로 푸니깐 시간초과가 나온다. 마지막은 배열을 간단히 출력할 때 유용하다. 

이 코드는 fill에서 재귀를 돌면서 스도쿠에서 가장처음으로 비어있는 칸을 찾은 후 모든 조건(가로,세로,네모)를 만족하는 1~9중 수를 찾아 입력한다. 

만약 다음 빈칸에서 모든 수를 넣어도 만족하지 않으면 그 전으로 돌아와 다른 수를 넣고 다시 시도한다.