url : https://www.acmicpc.net/problem/2580

1. 문제

2. 풀이

1. 백트래킹을 이용하여 풀 수 있는 문제이다.
2. 각 세로줄, 가로줄, 3*3 구역에 1~9까지의 숫자가 중복 없이 들어가야 한다.
3. 0인 곳의 위치를 찾아 숫자를 채워 넣는데 재귀함수를 사용한다.
4. 각 구역을 체크하며 0을 하나하나 채워간다.
5. 스도쿠를 전부 채웠을 때, 완성된 스도쿠를 출력한다.

3. 코드

import sys
sys.stdin = open("test.txt")

# x 세로줄의 n이 있는지 확인
def check_Row(x, n):
    for i in range(9):
        if n == graph[x][i]:
            return False
    return True


# y 가로줄의 n이 있는지 확인
def check_Col(y, n):
    for i in range(9):
        if n == graph[i][y]:
            return False
    return True


# 3 * 3 칸에 n이 있는지 확인
def check_Rect(x, y, n):
    nx = x // 3 * 3
    ny = y // 3 * 3
    for i in range(3):
        for j in range(3):
            if n == graph[nx+i][ny+j]:
                return False
    return True


# dfs + 백트래킹
def solution(n):
    # 스도쿠를 모두 채웠다면
    if n == len(blank):
        for _ in range(9):
        	# *arg - 리스트, 튜플, 컬렉션 등을 언패킹
            print(*graph[_])
        exit(0)

    for i in range(1, 10):
        x = blank[n][0] # 빈칸의 x좌표
        y = blank[n][1] # 빈칸의 y좌표

        if check_Row(x, i) and check_Col(y, i) and check_Rect(x, y, i):
            graph[x][y] = i
            solution(n + 1)
            graph[x][y] = 0

graph = [list(map(int, input().split())) for _ in range(9)]
blank = [(i, j) for i in range(9) for j in range(9) if graph[i][j] == 0]

solution(0)

• 2차원 리스트로 스도쿠를 그래프를 입력받는다.
• 그래프를 순회하며 값이 0인 위치를 찾아 리스트로 저장한다.
• check_Row 함수로 세로줄, check_Col로 가로줄, check_Rect로 3*3 구역을 검사하여 숫자를 채워넣는다.
  - check_Rect : 0인 값의 좌표를 입력받아 3을 나눠 그 몫에 3을 곱하여 3 x 3 구역의 첫 좌표를 구해 반복문으로 3 x 3 만큼 순회를 한다.
• graph[x][y] = 0 - 이전 빈칸을 채우고 다음 빈칸을 채울때, 막히는 경우가 있어 그때 이전 단계로 돌아가기 위한 코드이다.
• 그래프가 모두 채워졌다면 재귀를 끝내고 그래프 전체를 출력한다.