2239. 스도쿠

문제

코드

def possible(i, j):
    # 가로체크
    possible_num = [1 for _ in range(10)]
    for r in range(9):
        if arr[i][r] != 0:
            possible_num[arr[i][r]] = 0
    # 세로체크
    for c in range(9):
        if arr[c][j] != 0:
            possible_num[arr[c][j]] = 0
    # 3x3체크
    for t in range(3):
        for h in range(3):
            possible_num[arr[(i//3)*3 + t][(j//3)*3 + h]] = 0
    return possible_num

def fill_num(idx):
    global path
    if idx == len(path):
        for p in range(9):
            print(*arr[p], sep="")
        exit()

    ni, nj = path[idx][0], path[idx][1]
    possibles = possible(ni, nj)
    for i in range(1, 10):
        if possibles[i]: # True
            arr[ni][nj] = i
            fill_num(idx+1)
            arr[ni][nj] = 0

arr = [list(map(int, input())) for _ in range(9)]
path = []
for i in range(9):
    for j in range(9):
        if arr[i][j] == 0:
            path.append((i,j))

fill_num(0)

풀이

# def fill_num(i, j, possible_nums):
#     if not possible_nums: # 넣을 게 아무것도 없을 경우
#         # 뒤로 돌아가야하는데...
#         return
#     for f in range(1,10): # 12345678
#         if possible_nums[f]: # 가능한 수 젤 앞자리 냅다 집어넣기
#             arr[i][j] = f
#             break # 해야 뒤도 있을 경우 갱신이 안됨

중간에 백트랙을 어떻게 해야할 지 생각이 안나서 삽질 한 코드...
동기분의 도움을 받아서 한방에 해결!!!!!!!!! 최고다!!!!!!!!!!!!!!!

🕵️‍로직은 간단
0을 발견했을 때 위치를 리스트에 넣어준다 ( 이는 백트랙을 위함이다 )

그 위치를 순회하면서 넣을 값을 possible 함수로 찾아주는데

possible은 그 인덱스를 기점으로 가로 쫙 세로 쫙 속한 3x3구역 돌아서 가능한 숫자를 추려준다

그리고 fill_num에서 그 추려진 리스트를 돌면서 가능한 숫자가 있을 때 그걸 스도쿠arr에 함 넣어본다

이 때 문제가 없으면 앞으로 계속 가서 idx값이 증가해 path의 길이의 수와 일치하게 된다면 스도쿠가 다 채워진 것 이므로 종료하고 스도쿠를 출력한다

하지만 문제가 있어 다음 0의 위치(채울위치)로 넘어 갔을 때 possible 값에서 넣을 값이 없다면 무언가 잘못된 것이므로 다시 돌아와 방금 값을 넣었던 자리를 0으로 바꿔주고(원래대로 돌려주고) for문을 계속 돌아 다음 possible 값을 가지고 재귀를 들어가게 된다

머 이때 왠벽하다면 끝까지 갈꺼고 안 된다면 다시 for문 타서 다음 값 넣고 반복한다 ~.~