(Elice / 완전탐색 / Python)스도쿠 마스터

스도쿠 마스터

퍼즐 게임을 좋아하는 체셔는 요즘 스도쿠에 푹 빠져있습니다. 스도쿠는 숫자퍼즐게임으로 다음과 같은 규칙을 가지고 있습니다.

스도쿠의 규칙

1. 각각의 가로줄과 세로줄에 숫자 1~9가 중복 없이 하나씩 들어간다.
2. 3X3 모양의 네모난 박스 안에는 1~9가 중복 없이 하나씩 들어간다.

체셔는 재밌는 스도쿠를 여러 친구들과 같이 즐기고 싶어서 문제와 답지를 같이 건네주려고 합니다. 하지만 체셔는 답지를 가지고 있지 않아 모든 문제의 답을 찾는 시간이 너무 아깝게 느껴졌습니다. 이런 체셔를 위해 여러분이 스도쿠의 답을 출력해주는 프로그램을 만들어주세요.

입력 예시

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

출력 예시

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

 

입력

• 9개의 숫자가 공백을 기준으로 나뉘어 9줄로 제공됩니다.
• 현재 스도쿠의 비어있는 칸은 0으로 표시됩니다.
• 정답을 찾을 수 없는 입력값은 주어지지 않습니다.
• 정답이 여러 개일 수 있는 입력은 주어지지 않습니다.

출력

• 모든 빈 칸이 채워진 스도쿠의 정답을 입력값과 동일한 형태인 9개의 숫자를 공백을 기준으로 9줄로 출력하세요.

소스 코드

arr = []
for i in range(9):
    arr.append(list(map(int, input().split())))
    
done = False

def sudoku_check(r,c, value):
    for i in range(9):
        if arr[r][i] == value:
            return False
    for i in range(9):
        if arr[i][c] == value:
            return False
    x = (r//3)*3
    y = (c//3)*3
    for i in range(3):
        for j in range(3):
            if arr[x+i][y+j] == value:
                return False
    return True
    
def sudoku():
    global done
    for i in range(9):
        for j in range(9):
            if arr[i][j] != 0:
                continue
            for k in range(1,10):
                if sudoku_check(i,j,k):
                    arr[i][j] = k
                    sudoku()
                    if done:
                        return
                    arr[i][j] = 0
            return
    done = True
    return

sudoku()
for i in range(9):
    print(' '.join(map(str,arr[i])))