BOJ2580 스도쿠

문제

BOJ2580 스도쿠
골드IV | 백준 2580 | Python3 파이썬 풀이

알고리즘

코드

import sys

input = sys.stdin.readline

# find empty place
def findEmpty():
    for i in range(9):
        for j in range(9):
            if table[i][j] == 0:
                return (i, j)
    
    return (-1, -1)


# check that X can be written in (r, c)
def check(r, c, x):
    
    # check 3 by 3 table
    for i in range(3):
        if x in table[3 * (r // 3) + i][3 * (c // 3) : 3 * (c // 3) + 3]:
            return False

    # check row, column
    if x in table[r]:
        return False
    
    for i in range(9):
        if x == table[i][c]:
            return False

    return True


def DFS():
    global table

    r, c = findEmpty()

    if r == -1 and c == -1:
        return True

    else:
        for nn in range(1, 10):
            if check(r, c, nn):
                table[r][c] = nn
                # go next (recurrsive)
                if DFS(): return True

                # not fit - back tracking
                table[r][c] = 0

        return False

point = []
table = []
for _ in range(9):
    table.append(list(map(int, input().split())))

# print(table)

DFS()

# print(table)

for row in table:
    for col in row:
        print(col, end=' ')
    print()

결과

예전에 알고리즘 공부할 때, 스도쿠 문제를 여러 번 풀어서인지 쉽게 풀 수 있었다. (백준에 스도쿠 문제가 매우 많다. 조금씩 다르지만 알고리즘은 거의 비슷하다)