문제 출처 : https://www.acmicpc.net/problem/2580

---

문제 파악

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성해야 한다.

입력으로 이렇게 공백을 기준으로 9x9의 스도쿠 board가 주어졌을 때,
출력으로 빈칸을 의미하는 0을 적합한 수로 채워 출력하면 된다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다고 한다.
그리고 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다고 한다.

---

1. 먼저 문제에서 빈 칸은 0으로 주어지기 때문에
   graph의 0인칸의 위치정보(x, y)를 blank 리스트에 넣어준다.

2. 첫 번째 빈칸에 1~9까지의 수 중 넣을 수 있는 수를 넣는다.
   넣을 수 있는 수는 빈칸의 행,열,3x3정사각형에 없는 수임을 확인하자.
   확인이 되면 그 빈칸에는 그 수를 넣어준다.

3. 그 다음 빈칸에 대해서도 같은 방법을 수행한다.

4. 마지막 빈칸까지 채우면 스도쿠를 완성하므로 맵을 출력한다.

해답 및 풀이

import sys
input = sys.stdin.readline

graph = []
blank = []

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.append((i,j))

def checkRow(x, a): # x행에 a가 있으면 False, 없으면 True
    for i in range(9):
        if a == graph[x][i]:
            return False
    return True

def checkCol(y, a): # y열에 a가 있으면 False, 없으면 True
    for i in range(9):
        if a == graph[i][y]:
            return False
    return True

def checkRect(x,y,a): # x,y가 속한 3*3 영역에 a가 있는 지 함수
    nx = x // 3 * 3 # x가 0,1,2 면 0 / 3,4,5 면 / 3 / 6,7,8 이면 / 6
    ny = y // 3 * 3
    for i in range(3):
        for j in range(3):
            if a == graph[nx+i][ny+j]: # 0~2 / 3~5 / 6~8 검사
                return False
    return True

def dfs(idx):
    # 종료 조건
    if idx == len(blank):
        for i in range(9):
            print(*graph[i])
        exit() # 정답을 출력했으므로 프로그램을 종료시키는 메소드

    for i in range(1,10):
        x = blank[idx][0]
        y = blank[idx][1]

        if checkRow(x, i) and checkCol(y, i) and checkRect(x,y,i):
            graph[x][y] = i
            dfs(idx+1)
            graph[x][y] = 0

dfs(0)
    

dfs(idx)의 idx는 몇 번째 빈칸을 채우는 중인지를 뜻함.
x, y = blank[idx]로 이번에 채울 좌표를 꺼냄.
1~9 숫자를 검사해서 가능하면 배치 → 다음 빈칸으로 진행(dfs(idx+1)).
실패하면 원복(graph[x][y] = 0)하고 다른 숫자 시도.

---

다음날 다시 푼 코드

# 0 3 5 4 6 9 2 7 8
# 7 8 2 1 0 5 6 0 9
# 0 6 0 2 7 8 1 3 5
# 3 2 1 0 4 6 8 9 7
# 8 0 4 9 1 3 5 0 6
# 5 9 6 8 2 0 4 1 3
# 9 1 7 6 5 2 0 8 0
# 6 0 3 7 0 1 9 5 2
# 2 5 8 3 9 4 7 6 0

# 입력받아서 

# 1 3 5 4 6 9 2 7 8
# 7 8 2 1 3 5 6 4 9
# 4 6 9 2 7 8 1 3 5
# 3 2 1 5 4 6 8 9 7
# 8 7 4 9 1 3 5 2 6
# 5 9 6 8 2 7 4 1 3
# 9 1 7 6 5 2 3 8 4
# 6 4 3 7 8 1 9 5 2
# 2 5 8 3 9 4 7 6 1

# 빈칸(0)을 스도쿠 규칙에 맞춰서 채워넣은 뒤 출력 시키기.

# ---------------------------------------------


import sys
input = sys.stdin.readline

board = []
blank = [] # 0의 위치 (r,c)를 입력받음

# board 입력 받기
for i in range(9):
    row = list(map(int,input().split()))
    board.append(row)

# 입력받은 board 에서 blank 찾기
for i in range(9):
    for j in range(9):
        if board[i][j] == 0:
            blank.append([i,j])

# 스도쿠 조건 함수들로 정의
def checkRow(x,a): # x행에 a가 있나 없나, 있으면 False처리, 없으면 True
    for i in range(9):
        if board[x][i] == a:
            return False
    return True

def checkCol(y,a): # y열에 a가 있나 없나, 있으면 False, 없으면 True
    for i in range(9):
        if board[i][y] == a:
            return False
    return True

def checkRect(x,y,a): # x,y가 속한 Rect내 a가 있나 없나, 있으면 False, 없으면 True
    nx = (x // 3) * 3
    ny = (y // 3) * 3
    for i in range(3):
        for j in range(3):
            if board[nx+i][ny+j] == a:
                return False
    return True


# blank 리스트에 인덱스를 하나씩 넣어 볼 것임
# 끝까지 다 채워지면 print
# check함수들을 만족하지 않는다면, 다시 돌아와서 dfs
def dfs(idx): 
    # 끝까지 다 채워지면 완성된 board판 print 후 함수 탈출
    if idx == len(blank):
        for i in range(9):
            print(*board[i])
        exit()

    for i in range(1,10):
        x = blank[idx][0]
        y = blank[idx][1]
        
        if checkRow(x,i) and checkCol(y,i) and checkRect(x,y,i):
            board[x][y] = i 
            dfs(idx+1)
            board[x][y] = 0

dfs(0)

코드는 동일하게 떠올렸지만 마지막 dfs함수에서
range(1,10) 이 아닌 range(9)라고 값이 아닌 인덱스 기준으로 반복문을 돈 것과
x = blank[idx][0]
y = blank[idx][1]
로 blank 리스트에서 좌표를 추출하는 코드를 떠올리지 못했었다.