[Baekjoon] 2580번 : 스도쿠

 

2580번: 스도쿠

Gold 4.

스도쿠의 규칙대로 빈 칸을 채우는 문제!

스도쿠는 9x9 칸에 가로, 세로, 3x3칸 내에 1-9까지의 숫자가 중복없이 들어가야 한다. 

 

문제 풀이

백트래킹 알고리즘 이용

1) 빈칸에 대해서 1-9까지 값을 넣어보고 가능한지 확인한다.

2) 가능하면 값을 넣고 다음 노드로 이동한다.

 

코드

graph, blank_list = [], []
for i in range(9):
    graph.append(list(map(int, input().split())))

for i in range(9):
    for j in range(9):
        if graph[i][j] == 0:
            blank_list.append((i, j))

# 가로줄에 중복되는 값이 있는지 확인
def check_board_a(x, num):
    for i in range(9):
        if num == graph[x][i]:
            return False
    return True

# 세로줄에 중복되는 값이 있는지 확인
def check_board_b(y, num):
    for i in range(9):
        if num == graph[i][y]:
            return False
    return True


# 3x3 정사각형 안에 중복되는 값이 있는지 확인
def check_board_c(x, y, num):
    nx = x // 3 * 3
    ny = y // 3 * 3
    for i in range(3):
        for j in range(3):
            if num == graph[nx+i][ny+j]:
                return False
    return True

def solution(idx):
    # idx가 마지막까지 가면 빈칸이 모두 채워진 것
    if idx == len(blank_list):
        for i in range(9):
            print(*graph[i]) #리스트의 값만 프린트
        exit(0)

    x = blank_list[idx][0]
    y = blank_list[idx][1]
    for i in range(1, 10):
        if check_board_a(x, i) and check_board_b(y, i) and check_board_c(x, y, i):
            graph[x][y] = i
            solution(idx+1)
            graph[x][y] = 0

solution(0)

 

여담(?)

 exit(0)을  사용하면 프로그램을 바로 끝낼 수 있다!

그리고 리스트를 문자열로 바꾸고 join할 필요 없이 *을 붙이면 값만을 print할 수 있다 ㅎ..

 

참고한 블로그 : https://hongcoding.tistory.com/118