Sign in Subscribe
PS

[PS] BOJ 2580 / 스도쿠

Minjun Kim

• 2 min read
[PS] BOJ 2580 / 스도쿠
Thumbnail: Photo by Kourosh Qaffari (Unsplash)
문제 링크: https://www.acmicpc.net/problem/2580

백트래킹으로 가능한 모든 경우를 찾아보는 문제입니다.

풀이

​스도쿠 규칙

간단하게, 한 개의 행/열/칸(굵은 선으로 구분된 3x3 격자)에는 1~9까지의 수가 한 개 씩 등장해야 합니다.

따라서, 백트래킹에서 분기의 유망성을 판단할 때 현재 분기에서 채우려는 수 $i$가 같은 행/열/칸에 모두 사용되지 않았는지를 검사하면 됩니다.

이는 9개의 행/열/칸에서 1~9까지의 사용 여부를 배열 형태로 기록하면 됩니다.

rows = [[False for _ in range(10)] for _ in range(9)]
cols = [[False for _ in range(10)] for _ in range(9)]
grids = [[False for _ in range(10)] for _ in range(9)]

def get_grid_idx(r, c): # 왼쪽 위 격자를 0번, 오른쪽 아래 격자를 8번으로 계산
    return r // 3 * 3 + c // 3

분기의 유망성 검사를 위한 배열

백트래킹

가능한 스도쿠 배치를 한 개만 찾으면 되기 때문에, 답을 찾는 즉시 백트래킹을 중단하도록 구현했습니다.

def backtracking(depth):
    if depth == len(blanks):
        print_sudoku()
        return True
    
    r, c = blanks[depth]
    g = get_grid_idx(r, c)
    for i in range(1, 10):
        if rows[r][i] or cols[c][i] or grids[g][i]:
            continue
        # set blank to i
        sudoku[r][c] = i
        rows[r][i] = True
        cols[c][i] = True
        grids[g][i] = True

        # backtracking
        if backtracking(depth + 1):
            return

        # undo
        rows[r][i] = False
        cols[c][i] = False
        grids[g][i] = False

    sudoku[r][c] = 0
    return False

전체 코드

input = open(0).readline

rows = [[False for _ in range(10)] for _ in range(9)]
cols = [[False for _ in range(10)] for _ in range(9)]
grids = [[False for _ in range(10)] for _ in range(9)]

def get_grid_idx(r, c):
    return r // 3 * 3 + c // 3

sudoku = [[0 for _ in range(9)] for _ in range(9)]
blanks = []

for r in range(9):
    for c, t in enumerate(map(int, input().split())):
        if t == 0:
            blanks.append((r, c))
        else:
            sudoku[r][c] = t
            rows[r][t] = True
            cols[c][t] = True
            grids[get_grid_idx(r, c)][t] = True

def print_sudoku():
    for r in range(9):
        print(" ".join(map(str, sudoku[r])))

def backtracking(depth):
    if depth == len(blanks):
        print_sudoku()
        return True
    
    r, c = blanks[depth]
    g = get_grid_idx(r, c)
    for i in range(1, 10):
        if rows[r][i] or cols[c][i] or grids[g][i]:
            continue
        # set blank to i
        sudoku[r][c] = i
        rows[r][i] = True
        cols[c][i] = True
        grids[g][i] = True

        # backtracking
        if backtracking(depth + 1):
            return

        # undo
        rows[r][i] = False
        cols[c][i] = False
        grids[g][i] = False

    sudoku[r][c] = 0
    return False

backtracking(0)

solution.py