문제

링크

풀이

빈 칸을 채우는 방식은 두가지 조건이 있다.

• 각각의 가로줄과 세로줄에는 1~9의 숫자가 1번씩만 들어가야 한다.
• 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1~9의 숫자가 1번씩만 들어가야 한다.

풀이 방법은 위 조건을 만족하는 후보 숫자군을 만들어 빈칸에 후보 숫자군들을 대입하면서 탐색을 진행하면 된다. 주의할 것은 스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다는 조건이다. 문제를 꼼꼼히 읽지 않아 이 조건을 무시한 채 채점을 진행하여 시간이 많이 걸렸다...

1. 스도쿠 판의 빈칸에 들어갈 수 있는 숫자 후보들을 생성한다. (각각의 가로줄, 세로줄, 3x3 정사각형에 존재하는 숫자들을 지우면서 빈칸에 들어갈 수 있는 숫자 후보들을 생성한다.)

2. 숫자 후보들을 하나씩 대입하여 스도쿠 판을 채운다.

3. 2번 과정을 계속 반복하면서 답이 맞다면 계속 탐색하고 아니라면 전 단계로 돌아가 탐색한다. (DFS)

코드

# PyPy3만 통과
import sys

input = sys.stdin.readline
sudoku = [list(map(int, input().split())) for _ in range(9)]
empty = [(x, y) for x in range(9) for y in range(9) if sudoku[x][y] == 0]


def make_cases(x, y):
    numbers = [i + 1 for i in range(9)]

    for k in range(9):
        if sudoku[x][k] in numbers:
            numbers.remove(sudoku[x][k])
        if sudoku[k][y] in numbers:
            numbers.remove(sudoku[k][y])

    x1 = (x // 3) * 3
    y1 = (y // 3) * 3
    for r in range(x1, x1 + 3):
        for c in range(y1, y1 + 3):
            if sudoku[r][c] in numbers:
                numbers.remove(sudoku[r][c])

    return numbers


flag = False    # 스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력해야하기 때문에!!


def dfs(depth):
    global flag
    if flag:
        return

    if depth == len(empty):
        for s in sudoku:
            print(*s)
        flag = True
        return

    r, c = empty[depth]
    cases = make_cases(r, c)

    for case in cases:
        sudoku[r][c] = case
        dfs(depth + 1)
        sudoku[r][c] = 0


dfs(0)