스도쿠 ( 2239 번 )

2239번: 스도쿠

 

🧠 알고리즘

재귀적으로 빈칸에 숫자를 채우는 함수이며, 백트래킹 알고리즘

 

🧾 코드

import sys

def _mk_list():
    answer_list, zero_list = [], []
    for i in range(9):
        now_list = list(map(int, sys.stdin.readline().rstrip()))
        for j in range(9):
            if now_list[j] == 0:
                zero_list.append((i, j))
        answer_list.append(now_list)

    return answer_list, zero_list

def _ck_raw(idx, n):
    for i in range(9):
        if sq_list[idx][i] == n:
            return False
    return True

def _ck_col(idx, n):
    for i in range(9):
        if sq_list[i][idx] == n:
            return False
    return True

def _ck_box(idx_a, idx_b, n):
    for i in range(((idx_a // 3) * 3), ((idx_a // 3) * 3) + 3):
        for j in range(((idx_b // 3) * 3), ((idx_b // 3) * 3) + 3):
            if sq_list[i][j] == n:
                return False
    return True

def _bk(n_idx):
    if n_idx == len(zero_list):
        for idx in range(9):
            print(''.join(map(str, sq_list[idx])))
        exit()

    a, b = zero_list[n_idx]
    for num in range(1, 10):
        if _ck_raw(a, num) and _ck_col(b, num) and _ck_box(a, b, num): # 스도쿠 조건 만족
            sq_list[a][b] = num
            _bk(n_idx + 1)
            sq_list[a][b] = 0

sq_list, zero_list = _mk_list()
_bk(0)

 

⏱️ 시간 복잡도

9x9 스도쿠판 + 재귀 : 9 ** n

해당 알고리즘 시간 복잡도 : 상수 시간 복잡도 ( 9 ** n )