[백준 2580번-파이썬] 스도쿠

http://acmicpc.net/problem/2580

{코드}

import sys


board = [list(map(int, input().split())) for _ in range(9)]
zeros = [(i, j) for i in range(9) for j in range(9) if board[i][j] == 0]


def get_possibles(r, c):
    possibles = set(range(1, 10))
    possibles -= set(board[r])
    test = set()
    for i in range(9):
        test.add(board[i][c])
    possibles -= test
    test = set()
    for i in range(r//3*3, r//3*3+3):
        for j in range(c//3*3, c//3*3+3):
            test.add(board[i][j])
    possibles -= test
    return tuple(possibles)


def solve(i):
    if i == len(zeros):
        [print(*row) for row in board]
        sys.exit()
    r, c = zeros[i]
    possibles = get_possibles(r, c)
    for num in possibles:
        board[r][c] = num
        solve(i+1)
        board[r][c] = 0


solve(0)

{설명}

먼저 스도쿠에 대해 간단히 설명하자면 어떤 칸에 대해서 그 칸이 포함된 행, 열, 그리고 3*3 격자에 1~9의 수가 딱 한 번씩 등장한다는 것입니다.

이 문제는 백트래킹 문제로 백트래킹은 그리디(탐욕법)에 특정 조건을 만족하게 하는 방법이라고 보셔도 될 것 같습니다.

여기서 특정 조건이란 위에 말한 1~9가 한 번씩 등장한다는 것이 되겠죠.

먼저 보드를 입력 받고 나면 어떤 위치에 0이 있는지, 즉 어디가 비어있는지를 저장합니다. (zeros)

그러면 각 위치에 대해서 가능한 수들을 확인한 후(get_possibles) 각 수에 대해서 해당 칸에 그 수를 저장하고 다음 비어있는 칸으로 이동합니다.

만약 모든 칸이 채워졌다면 (=i가 채운 칸의 수이므로 i가 비어있던 칸의 수와 같다면) 보드를 출력하면 됩니다.

*간단하게 말하면 어떤 칸에 들어갈 수 있는 수를 찾고 그걸 넣은 보드로 계속 가다가 다 채워지면 출력하는 것입니다.

**pypy로 제출하였습니다 - python으로 제출하면 시간 초과가 납니다.