BOJ 2580 스도쿠

https://www.acmicpc.net/problem/2580
시간 1초, 메모리 256MB
input :

• 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다.
• 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

output :

• 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력

조건 :

• 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
• 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

---

처음에 접근 부터 틀렸다...
0이 들어 있는 칸 들은 정해진 값이 존재하지만 그 칸에 들어 갈 수 있는 수들은 매우 많다.
이것들을 하나 씩 넣어보면서 모든 0을 채운 경우가 정답이 되는 것이다.

우선 0인 칸에 넣을 수 있는 수들을 구해야 한다.
이것은 가로, 세로, 3 * 3 사각형 안에서 나오는 숫자들을 다 빼고 남은 숫자들이다.

def possible(x, y):
    num = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    for i in range(9):
        if graph[i][y] in num:
            num.remove(graph[i][y])
        if graph[x][i] in num:
            num.remove(graph[x][i])

    start_x = x // 3 * 3
    start_y = y // 3 * 3
    for i in range(start_x, start_x + 3):
        for j in range(start_y, start_y + 3):
            if graph[i][j] in num:
                num.remove(graph[i][j])
    return num

인제 모든 0인 칸들에 재귀적으로 함수를 수행해야 한다. 위의 num들을 하나 씩 넣었다가 아니면 빼야 하기 때문에 재귀적으로 움직인다.

i == len(zeros) 0이 들어있는 위치를 나타내는 리스트의 길이와 같아져야 모든 0을 확인 한 것이다.

def dfs(i):
    global flag

    if flag:
        return

    if i == len(zeros):
        for j in range(9):
            for k in range(9):
                print(graph[j][k], end=" ")
            print()
        flag = True
        return

    else:
        x, y = zeros[i]
        nums = possible(x, y)
        for item in nums:
            graph[x][y] = item
            dfs(i + 1)
            graph[x][y] = 0

정답 코드 :

import sys

graph = []
zeros = []
for i in range(9):
    data = list(map(int, sys.stdin.readline().split()))
    for j in range(9):
        if data[j] == 0:
            zeros.append((i, j))
    graph.append(data)


def possible(x, y):
    num = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    for i in range(9):
        if graph[i][y] in num:
            num.remove(graph[i][y])
        if graph[x][i] in num:
            num.remove(graph[x][i])

    start_x = x // 3 * 3
    start_y = y // 3 * 3
    for i in range(start_x, start_x + 3):
        for j in range(start_y, start_y + 3):
            if graph[i][j] in num:
                num.remove(graph[i][j])
    return num


flag = False


def dfs(i):
    global flag

    if flag:
        return

    if i == len(zeros):
        for j in range(9):
            for k in range(9):
                print(graph[j][k], end=" ")
            print()
        flag = True
        return

    else:
        x, y = zeros[i]
        nums = possible(x, y)
        for item in nums:
            graph[x][y] = item
            dfs(i + 1)
            graph[x][y] = 0


dfs(0)

오늘의 선생님.
https://claude-u.tistory.com/360