[BOJ / 파이썬] 2580: 스도쿠

백준 / BOJ / Python / 파이썬

문제 링크 : https://www.acmicpc.net/problem/2580

2580번: 스도쿠

단계 : 백트래킹

알고리즘 분류 : 백트래킹 

 

풀이:

모르는 사람은 별로 없을 것 같지만 스도쿠는 3 x 3으로 판 9개로 이루어진 9 x 9의 판에 숫자를 채워넣는 게임이다. 숫자를 채워넣는 방법은 하나의 3 x 3 칸에 숫자 1~9까지의 숫자가 하나씩 들어가야 하고 9 x 9 판의 가로와 세로에도 1~9까지의 숫자가 하나씩 들어가야 한다.

 

먼저 현재 게임판의 상태를 입력 받는다. 0은 비어있는 숫자이므로 게임판의 숫자가 0으로 기록돼 있으면 to_solve 리스트에 비어있는 곳의 좌표를 입력해준다(푼지 조금 된 문제라 기억은 안나지만 아마 시간 초과를 피하려고 했던 작업 같다). 함수 solve에 현재까지 채운 칸의 개수인 0과 앞으로 채워야 할 칸의 수인 len(to_solve)를 인자로 넘겨준 후 둘이 같아지면 완성한 스도쿠를 출력 후 멈추도록 exit()를 이용한다.

 

칸을 채우는 방법은 다음과 같다. check 함수는 칸에 들어갈 수 있는 숫자인 1~9를 담은 key라는 리스트를 만들고 검사중인 칸에 들어갈 수 없는 숫자들은 지워준다. 행, 열 검사를 통해 가로, 세로에 들어간 숫자와 겹치는 숫자가 있다면 key 리스트에서 제거해준다. 또 현재 칸이 속해 있는 3 x 3 판에 있는 숫자들 또한 제거하기 위해 (x1: 현재 좌표를 3으로 나눈 몫) ~ (x1 + 3), (y1: 현재 좌표를 3으로 나눈 몫) ~ (y1 + 3)의 위치에 해당하는 숫자들도 검사하여 key에서 제거해준다. 남은 key를 반환하면 해당 위치의 칸에 들어갈 수 있는 모든 숫자들을 리스트로 반환하여 받을 수 있다.

 

그렇게 반환된 리스트에 있는 숫자들을 for문을 이용하여 숫자를 하나씩 뽑아 해당 칸에 그 숫자를 넣어본 후 재귀를 이용하여 진행해본다. 진행 과정 중 막혀서 더 이상 게임을 끝낼 수 없게 될 경우 그 재귀 이전에 있던 다른 숫자를 넣어 다음 안을 진행하는 방식이다. 그렇게 모든 안들을 찾아나가던 중 해결한 칸의 개수(solve의 첫번째 인자)가 해결해야하는 칸의 개수와 같을 경우 문제에서는 완성된 스도쿠 하나만 출력하라고 했으므로 exit()를 이용하여 종료해준다.

 

말로 설명하기 어렵지만 그냥 가능한 경우의 수를 모두 구해서 넣어보며 아닐 경우 그 지점 이전으로 돌아와 다른 안을 실행하는 방식으로 진행되는 타 문제들과 다를 바 없다고 생각하면 된다. 개인적으로 스도쿠도 좋아하는데 나중에 스도쿠를 한번 구현해볼 수 있으면 좋겠다.

 

코드

import sys


def check(x, y):
    key = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    for i in range(9):  # 가로세로 검사
        if game[x][i] in key:
            key.remove(game[x][i])
        if game[i][y] in key:
            key.remove(game[i][y])

    x1 = x // 3
    y1 = y // 3

    for i in range(x1 * 3, x1 * 3 + 3):  # 3곱3 검사
        for j in range(y1 * 3, y1 * 3 + 3):
            if game[i][j] in key:
                key.remove(game[i][j])

    return key


def solve(n, count):

    if n == count:
        for i in range(9):
            sys.stdout.write(" ".join(map(str, game[i])) + "\n")
        exit()

    i, j = tosolve[n]
    for item in check(i, j):
        game[i][j] = item
        solve(n + 1, count)
        game[i][j] = 0


game = []

for i in range(9):
    game.append(list(map(int, sys.stdin.readline().split())))

tosolve = [(i, j) for i in range(9) for j in range(9) if game[i][j] == 0]

solve(0, len(tosolve))