1. 문제

출처: 백준 2580번 스도쿠

2. 풀이

스도쿠의 규칙은 각 행과 열에 1~9까지 숫자가 하나씩만 들어가고, $3 \times 3$ 박스에도 1~9까지의 숫자가 하나씩만 들어가는 것이다.

규칙 세 개를 만족하는지 확인할 수 있는 함수를 만들고, 비어있는 칸에 들어갈 수 있는 숫자들을 하나씩 넣어보면 된다.

여기서 문제가 되는 것은 만족하는 조합이 여러 개일 경우도 있다는 것이다.
하나의 경우만 출력하라고 했기 때문에, 한 조합이 완성되면 return으로 함수를 끝내지 않고 exit()로 코드를 끝내준다.

Python 3로 제출할 경우, 시간 초과가 되니 PyPy3로 제출해야 한다.

3. 소스코드

blank = []
numbers = [list(map(int,input().split())) for _ in range(9)]

for i in range(9):
    for j in range(9):
        if numbers[i][j] == 0:
            blank.append([i,j])

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

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

def checkRect(x,y,num):
    X = x//3*3
    Y = y//3*3
    for i in range(3):
        for j in range(3):
            if num == numbers[X+i][Y+j]:
                return False
    return True

def dfs(idx):
    if idx == len(blank):
        for i in range(9):            
            print(*numbers[i], sep=" ")
        exit()
    for num in range(1,10):
        x = blank[idx][0]
        y = blank[idx][1]

        if checkRow(x,num) and checkCol(y,num) and checkRect(x,y,num):
            numbers[x][y] = num
            dfs(idx+1)
            numbers[x][y] = 0

dfs(0)

4. 그 외

고등학교 쉬는 시간에 간간이 풀었던, 스도쿠의 기억을 떠올려볼 수 있는 문제였다.