2580번: 스도쿠

2580번: 스도쿠

백트래킹을 사용해서 스도쿠를 채우면 되는 문제다.

 

스도쿠 판에 0이 들어 있는 칸들을 저장하는 리스트 zeros를 만들어준다.

zeros리스트에서 칸들을 하나씩 확인하면서, 숫자를 넣을 수 있는지 없는지 검증한다.

1부터 10까지 for문을 돌면서 i를 통해 해당 칸의 가로, 세로, 그리고 해당 칸이 포함된 3X3 사각형을 모두 확인해서 숫자를 넣을 수 있는 경우,  스도쿠 판의 숫자를 해당 i로 바꿔준다.

 

board = [list(map(int, input().split())) for _ in range(9)]

zeros = [] # 0인 칸들을 저장하는 리스트
for i in range(9):
    for j in range(9):
        if board[i][j] == 0:
            zeros.append((i, j))


# 보드의 (i,j)칸에 숫자 n이 들어가도 되는지 확인하는 함수
def check_sudoku(i, j, n):
    
    # 대각선 확인을 위한 계산
    tx = j // 3 * 3
    ty = i // 3 * 3
    
    for x in range(9):
        # 가로 확인
        if board[i][x] == n:
            return False
        # 세로 확인
        if board[x][j] == n:
            return False
        # 3*3 사각형 확인
        if board[ty + x // 3][tx + x % 3] == n:
            return False
        
    return True





def back_tracking(num):
    if num == len(zeros):
        for line in board:
            print(*line)
        exit(0)
    
    else:
        y, x = zeros[num]
        for i in range(1, 10):
            if check_sudoku(y, x, i):
                board[y][x] = i
                back_tracking(num+1)
                board[y][x] = 0


back_tracking(0)

---

참고

(파이썬) 백준 2580번 "스도쿠"

[Python] 백트래킹 (+ DFS와 차이)

[실전 알고리즘] 0x0C강 - 백트래킹