[python] 백준 2580 스도쿠

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

2580번: 스도쿠

 

문제 해결

• 스도쿠는 문제 해결 방식을 이해하면 풀기 쉽다.
• 먼저 값이 0인(빈칸) 좌표를 찾는다.
• 1부터 9까지 값을 대입해가며 대입했을 때 그 행, 그 열, 박스 안 숫자에 중복이 없는지 확인을 하고 문제 없으면 다음 빈칸을 채우는 코드를 짜면 된다.
• 빈칸이 없어질 때 까지 문제가 생기지 않으면 그 스도쿠 판을 출력하면 된다.

 

CODE

def find_empty():
    for i in range(9):
        for j in range(9):
            if board[i][j] ==0:
                return i, j
    return None, None
def valid(col,row,i):
    for j in range(9):
        if board[col][j] == i: return False
        if board[j][row] == i: return False
    box_col = col//3
    box_row = row//3
    for r_r in range(3):
        for r_c in range(3):
            if board[box_col*3+r_c][box_row*3+r_r] == i:
                return False
    return True
def solution():
    col, row = find_empty()
    if col == None: return True

    for i in range(1,10):
        if valid(col,row,i):
            board[col][row] = i
            if solution():
                return True
            board[col][row] = 0
    return False

if __name__=='__main__':
    board = [list(map(int, input().split())) for _ in range(9)]
    solution()
    for i in range(9):
        print(*board[i])