백준 2239: 스도쿠 (Python)

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

유사문제

백준 25870번은 문제 이름까지 똑같은 문제이며, 같은 소스코드 제출로도 통과가 가능하다.

해설

백트래킹을 활용해 풀 수 있는 대표적인 문제다.

생각의 흐름만 제대로 정리하면 풀기 어렵지 않다.

• 우선 비어있는 칸에 들어갈 수 있는 숫자 후보군을 모두 구한다
• 후보를 하나씩 대입해보며 스도쿠를 푼다
• 만약 숫자가 겹치는 부분이 있다면 되돌아가서 다른 후보를 대입한다

 

백트래킹

백트래킹의 본질이 '모든 경우의 수를 탐색하고, 그 수가 유망하지 않으면 돌아가서 다시 시도하는 전략' 인만큼, 스도쿠 문제 역시 비어있는 칸에 들어갈 수 있는 모든 후보 숫자를 구한다음 백트래킹으로 무식하게 모든 경우를 탐색해주면 된다.

코드

from collections import deque
import sys
import time


def GetAreaNumbers(y, x):  # 박스 내 숫자들
    px = x // 3
    py = y // 3
    arr = []
    for i in range(py*3, py*3 + 3):
        for j in range(px*3, px*3 + 3):
            if board[i][j] != 0:
                arr.append(board[i][j])
    return arr


def GetRowNumbers(y, x):  # 가로
    arr = []
    for i in range(9):
        if board[y][i] != 0:
            arr.append(board[y][i])
    return arr


def GetColumnNumbers(y, x):  # 세로
    arr = []
    for i in range(9):
        if board[i][x] != 0:
            arr.append(board[i][x])
    return arr


count = 0


def Backtracking(y, x, Q, depth):
    global count
    count += 1
    candidate = list(range(1, 10))
    exists = []
    exists += GetAreaNumbers(y, x)
    exists += GetRowNumbers(y, x)
    exists += GetColumnNumbers(y, x)

    # candidate - exists (차집합)
    candidate = [x for x in candidate if x not in exists]

    for num in candidate:
        board[y][x] = num
        if len(Q) == depth:
            for i in range(9):
                for j in range(9):
                    print(board[i][j], end=' ')
                print()
            return -1
        ny, nx = Q[depth][0], Q[depth][1]
        res = Backtracking(ny, nx, Q, depth+1)
        if res == -1:  # -1 반환시 즉시 백트래킹 탈출, 종료
            return -1
        board[y][x] = 0


board = [[0]*9 for _ in range(9)]
Q = deque()  # 비어 있는 칸들의 좌표 큐
for i in range(9):
    board[i] = list(map(int, sys.stdin.readline().split()))
    for j in range(9):
        if board[i][j] == 0:
            Q.append([i, j])


# 백트래킹 시작위치 초기화
y, x = Q[0][0], Q[0][1]
Q.popleft()
Backtracking(y, x, Q, 0)

여담

pyautogui와 keyboard 모듈을 활용하면 웹사이트 스도쿠를 자동으로 푸는 매크로를 만들 수도 있다.