[엘리스] 스도쿠 마스터

스도쿠 마스터

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

스도쿠의 규칙

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줄로 출력하세요.

풀이

• backtracking을 통해 모든 경우 조사 

# https://claude-u.tistory.com/360
# 위의 글 보고 코드 작성했는데, 다시 들어가서 보니 똑같은...

def dfs(idx):
    # flag가 True로 이미 완성되었으면 모든 dfs 탈출 
    global flag 
    if flag: 
        return 
    
    # zeros가 다 차면 탈출 
    if len(zeros) == idx: 
        for row in sudoku:
            print(*row)
        flag = True #답 출력
        return
    
    # 전부 차지 않은 경우 확인 
    else: 
        (i, j) = zeros[idx]
        
        # 다음에 넣어도 괜찮은 값을 반환 
        candidate_list = candidate(i, j) 
        
        for num in candidate_list:
            sudoku[i][j] = num
            dfs(idx + 1)
            # 답이 없는 경우 
            sudoku[i][j] = 0
        
            

def candidate(i, j): 
    numbers = [c for c in range(1, 10)]
    
    for k in range(0, 9):
        if sudoku[i][k] in numbers:
            numbers.remove(sudoku[i][k])
        if sudoku[k][j] in numbers:
            numbers.remove(sudoku[k][j])
    
    start_i = i // 3
    start_j = j // 3
    for dx in range(start_i * 3, (start_i+1) * 3):
        for dy in range(start_j * 3, (start_j+1) * 3):
            if sudoku[dx][dy] in numbers:
                numbers.remove(sudoku[dx][dy])
    
    return numbers
        

sudoku = [list(map(int, input().split())) for i in range(9)]
zeros = [(i, j) for i in range(9) for j in range(9) if sudoku[i][j] == 0]
flag = False

dfs(0)    



# 참고자료 
# https://claude-u.tistory.com/360

 

참고자료

• 파이리썬의 파이썬

 

출처 : 엘리스 아카데미, https://academy.elice.io/learn