Jin의 일상

본 풀이는 유튜브 강의를 토대로 작성했습니다.

문제 분석

- 스도쿠를 푸는 알고리즘을 작성해야 한다.

- 스도쿠의 각 칸에는 가로/세로/ 3 x 3 박스 내에 1~9까지 곂치는 수가 존재하지 않아야 한다.

본 문제를 풀이할 때 주의사항이 있다.

"가로/세로/ 3 x 3 박스 내에 1~9까지 곂치는 수"를 고려하여 문제를 풀었을 때 답이 나오지 않는 경우가 존재한다. 

그럴 때는 이전 칸으로 돌아가서 조건에 맞는 다른 수로 수정해야 한다.

따라서 이 문제는 백 트래킹을 사용해야 한다.

알고리즘

1. 스도쿠에 빈 공간(0)이 있는지 확인한다. 

2. 빈 공간이 없으면 스도쿠가 완성됐으므로 종료한다.

3. 빈 공간이 있으면 빈 공간(col, row)이 어딘지 말한다.

4. 빈 공간에 어떤 값(1~9)이 들어갈 수 있는지 탐색한다.

 - 찾았다면 스도쿠에 채워넣는다.

 - 채워넣을 수 있는 게 없다면 백 트래킹 한다.

스도쿠에 빈 공간 확인하기

1. 스도쿠 전체를 탐색하며 빈 공간(0)이 발견되면 해당 좌표를 리턴한다.

2. 스도쿠에서 빈 공간이 발견되지 않으면, None을 리턴한다.

빈 공간에 들어갈 수 있는 값인지 식별하기

빈 공간에 들어갈 수 있는 값인지 식별하기 위해서는 "가로 / 세로 / 3 x 3 박스"를 탐색해야 한다.

1. 가로 탐색

스도쿠의 column을 고정시키고 row 방향으로 이동 탐색을 진행한다.

들어가고자 하는 값이 발견되면 False를 리턴한다.

2. 세로 탐색

스도쿠의 row을 고정시키고 col 방향으로 이동 탐색을 진행한다.

들어가고자 하는 값이 발견되면 False를 리턴한다.

3. 3 x 3 박스 탐색

1. 탐색이 시작될 지점을 계산한다

2. 탐색시작 지점에서부터 3 x 3 지점을 탐색한다.

1. (7, 4) 지점이 속한 박스 영역의 시작 지점을 찾는다고 가정하자.

2. 왼쪽 그림의 경우 박스의 시작 지점은 (6, 3)이다.

3. 박스 영역의 시작 지점을 찾는 공식은 (컬럼좌표//3 * 3, 로우좌표//3 *3)이다.

("a//b"는 a와 b를 나눴을 때 몫과 나머지 중에 몫만 출력한다)

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

def pretty_print():
    for i in range(9):
        for j in range(9):
            print(board[i][j], end='')
        print()

def find_empty():
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return i, j
    return None, None

def valid(col, row, val):
    # 가로 축 점검
    for i in range(9):
        if board[col][i] == val:
            return False

    # 세로 축 점검
    for i in range(9):
        if board[i][row] == val:
            return False

    # 3x3 박스 점검
    box_col = col // 3 * 3
    box_row = row // 3 * 3
    for i in range(3):
        for j in range(3):
            if board[box_col+i][box_row+j] == val:
                return False
    return True

def solution():
    col, row = find_empty()
    if col is None:
        return True
    else:
        for i in range(1, 10):
            if valid(col, row, i):
                board[col][row] = i
                if solution():
                    return True
                board[col][row] = 0
        return False

if __name__ == '__main__':
    board = [list(map(int, input())) for _ in range(9)]
    solution()
    pretty_print()