📚 2580 - 스도쿠

스도쿠

이해

✏️ 스도쿠 규칙
빈공간에 값을 넣기
(1) 가로로 빈공간에 넣을 수 있는 숫자 찾기
(2) 세로로 빈공간에 넣을 수 있는 숫자 찾기
(3) 1, 4, 7 번째 인덱스에서 3x3으로 넣을 수 있는 숫자 찾기

처음에는 문제를 보고 어떻게 규칙을 넣을 수 있을까?
라는 생각에 검색을 하니, 백트래킹을 이용한다고 한다.

백트래킹 : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법이다. 최적화 문제와 결정 문제를 푸는 방법이 된다.

ex) (3, 4) 위치가 0이고

• 가로로 0인 곳에 넣을 수 있는 숫자(가로만 보았을 때) : 2, 3, 4, 5, 7
• 세로로 0인 곳에 넣을 수 있는 숫자(세로만 보았을 때) : 1, 4, 5, 8
• 3 x 3에서 0인 곳에 넣을 수 있는 숫자 : 2, 3, 4, 5

일 때, 공통인 것을 넣으면 된다. (예시로 보면, 4와 5)
(1) 4를 (3, 4) 위치에 넣고 다음 번째 0인 곳을 가로, 세로, 3 x 3으로 돌린다. 중간 돌리다가 (3, 4)위치에 넣을 숫자가 4가 아니라면 취소한다.
(2) 5를 (3, 4) 위치에 넣고 다음 번째 0인 곳을 가로, 세로, 3 x 3으로 돌린다. 0인 공간에 전부 1~9 숫자를 넣었다면 종료한다.

이를 적용하여 코드를 작성하면 된다!

소스

import sys

# 경우의 수 : 상하 좌우, 현재위치부터 3x3방면
# 현재 0인 위치를 찾고, 백트래킹을 적용한다.


read = sys.stdin.readline

# 먼저 배열을 입력받는다.
# 입력받고 나서 만약 위치가 0인 것들의 위치를 저장한다.
sku_arr = [list(map(int, read().split())) for _ in range(9)]
zero_arr = [(i, j) for i in range(9) for j in range(9) if sku_arr[i][j] == 0]


# get_reference 함수
# (1) row_zero 행을 기준으로 0의 위치를 찾는다.
# (2) col_zero 열을 기준으로 0의 위치를 찾는다.
# (1) - (2) 로 공통적이지 않는 곳을 찾는다.
# (3) 3 x 3 으로 0의 위치를 찾는다.
# (1) - (2) - (3) 으로 공통적이지 않는 숫자를 찾는다.
# 결과를 return 한다.

def get_loc_value(r, c):
    possible = set(range(1, 10))
    possible -= set(sku_arr[r])

    col_zero = set()

    for i in range(9):
        col_zero.add(sku_arr[i][c])

    possible -= col_zero

    in_zero = set()
    # 3 x 3
    for i in range(r // 3 * 3, r // 3 * 3 + 3):
        for j in range(c // 3 * 3, c // 3 * 3 + 3):
            in_zero.add(sku_arr[i][j])
    possible -= in_zero

    return tuple(possible)


# 해결책 함수 0의 개수 0개부터 시작한다.
# 만약 갯수가 총 0의 개수일 때는 출력하고 종료한다.
# 0의 개수로 0인 것들의 배열로 부터 데이터를 받는다. r, c
# get_reference 함수를 호출한다.
# 결과를 받아서
# 반복문을 돌린다.
# 그래프 r, c 좌표에 결과를 저장하며
# 다시, 해결책 함수에 현재 개수 + 1을 한다.
# 해결책 함수 종료될 시 r, c 좌표 값은 0으로 바꾼다.

def solve(cnt):
    if cnt == len(zero_arr):
        [print(*row) for row in sku_arr]
        sys.exit() # 찾았을 경우, 즉시 종료
    r, c = zero_arr[cnt]
    permission = get_loc_value(r, c)

    for cur_data in permission:
        sku_arr[r][c] = cur_data
        solve(cnt + 1)
        sku_arr[r][c] = 0


solve(0)

채점 결과

참고 : https://coder38611.tistory.com/137